joaoh82 / rust_sqlite / 25012261331 / 1
69%
main: 69%

DEFAULT BRANCH: main
Ran
Files 29
Run time 1s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 68.673% (+0.5%) from 68.221%
25012261331.1

push

github

web-flow 
Phase 7c: bounded-heap top-k for ORDER BY <expr> LIMIT k (#46)

Recognizes the KNN-shaped query

  SELECT id FROM docs
  ORDER BY vec_distance_l2(embedding, [...])
  LIMIT 10;

and runs it through a `BinaryHeap<HeapEntry>` of size k instead of
full-sorting all matching rowids. O(N log k) instead of O(N log N).

The SELECT executor now branches in three cases on the
(order_by, limit) tuple:

  1. (Some, Some(k)) where k < |matching|  → bounded heap path
                                              (the new code)
  2. (Some, _)  → full sort + truncate (heap saves nothing when
                  we'd keep everyone anyway, e.g. k >= N)
  3. (None, Some(k)) → just truncate (no sort needed)
  4. (None, None) → no-op

**Implementation note: max-heap with direction-aware Ord.**

A single `HeapEntry { key: Value, rowid: i64, asc: bool }`
wrapper handles both `ORDER BY ASC LIMIT k` and `... DESC LIMIT k`
without forking into two code paths. The `asc` flag inverts the
natural Ord, so the displacement test reduces to "new entry < heap
top" in both cases:

  - ASC: max-heap, top is current largest kept; new smaller items
         displace.
  - DESC: Ord reversed, max-heap, top is current SMALLEST kept
         (under reversed Ord, smallest looks largest); new larger
         items displace.

After the scan, `into_sorted_vec()` returns the right caller-facing
order: ascending by raw key for ASC, descending for DESC.

**HeapEntry needs custom Eq.** Value is PartialEq-only because of
f64 NaN; BinaryHeap requires Ord which requires Eq. Defined a
manual Eq via "two entries are Equal if their direction-aware cmp
returns Equal". Fine for our purposes — the heap doesn't need a
total bit-equivalent equivalence relation, just one consistent
with Ord.

**Measured speedup** (N=10k, k=10, single REAL column sort key,
release build, Apple Silicon laptop):
  - bounded heap:   ~820µs
  - full sort+trunc: ~1.5ms
  - ratio:          ~1.8×

The advantage scales with N and per-row wo... (continued)

4483 of 6528 relevant lines covered (68.67%)

1.25 hits per line

Source Files on job 25012261331.1