Summary

• HORIZON JOIN's keyed ASOF lookup now starts in backward-only mode (cheap for low-cardinality key spaces) and adaptively switches to forward scan mode within a frame when backward scan cost
  becomes excessive — e.g., with high-cardinality symbols or rare/infrequent keys that cause deep backward scans.
• The switch uses two criteria: a relative threshold (SWITCH_FACTOR=8, MIN_GAP=1,024) where backward scan cost at a position must exceed 8x the gap to trigger, and an absolute threshold (BWD_SCAN_ABSOLUTE_THRESHOLD=131,072) to handle cross-partition boundaries where the relative check cannot trigger. Once switched, the frame stays in forward mode for its remainder.
• Re-enables the ASOF row cache in HorizonJoinTimeFrameHelper and resets bookmarks on toTop() to eliminate jitter from out-of-order frame processing.

Background

The previous backward-only strategy (commit 6145bafc) clears the key map on each ASOF position change and backward-scans ~K rows to repopulate it. This is 30x faster than forward scan for K=50 FX symbols, but degrades badly when K is large (e.g., K=5,000 equity tickers) or when rare keys appear infrequently — each rare-key lookup scans thousands of rows backward to the beginning of the table.

The adaptive approach retains the backward-only advantage for the common low-K case while automatically switching to forward scan when the data distribution makes backward scans expensive.

How it works

Each frame starts in backward-only mode. On each ASOF position change, the algorithm compares the backward scan row count at the previous position against the gap (row distance) to the current position. If bwdScanCost > gap * 8 and gap > 1,024, it switches to forward scan mode permanently for that frame.

Gap calculation uses raw rowId subtraction (asOfRowId - prevAsOfRowId). For same-frame positions, this gives the exact row count. For cross-frame positions, the frame-index bits produce a value >= 2^44, which safely prevents the relative switch condition from triggering. An absolute threshold (bwdScanCost > 131,072) handles the cross-partition case — e.g., a deep backward scan for a rare key right before a partition boundary.

Benchmark results

Benchmarked with 100M-row market_data and 50K-row fx_trades tables across five data distribution scenarios (see this gist).

Test query:

SELECT
    t.symbol,
    t.side,
    h.offset / 1000000000 AS horizon_sec,
    count() AS n,
    avg(
        CASE t.side
            WHEN 'buy'  THEN ((m.best_bid + m.best_ask) / 2 - t.price)
                             / t.price * 10000
            WHEN 'sell' THEN (t.price - (m.best_bid + m.best_ask) / 2)
                             / t.price * 10000
        END
    ) AS avg_markout_bps,
    sum(
        CASE t.side
            WHEN 'buy'  THEN ((m.best_bid + m.best_ask) / 2 - t.price)
                             * t.quantity
            WHEN 'sell' THEN (t.price - (m.best_bid + m.best_ask) / 2)
                             * t.quantity
        END
    ) AS total_pnl
FROM fx_trades_xyz t
HORIZON JOIN market_data_xyz m ON (symbol)
    RANGE FROM 0s TO 30s STEP 5s AS h;

Dev box results

Environment: GraalVM CE 17, Ryzen 7900x, 64GB RAM

The _injected scenario is a synthetic worst case where rare symbols appear only once at the very beginning of market_data. Both master and patch handle it poorly (156s and 171s respectively). The patch regresses by 10% because backward-only mode must complete at least one deep scan before the adaptive switch triggers, whereas master's always-forward approach never clears the key map.

c6a.16xlarge EC2 instance results

The patch shows clear wins on dense (-21%), sparse (-96%, dramatic), rare (-19%), and equity (-13%). The injected scenario (rare symbols planted at the very start forcing full backward scans) is essentially unchanged (+1.4%, within noise).

The sparse result stands out — the adaptive scan switch appears to be extremely effective when the gap between LHS rows is large (~2000 market_data rows per trade) with few symbols.

Also, no huge jitter noticed: the worst jitter was ~26% and was in the equity scenario. In other scenarios it was within 3-10%.

Test plan

• Existing HorizonJoinTest (113 tests) and HorizonJoinFuzzTest pass
• New testHorizonJoinKeyedAdaptiveScanSwitch in HorizonJoinTest: deterministic test with a rare key at row 0 that triggers the backward-to-forward switch
• New testParallelHorizonJoinAdaptiveScan and testParallelHorizonJoinAdaptiveScan2 in ParallelHorizonJoinFuzzTest: parallel tests with microsecond-spaced data in one partition, comparing HORIZON JOIN results against reference UNION ALL of ASOF JOINs
• Manual benchmarking with test_distributions.sql scenarios (dense, sparse, rare, equity, injected) to verify switching behavior across different cardinalities and distributions