Keyed upsert of a table payload writes cell by cell (boxing + append/memcpy per cell), ~5x slower than a column scatter

[vbmithr]

Summary

A keyed upsert of a table payload goes through a per-cell path even when the
table-resident key map is attached and every payload column is a typed vector.
Updating a 935-row batch of existing keys in a 360 000-row table takes
0.41 ms. Writing the same values with one alter … set per value column takes
0.087 ms, 4.8× less, and that scatter still pays interpreter overhead.

Follow-up to #531 and #533, measured on fdf928b. In our real-time depth RDB,
this upsert is now the largest remaining cost: about 35% of the CPU per
tickerplant batch.

Where the time goes

For a table payload, upsert_apply (src/ops/query.c) does the following:

1. Boxes every payload cell. collection_elem(sc, r, &alloc) runs for
   each of the m × ncols cells and allocates an atom per cell, which is freed
   at the end. For 935 rows × 6 columns that is 5 610 allocations per call.

2. Checks types cell by cell against the target columns.

3. Hashes and compares each row through those atoms
   (upsert_hash_atoms, upsert_map_find → upsert_row_eq_atoms).

4. Overwrites each non-key cell of a matched row the long way
   (upsert_write_cell), for fixed-width columns:

   • ray_index_drop(&slots[c]), then clear RAY_ATTR_SORTED;
   • append_atom_to_col(col, cell): append at the tail, which may
     reallocate;
   • memcpy the tail element into row;
   • res->len = tail.

   That is one append, one copy and one index-drop call per written cell.

perf record --call-graph fp, update mode, N = 360 000, 2 000 batches:

 92.0%  upsert_apply              (27.0% self)
 45.7%    upsert_write_cell       (inlined; ray_vec_append 11.8%, memcpy 5.2%)
 12.4%    ray_free
 11.3%    ray_alloc               (+ heap_coalesce 5.1%)
 11.6%    upsert_map_find         (upsert_row_eq_atoms 6.3%)
  3.6%    collection_elem
  1.9%    ray_index_drop

Looking up the key map is ~12%. The rest is boxing and cell-at-a-time writing.

Measurements

upsert_scaling.rfl (below), -c 1, batch = 935 rows, 200 batches. levels
is referenced only by its global binding, so the ukey map is attached and
reused:

table rows	update (existing keys)	insert (new keys)
1 000	0.24 ms (0.25 µs/row)	0.33 ms
100 000	0.31 ms (0.33 µs/row)	0.32 ms
360 000	0.37 ms (0.40 µs/row)	0.47 ms
1 000 000	0.43 ms (0.46 µs/row)	0.69 ms

The map does its job, since cost is nearly flat in table size. The constant
is what's large: ~65 ns per written cell.

upsert_scatter.rfl (below): the same batches and target rows, written as
(alter 'col set rows values) for the three value columns:

path	per batch
upsert 'levels 3 batch	0.412 ms
3 × alter … set (no key lookup)	0.087 ms

Suggested direction

When the payload is a table whose columns are typed vectors matching the
target types (the common case, and cheap to check once per column):

1. Hash and compare keys directly from the payload's key vectors, as
   upsert_hash_row already does for the target, instead of through
   per-cell atoms.
2. Resolve the batch to two index vectors: matched target rows and
   payload rows to append.
3. Scatter each non-key column once: dst[hit[i]] = src[i] with the column's
   element size, dropping indexes and clearing SORTED once per column rather
   than per cell.
4. Append the unmatched rows with one gather-append per column, then add them
   to the ukey map.

The atom path would remain for LIST/STR columns, partial payloads, and type
coercions.

upsert_scaling.rfl

;; Keyed upsert of a ~935-row batch into a levels-shaped table that is
;; referenced only by its global binding (so the table-resident key map is
;; kept across calls).
;; Usage: N=360000 BATCH=935 MODE=update|insert REPS=200 rayforce -c 1 upsert_scaling.rfl
(set N (as 'I64 (.os.getenv "N")))
(set BATCH (as 'I64 (.os.getenv "BATCH")))
(set MODE (.os.getenv "MODE"))
(set REPS (as 'I64 (.os.getenv "REPS")))
(set NI 766)
(set insts (as 'SYMBOL (map (fn [i] (format "i%" i)) (til NI))))
(set TS 2026.09.15D12:00:00.000000000)
(set mk (fn [ids]
  (do (set n (count ids))
      (table [instrument side px sz ts_evt ts_recv]
        (list (at insts (% ids NI)) (at ['B 'A] (% ids 2)) (+ 100000 ids) (take [5] n)
              (take (enlist TS) n) (take (enlist TS) n))))))
(set levels (mk (til N)))
;; warm-up: builds and attaches the key map
(upsert 'levels 3 (mk (% (* 7919 (til BATCH)) N)))
(set bats (map (fn [r] (if (== MODE "update")
                           (mk (% (+ (* 7919 (til BATCH)) (* r 104729)) N))
                           (mk (+ (+ N (* BATCH r)) (til BATCH)))))
               (til REPS)))
(set el (timeit (map (fn [r] (upsert 'levels 3 (at bats r))) (til REPS))))
(println (format "mode=% N=% rows_after=% batch=% reps=% per_batch=% ms per_row=% us"
                 MODE N (count levels) BATCH REPS (/ el REPS) (/ (* 1000.0 el) (* REPS BATCH))))

upsert_scatter.rfl

;; Same 935-row update of a 360k-row levels table: keyed upsert vs a
;; column-wise scatter at known row positions (upper bound on what a
;; vector write path could save, key lookup excluded).
(set N 360000) (set BATCH 935) (set REPS 2000) (set NI 766)
(set insts (as 'SYMBOL (map (fn [i] (format "i%" i)) (til NI))))
(set TS 2026.09.15D12:00:00.000000000)
(set mk (fn [ids]
  (do (set n (count ids))
      (table [instrument side px sz ts_evt ts_recv]
        (list (at insts (% ids NI)) (at ['B 'A] (% ids 2)) (+ 100000 ids) (take [5] n)
              (take (enlist TS) n) (take (enlist TS) n))))))
(set levels (mk (til N)))
(upsert 'levels 3 (mk (% (* 7919 (til BATCH)) N)))
(set rows (map (fn [r] (% (+ (* 7919 (til BATCH)) (* r 104729)) N)) (til REPS)))
(set bats (map (fn [r] (mk (at rows r))) (til REPS)))
(set tu (timeit (map (fn [r] (upsert 'levels 3 (at bats r))) (til REPS))))
(set szc (get levels 'sz)) (set tec (get levels 'ts_evt)) (set trc (get levels 'ts_recv))
(set ts (timeit (map (fn [r] (do (set b (at bats r)) (set ix (at rows r))
                                 (alter 'szc set ix (get b 'sz))
                                 (alter 'tec set ix (get b 'ts_evt))
                                 (alter 'trc set ix (get b 'ts_recv))))
                     (til REPS))))
(println (format "upsert: % ms/batch  scatter(3 cols): % ms/batch  ratio=%x" (/ tu REPS) (/ ts REPS) (/ tu ts)))