Skip to content

feat(sql): speed up ASOF JOIN on indexed symbol column#6158

Merged
bluestreak01 merged 65 commits intomasterfrom
mt_asof-join-index
Sep 25, 2025
Merged

feat(sql): speed up ASOF JOIN on indexed symbol column#6158
bluestreak01 merged 65 commits intomasterfrom
mt_asof-join-index

Conversation

@mtopolnik
Copy link
Copy Markdown
Contributor

@mtopolnik mtopolnik commented Sep 18, 2025

Leverage the symbol index on the right-hand side of the ASOF JOIN, avoiding the need to visit any rows that don't have the matching symbol.

Where this matters

The major use case for this optimization is markout analysis.

For a given trade, you want to see whether you could have got a better deal if you placed your order a bit sooner or a bit later. In a representative example, you inspect a window of +/- 10 minutes around the trade, amounting to 1200 points in time (one per second).

When dealing with FOREX, you need two numbers for each trade: USD rate of currency you're selling, and of the currency you're buying. There's a single table that contains all price changes for all currencies.

Therefore this analysis requires 2400 lookups of a matching RHS row (USD rate) for each LHS row (trade event), conditioned on the currency symbol. The worst problem are illiquid assets, having their last price posted way back in the past.

The current code will scan all the rows backwards until it finds a match. The new code makes only one symbol index lookup per partition. So, if the last asset price was posted 30 days ago, that's 30 lookups vs. scanning the full 30 days of currency price updates, for all currencies.

Benchmark

I did a quick ad-hoc benchmark set up as follows.

  1. Price table:
CREATE TABLE prices (
      ts TIMESTAMP,
      sym SYMBOL,
      price DOUBLE
  ) timestamp(ts) PARTITION BY DAY;
  • Five currency symbols: 'EUR', 'GBP', 'JPY', 'CAD', 'AUD'
  • 320 million rows, one per second -> 3700 partitions
  • AUD appears only in the very first partition
  1. Trade event table:
CREATE TABLE orders (
    order_id LONG,
    order_completed_ts TIMESTAMP,
    sym1 SYMBOL,
    sym2 SYMBOL,
    quantity DOUBLE
) timestamp(order_completed_ts) PARTITION BY DAY;

INSERT INTO order VALUES
  (1001, '2025-09-09T09:00:00.000000Z', 'EUR', 'GBP', 50000.0),
  (1002, '2025-09-09T09:00:03.000000Z', 'GBP', 'JPY', 25000.0),
  (1003, '2025-09-09T09:00:07.000000Z', 'CAD', 'AUD', 75000.0),
  (1004, '2025-09-09T09:00:12.000000Z', 'JPY', 'EUR', 12500000.0),
  (1005, '2025-09-09T09:00:15.000000Z', 'EUR', 'CAD', 80000.0),
  (1006, '2025-09-09T09:00:21.000000Z', 'EUR', 'JPY', 45000.0),
  (1007, '2025-09-09T09:00:26.000000Z', 'GBP', 'CAD', 30000.0),
  (1008, '2025-09-09T09:00:32.000000Z', 'AUD', 'EUR', 60000.0),
  (1009, '2025-09-09T09:00:38.000000Z', 'CAD', 'GBP', 35000.0),
  (1010, '2025-09-09T09:00:43.000000Z', 'JPY', 'AUD', 15000000.0);
  1. Query:
WITH
  offsets AS (
      SELECT x-601 AS sec_offs FROM long_sequence(1201)
  ),
  orders AS (
    SELECT id, order_ts, sym1, sym2 FROM orders
  ),
  points AS (
    SELECT orders.*, offsets.sec_offs, order_ts + 1_000_000 * sec_offs AS ts
    FROM orders CROSS JOIN offsets
    ORDER BY order_ts + 1_000_000 * sec_offs
  ),
  rslt1 AS (
    SELECT t.*, p.price AS sym1_price
    FROM points as t
    ASOF JOIN prices as p
    ON (t.sym1 = p.sym)
  ),
  rslt2 AS (
    SELECT t.*, p.price AS sym2_price
    FROM rslt1 as t
    ASOF JOIN prices as p
    ON (t.sym2 = p.sym)
  )
