M2c.2: The optimizer pass pipeline
- Dominant language
- Mojo
- Stars
- 1
- Forks
- 0
- PR merge metrics
- PR metrics pending
Description
Part of #372. Depends on #376. The design is `docs/specs/planner/02-the-pass-pipeline.md`.
The passes, in the order they run. Every one of these was done by hand on the TPC-H driver in tamnd/firepanda-bench, so each carries a number that is ours rather than a number from a paper. The twenty two queries went from 6.671 seconds at sf1 to about 1.2, and this list is most of that distance.
- [x] Expression simplification: constant folding, comparison simplification, conjunction flattening, applied to a fixed point. This is what stops `date '1998-12-01' - interval '90 days'` being evaluated six million times.
- [x] The flattened conjunction survives lowering, one operator over every operand rather than a chain of pairs. The pass flattened it and the lowering folded it straight back, so the rewrite bought the plan text and nothing else.
- [ ] Type coercion inserted as explicit cast nodes, so the plan says where a cast happens rather than leaving it to the kernel
- [x] Projection pushdown. The largest single pass. Ours by hand was most of the distance from 6.671 seconds to about 2 across the twenty two queries.
- [x] Predicate pushdown. Second largest. Ours by hand: q19 83 milliseconds to 70, q21 285 to 169.
- [x] Transitive predicates across equality join conditions, so a filter on one side of `a.k = b.k` reaches the other
- [x] Common subplan elimination
- [x] Common subexpression elimination
- [x] Projection merging, adjacent projections into one node. This removes the copy that `DataFrame.add_column` exists to let a caller avoid by hand: q1's two additions were 93 milliseconds and are 37.
- [x] Slice pushdown
- [x] Top n recognition, a limit above a sort becoming the bounded heap we already have
- [x] Empty and constant pruning
- [ ] `IN` against a large constant list rewritten as a join
- [ ] A semi join whose right side is distinct on the key rewritten as an inner join
## Quality
- [ ] Every pass has a test asserting on printed plan text, which is how every optimizer in the world is tested and is easier to read than assertions about tree structure
- [ ] A differential test running each TPC-H query with the optimizer on and off and comparing answers
## Done when
A plain translation of all twenty two TPC-H queries, written against the frame API with no hand planning, performs within a few per cent of the hand planned driver, and the hand written helpers in the benchmark driver are deleted because binding made them unnecessary.
Contributor guide
Research direction
Start with docs/specs/planner/02-the-pass-pipeline.md and review dependency #376 before choosing one of the unchecked passes or quality tasks. Use printed plan text for pass tests and the TPC-H driver in tamnd/firepanda-bench for comparison. Done means all twenty-two plain frame-API queries perform within a few percent of the hand-planned driver and the handwritten benchmark helpers are removed.
Written by the indexing model from the issue text.
Assessment
- Domain
- data-engineering, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100