Reading: filters, ranges, AND/OR, composite prefixes

WHERE syntax and precedence#

A condition is a tree of comparisons combined with AND / OR, with parentheses for grouping. Precedence: OR is lowest, then AND, then a comparison or a parenthesized group. Each comparison is field <op> value where op is one of = != < <= > >=.

SELECT * FROM users
WHERE age >= 18 AND (status = "open" OR status = "vip")
SORT age DESC LIMIT 100

Fields can be dotted nested paths (addr.city): the engine first looks for a flat field literally named addr.city, then splits on . and navigates through nested Map values.

Primary key: O(1) point lookup#

A filter that is EXACTLY _id = <integer> (and no join/search/traverse/nearest) is recognized as a point lookup and resolved through the in-memory _id → position hash map in O(1), never consulting a secondary index or scanning. This is the fastest read path.

SELECT * FROM users WHERE _id = 1

{ "error": null, "data": [ { "_id": 1, "name": "alice", "age": 30 } ], "root": { "count": 1 } }

Secondary index: equality and range#

A single-field equality/range index (Filter, Nested, or Composite) is stored as a BTreeMap from an order-preserving key to row positions. An equality (field = v) is a single bucket lookup; a range (<, <=, >, >=) is a BTreeMap range scan. Keys are numerically ordered across types, so age > 9 correctly returns 10, 20, 50, 99 (numeric, not lexical). != (Ne) is NOT index-served and falls back to a scan.

-- table t has a Filter index on `age`, rows: 5, 9, 10, 20, 50, 99
SELECT * FROM t WHERE age > 9
SELECT * FROM t WHERE age >= 9
SELECT * FROM t WHERE age < 10

// counts: WHERE age > 9 -> 4 (10,20,50,99); >= 9 -> 5; < 10 -> 2 (5,9)

AND / OR index coverage#

• AND: the engine first tries a composite leftmost-prefix over the whole AND (most selective). Otherwise it intersects the positions of the index-covered conjuncts. If only one side is indexed, its candidates are a sound superset and the residual filter re-checks the other side.
• OR: a union is only sound when BOTH branches are index-covered; if either would need a scan, the whole OR scans. When both are covered, the positions are unioned (then sorted and deduped).

SELECT * FROM t WHERE age = 5 OR age = 50

// count: 2  (union of the two equality buckets)

Composite index: leftmost-prefix#

A composite index over (a, b, ...) serves a query that constrains a leading run of its columns by equality. The planner picks the composite index with the LONGEST satisfiable leading prefix and does a prefix range scan over the sorted index. A query that constrains only a uses the prefix [a]; a query constraining a and b uses [a, b]. The prefix stops at the first unconstrained column (e.g. constraining only b does not use an (a, b) index).

-- table t has a Composite index on (a, b)
SELECT * FROM t WHERE a = 1            -- prefix [a]
SELECT * FROM t WHERE a = 1 AND b = 2  -- prefix [a, b]

// with rows {a:1,b:1},{a:1,b:2},{a:2,b:9}:  WHERE a=1 -> 2 rows ; WHERE a=1 AND b=2 -> 1 row

Array-contains and nested-path filters#

When a filtered field holds a List, the comparison is array-contains: the row matches if ANY element satisfies the comparison. A single-field index over a List column is multi-valued — the row is indexed under each element's key — so WHERE tags = "x" is index-served and means "the tags array contains x". Nested-path filters (WHERE addr.city = "NYC") work the same and can be indexed by declaring the index on the dotted path.

-- table p, Filter index on `tags`
-- rows: a tags [red,blue]; b tags [green]; c tags [blue,green]
SELECT * FROM p WHERE tags = "blue"
SELECT * FROM p WHERE tags = "green"
SELECT * FROM p WHERE tags = "red"

// counts: blue -> 2 (a,c) ; green -> 2 (b,c) ; red -> 1 (a)

SELECT name FROM u WHERE addr.city = "NYC"

{ "error": null, "data": [ { "name": "a" } ], "root": { "count": 1 } }

Residual filtering and the exact-single-eq optimization#

An index normally returns a SUPERSET of matching positions, so the engine re-applies the full filter as a residual eval_cond check on every candidate — this keeps AND/OR/range/composite-prefix correct. The one case where the recheck is provably redundant is a lone field = scalar covered by a single-field equality index: the bucket holds exactly the matching rows, so the residual is skipped. Range, AND/OR, and composite-prefix are all supersets and keep the residual.