SELECT id, sec_offs, sym1_price/sym2_price AS price FROM rslt2
WHERE sym1_price is not null and sym2_price is not null
ORDER BY id, sec_offs;

Without the symbol index, the query times out. Profiling the query in more detail, one trade row at a time, a clear pattern shows up: if the row involves AUD, it's super-slow.

With the symbol index, the query is done within a second.

Copy link
Copy Markdown
Contributor

@puzpuzpuz puzpuzpuz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've tried to compare the new factory with the old one in a degenerate case:

create table trades AS (
  select 'BTC-USD'::symbol symbol, x::double price, 42.0 amount, x::timestamp as ts
  from long_sequence(1_000_000)
), index(symbol) timestamp(ts);

-- new factory: 3.7s
-- old factory: 50ms
select sum(t2.price)
from trades t1
asof join trades t2 on t1.symbol = t2.symbol;

@mtopolnik do the results make sense to you? If so, maybe we should introduce a hint to disable index usage? We already have a few hints, e.g. avoid_asof_binary_search, but not the index one.

@mtopolnik
Copy link
Copy Markdown
Contributor Author

mtopolnik commented Sep 25, 2025

@mtopolnik do the results make sense to you? If so, maybe we should introduce a hint to disable index usage? We already have a few hints, e.g. avoid_asof_binary_search, but not the index one.

I profiled this query, time is spent in the code that looks through the index to find the starting row. It involves traversing a linked list backwards. In this degenerate case, all rows are in the index, but there's no dead-reckoning way of going straight to a given row. So it degrades into linear search.

@puzpuzpuz
Copy link
Copy Markdown
Contributor

@mtopolnik do the results make sense to you? If so, maybe we should introduce a hint to disable index usage? We already have a few hints, e.g. avoid_asof_binary_search, but not the index one.

I profiled this query, time is spent in the code that looks through the index to find the starting row. It involves traversing a linked list backwards. In this degenerate case, all rows are in the index, but there's no dead-reckoning way of going straight to a given row. So it degrades into linear search.

@bluestreak01 @nwoolmer it sounds like our symbol index could be enhanced by adding a sparse index of blocks - the goal is to speed up row id-based block search. See #6158 (review) for the overhead of the block search.

@glasstiger
Copy link
Copy Markdown
Contributor

[PR Coverage check]

😍 pass : 158 / 165 (95.76%)

file detail

path covered line new line coverage
🔵 io/questdb/griffin/engine/table/SelectedRecordCursorFactory.java 0 1 00.00%
🔵 io/questdb/griffin/engine/table/TimeFrameRecordCursorImpl.java 5 7 71.43%
🔵 io/questdb/griffin/engine/join/AsOfJoinIndexedRecordCursorFactory.java 67 71 94.37%
🔵 io/questdb/griffin/engine/join/AsOfJoinNoKeyFastRecordCursorFactory.java 1 1 100.00%
🔵 io/questdb/griffin/engine/join/AbstractAsOfJoinFastRecordCursor.java 6 6 100.00%
🔵 io/questdb/griffin/engine/join/LtJoinNoKeyFastRecordCursorFactory.java 1 1 100.00%
🔵 io/questdb/griffin/engine/join/AsOfJoinFastRecordCursorFactory.java 12 12 100.00%
🔵 io/questdb/griffin/engine/join/FilteredAsOfJoinNoKeyFastRecordCursorFactory.java 1 1 100.00%
🔵 io/questdb/griffin/engine/join/AbstractKeyedAsOfJoinRecordCursor.java 47 47 100.00%
🔵 io/questdb/griffin/engine/join/FilteredAsOfJoinFastRecordCursorFactory.java 1 1 100.00%
🔵 io/questdb/griffin/SqlCodeGenerator.java 17 17 100.00%

@bluestreak01 bluestreak01 merged commit f1c0d7a into master Sep 25, 2025
33 of 35 checks passed
@bluestreak01 bluestreak01 deleted the mt_asof-join-index branch September 25, 2025 16:34
@tris0laris tris0laris moved this from Imminent Release to Shipped in QuestDB Public Roadmap (Legacy) Oct 3, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Performance Performance improvements SQL Issues or changes relating to SQL execution

Projects

Development

Successfully merging this pull request may close these issues.

5 participants