Icebug format design discussion

[adsharma]

A few topics to discuss:

• Which of these API styles should we go with:

createGraph(nodes, edges, directed)

vs

createGraph(nodes, fwd_indices, fwd_indptr, bwd_indices, bwd_indptr)

• Metadata, versioning

Metadata and versioning needed for on-disk data structures for sure. Not clear for in-memory arrow based variants

• Naming

Parquet and Arrow are well known in the industry. We tried to call this graph-std and quickly came to the conclusion that it was a bad choice (people can't google it). Icebug-format was chosen since it's unique enough, associated with the sister project icebug and logical (ice = frozen = immutable).

However, icebug-disk (icedisk) or icebug-mem (icemem) are generally not well known. People don't recognize them and hard to lookup. This could change if the ideas are widely implemented in the industry. Too early to tell.

• Code reuse

We have (in-memory vs persistent) * (flat tuples vs CSR) * (node vs rel tables) = 8 different combinations of very similar code. How do we manage this complexity balancing code reuse vs avoiding complex control flow.

More discussion in #496 (+1650 lines of code)

[adsharma]

This works for python users, but C++ arrow API users will have to compute bwd from fwd using a loop. It's still possible to do it with minimal copy.

from scipy.sparse import csr_matrix

# Build CSR from your indptr/indices
A = csr_matrix((data, indices, indptr), shape=(num_src, num_dst))

# Transpose — returns a CSC, which is the CSR of the reverse graph
A_T = A.T  # or A.transpose()

# Get the backward indices/indptr
indices_T = A_T.tocsr().indices
indptr_T  = A_T.tocsr().indptr

[aheev]

However it can't be used when data is not a 1D array. Maybe we can build our own custom impl based on scipy's, but it would be a costly operation

[adsharma]

#506 is the approach I've been thinking about. It has more code reuse and less terminology, but it's not complete.

• Reconcile native/parquet/arrow with respect to logical vs physical storage #505 needs to be addressed
• Not clear if the FLAT or CSR paths are as optimized as they're in your implementation. Needs review/tuning.

[adsharma]

The implementation stores arrow tables in only direction and satisfies reverse queries by scanning tables in memory. Unlike disk based indices, it's not clear that duplicating relations in memory is a good idea. More details:

lbug_connection_create_arrow_rel_table_csr() itself does not take a direction/undirected flag. It only registers one logical directed rel table:

  CREATE REL TABLE <table> (FROM <src> TO <dst>, ...)
  WITH (storage='arrow://...')

Direction handling happens later in ArrowRelTable::scanCSR() based on the query planner’s RelDataDirection.

For CSR layout, the Arrow data is assumed to be source-oriented:

• indptr[src_offset]..indptr[src_offset + 1] gives edge rows for that source node.
• indices["to"] contains destination node offsets.
• Rel properties live in the same indices rows.

For forward scans, ()-[r]->():

• Bound node is treated as the source.
• It reads indptr(bound_src_offset) and indptr(bound_src_offset + 1).
• It scans only that CSR slice.
• It outputs neighbor IDs as {to_offset, dst_table_id}.
• This is efficient CSR traversal.

For backward scans, ()<-[r]-():

• Bound node is treated as the destination.
• There is no reverse CSR/CSC structure.
• The implementation scans all relationship rows, reads each to, and checks whether it matches the bound destination.
• When it finds a match, it calls findCSRSourceOffset(relOffset) to binary-search indptr and recover the source node offset.
• It outputs neighbor IDs as {src_offset, src_table_id}.
• This is correct but much less efficient than forward traversal.

So: CSR Arrow rel tables store only one physical direction, source to destination. Backward traversal is supported logically by scanning the forward CSR data and reconstructing the source.

For “undirected” Cypher patterns like ()-[r]-(), the table is not stored as undirected. The planner can scan available storage directions; with current default DEFAULT_REL_STORAGE_DIRECTION = BOTH_REL_STORAGE, the created rel table exposes both FWD and BWD scan directions over the same directed edge set. If you need true undirected graph semantics, you still need either symmetric input edges or query semantics that intentionally scan both directions.

[aheev]

I will take a look today

[aheev]

indices["to"] contains destination node offsets.

in icebug-disk it is always the first column

[aheev]

approach LGTM