optimization ideas to improve performance of 2+ hop graph traversals

[adsharma]

Immediate Improvements

1. Change Default Scan Mode to Sequential

The OnDiskGraphNbrScanState constructor defaults randomLookup to true, causing unordered scans (on_disk_graph.cpp:89-93). Changing this default to false would use scanCommittedInMemSequential by default, which processes rows in order (csr_node_group.cpp:277-304).

// In src/graph/on_disk_graph.cpp, line 91
// Change from: bool randomLookup) {
// To: bool randomLookup = false) {

2. Optimize CSR Index for Sequential Access

The CSR scan checks if row indices are sequential before choosing scan mode (csr_node_group.cpp:257-260). During CSR index construction in updateCSRIndex, ensure adjacency lists are stored contiguously when possible to increase the isSequential hit rate (csr_node_group.cpp:345-373).

3. Implement Chunk Group Prefetching

The random scan frequently switches between chunk groups, causing cache misses (csr_node_group.cpp:318-334). Add prefetching logic when chunkIdx != currentChunkIdx to reduce latency:

// In src/storage/table/csr_node_group.cpp, around line 323
if (chunkIdx != currentChunkIdx) {
    // Add: __builtin_prefetch(chunkedGroups.getGroup(lock, chunkIdx));
    currentChunkIdx = chunkIdx;
    chunkedGroup = chunkedGroups.getGroup(lock, chunkIdx);
}

Structural Improvements

4. Reorganize IceDisk Data Layout

IceDisk CSR scans filter rows by bound node offsets, causing non-sequential access (ice_disk_rel_table.cpp:264-358). Consider:

• Sorting edges by source node offset within Parquet files
• Creating node-local partitions to reduce cross-bound-node scanning
• Implementing zone maps to skip irrelevant row groups

5. Bound Node Reordering for Multi-level Traversals

For 2+ level traversals, reorder bound nodes between levels to maximize locality. The current implementation processes bound nodes sequentially (ice_disk_rel_table.cpp:295-308). Implement a reordering strategy that groups nodes by their physical storage location.

6. Adaptive Scan Mode Selection

Currently, the scan mode is determined at initialization (csr_node_group.cpp:61-84). Implement runtime adaptation:

• Monitor chunk group switch frequency during scans
• Dynamically switch between random and sequential modes based on observed locality patterns
• Use cost-based optimization for multi-hop queries

[SevorisDoe]

Dumping some of my related thoughts here from the poking at the underlying research papers that prompted this discussion:

The idea behind the precomputed CSR indices is to make the overall computation of the database more efficient then resolving the joins add-hoc. In particular, the original paper for the S-Join algorithm that lead to the ASP-join algorithm implemented in Kuzu, cites the notion of using the CSR to be able to build sideways information passes into the second node table scan involved in an edge expansion. See https://dl.acm.org/doi/10.14778/3510397.3510400 and then https://dl.acm.org/doi/10.1145/3631504.3631514.

However, what becomes noticeable when you look at the overall notion - we have a left side of nodes we have scanned. We're now scanning the CSR for those nodes. Those nodes may be in order, but once a first join has ocured, they definitely won't be. Even assuming we joined with an ordered CSR list (and Ladybug appears to just append new adjacencies to the end of a given node's offset range and then adjust offsets within the row group) we'd now have mixes of small-to-large node IDs. So on the next CSR lookup, we end up with looking up in the CSR for a small node row ID, then for a large node row ID, then for a smaller again - bouncing all over the offset array of the CSR. Potentially, we'll loose parts of the CSR to database cache eviction as different blocks are required. We're also only making so efficient use of our CPU cache.

That raises the question if directly resolving from left side row IDs to file offsets is worth it for an OLAP (instead of an OLTP) workload. Other system designs generally attempt to streamline and make continuous the file scans as much as possible. The current design seems to defy this, potentially with adverse consequences.

Looking at the above analysis then:

Probably the best-ish option to check for a first optimization is to sort the results of an extension by the node rowIDs. That ensures the next CSR scan will proceed optimally against disk. Or at least - that can be benchmarked easily. There's probably a pay-off if you have intermediate-sized nodes set.

• potentially interesting aspect - an absolutely perfect sort may not be needed. So long as we avoid both block misses and especially cache misses most of the time, we're okay? Having strong ordering per cache size (vector of 2048 records) and strong-enough ordering between vectors could be okay.

Alternatively, it may be worth it to conduct a hash build on the left node side and probe the relationship table's left side row IDs against it (or the inverse, building from the rel table and probing the node table, if there are only very few edges of this type originating from the left node type). This involves random access in the hash join itself, but avoids any random access on the disk table, and may be cheaper then the sorting costs before scanning the CSR. The disk table layout itself would still be ordered on left side row ID first, then either ordered or unordered on the right side row ID - and so this layout could still be used for SIP on the scan of the right-side node table with the same assumptions as the existing extension.
-> on second glance, this may be a situational optimization, depending on how the left node table measures up against the relation in size.