M2c.4: Join ordering, and the estimates we refuse to build
- Dominant language
- Mojo
- Stars
- 1
- Forks
- 0
- PR merge metrics
- PR metrics pending
Description
Part of #372. Depends on #378. The design is `docs/specs/planner/03-join-ordering.md` and `docs/specs/planner/05-cardinality-and-cost.md`.
This issue is deliberately small, and it is last, because predicate transfer is expected to take most of the reason for it away. Robust Predicate Transfer measures the ratio between the worst and best random join order on an acyclic query dropping to 1.6, which is a range a greedy ordering from exact row counts can live inside.
The other reason it is small is that we are not going to build a cardinality estimator. Four families exist, histograms, sampling, sketches and learned models, and the Join Order Benchmark result is that all of them are wrong by orders of magnitude past three relations and that the cost model matters far less than the estimates. There is also a contrarian thread worth taking seriously, that modern main memory systems operate with limited or no estimation and stay competitive.
## What we know exactly and should use
- [ ] Exact row counts, because in an engine that runs a plan node by node the input to the node being chosen has usually already been computed
- [ ] Cached distinct counts from #375
- [ ] Measured selectivity, recorded as a filter runs rather than predicted before it does
## The one estimate we cannot avoid
- [ ] Join output size estimated as the size of the larger side, with the foreign key assumption written down where a reader will find it
- [ ] Estimate bail out: when a join's output exceeds its estimate by a large factor, re-decide the next operator from the measured number rather than compounding the estimate
## The ordering
- [ ] Greedy ordering from exact row counts, joining the pair whose result is estimated smallest
- [ ] A cost model that is rows moved and nothing else
- [ ] DPccp for fewer than ten relations, only if a measured query still needs it after predicate transfer lands in #378
- [ ] DPhyp deliberately not built
## Done when
Greedy ordering is in, and either a measured TPC-H or JOB query needs DPccp and gets it, or none does and this issue closes saying so.
Contributor guide
Research direction
Start with docs/specs/planner/03-join-ordering.md and docs/specs/planner/05-cardinality-and-cost.md, then read #378 and #375 for predicate transfer and cached distinct counts. Implement greedy ordering and the stated estimate bail-out, considering DPccp only if a measured TPC-H or JOB query needs it. Done means greedy ordering is in and the DPccp outcome is documented.
Written by the indexing model from the issue text.
Assessment
- Domain
- data-engineering, databases
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100