Skip to content

Front-code the string table and run queries on string IDs #64

Description

@matiastoro

Motivation

The string table is the single largest consumer of base RAM: on LDBC SF0.1 it is ~122 MiB of the ~181 MiB Lazy open footprint (measured). Two related optimizations could cut both memory and per-row query cost:

  1. Query on string IDs, resolve text only at the end. Operate on interned u32 string IDs throughout query execution and resolve to text only at RETURN projection. Today string property values are resolved to Value::Str(String) (text) during evaluation and compared as text (cmp_values / eq_value in src/runtime/mod.rs, src/runtime/engine.rs), so the id_to_str table is touched per row.
  2. Front-coding. Delta-encode shared prefixes of lexicographically sorted strings to compress the table on disk and in RAM.

Current state (feasibility)

  • Value::Str(String) holds text (src/model/value.rs:17); comparisons operate on text.
  • StringTable (src/store/string_table.rs) interns to u32 but assigns IDs in insertion order (id = id_to_str.len()), NOT lexicographic order.
  • Node/edge records reference strings by ID (VALUE_TYPE_STR = [str_id: u32], src/store/record.rs).

Key feasibility nuance

Equality on IDs works today (IDs are deduplicated). But ORDER BY / range / prefix (<, >, LIKE) on strings requires order-preserving IDs, i.e. IDs assigned in lexicographic order. Front-coding also requires sorted order. So both features share one prerequisite: sort the string table and assign order-preserving IDs, then remap every record's str_id on save. That is a .gdb format change.

Scope

  • Sorted, order-preserving string-ID assignment + record remap on save (src/store/io.rs).
  • Front-coded on-disk encoding (src/store/string_table.rs).
  • ID-based comparison path in the runtime; resolve to text only at projection.
  • Benchmark memory (target: shrink the ~122 MiB table) and query latency.

Large; storage-format change. Related: #LIKE/text-index discussions.

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceSpeed / memory optimizationresearchResearch / evaluation / spike

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions