Investigate columnar (structure-of-arrays) representation for arrays of uniform JqObjects

[stalep]

Summary

Investigate a columnar internal representation for JqArray instances that contain JqObjects with identical key sets (arrays of records). Instead of each JqObject storing its own keys[] + values[] arrays (row-oriented), store the data as shared keys + per-field value arrays (column-oriented). This eliminates pointer chasing when querying a single field across all elements.

Background

The access pattern

Many jq queries iterate an array of objects and extract a single field:

[.pcp_time_series[] | .["mem.util.used"]]
[.data[] | .sample_uuid]
[.stressng_workload[] | .test_results]

These are the most common patterns in h5m's rhivos pipeline (30% of all production jq expressions are this shape).

The current layout (row-oriented)

JqArray (502 elements)
  ├── JqObject₀ { keys[127], values[127], hashSlots[256] }  ← heap location A
  ├── JqObject₁ { keys[127], values[127], hashSlots[256] }  ← heap location B
  ├── JqObject₂ { keys[127], values[127], hashSlots[256] }  ← heap location C
  └── ... × 502

Querying .["mem.util.used"] on all 502 objects requires:

1. For each object: dereference JqObject pointer → access hashSlots[] → access keys[] → access values[]
2. 502 different hashSlots[] arrays, 502 different keys[] arrays, 502 different values[] arrays
3. Each array is a separate heap allocation at an unpredictable location
4. Result: 4,658 L1-dcache-load-misses (5.69% miss rate) from pointer chasing across the heap

The columnar layout (column-oriented)

ColumnarJqArray (502 elements)
  ├── sharedKeys: String[127]           ← one array, shared
  ├── sharedHashSlots: int[256]         ← one array, shared
  ├── columns[0]: JqValue[502]          ← "mem.util.used" values, contiguous
  ├── columns[1]: JqValue[502]          ← "mem.util.free" values, contiguous
  └── ... × 127 columns

Querying .["mem.util.used"] becomes:

1. Look up column index for "mem.util.used" in sharedKeys (once, using hash index)
2. Access columns[colIdx] — a single contiguous JqValue[502] array
3. Sequential memory access through one array — L1-friendly

Profiling data (2026-07-02)

Benchmark	L1-dcache-load-misses	Miss rate	Pattern
prod_topField	0.003	0.01%	Single field access (no iteration)
prod_deepField	0.053	0.02%	Deep field chain (no iteration)
prod_keys	0.704	0.15%	Keys of single object
prod_extractMetric	4,658	5.69%	Iterate 502 objects, access one field each
prod_iterateExtract	3.930	0.44%	Iterate small array

prod_extractMetric has 100x more L1 misses than other benchmarks because it iterates a large array of objects — exactly the pattern columnar layout optimizes.

Design Considerations

1. Detection: when to create columnar layout

