feat: CSR adjacency index for native graph traversal (inspired by DuckPGQ + icebug-format)

@aheev

The problem

Today lance-graph translates every Cypher query into SQL joins through DataFusion. A simple (a)-[:KNOWS]->(b)-[:LIKES]->(c) becomes a chain of self-joins that scales as O(N^k) for k hops. The LanceNativePlanner exists as a placeholder but doesn't do anything yet.

We need a CSR (Compressed Sparse Row) adjacency index so that graph traversals can do direct neighbor lookups instead of join scans.

Prior art and what we learned

We looked at three approaches and landed on a direction that combines ideas from DuckPGQ and icebug-format.

GraphAr (Apache incubator)

GraphAr showed that you can encode CSR offset tables directly in Parquet files, giving you adjacency-list access without SQL joins. The spec says: "the sorted adjList table together with the offset table can be used as CSR, supporting fast access of outgoing edges for a given vertex."

However, GraphAr is fundamentally a data interchange format -- it's designed for archiving and bulk loading into graph databases, not for online querying. It uses a deeply nested directory structure with YAML manifests, which adds overhead when you want to mount and query immediately.

icebug-format (Ladybug-Memory)

icebug-format takes a different stance that's closer to what we want. Key design choices:

Cypher schema as catalog instead of YAML/JSON config -- a schema.cypher file like CREATE NODE TABLE nodes(id INT64, club STRING, PRIMARY KEY(id)); CREATE REL TABLE edges(FROM nodes TO nodes); that a graph database can mount directly
Flat file layout -- three Parquet files per edge type (nodes_<name>.parquet, indices_<name>.parquet, indptr_<name>.parquet) instead of GraphAr's nested directories
Two flavors: icebug-disk (Parquet on object storage) and icebug-memory (Arrow tables, zero-copy)
DuckDB-native CSR construction -- builds the CSR using DuckDB SQL, no custom binary tooling
Designed like native tables in a graph database -- less generality than GraphAr, but you can mount it and query instantly

The philosophy is similar to DuckLake: keep metadata in the system catalog of the database, not in sidecar config files.

DuckPGQ (CIDR 2023, peer-reviewed)

DuckPGQ validated that the relational engine + CSR acceleration pattern works well in practice:

Rewrites SQL/PGQ graph patterns into standard SQL joins (same as what we do with DataFusion)
Adds vectorized CSR-based UDFs for path-finding (Multi-Source BFS with SIMD/AVX-512)
Creates CSR on-the-fly from relational tables using ROWIDs -- no separate graph storage engine
On LDBC LSQB benchmarks (SF10-SF100): within an order of magnitude of Umbra, consistently outperforms Neo4j (which fails 4 queries on SF100)
BFS scales to SF3000 (9M vertices, 670M edges), while Umbra's recursive SQL OOMs on SF10

The key takeaway: you don't need a separate graph database. A relational engine with CSR acceleration handles both pattern matching (via joins) and path-finding (via native BFS on CSR).

SQL/PGQ expressiveness limits

Our research also surfaced where SQL/PGQ breaks down, which tells us what the native CSR engine must handle:

Pattern type	SQL/PGQ?	Native CSR needed?
Fixed-length (2-3 hops)	Standard joins	No
Unbounded (Kleene `*`, `+`)	Recursive SQL or BFS	Yes -- recursive CTEs OOM on large graphs
Cross-iteration edge properties (e.g. increasing timestamps along paths)	Fundamentally inexpressible	Yes -- only native traversal can do this

Direction

We think the right approach for lance-graph combines ideas from DuckPGQ and icebug-format, with one important revision based on discussion in this thread: the CSR adjacency structure should be a native Lance index kind, not a sidecar file that lance-graph maintains on the side.

The original sketch (CSR stored as separate Lance datasets in a flat layout) has the consistency and ownership problems @aheev raised: who keeps the adjacency in sync with edge writes, who owns the dataset, and what happens under concurrent access. Making CSR a first-class Lance index removes all of that -- index maintenance rides on Lance's own commit + index-update path, tied to a dataset version, the same way scalar/vector/FTS indices work today. lance-graph doesn't need exclusive access; Lance owns the index lifecycle and lance-graph just reads it.

CSR/adjacency as a native Lance secondary index -- a new index kind over an edge dataset's (src, dst) columns, built and updated through Lance's existing index infrastructure (versioned, transactional, lazily loaded at query time)
Native traversal operators in LanceNativePlanner that use CSR for Expand and VariableLengthExpand instead of SQL joins
Cypher-native schema rather than YAML/JSON config (we already parse Cypher, so this is natural)
In-memory CSR from Arrow tables for the zero-ETL case (same idea as icebug-memory), sharing the same neighbor-lookup API as the persistent index

