Ladybug Graph Database Documentation

In hash joins, Semi-side Information Passing (SIP) uses semi masks to reduce work on one side of the join based on information from the other.

SIP Directions

1. Build to Probe SIP: The build side (smaller table) is scanned first. Nodes matching join keys are recorded in a semi mask. The probe side then uses this mask to only check relevant nodes.
2. Probe to Build SIP: The probe side is scanned first. The build side uses the semi mask to filter which nodes need to be looked up in the hash table.

I/O Reduction Mechanism

The optimization relies on the Selection Vector (SelVector) being passed down to the column scan level. Instead of decompressing and reading every row in a segment, the column.cpp scan logic uses a Filterer to check if any positions in the SelVector fall within a specific compressed block. If no masked nodes exist in a block, the entire block is skipped, avoiding disk I/O and decompression overhead.

Ladybug is an embedded, serverless graph database that executes within the same process as the host application. Because it runs in-process, security is a shared responsibility between the Ladybug engine and the embedding application.

Key Trust Boundaries

• Host Application $\rightarrow$ Ladybug API: Query text, parameters, data files, and configuration are passed from the host to the engine.
• Ladybug $\rightarrow$ Local Filesystem: Database files, WAL/checkpoint files, and operations like COPY, LOAD FROM, ATTACH, and EXPORT interact with OS-managed storage.
• Ladybug $\rightarrow$ Remote Services: Extensions (e.g., httpfs, azure, postgres, sqlite, duckdb, delta, iceberg, neo4j, unity_catalog, llm) expand the boundary to external endpoints and credentials.
• Ladybug $\rightarrow$ Native Extensions: Commands like INSTALL and LOAD EXTENSION introduce dynamically loaded native code into the database process.
• Wasm Package $\rightarrow$ Runtime: Wasm builds inherit the sandbox of the browser or Node.js environment.

Ladybug uses morsel-driven parallelism to execute queries in parallel. Instead of processing an entire table at once, work is divided into small, independently processable chunks called morsels.

Different table formats handle morsels with different granularities:

1. Native Node Tables: Use coarse-grained morsels. A single morsel typically corresponds to an entire node group (defaulting to ~128K rows). One scan() call processes the entire assigned node group.
2. Arrow/Columnar Tables: Use fine-grained morsels. A morsel is a sub-section of an Arrow batch (defaulting to 2048 rows). The scan() call returns after processing exactly one morsel, requiring more frequent calls to nextMorsel() to progress through the batch.

Core Components

• ScanNodeTable Operator: The main operator managing the scan loop via getNextTuplesInternal(). It orchestrates calls to table->scan() and requests new morsels via nextMorsel() when the current one is exhausted.
• ScanNodeTableSharedState: Per-table state that manages morsel assignment. It uses an atomic counter (currentCommittedGroupIdx) to assign the next available morsel to requesting threads.
• NodeTableScanState: Per-thread state that tracks the current morsel being processed (nodeGroupIdx) and the data source (COMMITTED, UNCOMMITTED, or NONE).

┌─────────────────────────────────────────────────────────────┐
│                    ScanNodeTable Operator                   │
│  ┌────────────────────────────────────────────────────────┐ │
│  │  getNextTuplesInternal() - Main scan loop              │ │
│  ├─ calls table->scan(transaction, scanState)          │ │
│  ├─ calls nextMorsel() when morsel scan exhausted      │ │
│  └─ calls initScanState() for new morsel               │ │
│  └────────────────────────────────────────────────────────┘ │
├─────────────────────────────────────────────────────────────┤
│                   Shared State (per table)                  │
│  ┌────────────────────────────────────────────────────────┐ │
│  │  ScanNodeTableSharedState                              │ │
│  ├─ nextMorsel() - assigns next morsel                 │ │
│  │                    (based on table's morsel config) │ │
│  ├─ currentCommittedGroupIdx (atomic counter)          │ │
│  └─ numCommittedNodeGroups                             │ │
│  └────────────────────────────────────────────────────────┘ │
├─────────────────────────────────────────────────────────────┤
│                   Scan State (per thread)                   │
│  ┌────────────────────────────────────────────────────────┐ │
│  │  NodeTableScanState                                    │ │
│  ├─ nodeGroupIdx - current morsel being processed      │ │
│  ├─ source - COMMITTED/UNCOMMITTED/NONE                │ │
│  ├─ Table-specific state                               │ │
│  |                                                        | |
│  |  ArrowNodeTableScanState                               | │
│  |  ├─ currentBatchIdx                                    | │
│  |  ├─ currentMorselStartOffset                           | │
│  |  ├─ currentMorselEndOffset                             | │
│  |  └─ ...                                                 | │
│  └────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘

The shell operates in two primary input modes which change how linenoise behaves:

:singleline (Default)

• Display: The input buffer is truncated to fit a single line on the screen. The cursor is always kept on the visible screen.
• History: Whitespace characters (newlines, returns) are converted to spaces. Every four spaces are condensed into one to remove tabs.
• Editing: Users are restricted to editing only the most recent line.

:multiline

• Display: The input is not truncated to a single line; it can span multiple lines. Visual 'continuation markers' are added to indicate the current line being edited.
• History: Newlines and comments are preserved in the history. While ctrl_r (reverse-i-search) still treats history as single-line (converting newlines to spaces), the selected query is restored to its proper multiline format when displayed.
• Editing: Allows moving between lines and editing previous lines within the current query block.
• Highlighting: Supports advanced highlighting, including multiline comments and error detection (unclosed strings, unclosed brackets).

The Zero-copy CSR (Compressed Sparse Row) design is an optimization for reading large-scale graph data (e.g., ~0.75B edges) from columnar storage into Arrow CSR memory.

The Problem: Memory Bloat

In the original implementation, each parallel batch (one per thread) maintained a dense indptr array indexed by the global source row ID. This caused massive memory duplication: if a batch touched only a few rows but the global row ID was high, the indptr was padded with zeros up to the maximum global row ID. For ~50 parallel batches, this resulted in ~40-45 GB of redundant indptr data.

The Solution: Sparse Per-Batch CSR

The design exploits two invariants to replace the dense indptr with a sparse representation:

1. Monotonicity: Because morsels are acquired via an atomic counter, each thread receives a non-decreasing sequence of srcRowIDs.
2. Disjointness: Each source row is scanned in exactly one morsel, meaning per-batch sets of touched source rows are disjoint.

By using a sparse representation, the per-batch overhead drops from numSourceRows * 8 bytes to distinctSrcRowsInBatch * 16 bytes (storing only the srcRows ID and the counts of edges per row).