tamnd / tamnd/firepanda

S4. The logical plan and the first executions

Open
#309 84 comments 0 reactions 0 assignees View on GitHub
area/exec area/plan area/sql enhancement
Dominant language
Mojo
Stars
1
Forks
0
PR merge metrics
PR metrics pending

Description

Part of #304. Depends on S3, and shares its artifacts with M4.

The contract between the two halves of firepanda. This was written when there was nothing between the eager frame and the push driver that could be called a plan. `firepanda/plan/` is that plan now, built as part of the planner milestone, so the work here is lowering SQL into it and growing it where SQL reaches past what it holds rather than starting one.

This is the issue that argues the whole milestone moves ahead of M11. The plan is load bearing for the lazy frame, for the optimizer, for `query()` and for the TPC-H work in #299. SQL is the forcing function that gets it written against a demanding consumer instead of a hypothetical one.

### Scope

- [x] `LogicalPlan`, arena allocated and index referenced, every node carrying the schema it produces
- [ ] The fourteen logical operators
- [x] `BoundExpr`, where every column is a binding and column index pair and every cast is explicit
- [ ] Decorrelation by dependent join pushdown
- [x] JSON serialization that round trips, and the EXPLAIN printer
- [x] Enough physical planning to run SELECT, WHERE, GROUP BY, ORDER BY, LIMIT and inner joins on the existing morsel engine
- [x] The plan equality test between the SQL path and the dataframe path

### The operators

Get, TableFunction, Values, Projection, Filter, Aggregate, Window, Join, Order, Limit, Distinct, SetOp, Unnest, RecursiveCTE. Everything in the dialect lowers to those.

QUALIFY is a Filter above a Window. GROUPING SETS, CUBE and ROLLUP are masks on one Aggregate rather than a union of several, because the naive lowering is quadratically slower. PIVOT is an Aggregate with a generated grouping set and conditional aggregates. DISTINCT ON is Distinct with a key list under an Order. Semi, anti and mark joins are join types rather than subquery nodes, which is the entire point of decorrelation.

Two node types exist for the optimizer rather than for the binder. A mark join produces a boolean column rather than filtering, and is what IN and EXISTS become. A dependent join is the temporary node a correlated subquery binds to before decorrelation removes it.

### Decorrelation is not optional

A correlated subquery evaluated naively is one execution per outer row. On TPC-H q17 and q20 at SF10 that is millions of executions, and it turns a two second query into an unfinished one.

The rewrite is the one from Neumann and Kemper. The binder emits a dependent join with the outer columns made explicit, the pass pushes it down through the subquery plan one node type at a time until it reaches the point where the correlated columns are used, and there it becomes an ordinary join against the distinct set of outer values.

The last step is the whole discipline. No dependent join may survive the pass. A leftover one means a fallback to per row execution, and a fallback that works but is a thousand times slower is how a benchmark quietly fails. It is an assertion in debug builds and a logged plan warning in release.

Each subquery kind gets a rewrite. Scalar becomes a left join with a single row check, EXISTS a semi join, NOT EXISTS an anti join, IN a mark join, and NOT IN a null aware anti join because of the three valued semantics from S3. A plain anti join for NOT IN is the classic wrong answer and it is silent.

### The rule that keeps this honest

No node may have only a SQL constructor. If SQL can express something the dataframe API cannot, that is a gap in the dataframe API to be filed, not a private extension to the plan.

That is a real constraint on the API and not a slogan. The eager DataFrame becomes a facade that builds a one node plan and executes it, a LazyFrame becomes the same builder without the execute, and `df.filter(...).groupby(...).agg(...)` builds the same Aggregate over Filter over Get that the equivalent SELECT builds. The plan equality test asserts exactly that, and it is worth more than any benchmark, because it is what stops the SQL surface quietly becoming a second and worse engine.

### What the plan does not contain

No physical choices, so no join algorithm, no build side, no chunk size, no parallelism degree. No statistics, because cardinality estimates live beside the plan in the optimizer's own structures, which is what makes a plan comparable by structure across runs. No engine hints. And no unbound names, because if a plan contains a string that has to be resolved later then the binder did not finish its job.

### Exit criteria

- [x] TPC-H q1, q3 and q6 return correct results at SF1
- [ ] The plan equality test passes for those three queries
- [x] Plans round trip through the JSON form
- [ ] No dependent join survives decorrelation on any corpus query, asserted rather than hoped

### Depends on

S3. Overlaps M4, and the plan built here is the plan M4 needs.

Contributor guide

Open the contributing guide

Research direction

Start with S3 and the existing firepanda/plan/ implementation, then trace the SQL and dataframe lowering paths and the plan equality test. Done means the remaining logical operators and decorrelation are implemented, the three TPC-H plan equality checks pass, and no dependent join survives on the corpus queries.

Written by the indexing model from the issue text.

Assessment

Tech stack
sql
Domain
data-engineering, databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.