Skip to content

Shrink the CSR's per-node map and neighbours #79

Open

Description

@prrao87

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 u64 raw target keys.
  • Per source node: about 37 bytes, for its offset and its entry in Adjacency's FastMap<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

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 u32 offset from min_key when max_key - min_key fits in 32 bits, and keep u64 otherwise. This doesn't help SF1, and CsrIndex::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 main on both suites in both memory and lazy modes, following CONTRIBUTING.md, with resident memory reported next to latency.

Activity

  1. changed the title [-]Store CSR neighbours in fewer bytes[/-] [+]Shrink the CSR's per-node map and neighbours[/+] on Nov 3, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions