feat(sql): speed up ASOF JOIN on indexed symbol column#6158
feat(sql): speed up ASOF JOIN on indexed symbol column#6158bluestreak01 merged 65 commits intomasterfrom
Conversation
core/src/main/java/io/questdb/griffin/engine/join/AsOfJoinIndexedRecordCursorFactory.java
Show resolved
Hide resolved
core/src/main/java/io/questdb/griffin/engine/join/AsOfJoinIndexedRecordCursorFactory.java
Outdated
Show resolved
Hide resolved
There was a problem hiding this comment.
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.
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. |
c1cd8f4 to
a0e3150
Compare
[PR Coverage check]😍 pass : 158 / 165 (95.76%) file detail
|
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.
'EUR', 'GBP', 'JPY', 'CAD', 'AUD'AUDappears only in the very first partitionWithout 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.