`in` with a one-element right side builds a hash instead of lowering to an equality scan (~27x)

[vbmithr]

Summary

in compares every element of its left side against every element of its
right side. There is no hash set, and no specialisation for a single-element
right side, so a membership test against a column is O(n·m) and is beaten by
hand-written equality predicates by two to three orders of magnitude.

Measurement

A 351,393-element symbol column (766 distinct values), right side varied:

right side	(in col right)
1 symbol	6,500 us
10 symbols	11,950 us
100 symbols	76,800 us
766 symbols	298,200 us

For comparison, on the same column, (== col 'SYM) — the same question for
one element — is about 16 us. in is ~400x slower than the equality it could
lower to, before any set is involved.

Why it matters to us

We maintain an order book table (levels, ~351k rows, keyed conceptually by
(venue, instrument)) and frequently need "the rows belonging to these few
books". The three shapes available today:

• (left-join [venue instrument] levels keys) — correct, but sized by
  levels: ~13 ms whether the right side names one book or ten.
• (in instrument syms) — sized by n·m as above, and also wrong on its own
  for a compound key: (and (in venue vs) (in instrument is)) matches
  cross-venue pairs that are in neither input.
• OR-ed per-pair predicates, (or (and (== v ...) (== i ...)) ...) — what we
  ended up writing. 50 us for one book, 600 us for ten, linear in the number
  of books, and it crosses the join's flat cost at ~216 books.

The third is fastest for small key sets and is what we shipped, but it is a
loop building a boolean expression by hand, and it is linear where a hash set
would be flat.

What we are asking for

1. Hash the right side of in when it is a vector above some small
   length, so membership is O(n + m) rather than O(n·m). The machinery
   already exists — hash_row_keys is what the join builds.
2. Specialise a one-element right side to the equality scan. (in col [x]) should not cost 400x (== col x).

Optionally, and more useful still for our case:

3. A compound membership — a way to ask "is this row's (a, b) in this
   two-column table" without materialising a composite key column and without
   a full join. This is the primitive our workload actually wants; in per
   column cannot express it correctly.

Prior art

q's in hashes its right side, and ?/in over a compound key is expressed
with a keyed table lookup that probes a hash rather than scanning.

---

Measured on rayforce 2.6.2 (the build carrying bc350ddc, the while form).

[vbmithr]

Correction and a sharper framing, after reading docs/docs/queries/indexes.md.

My original text said there is no hash set. That is wrong, and I withdraw it:
.idx.hash exists, and the routing table already lists in as a consumption
site — "(in needles v) with v indexed … one probe per needle", and,
importantly, "Without an index, find / in hash whichever side is smaller
and scan the other once."

That documented fallback is O(n + m). What I measured is not. Against an
unindexed 351,393-element SYM column, with the needles as the left
argument:

right side	(in col right)
1 symbol	6,500 us
10 symbols	11,950 us
100 symbols	76,800 us
766 symbols	298,200 us

That is O(n·m): 100 needles cost ~12x what 10 do. If the smaller side (766
symbols, worst case here) were hashed and the column scanned once, the last
row should be in the same ballpark as the first, not 46x it. A plain
(== col 'SYM) over the same column is ~16 us.

So this is better read as a bug than a feature request: either the documented
"hash the smaller side" fallback does not apply to SYM vectors, or it is not
reached on this path. The type matrix says find/in accept SYM needles
against a same-family column, so it looks like it should be.

The feature half of the original request still stands, but narrows to:

• make the unindexed fallback match its documentation for symbol columns;
• a compound membership, which per-column in cannot express correctly
  regardless of speed — (and (in venue vs) (in instrument is)) matches
  cross-venue pairs present in neither input.

Measured on 2.6.2 (the build carrying bc350ddc).

[singaraiona]

Status correction. Prompted by a note in #596 that this no longer reproduces, I
re-measured all three requests on current dev (c5556113). Request 1 is
fixed; requests 2 and 3 still stand. Leaving this open for those, with the
headline corrected.

Request 1 — hash the right side: fixed by #519

A 351,393-element SYM column, right side varied, 10 reps:

right side	as filed	now
1	6,500 us	4,800 us
10	11,950 us	6,800 us
100	76,800 us	9,000 us
766	298,200 us	8,200 us
5,000	—	6,500 us
50,000	—	7,300 us

36x faster at 766, and flat from 1 to 50,000 needles — hash behaviour, not a
scan. The O(n·m) claim in the summary above is no longer true of this build.

Correctness spot-checked rather than assumed: a right side holding half the
distinct symbols masks 175,797 of 351,393 rows, against an expected ~175,696.

This is #519 ("let find / in with a vector of needles consult the attached
hash index"), closed 2026-09-13 — filed separately and never cross-referenced
here, which is why this issue kept its original headline.

Request 2 — specialise a one-element right side: still open

The gap is smaller than filed but still large. Same column, 20 reps:

(== col s)     ->    50 us
(in col one)   -> 4,600 us      92x, identical output (459 rows)

The issue estimated ~400x (6,500 vs 16); it is 92x now. Building a one-entry
hash to answer a question a vectorised equality scan answers directly is still
the wrong shape, so this part of the ask survives.

Request 3 — compound membership: still open, and tracked in #596

Unchanged, and it is the more valuable of the two remaining. #596 asks for the
same primitive from the other direction — a join that returns a row selection
over multi-column keys instead of a materialised table — and the reporter there
confirms every hot join in that service is [venue instrument] or a four-column
key, with no single-key join anywhere.

Worth noting the two are the same gap seen from opposite ends: in per column
cannot express a pinned pair (independent in predicates over venue and
instrument match cross-venue pairs present in neither input), and the join
that can express it is sized by the left side rather than by the selection.
Measured here on a 351,393-row table:

left-join books=1     43,100 us     459 rows selected
left-join books=128   51,350 us     58,752 rows selected
left-join books=766   58,550 us     351,393 rows selected (all)

Selecting 0.13% of the table costs 74% of what selecting all of it costs.

I would rather solve request 3 once, in the form #596 describes, than twice —
so I am tracking the compound case there and keeping this issue for request 2.

[vbmithr]

Confirming your status correction from this side, and leaving the clear
reproducer request 2 deserves — my original report has none that isolates it.

Request 1 is fixed; I agree this issue should stay open for request 2.
I re-measured independently before reading your comment and got the same shape:
flat from 10 to 50,000 needles, ~3.6 ms where the report says 298 ms at 766.
The Summary above is simply wrong about this build, and #519 is the fix.

Reproducer for request 2

Self-contained, no IPC and no data files. The first line proves both
expressions answer the same question, so the comparison is honest.

(println "build=" (.sys.build))
(set NL 351393)
(set NI 766)
(set insts (as 'SYM (map (fn [i] (format "INST%" i)) (til NI))))
(set col (take insts NL))          ;; 351,393 rows, 766 distinct SYM
(set s (first insts))
(set one (take insts 1))           ;; one-element SYM vector

;; identical output, so this is the same question asked two ways
(set a (== col s))
(set b (in col one))
(println "same result: " (all (== a b)) "   rows selected: " (sum a))

(set bench
  (fn [name n f]
    (do (f)
        (let t0 (.time.now))
        (let i 0)
        (while (< i n) (f) (let i (+ i 1)))
        (let el (- (.time.now) t0))
        (println name "  " (/ (* 1000.0 el) n) " us/call   [" n " calls, " el " ms]"))))

(set two  (take insts 2))
(set ten  (take insts 10))
(set many (as 'SYM (map (fn [i] (format "INST%" i)) (til 50000))))

(bench "(== col s)     " 50 (fn [] (== col s)))
(bench "(in col one)   " 50 (fn [] (in col one)))
(bench "(in col two)   " 50 (fn [] (in col two)))
(bench "(in col ten)   " 50 (fn [] (in col ten)))
(bench "(in col 50000) " 50 (fn [] (in col many)))

On 2.6.2.r237.gc5556113, -c 2:

same result:  true    rows selected:  459
(== col s)         40 us/call
(in col one)     2680 us/call      67x
(in col two)     2560 us/call
(in col ten)     3080 us/call
(in col 50000)   3000 us/call

67x rather than the ~400x I estimated, and rather than your 92x — same
conclusion, and the difference is just (== col s) being faster here (40 us).

The flatness is the bug, not just evidence of the fix

The interesting line is the last one: one needle costs the same as fifty
thousand. Whatever in pays, it pays entirely up front and independently of
the right side's size, so the degenerate case is charged the full hash-path
price for a question (== col x) answers in 40 us with a single vectorised
scan. That also predicts the fix is a cheap early-out on the needle count
rather than anything structural.

I have no evidence this costs us anything — we do not have a hot one-element
in — so please weight it accordingly. It is a sharp edge for anyone who
writes in uniformly over a needle list that happens to be a singleton.

Housekeeping

I have retitled this issue to describe what remains, since the old headline
asserted the O(n·m) behaviour you have just shown is gone, and left the
original report body untouched below for the record. Request 3 I am not
duplicating here — #596 is the better home for it, and I agree with your call
to solve it once from that end.

[singaraiona]

Your reproducer found something bigger than the sharp edge you filed it as.
Fixed in #607.

It was not a missing small-needle early-out

Your prediction was "a cheap early-out on the needle count rather than anything
structural". Reasonable from the outside, and it is what I was about to build.
Before writing it I instrumented ray_in_fn to print which branch your case
actually takes:

INPROBE val_nulls=1(t=12) vec_nulls=1(t=12)     <- SYM
INPROBE needle_side_ok=0
INPROBE fell_through_to_hashset

versus the same shape on an i64 column:

INPROBE val_nulls=0(t=5) vec_nulls=0(t=5)
INPROBE typed_kernel=HIT

in has a typed kernel — and it carries a verdict-LUT written specifically
for SYM, one byte load per row regardless of set size. Your call never reached
it. The gate is:

if (!ray_vec_may_have_nulls(val) && !ray_vec_may_have_nulls(vec))

and that predicate is:

if (v->type == RAY_SYM || v->type == RAY_STR) return true;

Unconditionally true for text, because a SYM/STR null is a payload value (id 0 /
"") rather than an attribute bit, so attrs cannot prove the column null-free.
The condition was never satisfiable with a text operand. Every in over a
symbol or string column — not just one-element ones — fell through to the
generic per-row hashset probe. The SYM-specific kernel was dead code for the
only type it was written for.

vec.h draws the distinction correctly where it defines the pair:
may_have_nulls is "a row-kernel gate, not a reason to reject a text
optimization", and "paths requiring null-free data use has_nulls below". The
admission check was asking the wrong one.

What the fix does to your numbers

Asking the exact ray_vec_has_nulls instead. 351,393-row SYM column, 766
distinct, -c 2:

needles	before	after
1	4,820 us	200 us	24x
2	5,180 us	160 us	32x
10	8,320 us	160 us	52x
100	8,660 us	180 us	48x
766	8,440 us	180 us	47x
50,000	7,360 us	520 us	14x

So request 2 is fixed, but note the shape: the whole column moves, not just
the degenerate row. Your (in col 50000) at ~3 ms and your (in col ten) at
~3 ms were also paying for this — the flatness you correctly identified was
flatness of the wrong path. The remaining one-needle gap against (== col s)
is ~5x rather than your 67x, which is the ordinary cost of a general operator
over a specialised one and not worth chasing.

Your observation that the cost was independent of the right side is what made
this findable, so the framing in your comment was right even though the
predicted fix was not. Worth recording that I nearly built the early-out you
suggested; the instrumentation is what stopped me.

Null semantics

That gate existed for a real reason — the kernel treats a null as matching
nothing, while the fallback is null-equals-null — so the fix admits the kernel
only when both operands are exactly null-free. A null on either side still
falls through, including the asymmetric case where only the needles carry one.

All eight null shapes are byte-identical to the pre-fix binary. They are now
pinned in test/rfl/collection/in.rfl, which had no null coverage whatsoever —
which is how a text column being locked out of its own fast path went unnoticed.

ClickBench is unaffected: hot-time sum 5690.7 ms -> 5664.6 ms over 43 queries x
3, nothing beyond +4%.

Where that leaves this issue

• Request 1 (hash the right side): fixed earlier by Engine ask — a keyed lookup against a large vector rebuilds a hash on every call: let find / in with a vector of needles consult the attached hash index, admit STR to it, and keep it across concat #519.
• Request 2 (one-element right side): fixed by fix(in): admit the typed kernel for text columns, which it never reached #607, as a consequence of a
  larger fix rather than the early-out.
• Request 3 (compound membership): still open, tracked in A join that returns a row selection instead of a materialised table #596.

I will close this once #607 merges, since request 3 lives in #596 by your own
agreement. The title you rewrote is accurate for what #607 addresses.

One follow-up your report has flushed out: other admission sites gate on
may_have_nulls the same way and are probably the same bug — idxop.c:2158
keeps a sorted-index probe permanently off for text columns, for instance. Kept
out of #607 so each can be measured separately, but that is a thread worth
pulling, and it exists because the two predicates are one word apart at the call
site.

[singaraiona]

Correcting my own last comment. I said at the end that other admission sites
gate on may_have_nulls the same way and were "probably the same bug",
naming idxop.c:2158. That is wrong. I had grepped for the pattern and
inferred it, without reading the type guard immediately below:

if (!ray_attr_is_sorted(col) || ray_vec_may_have_nulls(col))
    return NULL;

bool col_is_float = (col->type == RAY_F32 || col->type == RAY_F64);
bool col_is_int   = col->type == RAY_BOOL || ... || RAY_TIMESTAMP;
if (!col_is_float && !col_is_int) return NULL;

ray_sorted_range_rowsel takes numeric and temporal columns only. Text can
never reach that path whatever the null predicate answers, so the always-true
result changes nothing there.

I checked the rest rather than leave the claim hanging, and every other reader of
that predicate is also correct:

• str_scalar_int (string.c) gates the same way, and its switch accepts no text
  type — text returns false through default.
• fills_vec_eager (collection.c) names RAY_SYM and RAY_STR explicitly in
  the same condition, returning text unchanged by design.
• The remainder read the predicate in the direction where an always-true answer
  is the safe one — propagating HAS_NULLS onto a result, or an early return that
  only skips work.

So in was a genuine one-off, not an instance of a systemic pattern, and there
is no thread to pull after all. The commit message and #607's description have
been amended; this is the third place the claim appeared, hence this note.

The substance of the fix is unaffected — the measurements and the null-semantics
diff stand as posted.

[vbmithr]

Part of the 67x I reported is not the hash path — it is that in runs on one
core while == runs on all of them. They separate cleanly by core count, so the
number in the title depends on the host's thread count.

Same 351,393-element SYM column as my reproducer above, 50 reps:

	-c 1	-c 4	-c 16	scaling
(sum (== col s))	100 us	20 us	20 us	5.0x
(sum (in col one))	2660 us	1920 us	1900 us	1.4x
(sum (in col many))	4180 us	3660 us	3660 us	1.14x

So:

-c 1     in/==  =  2660/100  =  26.6x     algorithmic only
-c 16    in/==  =  1900/20   =  95.0x     algorithmic + missing parallelism

The real size of request 2 is ~27x, not 67x — that is the part attributable
to building a one-entry hash instead of lowering to a vectorised equality scan.
The rest is == scaling to the pool while in stays serial, which scales with
the host and is why my 67x, your 92x and this 95x all differ: we were each
measuring on different thread counts.

That second half is not specific to in — like over a vector is serial too,
and the same predicate inside a select is not. I have filed it separately as
#608, since it is a different fix and affects both primitives.

Nothing here changes the ask on this issue. It sharpens it: request 2 is worth
about 27x on its own, and #608 is worth the remainder independently.