The Dense ASOF JOIN algorithm is a variant of the Light algorithm:

• Light algo starts the scan of the right-hand table at the top
• Dense algo uses binary search to quickly jump to the timestamp matching the first left-hand row

This difference is highly important when the right-hand table has history that predates the first left-hand row. The entire history will be skipped, except for some recent history needed to find matches of initial few left-hand rows.

Let's use the diagram below to explain the key differences among algorithms. It shows two tables, LHS and RHS. LHS rows are less densely distributed over time than RHS rows, but not much less. We show the rows aligned on timestamp, so there are gaps in the LHS column. These gaps don't represent any LHS rows, it is just the way we visualize the two tables.

row | LHS | RHS
----|-----|----
 1  |     | G
 2  |     | C
 3  |     | G
 4  |     | A
 5  |     | F
 6  |   A | B
 7  |     | D
 8  |     | B
 9  |   C | G
10  |     | F
11  |     | D
12  |   B | E
13  |     | D
14  |     | C
15  |   A | B

Light algo

Light algo uses a forward-only scan of the RHS table. When matching the first RHS symbol (row 6, symbol A), it starts from RHS row 1, and proceeds all the way to row 6, collecting all the symbols into a hashtable. When done, it looks up symbol A in the hashtable and finds the prevailing RHS row is row 4. When matching the next RHS symbol (row 9, symbol C), it resumes the forward scan, touching rows 7, 8 and 9. Then it looks up symbol C, and finds the prevailing row is row 2.

Fast algo

Fast algo uses binary search over RHS timestamps to zero in on row 6 as the most recent row not newer than the first LHS row. Then it scans backward: rows 6, 5, 4, and there it finds the matching symbol A. When matching the next LHS symbol (row 9, symbol C), it uses binary search to zero in on RHS row 9, then scans all the way back to row 2, where it finds symbol C.

When matching symbol A in row LHS row 15, it uses binary search to zero in or RHS row 15, then scans backward, again all the way back to row 4.

There's also an optimization that avoids the fixed cost of binary search by first searching linearly for the matching timestamp in the RHS row, for a smallish number of steps. This doesn't affect the backward search for the symbol.

Memoized algo

The Memoized algo is a variant of the Fast algo. It uses the exact same linear/binary search to find the matching timestamp in the RHS, and then uses the same backward search for the symbol. However, it memorizes for each symbol where it started the backward search, and where it found it.

In our example, this means it handles the first LHS row (6) exactly the same way, scanning backward to row 4. But when it encounters the same symbol A in row 15, it scans backward only until reaching row 6, and then directly uses the remembered result of the previous scan, and matches up with row 4.

With Drive-By caching enabled, Memoized algo will memorize not just the symbol it's looking for, but also any other symbol. However, it can only memorize it on the first encounter. This is valuable for rare symbols that occur deep in the past, but otherwise it just introduces more overhead.

Dense algo

The Dense algo starts like the Fast algo, performing a binary search to zero in on RHS row 6 and searching backward to find symbol A in row 4 of RHS. From then on, it behaves more like the Light algo.

To match up LHS row 9 (symbol C), it first does a linear scan forward from row 6 to row 9 (exactly like the Light algo). Since it didn't find C in this scan, it resumes the backward scan, touching rows 3 and 2, and there it finds the symbol C.

At LHS row 12 (symbol B), it resumes the forward scan, touching rows 10, 11, and 12. Then it finds symbol B in the hashtable, getting row 8 as the prevailing row. No backward scan nedeed here.

At LHS row 15 (symbol A), it resumes the forward scan, touching rows 13, 14, and 15. Then it looks up symbol A in the hashtable of the forward scan, finding nothing. Then it looks up symbol A in the hashtable of the backward scan, and finds it there. The prevailing row is number 4. Again, no backward search was needed.

Discussion

We can see that the Fast and Memoized algos had to touch the most rows. Especially, when matching row 15, Fast algo had to scan backward to row 4, and Memoized did only slighly better, scanning until row 6.

