in on an indexed attribute scans the whole index (one setImmediate per entry) instead of seeking each value #3240

Problem

A search condition { attribute: X, comparator: 'in', value: [...] } on an indexed attribute does not look up the listed values in X's index. It reads every entry in that index and tests each key against the value set. On the async path, the test for each entry also waits on its own setImmediate. Search cost therefore grows with the size of the index, not with the number of matches, and wall time is several times CPU time.

resources/search.ts, searchByIndex:

case 'in':
	// Phase 1: route through filter — index-merge optimization is a Phase 2 follow-up.
	...
	start = true;
	needFullScan = true;

needFullScan sends an indexed attribute to index.getRange({ start: true, ... }).map(...). That is a scan of the whole index, with one new Promise(r => setImmediate(...)) per entry. This has been the case since in was added in f3e1db0, and it ships in 5.3.x and on main.

Nothing reports it. The query returns correct results, allowFullScan: false does not reject it, and an application author has every reason to believe an in on an @indexed attribute is an index lookup.

Measured

Unit-level repro on main (5ed056a), rocksdb. A 5,000-row table with two @indexed array attributes, each row holding one value or '*'. The query is tierKeys in [gold, *] AND categoryKeys in [c1, c2, c3, *], which matches 2,172 / 1,426 / 599 rows for tier only / categories only / both. Mean of 40 searches after warm-up:

The in form is about 26× slower in wall time and about 5× in CPU. Its cost is flat across conditions because every variant reads the whole index. Inside a single in search, rows arrive in bursts with 5–14 ms gaps and a ~30 ms tail after the last row: the per-entry setImmediate yields.

This was found in an application benchmark (a cart-quote endpoint probing a 5,000-row promotions table on every request). The in probe was a large share of the quote's 19 ms data phase. A Postgres GIN bitmap scan answered the same predicate in 0.75 ms.

Fix

1. in on an indexed attribute → one point range per value. Use the same plan as an or group of equals conditions: union the per-value ranges and dedupe with distinctRecords for multi-valued attributes, which the or path already handles. Do this either by rewriting the condition in prepareConditions or by teaching searchByIndex to iterate the value list. The estimate should be the sum of the per-value estimates, so the planner orders it correctly against other conditions.
2. Intersect the second indexed AND term when it is an in / or group. The adaptive switch in filterByType's attributeComparator, which replaces record filtering with an id set after enough misses, applies only to a leaf condition. With both terms written as or groups, the AND above loads 1,426 records to return 599. The candidate-key intersection already used for filtered vector search (collectCandidateKeys, Answer a filtered vector search's indexed conditions from the index, instead of decoding a record at every visited node #2691) intersects on primary key before any record is loaded, and could plan plain AND searches whose terms are all index-answerable.

Part 1 is the large win and is small. Part 2 removes the remaining record loads for non-matching rows.

Until part 1 lands, applications can write { operator: 'or', conditions: values.map(value => ({ attribute, value })) } instead of in.

Acceptance

• An in condition on an indexed attribute reads only the index entries for its listed values. A unit test asserts the number of index entries read, not only the results.
• An AND of two index-answerable conditions loads only records in their intersection.
• A multi-valued attribute with several listed values on one record returns that record once.

🤖 Generated with Claude Code