Option A: Parse-time detection (builds on #48)

• During parsing, if N consecutive objects share the same keys[] (detected by Share key arrays across JqObjects with identical schemas to reduce heap pressure and cache misses #48's shared key mechanism), convert to columnar after the array is complete
• Pro: zero cost at query time. Con: adds parse-time overhead for arrays that are never iterated by field.

Option B: Lazy conversion on first iteration

• Store row-oriented initially. On first .[] + field access pattern, convert to columnar and cache.
• Pro: zero cost if the array is never iterated by field. Con: first query pays conversion cost.

Option C: Explicit API

• JqArray.toColumnar() for callers who know their data shape.
• Pro: no heuristic. Con: requires caller awareness.

Recommendation: Option A (parse-time) since h5m's dominant pattern is parse-once-query-many, and the detection mechanism from #48 is already available.

2. JqValue sealed interface constraint

JqValue is a sealed interface with 6 permitted subtypes. A ColumnarJqArray cannot be a new subtype. Options:

Option A: Internal flag on JqArray

public final class JqArray implements JqValue {
    private final List<JqValue> elements;          // row-oriented (null when columnar)
    private final String[] columnKeys;              // columnar keys (null when row-oriented)
    private final JqValue[][] columns;              // columnar values (null when row-oriented)
    private final int[] columnHashSlots;             // columnar hash index
    private final int columnHashMask;
    private final int rowCount;
}

The get(int index) method returns a view JqObject backed by the column data:

public JqValue get(int index) {
    if (columns != null) {
        // Return a view object that reads from column arrays
        return new ColumnViewJqObject(columnKeys, columns, columnHashSlots, columnHashMask, index);
    }
    // Fall back to row-oriented
    return elements.get(resolveIndex(index));
}

Option B: Wrapper JqArray
A ColumnarJqArray that wraps column data and is returned from parsing instead of the standard JqArray. Since it's the same JqArray class (just different internal state), it satisfies the sealed constraint.

3. The ColumnViewJqObject

When columnar, get(int rowIndex) returns a lightweight view:

// A JqObject view backed by columnar storage — no allocation except the view object itself
class ColumnViewJqObject extends JqObject {
    private final JqValue[][] columns;
    private final int rowIndex;
    
    JqValue get(String key) {
        int colIdx = hashLookup(key);  // uses shared hash index
        return columns[colIdx][rowIndex];  // direct array access
    }
}

This view object is small (2 references + 1 int) and could be cached/reused during iteration to avoid per-element allocation.

4. Column-major vs row-major

• Column-major (JqValue[numFields][numRows]): one array per field. Best for single-field queries (.[] | .x). Each field's values are contiguous.
• Row-major (JqValue[numRows][numFields]): one array per row. Best for full-object access (.[] | {a, b, c}). Each row's values are contiguous.

Recommendation: column-major since the dominant query pattern is single-field extraction.

5. Write operations

Columnar layout is read-optimized. JqArray's copy-on-write methods (with(), append()) would need to either:

• Convert back to row-oriented on mutation (simple, safe)
• Implement columnar-aware mutation (complex, marginal benefit)

Since jjq values are immutable after construction, mutations are rare (only in jq's |= operator and setpath). Converting back to row-oriented on mutation is the pragmatic choice.

6. Non-uniform arrays

Arrays where objects have different key sets remain row-oriented. The detection threshold could be configurable:

• 100% uniform → columnar (strict, safe)

• 80% uniform → columnar with row-oriented outliers stored separately

• Recommendation: start with 100% uniform (simplest, covers the common case)

Estimated Impact

prod_extractMetric ([.pcp_time_series[] | .["mem.util.used"]])

Metric	Current (row)	Expected (columnar)
L1-dcache-load-misses	4,658	~50-100 (single contiguous array)
Memory for keys	502 × 1KB = 500KB	1KB (shared)
Memory for hashSlots	502 × 1KB = 500KB	1KB (shared)
Field access pattern	502 pointer chases	1 sequential array scan

Other production queries

Any query matching [.array[] | .field] benefits:

• [.data[] | .sample_uuid] — same pattern
• [.stressng_workload[] | .test_results] — same pattern
• {user, uuid, run_id} on single objects — no benefit (not an array iteration)

Implementation Plan

1. Prerequisite: implement Share key arrays across JqObjects with identical schemas to reduce heap pressure and cache misses #48 (shared key arrays) — validates the schema detection mechanism
2. Add columnar storage fields to JqArray (internal, behind a flag)
3. Implement ColumnViewJqObject — lightweight view backed by column data
4. Parse-time detection: when Share key arrays across JqObjects with identical schemas to reduce heap pressure and cache misses #48's shared key mechanism detects uniform objects, construct columnar JqArray instead of standard
5. Benchmark: compare row vs columnar on prod_extractMetric with -prof perfnorm
6. Fallback: ensure with()/append() convert to row-oriented

Acceptance Criteria

• Arrays of uniform JqObjects use columnar internal representation
• get(int) returns a ColumnViewJqObject that reads from column arrays
• JqObject.get(String) on column views uses the shared hash index
• Non-uniform arrays remain row-oriented
• All existing tests pass (478 in jjq-core, 991 in test-suite)
• Measurable L1-dcache-load-miss reduction on prod_extractMetric
• No regression on parse throughput or non-array query benchmarks
• Copy-on-write operations (with, append) work correctly (convert to row-oriented)

Relationship to Other Issues

• Depends on Share key arrays across JqObjects with identical schemas to reduce heap pressure and cache misses #48 (shared key arrays) — the schema detection mechanism
• Complements Reduce INTERN_TABLE from 2048 to 512 slots to improve L1 cache locality during parsing #47 (smaller intern table) — both reduce L1 cache pressure
• Parallels h5m #155 (storage redesign) — the database-level equivalent of row-to-column transformation
• The jq VM's COLLECT_ITERATE opcode could be optimized to detect columnar arrays and extract the column directly without per-element get() calls (future optimization)

References

• perf stat data from 2026-07-02 profiling session
• Mitchell Hashimoto: "Everyone Should Know SIMD" — cache-aware data processing patterns
• Apache Arrow — columnar in-memory format (similar concept, much more complex)
• jjq knowledge tree: "L1 cache misses are the primary parse bottleneck"
• h5m #155: storage redesign proposes the same row-to-column transformation at the database level