in case such a clause met we ignore it and return an error of it being unimplemented yet

fix: make expressions with references under GroupBy and parent relational operators be compared by Reference `targets` and `position` fields instead of Reference aliases

- `propagate_equality` transformation did not
compute equality classes correctly, its 'merge'
function was completely wrong: it tried to add
intersection of classes to a another class,
instead of doing union
- to merge classes correctly we must do it
when we add a new pair of equal expressions:
otherwise later there will too many classes
that contain common elements, so 'merge'
function was removed and 'insert' now merges
two classes that contain common elements
- Also this logic is now covered by tests

- In case we have equality between columns
of the same table, `eq_cols_from_eq` should
return empty equality cols, but it returned
None, which led to wrong motion. Fixed that.
- It was found after a merge tuples transform
fix, in front_sql_join_single_left_5 test
where now there are two equalities instead of one.
Earlier, there always was one equality because
merge tuples produced a single (..) = (..)
term for an and-chain. And this test didn't work,
because this term contained one equality pair.
Now there are two terms: (..) = (..) and (..)=(..)
and one of them does not contain any equality
pairs.

- merge tuple transformation that merges several
and-ed equalities into equlities of rows didn't
group columns by child they refer to. This led
to rows where we couldn't find sharding keys,
because they were scattered across the different
rows:

```
sk(t1) = (a, b), sk(t2) = (e, f)
... on (t1.a, t2.f) = (t2.e, t1.b)
```

But now correct rows are generated:

```
... on (t1.a, t1.b) = (t2.e, t2.f)
```

Arseniy Volynets authored 5 months ago and Denis Smirnov committed 5 months ago

- Add new line in explain reporting on which buckets query will
  be executed.
- For queries consisting of a single subtree we can say exactly on
  which buckets it will be executed, for queries with more subtrees
  (with motions), we provide an upper bound of total buckets used
  in the query. Upper bound is computed by merging buckets from the
  leaf subtrees.
- In case for DML query with non-local motion we can't provide an
  upper bound, and print 'buckets: unknown'

Examples:
```
explain select a from t
->
projection ("t"."a"::integer -> "a")
    scan "t"
execution options:
    vdbe_max_steps = 45000
    vtable_max_rows = 5000
buckets = [1-3000]

explain select t.a from t join t as t2
on t.a = t2.b
->
projection ("t"."a"::integer -> "a")
  ...
execution options:
    vdbe_max_steps = 45000
    vtable_max_rows = 5000
buckets <= [1-3000]

explain select id from _pico_table
->
projection ("_pico_table"."id"::unsigned -> "id")
    scan "_pico_table"
execution options:
    vdbe_max_steps = 45000
    vtable_max_rows = 5000
buckets = any

explain insert into t values (1, 2)
->
insert "t" on conflict: fail
motion [policy: segment([ref("COLUMN_1")])]
    values
        value row (...)
execution options:
    vdbe_max_steps = 45000
    vtable_max_rows = 5000
buckets = unknown
```

The queries `select * from t where sk = 1 and sk = 2` discovered
the bucket for the constant 1, rather then an empty set. The reason
was that the tuple merge transformed `sk = 1 and sk = 2` to
`(sk, sk) = (1, 2)`, while the distribution took into account only
the first position (constant 1).

To compute all keys we now take a cartesian product between all
groups of columns of a tuple, where each group consists of columns
corresponding to single column of sharding key.

Suppose tuple is (a, b, a). (a, b) refer to sharding columns, then
we have two groups:
a -> {0, 2}
b -> {1}

And the distribution keys are:
{0, 2} x {1} = {(0, 1), (2, 1)}

Co-authored-by: Arseniy Volynets <a.volynets@picodata.io>

Previously, during bucket discovery, we used Buckets::Any for
Motion(Local) nodes. This caused DML queries to be executed on all
nodes instead of targeting specific bucket children. We now apply
Motion(Local) only in the following cases:

- update/delete. When materializing the reading subtree for DML
  operations, Buckets::Any was used, but the reason for this is
  unclear.
- union all between sharded and local tables. To prevent duplicates,
  we materialize the global subtree only on a single storage node.
  Consequently, the subtree with Motion(Local) must have the same
  buckets as its child (the child node will always have Buckets::Any).

Co-authored-by: Arseniy Volynets <a.volynets@picodata.io>

- Previously we computed slices based on their
level in bfs tree traversal. This was wrong, as
motions that were independent could be in
different slices
- Fix that, now we the slice in which motion will
be is the max number of other motion nodes in path
from this motion to any leaf node

- ExecuteOptions is a hashmap that always
stores only 1 entry. Moreover this led to
a bug, when we expected that it stores ALL
execution options, while it stored only
vdbe_max_steps

- We didn't apply vtable max rows value
when executing local sql. We tried to lookup
it in the execute options hashmap and took
the default value instead, though it was
not stored in the hashmap.

- Earlier we returned empty buckets for
Values/ValuesRow nodes and then choosed
random bucket for execution if they were
a subtree root.
- Buckets::Any provides the same semantics,
use it instead and simplify `empty_query_result`
function, which now always returns empty result.

Arseniy Volynets authored 5 months ago and Denis Smirnov committed 5 months ago

- When creating Values node in IR we didn't check
that all values rows have the same length.
- This led to panic on earlier pipeline stages:
syntax plan build
- Add a check that all values rows have the same
length

- When adding concat to plan, we had a check
that both concat children are expressions.
- This leads to error, when children are
parameters.
- Replace error with debug assert that checks
for expression | parameter children. Debug assert
is used because it is quiet unlikely that we will
mess up expression children, no need to check it
in release builds.

- Support simple queries that do not select
data from tables. This is similar to `values ..`,
but allows to add aliases for expressions.
- Such selects can also be used in subqueries
- Examples:
```
select 1;
select (select count(*) from t);
select 2 as foo, 3 as bar;

select a from t
where b in (select 100)
```

- We didn't traverse output during subtree
traversal when calculating hash. Some nodes
(Motion, Projection) store non-trivial
information, which allows to distinguish
different plans. We came across this by
collision between two different queries:
```
SELECT w.n FROM t JOIN w ON t.n = w.n
LIMIT 3

SELECT id, count(*) FROM t
GROUP BY id
HAVING id > 2
LIMIT 3
```
These plan happened to have subtrees that match
exactly except for output of projection, that
we didn't traverse.

- fix this by traversing subtree fully

- ValuesRow node have `data` and `output`
fields refer to the same stuff in query
`values (1)`. For except between global
and sharded table we applied special
transformation, in which we cloned
global subtree.
- Subtree cloner didn't respect DAG structure
of our plan: there maybe multiple references
to the same node. Instead it expected a tree.
Fix that