Discussion: would an ordered (memcomparable) __pgt_row_id be worth the migration?

[Teletele-Lin]

Discussion: would an ordered (memcomparable) byte encoding for __pgt_row_id be worth the migration?

Opening this as a discussion rather than a formal proposal — we've been running a similar technique in our differential-refresh engine and it looked promising enough to bring back here.

Why bring this up

Both pg-trickle and our engine identify rows via a hash and index on it. We took the same conceptual path originally, and from profiling our differential-refresh hot path two costs sat at the top in a way that no further pipeline tuning was going to move — and both turned out to come from the choice of hash as the row identity, not from anything specific to our codebase:

1. Per-row CPU. Producing a hash from typed column values requires turning them into a hashable byte sequence first — per column, per call. The same row-id expression typically appears at several stages of a differential pipeline, so the per-row cost compounds with pipeline depth. The exact constants depend on how each implementation converts values to bytes; the shape of the cost is shared.

2. Random index access. A hash output is uniformly distributed by construction, so the index on the row-id column is uncorrelated with the physical write order of the base table. MERGE-time probes hit random index pages, and the buffer pool can't keep the working set warm when the storage table outgrows shared_buffers. This one is purely structural — it follows from "row ID = hash" regardless of which hash function or storage layout is in use.

These observations come from our engine, so we won't claim the constants carry over to pg-trickle directly. But the mechanism is shared, and that's what motivated us to look for an alternative to hash-based row identity in the first place.

The idea

Replace the hash with a memcomparable byte encoding of the key columns, stored as __pgt_row_id BYTEA. The default bytea_ops BTREE then gives an order-preserving index for free — index access pattern follows the base PK order instead of being scrambled.

The encoding is simple — one per-type appender that writes bytes whose memcmp order matches the natural value order of the source type:

• Signed integers: flip the sign bit, then write big-endian.
• Unsigned / oid / date / uuid: straight big-endian.
• Text family: detoasted bytes followed by a \0 terminator (PG text disallows embedded NUL, so the terminator delimits adjacent columns under memcmp).
• NULL: each column is prefixed by a 1-byte NULL tag, so NULL is unambiguously distinct from empty / zero.

Up front: this is the one direction we've actually built. If anyone in the community has tried a better encoding in a similar setting we'd genuinely like to hear about it before pg-trickle commits to anything. Memcomparable bytea is a known-good baseline, not necessarily the optimum.

The encoder function's own performance is the part that matters most. Whatever encoding wins on paper, the function runs once per row per CTE stage on every refresh — algorithmic elegance doesn't help if the implementation allocates or does fmgr lookups on the hot path. The shape we'd want:

• Take record, not Vec<String>. Resolve the record's TupleDesc once, deform the tuple directly. No ::TEXT cast, no Vec<Option<String>> allocation.
• Reuse a single growing buffer across rows to avoid per-row allocations.
• Type dispatch via cached function pointers, resolved once per record-type and stored indexed by column position.

How it would slot into pg-trickle

The existing abstractions hold. RowIdStrategy / RowIdSchema in src/dvm/row_id.rs decides which columns participate in the identity — that contract doesn't change. The only thing that changes is the kernel behind the __pgt_row_id column:

pg-trickle today	Under this idea
pg_trickle_hash_multi(ARRAY[col::TEXT, ...])	encode_row_id(ROW(col, ...))
__pgt_row_id BIGINT UNIQUE INDEX	__pgt_row_id BYTEA UNIQUE INDEX (default bytea_ops)
ON CONFLICT (__pgt_row_id) / MERGE ON ... = ...	unchanged — same equality, same plan shape
Keyless source forced to non-UNIQUE	Can be UNIQUE — encoding is injective

The RowIdSchema plan-time guardrail doesn't care whether the kernel is xxh3 or memcomparable bytes; it checks column membership, not encoding.

Open questions

We don't have confident answers for these, and they probably gate the conversation:

• Is __pgt_row_id an external contract? It's observable to the DuckLake sink, the outbox publisher, and any dbt model built on pgtrickle.pgt_* tables. Changing the column type from BIGINT to BYTEA is a wire-format break, and if downstream consumers parse it, this question constrains the rest of the design before the technical discussion even starts.

• Type coverage policy. Memcomparable encoding is intrinsically per-type. A whitelist (bool, int2/4/8, oid, date, time, timestamp(tz), uuid, text/varchar/bpchar) covers the PKs we've seen in practice, but pg-trickle today accepts anything that can be ::TEXT-cast. Reject unsupported types at CREATE time, or fall back to hash for them? Both are defensible; the trade-off is "fewer supported workloads, simpler invariants" vs "broader coverage, two code paths".

• Is bytea memcomparable the right encoding? We validated it works; we haven't compared it against alternatives. If the community has experience with a better-suited approach we'd rather build on that than re-derive a worse-than-known result.

What we're asking for

Mostly: does this direction sound interesting enough to validate against pg-trickle? A small spike against a representative workload should be enough to tell whether the win carries over from our setting — pg-trickle's pipeline has different cost weights, and we'd much rather have a real measurement on real pg-trickle than port any number from elsewhere.

We're happy to share the encoder shape, the call-site caching pattern, or a microbenchmark harness in whatever form is most useful — or to put up a draft PR if maintainers prefer something concrete to react to.

[grove]

Thanks for the detailed write-up — the two cost drivers you identified (per-row hash CPU and random index access) are real and structural, and the profiling story makes sense. A few thoughts from looking at how pg-trickle is currently built:

The ordering benefit is real, but has an upper bound

The index locality win only materialises once the stream table outgrows shared_buffers. For small-to-medium tables that fit in cache, you'd pay wider storage (BYTEA varlena vs fixed 8-byte BIGINT), a larger B-tree (variable-length keys, fewer entries per page), and slower equality comparisons inside MERGE (memcmp vs integer compare) — with no offsetting gain. The proposal is a clear win for large-table workloads and potentially a regression for small ones.

__pgt_row_id is a public column

It's documented as BIGINT | Public in our schema stability report and gets replicated via logical replication publications. Changing its type globally is a wire-format break for subscribers, the DuckLake sink, outbox consumers, and any dbt model that references it explicitly. That makes a global switch a major-version boundary event, not an incremental improvement.

The keyless (all-columns) case is concerning

For stream tables without a primary key, the row ID currently hashes all output columns into a single BIGINT. A memcomparable encoding of, say, 20 text columns could be very wide. The index size penalty in that case could easily outweigh the ordering benefit.

Combined join IDs need a delimiter scheme

Join row IDs currently combine two child IDs by hashing them together (BIGINT + BIGINT → BIGINT). With BYTEA concatenation you need an unambiguous delimiter that keeps the result injective across all type combinations — solvable, but an invariant that has to be maintained across every join operator.

---

The question we'd like your take on: would opt-in per stream table work for your use case?

The StreamTableMeta struct already follows a pattern of per-table options (is_append_only, temporal_mode, pooler_compatibility_mode, etc.). Adding row_id_encoding = 'memcomparable' as a CREATE STREAM TABLE ... WITH (...) option would:

• Let large-table workloads opt in where the index locality win dominates
• Leave existing tables and downstream integrations undisturbed
• Make REINITIALIZE mandatory on encoding change (the column type changes, so existing hash values are meaningless anyway)
• Keep the two code paths explicit rather than hiding a global behaviour change

The implementation surface is bounded: the CREATE TABLE DDL, the row-id expression in the codegen, and the 0::BIGINT / NULL::BIGINT sentinel literals in the join and scan operators are the three places that would branch.

Does opt-in cover your actual use case, or do you need the ordering behaviour to apply uniformly across all tables for the workload you have in mind? Happy to discuss a concrete spike design if the opt-in framing works.

[Teletele-Lin]

Thanks for the detailed breakdown. Thinking through the opt-in approach you suggested, we realize it actually introduces a fundamental architectural conflict for our specific pipeline:

1. The Change Buffer Consistency Issue:
   The encoding cannot easily be heterogeneous. In our architecture, the row ID computation doesn't just happen at the MERGE stage; it happens upstream in the change buffer when capturing the data. If encoding varies per stream table, the upstream buffer suddenly needs to query downstream metadata to figure out how to format the ID for matching. This breaks the decoupling.

2. Strict UNIQUE NOT NULL Requirement:
   Regarding the keyless table concern: our approach strictly requires the base table to have a UNIQUE NOT NULL constraint. We simply do not support this path for normal tables without explicit unique indexes, which naturally eliminates the massive index bloat scenario you mentioned.

3. JOIN Scenarios:
   For combined JOIN IDs, our concept is to simply concatenate the index fields of the multiple tables based on the JOIN order. Structurally, this handles uniqueness in the same way the current hash combination does.

Conclusion & A Pivot:
Given the strict upstream/downstream consistency we need (Point 1), we realize our BYTEA approach might be too rigidly tied to our specific constraints and might not fit cleanly into pg-trickle's general-purpose, decoupled design.

Since keeping the BIGINT interface seems structurally necessary for the framework, we'd like to pivot the discussion: is it possible to build a "roughly ordered" hash index (for instance, by bit-packing a timestamp/sequence prefix with a collision-resistant hash suffix)? We are curious if there is a way to maintain the fixed-length integer contract while preserving enough physical locality to prevent B-Tree thrashing.

[grove]

Thanks for following up with the architectural context — the change-buffer consistency point is the most substantive part and worth engaging with carefully.

On change-buffer consistency (Point 1)

In pg-trickle's current implementation the row-id expression is generated at CREATE STREAM TABLE time and baked into the trigger body (or into the WAL decoder's codegen pass) as a SQL string. The per-table encoding flag lives in StreamTableMeta and is read at that codegen stage — not per-row at runtime — so there is no hot-path catalog dependency. The generated trigger body would call either pg_trickle_hash_multi(...) or encode_row_id(...) depending on the flag chosen at creation time. Changing the encoding afterwards is handled the same way as any column-type change: REINITIALIZE drops and rebuilds the storage table, which also regenerates the trigger body. The coupling exists at creation/reinit time, which is already where all other per-table options (is_append_only, has_keyless_source, etc.) are resolved.

On the "roughly ordered hash" idea

The challenge with a timestamp/sequence prefix packed into the BIGINT is that the row-id needs to be a deterministic function of the key column values alone, so that CDC capture and the refresh MERGE agree on the same value for the same row across time. A time-derived prefix would differ between the INSERT event and a later UPDATE event for the same row, so MERGE would never find the match. That said, the underlying motivation — reducing B-tree scatter without changing the column type — is real, and we haven't found a clean answer for it within the BIGINT constraint either. If you have a formulation that keeps the value stable across events we'd genuinely like to see it.

Two things we think are worth measuring

1. Integer PK fast path. When the identity is a single int4 or int8 column, skip the hash and write the raw value as __pgt_row_id BIGINT. Zero encoding cost, perfect B-tree correlation with the base PK, no type change, no migration. RowIdStrategy in src/dvm/row_id.rs already distinguishes single-column from multi-column keys at the type level, but the code-generation paths in the refresh engine and WAL decoder still call pg_trickle_hash unconditionally — wiring up the fast path there is the real work. This covers a large share of real workloads and should show up clearly in benchmarks.

2. Opt-in BYTEA for multi-column PKs on large tables. Per-table WITH (row_id_encoding = 'memcomparable'), BYTEA column type, bytea_ops BTREE, REINITIALIZE required on encoding change. The change-buffer concern from Point 1 is addressable within the existing codegen pattern.

On the ::TEXT cast cost

The current pg_trickle_hash_multi(ARRAY[col::TEXT, ...]) call pays a TEXT cast per column per row regardless of encoding. Deforming the tuple via TupleDesc directly — as the original post described — reduces that cost on the hash path too, not just the BYTEA path. That's an orthogonal improvement that can land independently of whichever encoding question is resolved first.

We're planning to spike the integer PK fast path and will share numbers when we have them. If you're open to sharing the microbenchmark harness in the meantime, it would help us calibrate against a common baseline.

[Teletele-Lin]

Hi grove,

Thanks for the clarification on how metadata lookup and codegen resolve options at creation/reinit time. That makes a lot of sense.
To address the points you raised, here are my thoughts on the change buffer tables, encoding logic, and how these optimizations fit into pg-trickle's architecture. Please note that the optimizations discussed below are strictly under the prerequisite that the base table has a valid UNIQUE NOT NULL index (or primary key).

1. There might be some misunderstanding of my previous point. I am considering the scenario where a change buffer is depended upon by multiple stream tables, and the stream tables might have different encoding modes (specified via the optional parameter you proposed). In this case, the matching logic of the stream tables might conflict.

2. For base tables with a UNIQUE NOT NULL index (or primary key), in a single-table incremental computation scenario, it is feasible not to need extra encoding for processing and matching. However, if this primary key has multiple columns, if "no encoding" computation is done, I might need to add these columns to the streaming table, and at the same time, create indexes on these columns to improve MERGE performance. If "encoding" computation is done to merge them into a single column for processing, it still falls back to the mode requiring encoding at refresh time.

3. For the case where the base table has a UNIQUE NOT NULL index (or primary key), I had an additional thought: if the change buffer table does not store the row_id column, the CDC path does not need to perform encoding computation when writing. If it is a multi-column primary key, the encoding computation is performed at refresh time (under the prerequisite of having a unique index, the encoding logic of the base table is unified, which seems more elegant here). This is equivalent to eliminating the encoding computation on the CDC path.

4. Thinking further, for the case where the base table has a UNIQUE NOT NULL index (or primary key), if the change buffer table can still perform encoding computation and store the row_id column during the CDC phase, my doubt in the first point seems to be resolved. This way, the logic for adding an optional parameter also seems able to be unified. However, the cost is that the CDC path has one extra hash computation (if there is a unique NOT NULL index constraint for the base table, this cost can be optimized away).