Storage model

Edges stay a normal Lance dataset (knows.lance) with whatever properties the user defines -- no required row ordering. The adjacency lives as a secondary index on that dataset:

Offset table -- {vertex_id, offset, degree}, one entry per vertex plus a sentinel
Neighbor list -- {dst_id} ordered by source vertex

For vertex v, its neighbors are neighbors[offsets[v]..offsets[v+1]]. Direction is a build-time property of the index, not the table: outgoing (CSR) keys on src, incoming (CSC) is the same construction with the columns swapped (key on dst). The two directions are independent index instances -- the reverse adjacency is materialized by re-sorting on the destination column, since reverse edges are not contiguous in the forward layout.

At query time the index is range-loaded: for a set of source vertices we read only their offset entries and the corresponding neighbor slices via take()/range scans, not the whole adjacency.

Why a native index over a sidecar

Atomic, versioned maintenance -- adjacency updates commit with edge inserts through Lance's index path; no drift, no separate exclusive owner
Lazy, partial loading -- only touched vertices' adjacency ranges are read, same as other Lance indices
Random access via take() -- O(1) row lookup by ID during traversal
Vector search integration -- combine graph traversal with ANN search ("find 2-hop neighbors whose embeddings are similar to X")

Implementation plan

Phase 1 -- CSR index builder ✅ (done -- #160)

In-memory CsrIndex (offset/indptr array + neighbor array)
Neighbor lookup + out-degree
BFS
Shortest path
Arrow serialization (offset table + neighbor list)
Builder sorts edges by source internally (no input ordering required)

Phase 2 -- Native single-hop expand

Wire in-memory CSR into LanceNativePlanner for single-hop Expand
Outgoing (CSR) direction
Incoming (CSC) direction via reversed-column build
DataFusion fallback for undirected expands
End-to-end parity tests vs. the join planner

Phase 3 -- Multi-hop and algorithms

Iterative CSR traversal for fixed-length multi-hop
VariableLengthExpand (Kleene * / +)
BFS operator
DFS operator
Shortest path operator
Cross-iteration edge-property predicates (e.g. increasing timestamps along a path)

Phase 4 -- Native Lance adjacency index (replaces the original sidecar-persistence plan)

Phase 5 -- Hybrid queries

Combine CSR traversal with vector (ANN) search
Combine CSR traversal with property filters
Example: "find 2-hop neighbors whose embeddings are similar to X"

References

GraphAr: An Open Source Library for Graph Data Storage and Retrieval (Apache incubator)
icebug-format: A proposal for graph standardization (Ladybug-Memory)
Graph Archiving with Apache GraphAr (blog post comparing GraphAr vs icebug)
DuckPGQ: Efficient Property Graph Queries in an Analytical RDBMS (CIDR 2023)
BACH: A Unified Graph Store Supporting Efficient Online Analytical Processing (PVLDB 2025)
SQL/PGQ: Property Graph Queries in SQL (SIGMOD 2022)
GQL Formal Semantics (VLDB 2025)
SQL/PGQ vs SQL Performance Analysis (2025)
TigerGraph: A Native MPP Graph Database
PostgreSQL 19 SQL/PGQ Docs

@beinan

Really great summary of the roadmap and an awesome literature summary too. Looks good as a starting point, curious what @beinan thinks!

Graph-ar is a data interchange format. Not sure if it's suitable for online querying.

https://github.com/Ladybug-Memory/icebug-format is similar and optimized for online querying. It's similar to DuckLake. Uses cypher metadata as catalog instead of yaml/json. Less generality and designed similar to native tables in a graph database.

feat: CSR adjacency index for native graph traversal (#160)

Re-open for tracking following phases

Makes sense - I've switched it to a checklist (item 1 is marked off). Looking forward to the future phases of this!

@jja725

@jja725 Couple of things to clarify

Assuming write access, how do you plan to update index? AFAIK lance doesn't support pluggable secondary indices. Also, does lance-graph have the exclusive access to the datasets?
I believe CSR index is loaded into memory progressively(during query time) similar to how lance indices work
edge properties, sorted by src_id (Lance dataset) how do you enforce this in user-provided tables?
Can you explain a bit about the structure of edges and CSR index files?
- lance datasets inherently doesn't have a direction. So, what does outgoing and incoming mean?
- How does knows_incoming look like? reverse_edges need not be sequential

@jja725 Couple of things to clarify

* Assuming write access, how do you plan to update index? AFAIK lance doesn't support pluggable secondary indices. Also, does lance-graph have the exclusive access to the datasets?

....

Wouldn't this be worth opening an discussion directly on lance https://github.com/lance-format/lance/discussions
to get some ideas on current best practise or to find that these kind of usecases may need an addition to lance?

@aheev

@aheev @hpvd Thanks for the discussion and great questions. The short answer would be: the right home for
the CSR adjacency structure is a native Lance index type, not a separate file that lance-graph maintains on the side. Lance already has secondary-index infrastructure (vector, scalar/btree, FTS) with versioned, transaction-scoped index maintenance. A CSR/adjacency index would be a new index kind plugged into that same machinery. With that framing, most of these answer themselves

Just FYI, we're actively looking into providing pluggable infrastructure for users to add new index types to Lance without requiring changes to the format spec. Once that's in place, these kinds of custom secondary indexes can be plugged in and added by the community even more easily (not that it's super hard even now, it just needs to pass through the vote to get into the format)

Just FYI, we're actively looking into providing pluggable infrastructure for users to add new index types to Lance without requiring changes to the format spec. Once that's in place, these kinds of custom secondary indexes can be plugged in and added by the community even more easily (not that it's super hard even now, it just needs to pass through the vote to get into the format)

Lovely!! Great to hear

@jja725

Hi @jja725 and @beinan,

I studied the current CsrIndex implementation in more detail and it looks like a great start. However, I think it's worth nailing down on the desired end-user experience on the Python end now, because the CSR Rust code is only the primitive for many users. Based on my past experience working with Kuzu, Neo4j and Ladybug, the big UX win for lance-graph users would be a smooth way to update the CSR index without needing to understand its internals. The scenario at play is when there already exists a sizeably large Lance table (with an existing CSR index), and new rows are inserted at a later time.

The Python user would simply declare the graph semantics upfront using with_relationship(...) as they do currently, append data to the underlying Lance table, inspect traversal freshness, and like other secondary indexes, simply apply optimize_indices to obtain the freshest relationship traversal access paths without even knowing about the CSR internals - is my understanding correct?

From the current Python API, users already define graph semantics through GraphConfig:

config = (
    GraphConfig.builder()
    .with_node_label("Person", "person_id")
    .with_relationship("KNOWS", "src_id", "dst_id")
    .build()
)

Users think in terms of a relationship Lance table / relationship mapping (KNOWS, src_id, dst_id), not directly in terms of CSR/CSC.

Since Lance is fragment/version oriented rather than node-group oriented like Kuzu, I'm just listing my understanding of how Lance would work under the hood via this mental model:

relationship Lance table remains the source of truth
with_relationship("KNOWS", source_field, target_field) declares graph semantics over that table
an optional traversal/access-path setting marks that relationship as traversal-ready
adjacency/CSR/CSC is the Lance secondary-index implementation over (src, dst), not the primary user concept
each index instance tracks the table version / indexed fragments it covers
new edge fragments can be indexed incrementally as adjacency delta segments
optimize() / optimize_indices() can later merge or compact those delta segments
by default, queries should follow Lance's existing secondary-index freshness contract: use the index for indexed fragments plus scan/traverse unindexed fragments as a delta for exact results
an explicit fast/indexed-only mode could skip unindexed edge fragments when stale-but-fast traversal is acceptable

This would make the UX something like:

config = (
    GraphConfig.builder()
    .with_node_label("Person", "person_id")
    .with_relationship("KNOWS", "src_id", "dst_id")
    # Future extension: relationship-level traversal options, not raw CSR plumbing.
    # .with_relationship_traversal_index("KNOWS", directions=["outgoing", "incoming"])
    # or .with_relationship("KNOWS", "src_id", "dst_id", traversal="indexed")
    .build()
)

# Existing Lance/LanceDB workflow, not lance-graph specific:
edges.add(new_edges)

# Provide stats to the user to know what version of the index they work with
engine.relationship_stats("KNOWS")
# indexed_version, current_version, num_unindexed_edges/fragments,
# outgoing/incoming freshness

# Update CSRs on the lance-graph engine to account for newly added relationships in the index
engine.optimize_relationships("KNOWS")

At all stages, we're clear that goal isn't "be a graph database" -> the win from a user's perspective is is always that ETL out from Lance and into a dedicated graph DB is expensive, so lance-graph would be a viable alternative to graph DBs that provides a convenient, usable and fast interface for people to run graph traversals over their Lance tables. Multi-hop query performance is unlikely to be as good as dedicated graph systems, but the tradeoff from a user perspective is that keeping large amounts of data in one place (single copy) is a bigger win than having the fastest graph engine out there (though performance is likely to become significantly better over time as we push down more and more operations to be Lance-native).

I hope my larger understanding is correct, based on the roadmap above! Curious to hear your comments as this design is fleshed out.

nice feature!

@prrao87

At all stages, we're clear that goal isn't "be a graph database" -> the win from a user's perspective is is always that ETL out from Lance and into a dedicated graph DB is expensive, so lance-graph would be a viable alternative to graph DBs that provides a convenient, usable and fast interface for people to run graph traversals over their Lance tables. Multi-hop query performance is unlikely to be as good as dedicated graph systems, but the tradeoff from a user perspective is that keeping large amounts of data in one place (single copy) is a bigger win than having the fastest graph engine out there (though performance is likely to become significantly better over time as we push down more and more operations to be Lance-native).

yeah sure not directly a native graph database...
But regarding performance one might expect to be more than pretty good in lots of case ;-)

This looks to be a good place to link once again the benchmarks for the current state of lance graph @prrao87 already has worked on:

Graph benchmarks for Kuzu, Ladybug and lance-graph

Basic:
https://github.com/prrao87/graph-benchmark#high-level-results

on LDBC SNB dataset :
https://github.com/prrao87/graph-benchmark-ldbc#high-level-results

@hpvd

Yeah my plan is to keep those benchmarks up to date with upcoming releases of lance-graph as we add more of these performance features in due course. I'll be closely following along as you have been, @hpvd :)

Note

Ladybug has deviated from (and has been significantly improved over) Kuzu thanks to a lot of consistent effort by @adsharma, so going forward, Ladybug is the new de facto standard "columnar, embedded graph db with native CSR traversals" as far as I'm concerned - and it only makes sense to benchmark lance-graph's performance against Ladybug and Neo4j's community edition as they cover the two ends of the spectrum.

Yeah my plan is to keep those benchmarks up to date with upcoming releases of lance-graph as we add more of these performance features in due course. I'll be closely following along as you have been, @hpvd :)

was hoping for this!
It's always a great motivation to see progress and comparison to other projects this clear and it also works as the perfect quality control for meeting the goals (and of course also to spot any kind of performance regressions..)

Since everybody is sharing his/her deep insides here, I just added something imho pretty interesting/helpful I stumbled across
(as issue, sorry there is no discussion functionality in this repo):
Overview: Index Types for Graph-DBs /-usage for speed
#164

Just FYI, we're actively looking into providing pluggable infrastructure for users to add new index types to Lance without requiring changes to the format spec. Once that's in place, these kinds of custom secondary indexes can be plugged in and added by the community even more easily (not that it's super hard even now, it just needs to pass through the vote to get into the format)

is there already an issue / discussion in lance format, or should be add one?

Navigation Menu

Repository navigation

feat: CSR adjacency index for native graph traversal (inspired by DuckPGQ + icebug-format) #159

The problem

Prior art and what we learned

GraphAr (Apache incubator)

icebug-format (Ladybug-Memory)

DuckPGQ (CIDR 2023, peer-reviewed)

SQL/PGQ expressiveness limits

Direction

Storage model

Why a native index over a sidecar

Implementation plan

Phase 1 -- CSR index builder ✅ (done -- #160)

Phase 2 -- Native single-hop expand

Phase 3 -- Multi-hop and algorithms

Phase 4 -- Native Lance adjacency index (replaces the original sidecar-persistence plan)

Phase 5 -- Hybrid queries

References

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

feat: CSR adjacency index for native graph traversal (inspired by DuckPGQ + icebug-format) #159

Description

The problem

Prior art and what we learned

GraphAr (Apache incubator)

icebug-format (Ladybug-Memory)

DuckPGQ (CIDR 2023, peer-reviewed)

SQL/PGQ expressiveness limits

Direction

Storage model

Why a native index over a sidecar

Implementation plan

Phase 1 -- CSR index builder ✅ (done -- #160)

Phase 2 -- Native single-hop expand

Phase 3 -- Multi-hop and algorithms

Phase 4 -- Native Lance adjacency index (replaces the original sidecar-persistence plan)

Phase 5 -- Hybrid queries

References

Activity

prrao87 commented on Jun 17, 2026

adsharma commented on Jun 17, 2026

jja725 commented on Jun 22, 2026

prrao87 commented on Jun 22, 2026

aheev commented on Jun 23, 2026

hpvd commented on Jun 23, 2026

jja725 commented on Jun 23, 2026

prrao87 commented on Jun 26, 2026

aheev commented on Jun 27, 2026

prrao87 commented on Jun 27, 2026

ted-wq-x commented on Jun 29, 2026

hpvd commented on Jun 29, 2026

prrao87 commented on Jun 29, 2026

hpvd commented on Jun 29, 2026

hpvd commented on Jun 29, 2026

hpvd commented on Sep 1, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions