Technical Analysis: Improving Index Selection for Logical Replication Apply with Replica Identity Full

Core Problem

When PostgreSQL performs logical replication with REPLICA IDENTITY FULL, UPDATE and DELETE operations on the subscriber must locate the target tuple to modify. Since PG14 (commits from the referenced threads), the apply worker can use existing indexes rather than always falling back to a sequential scan. However, the index selection algorithm is naive: it iterates through RelationGetIndexList() which returns indexes ordered by OID, and picks the first "suitable" index it finds.

This OID-ordering heuristic is essentially arbitrary from a performance perspective. If a low-cardinality index (e.g., on a boolean column) happens to have a lower OID than a high-cardinality unique index (e.g., on a UUID primary key), the apply worker will use the low-cardinality index. This results in index scans that return potentially hundreds of thousands of rows that must then be sequentially compared — performing no better (and possibly worse) than a sequential scan.

Why This Matters Architecturally

Logical Replication Apply Path

The logical replication apply worker (src/backend/replication/logical/worker.c) processes each change row-by-row. For each UPDATE/DELETE with REPLICA IDENTITY FULL:

1. The full old tuple image is received from the publisher
2. The subscriber must find the matching tuple in its local relation
3. The code in RelationFindReplTupleByIndex() or RelationFindReplTupleSeq() performs the lookup
4. The index selection happens in FindUsableIndexForReplicaIdentityFull() (or similar function depending on version)

The key issue is that this lookup happens per-row in a serial fashion. Unlike query execution where the planner can amortize planning cost over potentially millions of rows, each replicated row pays the cost of whatever index path is chosen. A 53-second vs. sub-1-second difference for 1,000 operations demonstrates that bad index selection causes O(n) scanning per row operation, turning what should be O(log n) lookups into O(n) or O(n * k) where k is the number of matching rows in the low-cardinality index.

Why REPLICA IDENTITY FULL Exists

Users sometimes cannot use REPLICA IDENTITY DEFAULT (primary key) or REPLICA IDENTITY USING INDEX because:

• Downstream logical consumers (Debezium, custom CDC pipelines) require full before-images
• Schema designs may not have stable unique identifiers suitable for replica identity
• Multi-target replication where different subscribers have different schema constraints

Proposed Solution

The patch introduces a smarter heuristic for index selection that avoids invoking the full query planner (which would be too expensive per-row) while still making significantly better choices:

Selection Priority:

1. Prefer unique indexes — A unique index guarantees at most one tuple match per lookup, eliminating the cardinality problem entirely. This transforms the lookup from "scan potentially thousands of matches" to "scan exactly 0 or 1 match."
2. Among unique indexes, prefer fewer columns — Fewer columns means a narrower index with less comparison overhead and potentially better cache behavior. A single-column unique index on a UUID is the ideal case.

Design Tradeoffs

• Not invoking the planner: Previous discussions (referenced threads) explicitly avoided calling the planner for index selection in this path. The planner requires statistics, catalog lookups, and significant per-invocation cost. For row-by-row apply, this overhead would be prohibitive.
• Heuristic vs. optimal: The proposed heuristic is not globally optimal — a non-unique index with very high cardinality and good statistics might occasionally outperform a unique index with many columns. However, the unique guarantee provides a hard upper bound (1 tuple) that no statistical estimate on a non-unique index can match.
• No statistics consultation: The patch deliberately avoids reading pg_statistic to assess index cardinality, keeping the selection logic simple and avoiding catalog access overhead during apply.

Correctness Considerations

The change is purely a performance optimization — any usable index will produce correct results since the apply worker already performs full tuple comparison after index lookup. The only question is efficiency of finding candidates.

Performance Impact

The benchmark demonstrates the pathological case:

• Table: 1M rows with a boolean column (cardinality ~2, so ~500K rows per value) and a UUID column (cardinality = 1M)
• The boolean index scans ~500K rows per lookup to find 1 match
• The UUID unique index scans exactly 1 row per lookup
• 1,000 operations × 500K row scans = catastrophic performance (53s)
• 1,000 operations × 1 row scan = optimal performance (<1s)

This is a 53x improvement in the pathological case, with no regression in cases where the unique index would already be selected (i.e., when it has the lowest OID).

Relationship to Prior Work

The referenced threads [1] and [2] established the foundation for using indexes at all with REPLICA IDENTITY FULL (PG14). This patch is a natural evolution — once index usage was enabled, the question of which index to use when multiple are available becomes the next optimization target.