5. Going back to the beginning, because pg-trickle needs to handle tables without primary key constraints, it introduced some complexity in the architecture, introducing hash functions to calculate row_id. For my optimization idea to align with pg-trickle, the reasoning logic above can be referred to.

6. Finally, still regarding the algorithm for building a "roughly ordered" index, if there is a highly efficient algorithm, the architecture wouldn't need a major change. The optimizations I discussed are all derived based on the current hash calculation for row_id. 😂

[Teletele-Lin]

Supplement : The question is after hashing, row _ id has no spatial locality on steaming table 's index.

[grove]

We have turned this discussion into a concrete proposal: [PROPOSAL_VERSIONED_ROW_IDENTIFY_ENCODING.md](https://github.com/trickle-labs/pg-trickle/blob/main/proposals/PROPOSAL_VERSIONED_ROW_IDENTIFY_ENCODING.md.

Our current recommendation is to adopt ordered, canonical BYTEA as the V2 __pgt_row_id format. The complete encoded bytes become the identity, so there is no 64-bit hash-collision failure mode and key ordering is preserved where the source type supports it.

Because PostgreSQL cannot index arbitrarily large BYTEA values directly, the design adds a bounded generated probe column for B-tree lookup. The probe is only an index accelerator; every match still compares the complete identity, so probe collisions cannot corrupt data.

This is intentionally a breaking, extension-wide migration. Existing stream tables and CDC state must be rebuilt, so retaining BIGINT would preserve compatibility at the cost of carrying forward the hash and locality problems.

WDYT?

[grove]

It might be an option to keep the BIGINT support as a pragmatic legacy/default mode with documented limits.

BIGINT is reasonable for existing users and small-to-medium workloads because xxhash is deterministic, fast, and collisions are unlikely at modest row counts. But it is not collision-proof.

[grove]

It think this summarizes the situation well:

1. Why BIGINT is a problem: pg_trickle currently uses a 64-bit hash as the row ID. This is compact and fast, but two different rows can theoretically produce the same number. If that happens, the system may update, overwrite, or delete the wrong row. With a unique index, PostgreSQL may raise an error; with a non-unique index, the problem may remain hidden and look like valid data. BIGINT also destroys key ordering, so large tables can suffer from random index access. It is acceptable for existing or small workloads, but it is not a perfect identity.

2. Why BYTEA is better: The proposed safer format stores the complete logical identity as ordered, canonical BYTEA instead of shrinking it into a 64-bit hash. This avoids hash collisions, makes composite fields unambiguous, and preserves useful ordering for indexes. Because very large byte values cannot always be indexed directly, the design adds a smaller probe column for lookup, but the full BYTEA value is always checked before accepting a match. The downside is that the values and indexes are larger, the encoder is more complicated, and PostgreSQL type semantics must be implemented very carefully.

3. The compatibility compromise: The most practical user-facing design is to let existing BIGINT stream tables keep working, make BYTEA the default for new stream tables, and allow users to explicitly request BIGINT. This avoids forcing every existing installation to rebuild immediately, while steering new users toward the safer format. The cost is that the system must support both modes across CDC, refresh, joins, aggregates, migrations, and shared change buffers. That is a significant amount of extra complexity, but it is acceptable if preserving existing tables is an important 1.0 requirement. The important message is that BIGINT would be a legacy compatibility mode, while BYTEA would be the recommended long-term choice.

[Teletele-Lin]

Thanks for writing this up — I'm in favor of the full V2 cutover.

My main argument against a BIGINT legacy mode is engineering cost: with two identity representations, every differential path — CDC buffers, joins, aggregates, MERGE, migration state — has to be adapted to both, and that cost is permanent. A one-time rebuild with clear migration documentation for existing users seems much cheaper than carrying two modes forever.

For the ordering benefit, I'd suggest profiling before we take it for granted: capture flamegraphs on the current MERGE path to confirm the hashed row ID actually causes the index cache/localization problem on large tables, then measure the same workload under V2 to show the ordered encoding delivers a real improvement. That would turn §13's expectations into evidence.

[grove]

Good to hear that.

The proposal will be implemented throughout the v0.87.15-v0.87.17 roadmap versions. The final proposal can be found in proposals/PROPOSAL_VERSIONED_ROW_IDENTIFY_ENCODING.md.

NOTE: This is a breaking change and all stream tables will be automatically recreated when upgrading to v0.87.17. No in-place migration is planned.

[grove]

v0.87.17 has been released now.