M2c.0: Stage zero, the decisions that need no plan
- Dominant language
- Mojo
- Stars
- 1
- Forks
- 0
- PR merge metrics
- PR metrics pending
Description
Part of #372. The design is `docs/specs/planner/07-operator-selection.md` and the first section of `docs/specs/planner/08-the-plan.md`.
These are decisions the engine makes today from a parameter name, or from a constant, or not at all, and none of them needs a plan layer to fix. They ship as ordinary pull requests and they are the first thing in the milestone because they are the cheapest thing in it.
## The join side
`firepanda/join/pairs.mojo` buckets the right side because the parameter is called right, whatever the two heights are. The table is the thing that has to be resident, so it should be built from the smaller side. The catch is that `join_indices` promises its output in left row order and probing the right side gives right row order, so an inner join that flips has to put the order back, which is a counting sort keyed on the left row and is exactly the pass `bucket_side` already writes three times.
- [x] Build side chosen by height rather than by parameter name, for the inner join
- [x] Left row order restored by a counting sort on the left row, so the documented order does not change
- [x] A test that an inner join with the small frame on the left returns the same rows in the same order as one with it on the right, transposed
## The join key routes
`align_keys` gives a single non text key a dictionary built on the smaller side, and `build_side` takes a table indexed by the value itself when the key is an integer with a narrow span, which is the perfect hash join and is already there. A single text key gets the same shape only when the two sides differ in height by a factor of eight. Everything else, which is every join on more than one key column, concatenates every key column across both sides and factorizes the tuple over the sum of the two heights.
- [x] A join on more than one key column building a dictionary on the smaller side and probing the larger
- [ ] A join on one text key taking the dictionary route when the two sides are close in height
- [x] A benchmark row for a compound key join, since nothing in either suite currently covers one
## Column metadata
Five decisions elsewhere in this milestone need to know something about a column that a kernel already computed and threw away. The discipline is that a flag is known true, known false, or unknown, and unknown is always safe.
- [ ] A sortedness flag, set by `sort_values` and by readers that know, cleared by everything that reorders
- [ ] An all valid flag, set by the kernels that already count nulls
- [x] A cached distinct count, written by `factorize`, which computes it as a side effect
- [ ] A cached minimum and maximum, written by the kernels that already scan for them
- [x] Invalidation on write, with a test that a mutated column reports unknown rather than stale
## What the metadata unlocks
- [x] Sorted group by, chosen when the key carries the sortedness flag, with no hash table at all
- [ ] The broadcast versus group and semi join choice made from the cached distinct count rather than hardcoded per query, with the crossover measured and recorded in the docstring
## Done when
Every item above is merged, the full test suite passes unchanged, and the TPC-H and db-benchmark numbers are no worse on any query.
Contributor guide
Research direction
Read docs/specs/planner/07-operator-selection.md and the first section of docs/specs/planner/08-the-plan.md, then inspect firepanda/join/pairs.mojo and the existing metadata paths. Run the relevant tests and benchmarks first; done means every unchecked item is implemented, the full test suite passes, and TPC-H and db-benchmark results are no worse on any query.
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