jayzhan211 commented on issue #5492: URL: https://github.com/apache/datafusion/issues/5492#issuecomment-6395684651
@mohammadnaqvi04 after alamb's comment on #26710, I built a prototype of Neumann's top-down unnesting to check how it fits DataFusion, and compared it with your plan. It covers the mapping you mentioned, so it may help with your design doc. A short summary of both comes first, for readers who haven't opened the docs. Branch: https://github.com/apache/datafusion/compare/main...jayzhan211:datafusion:poc/general-decorrelation This is a prototype to test the design, not a PR: it has no unit tests yet, the commits are work in progress, and a few shapes are still unsupported. **Your plan, in short** Your plan doc and shape catalog take Neumann's general unnesting as the goal and propose a fixed catalog of failing query shapes as the way to get there. The 11 shapes come mostly from DuckDB's subquery tests. Each would become an item under an EPIC and be fixed one at a time, so every PR has a checkpoint to verify against. Mapping Neumann's method onto DataFusion and `LATERAL` are left for later, and a design doc is in progress. **Why a general rule** Today a correlated subquery becomes a join by pulling its correlated filters up to the top of the subquery. Every operator a filter crosses needs its own check that the move is safe: a missing check is a "not supported" error, and a wrong check is a wrong result. The empty-input aggregate (the COUNT bug) is then compensated separately for scalar, `EXISTS`/`IN` and lateral subqueries. That design is the source of the 36 open decorrelation issues, 17 of which are wrong results. Of the 16 fixes to this code in the last year, 5 made a wrong result safe by turning it into a "not supported" error. **How the prototype works** It does the opposite and pushes the outer values down. The domain is the set of distinct outer values the subquery reads. Every operator on the way down also groups, partitions or joins by the domain columns, so the subquery returns its rows for all outer values at once, tagged with the value, and is joined back to the outer plan on those columns. An aggregate without `GROUP BY` is handled in one place: the domain is left-joined to the aggregate grouped by the domain, and outer values with no input get the aggregate's empty-input value. **How it maps onto DataFusion** - It is one logical optimizer rule that replaces `DecorrelatePredicateSubquery`, `ScalarSubqueryToJoin`, `DecorrelateLateralJoin` and `PullUpCorrelatedExpr`, so plans from SQL, the DataFrame API and Substrait all go through it. - The dependent join exists only inside the rule. No new `LogicalPlan` node or join type reaches Substrait, proto or the unparser. - When a conjunct is `inner = outer`, the rule binds the outer column to the inner one and builds no domain, which keeps today's plan shape for the common case. - "At most one row" is an aggregate that errors on a second value, like Calcite's `SINGLE_VALUE`. - The domain is computed by reading the outer plan again, so the rule refuses when that plan isn't deterministic. **Results, with the four old rules deleted** | | main | prototype | |---|---|---| | Your catalog, the 9 shapes that are valid SQL | 0 right | 9 right | | 39 repros from open decorrelation issues | 6 right, 10 wrong | 38 right, 0 wrong | | 15,000 random correlated queries | 4,660 right, 124 wrong | 14,958 right, 0 wrong | | dbolympics, 409 queries | 325 right, 50 errors | 366 right, 9 errors | None of the 9 remaining dbolympics errors comes from a subquery. The sqllogictests have no result changes, and 26 `EXPLAIN` expectations change. 6 of the 9 TPC-H subquery queries get identical plans, and the other 3 differ only in where scalar arithmetic runs. The costs: the rule is about 3,000 lines against 2,500 for the code it replaces, and `PullUpCorrelatedExpr` is public, called directly by lakehq/sail and alimardon123/pondra. <details> <summary><b>Feedback on the catalog</b></summary> - The three shapes listed as correctness bugs fail at planning on main with a schema error. They don't return wrong rows. - The two shapes whose aggregate reads only outer columns are not valid SQL, because such an aggregate belongs to the outer query. Postgres and DuckDB reject both ("must appear in the GROUP BY clause", "aggregate functions are not allowed in WHERE"), and DataFusion should reject them too. - The shapes that return wrong rows today matter most, and none of them is in the catalog yet: #26014, #26032, #25808, #26503 and #26692. In the random queries, most of main's wrong answers come from a `HAVING` over an aggregate without `GROUP BY` (#26503) or from `LATERAL` with `DISTINCT` (#25808). - The dbolympics failures add five more shapes: top-1 per outer row (#26710), range correlations (#14554), scalar subqueries without an aggregate (#16137), subqueries inside an aggregate (#26704), and references two levels up (#15558). - DuckDB 1.1.3 gets a few of these wrong itself (`NOT EXISTS` with `<>` on NULLs, correlated grouping sets), so I used SQLite as the reference. It runs each subquery once per outer row. </details> **A path that combines the two** Your strangler-fig plan fits the prototype well, with one change: split the work by operator rather than by shape. Most of the missing-capability shapes need the same core, so the first shape would carry most of the rule. 1. A tests-only PR that adds the catalog as sqllogictests: your shapes, the issue repros and the cases the fuzzer found, each with its reference answer. 2. Add the new rule after the existing ones, so it only rewrites correlated subqueries they leave in the plan. Plans that work today should not change, but I haven't run that ordering yet. The first PR is the core (domain, join back, aggregate without `GROUP BY`), then one PR per operator (`LIMIT`, window, `UNION`, joins, grouping sets), each turning the catalog entries it fixes from errors into right answers. 3. Move one subquery kind at a time (lateral, scalar, `EXISTS`, `IN`/`NOT IN`) ahead of the old rules, reviewing each plan diff. 4. Delete the old rules. @mohammadnaqvi04 would you like to take the test PR, and build your design doc on the prototype? I can send you the repros and the fuzzer. @alamb does one domain-based rule replacing the four look like the direction you had in mind? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
