Repository navigation
Open
Labels
enhancementNew feature or requestNew feature or request
Description
Problem
The CSR lives in memory even when tables are read lazily from Lance. On GDC SF1, its 17.3M edges take 732 MiB for both directions.
#109 packed the edge rows from 8 bytes to about 2 per edge per direction, which brought SF1 down from 926 MiB, at almost no query cost. What's left, per direction (from docs/csr.md):
- Neighbours: 8 bytes per edge, plain
u64raw target keys. - Per source node: about 37 bytes, for its offset and its entry in
Adjacency'sFastMap<i64, u64>from key to CSR position.
Worked out from those figures, not measured: at SF1 the edges account for about 330 MiB and the per-node part for about 400 MiB. If so, the map from key to position, not the neighbours, is now the largest piece.
Already tried
- Packing neighbours like the edge rows roughly halved them. But every hop reads neighbours, and lookup-heavy queries slowed down: custom Q30 by about 22% (feat(csr)!: store the csr inside each lance dataset and pack edge rows #109). They stay
u64. - A
min_keyplusu32offset doesn't fit SF1, whose node keys span up to 2^45. It would only help graphs with a compact key range.
Any decoding on the neighbour path costs every hop, so delta-encoding neighbours is unlikely to pay off either.
Ideas
- The map from key to position. Replace
FastMap<i64, u64>with something denser, such as a sorted key array searched by binary search (a stored CSR already holds keys in position order). That trades memory for slower lookups at the start of a hop, so it needs measuring on hop-heavy queries. - Narrower neighbours where the key range allows it. At build time, choose a
u32offset frommin_keywhenmax_key - min_keyfits in 32 bits, and keepu64otherwise. This doesn't help SF1, andCsrIndex::neighbors()returns&[u64], so it changes a public signature.
Before starting
- Measure the real split between the key-to-position map, offsets, neighbours and edge rows at SF1. The numbers above are worked out from type sizes and the documented totals.
- Benchmark against
mainon both suites in bothmemoryandlazymodes, followingCONTRIBUTING.md, with resident memory reported next to latency.
Metadata
Metadata
Assignees
Labels
enhancementNew feature or requestNew feature or request
Activity
[-]Store CSR neighbours in fewer bytes[/-][+]Shrink the CSR's per-node map and neighbours[/+]