Light algo had to initially scan all the history (rows 1 to 6), but from then on, it only needed to touch the additional rows that came into scope as the LHS timestamp was moving on.

Dense algo had the same advantage as Light, but it didn't have to scan all the history. It scanned only as far back into history as needed to find the most recent occurence of a symbol not yet seen in the forward scan.

Additional changes in the PR

The PR also optimizes symbol-to-symbol joins for the existing Light and Fast algos. It works through the RecordSink, which decides what data to copy from the table row to a buffer for comparison. Instead of copying the symbol string, it puts just the symbol key, after mapping the left-hand to the right-hand symbol key.

After applying this to Light cursor, there was no more need for a dedicated Single Symbol Light cursor, so the PR removes it. There's still some performance gap between writing a dedicated cursor that directly works with symbol keys, but it's a 30% difference and it isn't worth it for the Light cursor.

The Dense cursor has two implementations, one specialized for symbol-to-symbol comparison. This cursor could be critical to the performance of markout analysis, so I thought it's worth it. The implementation works through an abstract class, avoiding code duplication.

Benchmarking

Measurements taken on r7a.4xlarge.

Tables

Trades: 167.5 million rows, Jan 2, 00:00 to Jan 2, 08:00
Prices: 1.01 billion rows, Jan 1, 16:00 to Jan 2, 08:00

Time period of prices is a 50/50 split between history and overlap with trades.

CREATE TABLE trades (
        symbol SYMBOL,
        side SYMBOL,
        price DOUBLE,
        amount DOUBLE,
        timestamp TIMESTAMP
) timestamp(timestamp) PARTITION BY DAY WAL;

INSERT INTO trades SELECT
    rnd_symbol_zipf(1_000, 2.0) AS symbol,
    rnd_symbol('buy', 'sell') as side,
    rnd_double() * 20 + 10 AS price,
    rnd_double() * 20 + 10 AS amount,
    generate_series as timestamp
  FROM generate_series('2025-01-02', '2025-01-02T08', '172u');

CREATE TABLE prices (
      ts TIMESTAMP,
      sym SYMBOL CAPACITY 1024,
      bid DOUBLE,
      ask DOUBLE
  ) timestamp(ts) PARTITION BY DAY;
INSERT INTO prices
  SELECT
      '2025-01-01T16'::timestamp + (57*x) + rnd_long(-20, 20, 0) as ts,
      rnd_symbol_zipf(1_000, 2.0),
      rnd_double() * 10.0 + 5.0,
      rnd_double() * 10.0 + 5.0
      FROM long_sequence(1_010_000_000);

Query

To avoid timeouts, we limit trades to 10 million rows for most measurements. In the end we do Asof Dense with the full dataset.

Fast (Default)

SELECT sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN prices p on (t.symbol=p.sym);

59 seconds

Memoized

SELECT /*+ asof_memoized(t p) */ sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN prices p on (t.symbol=p.sym);

42 seconds

Memoized with Drive-By Caching

SELECT /*+ asof_memoized_driveby(t p) */ sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN prices p on (t.symbol=p.sym);

63 seconds

Light

SELECT /*+ asof_linear(t p) */ sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN prices p on (t.symbol=p.sym);

9.7 seconds

Dense Single Symbol

SELECT /*+ asof_dense(t p) */ sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN prices p on (t.symbol=p.sym);

730 milliseconds

Dense Single Symbol, Full Dataset

The full dataset is 16.7 times larger than the limited one used above.

SELECT sum(bid)
FROM trades t
ASOF JOIN prices p on (t.symbol=p.sym);

10.9 seconds

Bonus: Light with no history

Here we remove the history part of prices table, so it covers only the time period present in trades. This brings Light and Dense to an equal footing in terms of algorithm. The remaining difference is the additional single-symbol specialization in Dense algo.

SELECT /*+ asof_linear(t p) */ sum(bid)
FROM (trades limit 10_000_000) t
ASOF JOIN (prices limit 505_263_157, 1_010_000_000) p on (t.symbol=p.sym);

1.17 seconds