blockchain: block locator builder calls recursive CTE per skip-level — batch into one query

[oskarszoon]

Summary

services/blockchain/Server.go:3074 builds a block locator by calling store.GetBlockInChainByHeightHash(ctx, height, hash) in a loop with exponentially increasing step sizes. Each call independently re-traverses the chain from the supplied hash. For a 1.5M-height tip this means up to 21 separate recursive CTE invocations per locator build, each walking back further than the last. Coalescing into a single SQL pass eliminates the repeated round trips and the redundant recursion overlap.

Current code

services/blockchain/Server.go:3070-3085 (paraphrased):

locator := make([]*chainhash.Hash, 0, maxEntries)
step := uint32(1)
height := blockHeaderHeight
hash := blockHeaderHash

for {
    block, _, err := store.GetBlockInChainByHeightHash(ctx, height, hash)
    if err != nil {
        return nil, err
    }
    hash = block.Header.Hash()
    locator = append(locator, hash)
    if height == 0 {
        break
    }
    // adjust height by step, step doubles after the first ~10 entries
}

So:

• Iteration 1: walk back step=1 from tip → 1 lookup
• Iteration 2: walk back step=1 → 1 lookup
• …
• Iteration 11: walk back step=2 → 2 lookups
• Iteration 12: walk back step=4 → 4 lookups
• …
• Iteration N: walk back step=2^(N-11) → 2^(N-11) lookups

For a tip at 1.5M, total recursive iterations across all entries ≈ 2.1 M PK scans for a single locator build.

Proposed

Build all locator entries in a single SQL call. Two viable shapes:

Option A — Recursive CTE that emits at multiple heights

WITH RECURSIVE ChainBlocks AS (
    SELECT id, parent_id, height, 1 AS step_idx FROM blocks WHERE hash = $1
    UNION ALL
    SELECT bb.id, bb.parent_id, bb.height, cb.step_idx + 1
    FROM blocks bb JOIN ChainBlocks cb ON bb.id = cb.parent_id
    WHERE bb.height >= 0
)
SELECT id, hash, height FROM blocks
WHERE id IN (
    SELECT id FROM ChainBlocks
    WHERE height IN (<list of target heights computed in Go>)
)
ORDER BY height DESC

One round trip, one recursion pass.

Option B — Use unnest of target heights with main-chain fast-path

If we know the tip is on main chain (which is the common case — see companion main-chain fast-path issue):

SELECT b.* FROM blocks b
WHERE b.on_main_chain = true
  AND b.height = ANY($1::bigint[])
ORDER BY b.height DESC

Single index range scan on idx_on_main_chain_height, no recursion at all. Fall back to Option A only for off-main-chain tips.

Expected impact

• Round-trips to postgres drop from 12-21 per locator to 1
• For main-chain case (combined with the fast-path issue): zero recursive walk, just an index range scan
• For fork case (recursive needed): the recursion only happens once, not 21 times overlapping

Verification

• Unit test: existing and new code produce identical locator hash sequences for both main-chain and fork tips
• Bench: locator build latency before/after
• Integration: peer GetHeaders responses unchanged

Related

• (Main-chain fast-path issue) — Option B above is only viable if that issue's invariant holds. Ship that first; this issue is the natural consumer.
• (pskip skip-list issue) — Option A's recursive walk becomes O(log² N) once skip-list exists.
• This is the lowest-priority of the four blockchain-sql perf issues. Land (main-chain fast-path) and (drop unused indexes) first; revisit if locator generation is still a measurable cost.