BTree scalar index on id for business index tables #477

Activity

1. gloryfromca

   added

   enhancementNew feature or requestNew feature or request

   on Oct 9, 2026
2. gloryfromca

   added 2 commits that reference this issue on Oct 10, 2026

   docs: state the row key and the one-time Milvus rebuild

   ...

   b4987af

   fix(index): key rows on (app_id, project_id, id) (#481)

   ...

   1805535
3. gloryfromca commented on Oct 15, 2026

   

   gloryfromca

   on Oct 15, 2026

   Last edited by gloryfromca

   MemberAuthor

   More actions

   Ran the two prerequisites this issue names. Numbers below, lancedb 0.34.0 (same
   version as the measurement in the description), macOS/APFS, scripts are plain
   lancedb + pyarrow and reproduce in a few seconds.

   1. The index itself is free

   An episode-shaped table — string id, the (app_id, project_id) scope columns,
   md_path, entry_id, content, and a 1024-dim vector — at 100k rows is 400 MB on
   disk. Adding BTrees:

   index	added	share of table
   BTree on id (unique, ~50-char strings)	2.82 MB	0.7%
   BTree on md_path (low cardinality)	0.50 MB	0.1%

   Build time is 0.03 s at 100k rows. Fragment count does not move either number
   (measured at 10 and at 100 fragments). The vector column dominates so completely
   that the scalar index is noise.

   So the "4x on keyed lookups" is not being bought with disk.

   2. Index-directory growth is the real cost, and it is not free

   Every optimize() that re-indexes mints a new _indices/<uuid>/ and leaves
   the previous one in place. Measured on a 2-column table, writing 5k rows per
   round and calling optimize() every other round:

   after initial build        1 index dir
   7 write rounds, 3 optimizes 6 index dirs
   3 explicit index rebuilds   9 index dirs
   index_stats(id_idx)         num_indices: 1   (throughout)
   

   This matters because of what those directories currently contain. The husks the
   sweep in core/persistence/lancedb/repository.py reclaims today are empty —
   one inode and (on ext4) one 4KB block each. At the 60s optimize cooldown that
   v1.4.2 shipped, _HUSK_MIN_AGE_SECONDS puts the ceiling-load steady state at
   ~300k dirs / ~1.2 GB.

   A scalar index turns each new version directory into real bytes:

   table rows	id index per dir	md_path index per dir
   10k	272 KB	69 KB
   100k	2.6 MB	263 KB
   500k	12.3 MB	1.2 MB

   And these are not reclaimed by _remove_empty_index_dirs — it only calls
   rmdir, which the kernel refuses on a non-empty directory. They wait out
   lance's 7-day unverified window, exactly as optimize_prune_retention_seconds
   documents.

   Conclusion for this issue: steady-state footprint = (optimize cadence that
   re-indexes) x (number of scalar indexes) x (per-dir size above) x (retention
   horizon). The per-unit cost is now known; the cadence multiplier still needs a
   soak at a realistic write rate before this ships. That is the prerequisite in
   the description, and it is the one that can actually hurt — not the 3 MB.

   A side note on that GB figure, since it comes up when sizing this: it is an
   ext4 number. On APFS, 100,000 empty directories measure 0 KB under du —
   directory entries live in the filesystem's B-tree, not in allocated blocks. The
   cost there is inodes only (100k dirs = 99,964 inodes; the ~300k steady state
   would be 0.11% of free inodes on this machine). ext4 remains the case to size
   for.

   3. Two scope questions

   id is no longer the merge key. This issue was filed 2026-10-09; #481
   (1805535, merged 2026-10-12) re-keyed rows on (app_id, project_id, id), so
   merge_insert now matches on the composite. A BTree on bare id is no longer
   what that path needs — worth deciding explicitly whether this is a composite
   index or only serves point lookups.

   md_path may deserve to be in scope. The hot lookup in the daily-log
   handler chassis is find_where(eq("md_path", md_path))
   (memory/cascade/handlers/_daily_log_base.py:115), one per file per cascade
   batch, and it is a flat scan today. That is the scan #492 is bounding
   concurrency around. Indexing id alone leaves it untouched, and the wiring work
   is identical for both columns.

   Milvus. infra/persistence/milvus/_create_collection adds AUTOINDEX for
   vector fields and BM25 for sparse fields, and nothing else — so whatever is
   decided for md_path here has a counterpart there. (The primary key is handled
   by Milvus itself; I have not verified whether that covers __pk filters.)