DOCSEARCHbyAlgolia
Submit Docs

Rayforce Database Engine

repository·dev·Indexed 42 days ago

https://github.com/rayforcedb/rayforce

A pure C, zero-dependency, embeddable engine that fuses columnar analytics and graph traversal into a single operation DAG. It features a Lisp-like query language called Rayfall, morsel-driven bytecode execution, a custom buddy allocator, and multi-metric HNSW indexing for vector search.

Tokens
149.9K
Snippets
433
Records
571
Agent score
48%

What's inside Rayforce

  1. Overview of Rayforce capabilities

    dev

    Rayforce is an embeddable columnar analytics and graph traversal engine written in pure C. It is designed for high-performance workloads by combining morsel-driven vectorized execution with a multi-pass query optimizer and a native CSR (Compressed Sparse Row) graph engine.

    Key features include:

    • Vectorized Execution: Uses fixed-size morsels and SIMD where possible.
    • Query Optimization: Supports predicate pushdown, join reordering, and accelerator-index selection.
    • Graph Engine: Native CSR storage supporting algorithms like PageRank, Dijkstra, betweenness, Louvain, and MST.
    • Datalog Support: Recursive rules over EAV (Entity-Attribute-Value) triples.
    • Rayfall Language: A Lisp-flavored functional language for table and graph combinators.
    • IPC: Client/server architecture with authentication, restricted mode, and connection-lifecycle hooks.
    • Zero Dependencies: Distributed as a single binary, single shared library, and single header.

  2. Rayforce core features

    dev

    Rayforce is a fused engine for columnar analytics and graph traversal. Key capabilities include:

    • Execution Engine: Lazy DAGs, multi-pass optimizer, and bytecode-compiled morsel-driven execution.
    • Graph Engine: Double-indexed CSR storage with support for BFS, DFS, Dijkstra, A*, PageRank, Louvain, and more.
    • Rayfall Language: A Lisp-like language with builtins for arithmetic, strings, joins, and higher-order functions.
    • Memory Management: A custom buddy allocator with slab cache, thread-local arenas, and COW (Copy-On-Write) ref counting. It avoids the system allocator using ray_alloc/ray_free.
    • Vector Search: Multi-metric HNSW indexing (cosine, L2, inner-product) with filter-aware Approximate Nearest Neighbor (ANN) search.
    • Storage: Columnar files with mmap support, splayed tables, and a parallel mmap CSV reader.

  3. What is Datalog in Rayforce?

    dev

    Datalog is a rule-based declarative query language used in Rayforce. You define facts and rules, and the engine automatically derives all possible answers by applying rules until a fixpoint is reached.

    Key characteristics:

    • Recursive Queries: Handles transitive closure, reachability, and graph traversal natively.
    • Performance: Rules are compiled into a vectorized, morsel-parallel execution pipeline (DAG nodes) rather than being interpreted, avoiding interpretation overhead.
    • Storage Model: Uses Entity-Attribute-Value (EAV) triples stored in a columnar datoms table.

  4. Overview of the XCHECK Audit & Remediation Methodology

    dev

    XCHECK is a cross-agent methodology designed to perform reliable audits and remediations on large projects. It replaces long, error-prone agent sessions with a structured cycle of narrow, chartered sessions. This prevents agents from losing context, hallucinating findings, or forgetting previous decisions.

    The Audit Cycle

    The methodology follows a repeatable loop:

    1. Audit: An Auditor identifies defects and files them as evidence-backed findings.
    2. Human Triage: A human reviews findings to decide which are worth fixing.
    3. Remediate: A Remediator fixes the accepted findings.
    4. Verify: A Verifier provides a binding verdict on the fixes.

    Findings that pass verification are closed; those that fail are reopened for further remediation.

    Core Principles

    • Narrow Charters: Each session is limited in scope to prevent context loss.
    • Evidence-Anchored: Findings must be backed by verifiable evidence.
    • Cross-Agent Verification: The agent that fixes a finding is never allowed to verify it (the fixer is never the judge).

  5. What is Rayforce and how does it work?

    dev

    Rayforce is an embeddable analytics and graph engine written in pure C. It is designed to unify columnar analytics (tabular aggregation) and graph traversal into a single execution model. Instead of splitting work between two different runtimes, Rayforce treats both types of operations as part of the same lazy operation Directed Acyclic Graph (DAG). This allows a single optimizer to see the entire pipeline and execute it efficiently.

    Key architectural features include:

    • Unified DAG: Filters, joins, aggregations, window functions, and graph traversals are all part of one query graph that the optimizer rewrites before execution.
    • Morsel-driven execution: Operations are fused into single-pass pipelines that process data in 1024-element 'morsels' to maintain L1 cache residency.
    • Custom Memory Model: Uses a buddy allocator with slab caches and per-thread heaps to minimize allocator contention and avoid locks on the hot path.

  6. How Radix-Partitioned Hash Joins work

    dev

    Rayforce uses adaptive radix partitioning for hash joins to ensure hash tables fit within the L2 cache (targeting RAY_JOIN_L2_TARGET of 256 KB). The number of radix bits adapts between RAY_JOIN_MIN_RADIX (4 partitions) and RAY_JOIN_MAX_RADIX (16,384 partitions).

    Join Pipeline

    1. Partition: Both inputs are radix-partitioned by hash key bits.
    2. Build: Per-partition hash tables are built.
      • For INNER joins, the executor chooses the smaller input as the build side at runtime.
      • For LEFT, FULL, and ANTI joins, the right side is always built to preserve semantics.
      • Skew Handling: If a single key exceeds the duplication threshold (RADIX_DUP_RUN_MAX = 512), the engine abandons radix partitioning and uses a chained hash table (O(n)) to prevent quadratic degradation.
    3. Probe: Partitions are probed in parallel. Note that INNER join output order is not guaranteed to be stable.

  7. Understand Selection Bitmaps (RAY_SEL)

    dev

    A RAY_SEL is a lazy filter representation. Instead of creating new vectors for filtered data, Rayforce uses a compact bitmap to track which rows pass a predicate. This allows the optimizer to compose predicates via bitwise AND without copying data.

    Segment Flags

    Selections are organized into 1024-element segments. Each segment has a flag:

    • RAY_SEL_NONE (0): All bits zero; skip the entire morsel.
    • RAY_SEL_ALL (1): All bits one; process without checking the bitmap.
    • RAY_SEL_MIX (2): Mixed bits; must check the bitmap per row.

    Internal Layout

    A RAY_SEL object (type = 14) contains:

    • Segment flags: uint8_t per morsel.
    • Segment popcounts: int32_t per morsel (count of set bits).
    • Bit arrays: 16 uint64_t words per morsel (1024 bits).

  8. How ray_release() and ray_error_free() differ for errors

    dev

    Rayforce distinguishes between general resource release and specific error reclamation:

    1. ray_release(ray_t* ptr): A general-purpose function for releasing references. However, for error objects (RAY_IS_ERR(ptr) is true), this function is a no-op and does not reclaim memory.
    2. ray_error_free(ray_t* err): The required function for callers who hold the sole reference to an error object and want the memory reclaimed. Using this prevents memory leaks that occur when error objects are left until heap teardown.

  9. Use Dotted Namespaces for Nested Data

    dev

    A symbol containing dots (e.g., math.pi) acts as a path through nested dictionaries.

    • Writing: (set math.pi 3.14) automatically creates intermediate dictionaries.
    • Reading: math.pi traverses the path segment by segment.
    • Deleting: (del cfg.db.host) removes the leaf; deleting all leaves in a path removes the parent dictionaries.
    • Temporal Dispatch: If a dotted path ends on a temporal value (DATE/TIME/TIMESTAMP), the trailing segment (like .yyyy) triggers temporal extraction instead of a dictionary lookup.
    ; Nested writing
