Repository navigation
Track CSR storage and traversal improvements #80
Description
Goal
lance-csr rebuilds its CSR in memory on every engine start. (A hop that names its relationship variable used to fall back to joins too; #87 keeps it on the CSR, using the edge row addresses from #73.) On-disk CSR engines such as LadybugDB open without a build and keep edge properties next to the topology. This issue tracks the work to close that gap where it matters for lance-csr, with Lance staying the source of truth and the CSR staying a derived index on a single machine.
Most of these ideas come from lance-graph's CSR roadmap (lance-format/lance-graph#159) and the review of its native expand PR (lance-format/lance-graph#162).
Sub-issues
- Persist the CSR so engines skip the build at start-up #72: persist the CSR so engines skip the build at start-up (the staged plan)
- Store an edge row address in each CSR slot #73: store an edge row address in each CSR slot (relationship properties, edge identity, cross-hop edge predicates). Done in feat(csr)!: keep named relationships on the csr with edge rows #87.
- Look up CSR neighbours with async, batched calls #74: async, batched neighbour lookups (only needed for partial or disk-backed loading)
- Report CSR freshness in Lance index terms and add an optimize step #75: report CSR freshness in Lance index terms and add an optimize step. Done: reporting in feat(csr): report how far the base csr trails the data #93, the optimize step in feat(csr): fold the delta into a new base with optimize_csr() #98.
- Run shortestPath from many sources with multi-source BFS #76: multi-source BFS for
shortestPathfrom many sources - Evaluate icebug-format as the persisted CSR layout #77: evaluate icebug-format as the persisted CSR layout. Decided against: it stores dense node positions, which would break the raw-key layout Persist the CSR so engines skip the build at start-up #72 relies on (see its closing comment).
- Expand multi-hop patterns without materializing every intermediate row #78: factorized expansion for multi-hop patterns. A first narrow step landed in perf(planner): count two-hop paths from per-node degrees #97, which counts two-hop paths from node degrees (Count two-hop paths from per-node degrees instead of enumerating them #96).
- Store CSR neighbours in fewer bytes #79: store CSR neighbours in fewer bytes
Related, not a sub-issue: #92, IC5's memory-mode slowdown since #87 moved named hops onto the CSR.
Each sub-issue describes the problem and the idea only; designs come later, and anything claimed as faster is measured against main on both benchmark suites first.
Activity