Joins consult no index: add a join site to the index routing table #595

Activity

1. singaraiona commented on Sep 20, 2026

   

   singaraiona

   on Sep 20, 2026

   Collaborator

   More actions

   The core claim is correct and worth acting on: src/ops/join.c includes ops/idxop.h and never calls a single index function. Joins build a fresh hash over their input on every call, and none of the five routing sites is a join. No argument there.

   Three things before anyone scopes it, though — one of which affects the query you measured.

   The query in your measurement cannot benefit from an index

   (left-join [keys] left right) keeps every left row. So (left-join [venue instrument] levels keys), with the 351k-row levels as the left side, produces 351k rows by definition. Your own observation — "costs ~13 ms whether keys names one book or ten — the cost is the left side, every time" — is not an indexing failure. It is the semantics of the join you asked for. No index can make a left join emit fewer left rows, because every one of them is in the result.

   Where an index genuinely wins is the mirror image: an inner or semi join, probing a small key set into an indexed large side and collecting O(matches) instead of enumerating all 351k rows. That is a large win and it is what a join routing site should deliver — but it is a different query from the one you profiled.

   So the question back to you: do you want only the matched rows? If so, the lever is inner-join plus a join site, not left-join plus an index. If you need the unmatched left rows too, the result is inherently O(left) and the thing to attack is what you do with those rows — which sounds like your #596.

   The "needs no new index" alternative does not work as described

   The upsert key map is real, and it is maintained across appends (ukey_extend_after_append, query.c:15573). That part of your reasoning is sound — more so than you may realise, since a map surviving appends was a genuine gap until recently.

   But it cannot be probed on a prefix. upsert_hash_row (query.c:15496) seeds and combines all nk key cells into a single hash, and ukey_describes requires an exact nk match. Hashing [venue instrument] does not produce the hash stored for [venue instrument bid ask]. Your (upsert 'levels 4 rows) joined on a two-key prefix is exactly the case the structure cannot serve. Making it work needs either a join whose keys are all the upsert keys, or a second prefix-keyed map — which reintroduces the build cost the suggestion was meant to avoid.

   One property in your favour if that is ever built: the map chains duplicates in row order rather than keeping one row per key, so it can return all matches, which is what a join needs.

   Your point 2 is half-wrong, in your favour

   .idx.hash already accepts SYM and STR at attach time, and find / in already take SYM and STR needles. The integer-family restriction you cite applies only to the filter EQ/IN consumption site. A join site would not be starting from zero on symbol columns.

   Better still, idx_fresh_nonull (idxop.c:1399) has a SYM arm that answers "is this column null-free" in O(1) from the index's own row count instead of scanning — so an indexed join key would get that proof for free.

   Please re-measure on a build carrying #598

   The 13.28% ray_vec_is_null line in your profile is what #598 addresses, and hash_row_keys — your largest entry at 34.72% — loses its per-cell null branch as part of the same change. Both numbers will move, and so will the 73%-in-the-worker-pool figure. Sizing this work against the current profile would be sizing it against a build that no longer exists.

   What we think is buildable

   Single-key joins probing .idx.hash are straightforward, and #520 set the precedent: a vector of needles probes once per needle and builds nothing per call. That is the same shape a join probe wants.

   Compound keys are the real question, and there is no compound index. The tractable version is probing the more selective indexed key column and verifying the remaining keys on the candidate rows — that covers [venue instrument] without a new index kind, with a selectivity guard like the one .idx.sort already carries. A genuine compound index kind is a much larger piece of work and we would not start there.

   Keeping this open as accepted-in-principle. The most useful next thing from your side is a profile on a build with #598, and an answer on whether the matched rows alone would do.
2. vbmithr commented on Sep 20, 2026

   

   vbmithr

   on Sep 20, 2026

   ContributorAuthor

   More actions

   Thanks — the left-join point is correct and I should have caught it myself.

   Yes: matched rows alone would do

   Every hot join in our service wants only the matches. Going through them:

   • (inner-join [venue instrument] held ready_keys) — the held rows of books
     that just became ready. Small key set, large left side, matches only. This
     is our most expensive single join and it is exactly the shape you describe.
   • (inner-join [venue instrument session message_id] b h) — rows belonging to
     a set of messages. Matches only.
   • (inner-join [venue instrument beg] h …) — the oldest message per book.
     Matches only.
   • (inner-join [venue instrument] b bk_state) — attach per-book state to a
     wave. Matches only.

   The left-join you picked apart was not a join we wanted at all. It was
   computing a delete mask: the result went straight into
   (> (fill 0 (get j 'n)) 0) and was discarded. You are right that no index
   could have helped it. We have since replaced it with OR-ed per-book
   (and (== venue v) (== instrument i)) predicates — 50 us for one book against
   ~13 ms for the join, because a vectorised compare over 351k rows costs
   ~0.05 ns/row while anything hash-shaped costs ~8 ns/row. That call site is
   gone; please size the join work against the inner-joins above, not against it.

   Our anti-joins (anti-join [venue instrument session message_id] held …) do
   want the unmatched left rows, and they are O(left) by nature. Those are #596,
   as you say — they only ever feed a delete or replace the left table, so a
   mask would serve them and the gather would not be needed.

   Prefix probing — accepted

   You are right, and thank you for the pointer to upsert_hash_row. Seeding all
   nk cells into one hash means a two-key prefix is simply a different hash, and
   ukey_describes requiring exact nk makes it explicit. Withdrawn.

   #598: measured

   Re-profiled on 2.6.2.r229.ge7770412 (30 s, --call-graph fp), same service,
   same workload shape:

   symbol	before #598	after
   ray_vec_is_null	13.28%	4.81%
   hash_row_keys	34.72%	32.34%
   gather_fn	9.07%	11.90%

   The null-check line is down by about two thirds — that one is clean and
   attributable. Total CPU also roughly halved, but I cannot hand you that: we
   landed a fix of our own in the same window (hoisting a per-wave join out of a
   drain loop, ~3.3x on its own), so the two are confounded. hash_row_keys is
   still the single largest entry, which is the case for this issue.

   One practical constraint for a join site

   Our tables are written every batch, and I measured that an attached index does
   not survive a mutation:

   (set t2 (table [instrument px] (list (.idx.hash v) (til N))))
   (.idx.has? (get t2 'instrument))    ; true
   (insert 't2 …)
   (.idx.has? (get t2 'instrument))    ; false

   So for a workload like ours, a join site that requires an index on the large
   side only pays if the index survives appends — otherwise we rebuild per batch
   exactly what the join would have built anyway. A site that probes an index on
   the small side, or one that reuses a map maintained across appends the way
   ukey_extend_after_append does, does not have that problem.

   Related measurement, since it bears on the same machinery: with .idx.hash
   attached to the right-hand vector, (in bigcol keys) is flat at ~2.8 ms over
   351k rows for 1, 10 or 766 keys — one probe per needle, exactly as
   documented. Without the index the same call is 2.6 ms at one key and 4.2 ms at
   ten, and in the reversed direction it degrades to O(n·m). That is the #593
   fallback bug, and the index path proves the probe side works fine.
3. singaraiona commented on Sep 20, 2026

   

   singaraiona

   on Sep 20, 2026

   Collaborator

   More actions

   This is a good reply — the four inner-join shapes are what we needed, and the honesty about the confounded total is appreciated. A few things back, including a correction to my own suggestion.

   Correcting myself: single-key first would reach none of your joins

   I proposed starting with single-key .idx.hash probing as the easy increment. Looking at your four shapes — [venue instrument], [venue instrument session message_id], [venue instrument beg], [venue instrument] — every one is compound. A single-key site would reach exactly zero of them. That was the wrong increment to propose and I withdraw it; probe-the-selective-column-then-verify is the minimum viable version for this workload, not the second step.

   Your index-survival constraint is right, and it is sharper than you put it

   I pinned it down:

   • A batched upsert that only updates existing keys preserves the key columns' indexes — upsert_apply_vectors explicitly skips key columns when dropping (query.c:16076-16079, if (is_key) continue; /* matched: already equal */).
   • A batch that appends even one new key grows every column via ray_vec_append_raw, which drops the index on all of them — key columns included (query.c:16064-16067).

   So it is not that mutation invalidates the index generally; it is that one new book in the batch costs you the index on every column of the table. For a feed where instruments appear over the session, that is going to fire regularly and unpredictably — which is worse than a flat "no index after writes", because the performance cliff is data-dependent.

   The machinery to fix that already exists in the tree

   ukey_extend_after_append (query.c:15573) maintains the upsert key map across exactly those appends: new rows are entered as they land, and the map is dropped only if it can no longer describe the table. That is precisely the discipline .idx.hash lacks.

   The blocker for your workload is therefore not "joins need an index site" so much as the asymmetry: one hash structure in this codebase survives appends and the other does not, and the join site would be built on the wrong one. Teaching .idx.hash the ukey_extend_after_append discipline looks like the prerequisite, and it has value beyond joins — every existing routing site currently loses its index on the first append too.

   We are not committing to a design in this thread, but that is where we would start looking, and it reframes the issue usefully.

   On the residual 4.81%

   Two things worth separating before you read more into it. ray_vec_is_null has callers well outside the join — gather, morsel, eval — so some residue is expected and is not the join path. And gather_fn rising 9.07% → 11.90% is share-shift from a smaller total, not a regression.

   One thing genuinely worth checking on your side: an empty symbol is the SYM null. The #598 proof is all-or-nothing per join — if any cell of venue or instrument is ever the empty symbol, the proof fails for that whole join and you get none of the benefit, while still paying the scan that discovers it. If a book ever lands with an empty instrument, even rarely, that would explain a smaller-than-expected drop on the affected joins. Cheap to check directly against those columns.

   The in measurement is useful

   Flat at ~2.8 ms for 1, 10 and 766 needles against a 351k column is exactly the probe-per-needle contract, and it is good evidence that the probe side holds up at your key counts. Noted for #593 separately — the reversed-direction degradation you describe there is a real fallback bug and is not blocked on any of this.
4. vbmithr commented on Sep 20, 2026

   

   vbmithr

   on Sep 20, 2026

   ContributorAuthor

   More actions

   Empty symbols: checked, and we have none

   Audited the join key columns directly with element-wise nil?, on a live
   instance on the production feed, at two points ~3 minutes apart:

   levels_rows:298913  levels_venue_nulls:0  levels_instr_nulls:0
   held_rows:55700     held_venue_nulls:0    held_instr_nulls:0   held_session_nulls:0
   pending_rows:57     pending_venue_nulls:0 pending_instr_nulls:0 pending_session_nulls:0
   bk_rows:773         bk_venue_nulls:0      bk_instr_nulls:0
   

   Zero across every key column of every table the hot joins touch, over 773
   instruments. So the #598 proof should be holding for our joins, and the
   residual ray_vec_is_null is the non-join callers you name rather than a
   failed proof. Thank you for the pointer — it was worth ruling out, and it is
   now a check we can repeat cheaply if a venue ever starts emitting one.

   Agreed on gather_fn: share-shift from a smaller total, not a regression. We
   read it the same way.

   The append cliff matches what we see

   Your ray_vec_append_raw finding explains the shape of our workload exactly.
   Instruments appear over the course of a session — a venue lists something new,
   or a book we have never seen sends its first message — so batches that
   introduce a new key are irregular but routine, and they are not rare enough to
   ignore. A data-dependent cliff there would be worse for us than no index,
   because it would make a tuned service unpredictable rather than merely slower.
   Teaching .idx.hash the ukey_extend_after_append discipline being the
   prerequisite reads correctly to us, and we agree it is worth more than the
   join site alone.

   Taking the single-key correction as read, too — all four of our shapes are
   compound, so probe-the-selective-column-then-verify is indeed the minimum that
   reaches us.

   Where this sits for us now, in the interest of your prioritisation

   Since filing, we have taken this service from ~147% of a core to 6-9% steady
   (32,105 rows/s, 34 batches/s, 412k level rows, 773 instruments) — mostly by
   not asking the engine table-sized questions in the first place, plus -c 2
   from #599. hash_row_keys is still ~32% of what remains, so a join site would
   still be the single biggest structural win available to us, but it is now ~32%
   of a much smaller number.

   We are not blocked. Please weight this against the other issues accordingly —
   we would rather you build the append-surviving index properly than rush a join
   site onto a structure that loses itself on the next new instrument.
5. singaraiona commented on Oct 1, 2026

   

   singaraiona

   on Oct 1, 2026

   Collaborator

   More actions

   Picking this back up with one finding that changes the size of the prerequisite, and one that partly removes the dependency on it.

   Making .idx.hash survive appends is a redesign, not a port

   Last time I said the fix was to teach .idx.hash the ukey_extend_after_append discipline. The two structures are laid out differently, and that is what makes one easy and the other not:

   • The upsert key map is open-addressed, one slot per row (src/ops/query.c:17371). An append inserts new slots and touches nothing else, which is why extending it costs about what the append cost.
   • .idx.hash is grouped: a bucket table over distinct keys, plus each key's rows as one contiguous ascending slice (src/ops/idxop.h:117). Adding a row for a key that already exists means shifting every later key's slice.

   concat already keeps the hash when every appended key is new — a new key just goes on the end (#519) — and drops it on any repeat. On per-column venue / instrument indexes in a feed, nearly every appended row repeats a key, so that path reaches essentially none of your appends.

   The realistic design is a base-plus-delta index: keep the grouped layout as the base, enter appended rows into a small open-addressed side table, have lookups read both (base rows first, so ascending order holds), and fold the side table in past a size threshold. That benefits all five existing routing sites, but it is real work, and it is what a join site on a write-every-batch table would be waiting on.

   Much of the join win doesn't need an index at all

   The inner join already has a prefilter (src/ops/join.c:1603): it builds a bitmap of the right side's key values and skips any left row whose key bit is clear, before hashing it (join.c:1049). Today it is gated on a single I64 key and inner joins only, so it reaches none of your joins.

   Two things make it a good fit for your shape:

   • SYM ids are bounded, so a bitmap over the right side's instrument ids is cheap to build per call — the same O(right) the hash build already pays.
   • It works for compound keys without a compound index: test the selective column's bit first, then hash and verify the full [venue instrument …] key only on rows that pass. Rows that fail the bit test never reach hash_row_keys.

   So hash_row_keys drops from O(left) to O(candidates). The left side is still scanned, but with a bit test per row instead of a hash. It survives every append trivially because nothing persists between calls. It also covers left-join — the probe loop already emits unmatched rows on the skip path, so only the gate excludes it.

   That gives two access paths for the same compound-key match:

   path	cost	needs
   bitmap prefilter, then verify	O(left) bit tests + O(candidates) hashing	nothing; per-call
   index probe, then verify	O(matches)	an .idx.hash that survives appends

   This is the same work as #596

   #596's semi-mask / anti-mask is the output form of exactly this match: the candidate rows that pass verification are the mask. A join site here is the access path. Built once — a compound-key match with the two access paths above — it serves inner-join (then gather), semi-mask / anti-mask (no gather), and a count(join) rewrite (neither). I've left the same note on #596.

   Proposed order

   1. Lift the prefilter to SYM and compound keys (selective column first, then verify), for inner and left joins, with mask output for A join that returns a row selection instead of a materialised table #596. No index needed, no append problem.
   2. Base-plus-delta .idx.hash that survives appends.
   3. Index-probe access path on top of that, for when matches are a small fraction of the left side.

   Step 1 should reach all four of your inner joins and the #596 delete mask. Once there is a build, your benchmark from #596 is the right check.

   👍React with 👍1Reacted by Vincent Bernardoff