tamnd / tamnd/firepanda

M2c.4: Join ordering, and the estimates we refuse to build

Open
#379 0 comments 0 reactions 0 assignees View on GitHub
area/plan milestone performance
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.