(set cfg.db.host "localhost")
cfg.db.host          ; "localhost"

; Temporal path dispatch
(set d 2024.03.15)
d.yyyy               ; 2024

; Deleting
(del cfg.db.host)

  10. Compute Running Totals and Moving Windows

    dev

    Rayforce provides specialized verbs for common analytics paths that run with high performance via DAG vector kernels and morsel-based execution.

    Running Totals (Cumulative)

    Use these verbs for cumulative calculations over a vector:

    • sums: Cumulative sum
    • prds: Cumulative product
    • avgs, mins, maxs: Cumulative average, minimum, and maximum.

    Moving Windows (Fixed Trailing Window)

    Use these verbs to perform calculations over a sliding window of size $N$ (including the current row and the previous $N-1$ rows):

    • msum: Moving sum
    • mavg: Moving average
    • mmin: Moving minimum
    • mmax: Moving maximum
    • mcount: Moving count
    • mvar: Moving variance
    • mdev: Moving standard deviation
    ; sums is the DAG-backed running sum
(sums [3 1 4 1 5 9 2 6])

; Fixed trailing window: current row plus the previous two rows
(msum 3 [3 1 4 1 5 9])
(mavg 3 [3 1 4 1 5 9])
(mdev 3 [3 1 4 1 5 9])

  11. Understand the Rayforce Audit Scope and Norms

    dev

    The Rayforce audit defines the standards (norms) and dimensions used to ensure the correctness of the C engine, Rayfall runtime, tests, and documentation.

    Audit Scope

    The audit covers authored project material including:

    • Source code: include/, src/
    • Tests and Fuzzing: test/, fuzz/
    • Documentation and Examples: docs/, website/, examples/, bench/
    • Build and Packaging: scripts/, packaging/, .github/, Makefile

    Norms Catalog

    Norms are the authoritative sources for project behavior. Key norms include:

    • N01 (include/rayforce.h): Public types, ownership/lifetime, error, vector, table, progress, and API contracts.
    • N02 (src/**/*.h): Internal module interfaces and invariants.
    • N03 (Documentation): Published behavior, architecture, language, storage/wire, error/null, and lifecycle contracts.
    • N05 (Tests): Executable behavior and regression contracts.
    • N06 (CONTRIBUTING.md, Makefile): C17, zero-dependency, warnings-as-errors, and build-flavor policy.
    • N12 (ISO C17): Language-level undefined behavior and platform portability (POSIX/Windows).

  12. Use recursive rules for transitive closure

    dev

    Datalog in Rayforce supports recursive rules. When a rule references itself, the engine computes the transitive closure using semi-naive evaluation. This process iterates until no new facts are produced (the "fixpoint").

    To implement recursion, define a base case (a non-recursive rule) and a recursive case (a rule that calls itself).

    Example: Transitive closure on a graph

    ;; Build a directed graph: 1->2->3->4
(set gdb (datoms))
(set gdb (assert-fact gdb 1 'edge 2))
(set gdb (assert-fact gdb 2 'edge 3))
(set gdb (assert-fact gdb 3 'edge 4))

;; Base case: direct edge
(rule (reachable ?x ?y) (?x :edge ?y))

;; Recursive case: edge + reachability
(rule (reachable ?x ?z) (?x :edge ?y) (reachable ?y ?z))

;; Query: all reachable pairs
(show (query gdb (find ?x ?y) (where (reachable ?x ?y))))