search

ydb-platform / ydb

YDB is an open source Distributed SQL Database that combines high availability and scalability with strong consistency and ACID transactions
https://ydb.tech
Apache License 2.0
4k stars 564 forks source link

Cross join rewriting rule is incomplete #7403

Open pavelvelikhov opened 3 months ago

pavelvelikhov commented 3 months ago

We have a new cross-join rewriting rule, but it is not complete. Equivalence sets of attributes are not taken into account when pushing filters into a tree of cross-joins. This will result in some cross-joins remaining in the plan, even though they can be rewritten.

Here is a sketch of an example:

((A cross B) Cross C) Cross ( D Cross E)

Where

A.x = B.x AND AND B.y = C.y AND A.z = E.z AND A.z = D.w

Predicate A.z = D.w can be pushed to the right side into (D cross E) branch, because A.z = E.z However w/o equivalences this will not happen, instead A.z = D.w will be a condition of the top join, and D cross E will remain in the plan

pavelvelikhov commented 3 months ago

With the new cross-join rewrititing (by disabling RotateJoinTree) we have a regression on TPCDS64 on scale 1000 This can be reproduced in this PR by KqpJoinOrder unit test: https://github.com/ydb-platform/ydb/issues/7403

pavelvelikhov commented 3 months ago

TPCH queries Q8 and Q2 and some more are also failing in compilation when this rule is enabled