Description
IndexCursor::seek() (src/btree/index.rs:140-154) does not descend the b-tree at all. It calls first() to reach the leftmost leaf, then walks forward via next(), fully decode_record-ing each candidate, until it finds one >= target. This is O(n) cells scanned per seek.
Contrast with TableCursor::seek (src/btree.rs:290-396), which does real O(log n) binary search over cell pointers at each tree level — the class of fix that landed there previously (see 59c1e41) but was never applied to the index-cursor side.
Compounding: decode_leaf_entry/decode_interior_entry (src/btree/index.rs:346-394) eagerly call reassemble_payload (including chasing overflow chains) for every candidate visited during the scan, not just the eventually-matched row. TableCursor already defers payload reassembly to current_payload() (see #473) — IndexCursor does not.
This backs every indexed WHERE, unique-index point lookup, and the SeekIndexGE range-scan fast path added in #654 (src/vdbe/cursor.rs seek_index_eq/seek_index_ge, src/codegen/select/range_scan.rs). A nested-loop index join probing once per outer row turns an intended O(log n) probe into O(n) per probe — O(n·m) overall. Likely the single largest opcode/btree-level performance gap found in the current sweep.
Related but not overlapping: #659 fixed TableCursor::seek's per-call cost via inlining (varint/cell-decode functions weren't being folded by LTO) — that path was already an O(log n) binary search, just needed inlining. This ticket is about IndexCursor::seek not doing tree descent at all — an algorithmic gap, not an inlining gap. The #659 fix does not touch or subsume this.
Complexity
Estimate: medium
Reasoning: Requires porting TableCursor::seek's binary-search-over-cell-pointers logic to the index-cursor's tree shape (interior + leaf index pages have a different cell layout than table pages), plus reworking decode_leaf_entry/decode_interior_entry to defer payload reassembly until the matched row is known. Touches core btree traversal — needs careful test coverage (existing btree/index unit tests plus the EQP/opcode parity tests from #654) to avoid regressing correctness.
Context
Found via a bottom-up opcode/btree performance sweep comparing our VDBE/btree/pager stack against libsqlite3 (oracle), run alongside a top-down codegen-vs-EXPLAIN sweep. Cross-referenced against #659's profiling of the seek path and the #654 EQP-parity work.
Acceptance Criteria
Additional Notes
Consider adding a dedicated micro-benchmark or unit test with a deep/wide index (many leaves) to make regressions to this fix visible — the current bench fixtures may not have a large enough index to expose the O(n) cost clearly.
Description
IndexCursor::seek()(src/btree/index.rs:140-154) does not descend the b-tree at all. It callsfirst()to reach the leftmost leaf, then walks forward vianext(), fullydecode_record-ing each candidate, until it finds one>= target. This is O(n) cells scanned per seek.Contrast with
TableCursor::seek(src/btree.rs:290-396), which does real O(log n) binary search over cell pointers at each tree level — the class of fix that landed there previously (see 59c1e41) but was never applied to the index-cursor side.Compounding:
decode_leaf_entry/decode_interior_entry(src/btree/index.rs:346-394) eagerly callreassemble_payload(including chasing overflow chains) for every candidate visited during the scan, not just the eventually-matched row.TableCursoralready defers payload reassembly tocurrent_payload()(see #473) —IndexCursordoes not.This backs every indexed
WHERE, unique-index point lookup, and theSeekIndexGErange-scan fast path added in #654 (src/vdbe/cursor.rsseek_index_eq/seek_index_ge,src/codegen/select/range_scan.rs). A nested-loop index join probing once per outer row turns an intended O(log n) probe into O(n) per probe — O(n·m) overall. Likely the single largest opcode/btree-level performance gap found in the current sweep.Related but not overlapping: #659 fixed
TableCursor::seek's per-call cost via inlining (varint/cell-decode functions weren't being folded by LTO) — that path was already an O(log n) binary search, just needed inlining. This ticket is aboutIndexCursor::seeknot doing tree descent at all — an algorithmic gap, not an inlining gap. The #659 fix does not touch or subsume this.Complexity
Estimate: medium
Reasoning: Requires porting
TableCursor::seek's binary-search-over-cell-pointers logic to the index-cursor's tree shape (interior + leaf index pages have a different cell layout than table pages), plus reworkingdecode_leaf_entry/decode_interior_entryto defer payload reassembly until the matched row is known. Touches core btree traversal — needs careful test coverage (existing btree/index unit tests plus the EQP/opcode parity tests from #654) to avoid regressing correctness.Context
Found via a bottom-up opcode/btree performance sweep comparing our VDBE/btree/pager stack against libsqlite3 (oracle), run alongside a top-down codegen-vs-EXPLAIN sweep. Cross-referenced against #659's profiling of the seek path and the #654 EQP-parity work.
Acceptance Criteria
IndexCursor::seekperforms O(log n) binary search over index cell pointers per tree level, mirroringTableCursor::seek's approachreassemble_payload/overflow-chase) until the matched row is identifiedcargo bench --bench crud -- read_indexed_range(and any index-seek/join scenario) shows measurable improvement, ideally vs a large-index fixture where the O(n) vs O(log n) gap is visibleAdditional Notes
Consider adding a dedicated micro-benchmark or unit test with a deep/wide index (many leaves) to make regressions to this fix visible — the current bench fixtures may not have a large enough index to expose the O(n) cost clearly.