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

[vbmithr]

Summary

The index routing table in docs/docs/queries/indexes.md lists five
consumption sites: filter, where key IN … group by key, ORDER BY,
distinct, and find/in. Joins are not among them. join, left-join,
inner-join and anti-join build a fresh hash over their whole input on
every call, whatever indexes or attributes the key columns carry.

For a workload that joins a small key set against a large table repeatedly,
that is the dominant cost, and no existing accelerator can reduce it.

Measurement

A 30 s perf --call-graph fp of a market-data service (766 instruments,
~27k rows/s, a 351k-row table joined per batch):

34.72%  hash_row_keys
13.28%  ray_vec_is_null
 9.07%  gather_fn
       + ~18% libc memcpy, all under the join worker tasks

73% of samples were in the query worker pool, dispatched from
ray_anti_join_fn and exec_join_flat. At the table sizes above, one
(left-join [venue instrument] levels keys) costs ~13 ms whether keys
names one book or ten — the cost is the left side, every time.

For scale: the same service's actual state maintenance, (upsert 'levels 4 rows) with ~900 rows, is 260 us. The joins around it are two orders of
magnitude more expensive than the update they exist to support.

What we are asking for

A join consumption site in the routing table. When a join key column
carries .idx.hash (or part backing), probe it instead of building a new
hash over the whole side. The fallback contract would be the same as every
other site: identical results, scan path when ineligible.

Two details that matter for this shape of workload:

1. Compound keys. Our joins key on [venue instrument], and the four
   .idx.* kinds occupy one per-column slot today. A join site is only
   useful here if a multi-column key can be probed — either a compound index,
   or probing the more selective column and checking the rest.
2. Symbol columns. .idx.hash is wired to filter EQ/IN for
   integer-family columns only, while find/in accept SYM needles. Join
   keys in market data are overwhelmingly symbols, so a join site restricted
   to integer families would not reach this workload.

An alternative that needs no new index

upsert already maintains a key map for keyed tables (21dba3f1,
917d667f, 5b997dd1). A table written with (upsert 'levels 4 rows) has a
live map over its first four key columns. Letting a join on a prefix of
those keys probe that existing map would cover our case without introducing
a new index kind or a new build cost — the map is already there and already
maintained.

---

Measured on rayforce 2.6.2 (the build carrying bc350ddc).

[singaraiona]

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.

[vbmithr]

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.

[singaraiona]

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.

[vbmithr]

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.