ClickHouse / ClickHouse/ClickHouse
Index scan optimization for ASOF JOIN
- Dominant language
- C++
- Stars
- 49.9k
- Forks
- 9k
- Avg merge
- 17h 34m
- Merged PRs (30d)
- 479
Description
**Use case**
Find closest combination of key, timestamp, value for list of key, timestamp combinations.
IE during index scan ClickHouse will do:
1. Identify ranges/granules where needed exact key values could be
2. If possible (ie one key value spans multiple granules of single range), pick granules which has the closest timestamp value.
**Describe the solution you'd like**
```
CREATE TABLE tbl_asof
(
`key_a` UInt16,
`key_b` UInt16,
`ts` DateTime,
`value` UInt64
)
ENGINE = MergeTree
PARTITION BY toYYYYMM(ts)
ORDER BY (toDate(ts), key_a, key_b, ts);
INSERT INTO tbl_asof SELECT
rand() % 20,
rand(2) % 500,
toDateTime('2022-06-22 00:00:00') + intDiv(number, 100),
rand64()
FROM numbers(200000000);
OPTIMIZE TABLE tbl_asof FINAL;
WITH match_list AS
(
SELECT
key_a,
key_b,
needed_ts
FROM values('key_a UInt16, key_b UInt16, needed_ts DateTime', (0, 103, '2022-07-01 00:00:50'), (14, 56, '2022-07-05 20:00:50'))
)
SELECT
key_a,
key_b,
bnd.needed_ts,
src.ts,
src.value
FROM tbl_asof AS src
NEAREST ASOF INNER JOIN match_list AS bnd ON (src.key_a = bnd.key_a) AND (src.key_b = bnd.key_b) AND (src.ts <= bnd.needed_ts)
```
**Describe alternatives you've considered**
Today, it's kinda works via:
```
WITH match_list AS
(
SELECT
key_a,
key_b,
needed_ts,
CAST(needed_ts, 'Date') AS range_date
FROM values('key_a UInt16, key_b UInt16, needed_ts DateTime', (0, 103, '2022-07-01 00:01:50'), (14, 56, '2022-07-05 20:00:50'))
)
SELECT
key_a,
key_b,
bnd.needed_ts,
argMin(ts, abs(bnd.needed_ts - ts)) AS closest_ts,
argMin(value, abs(bnd.needed_ts - ts)) AS closest_value
FROM
(
SELECT *
FROM tbl_asof
WHERE indexHint((key_a, key_b, ts, toDate(ts)) IN (
SELECT
key_a,
key_b,
needed_ts,
range_date
FROM match_list
))
) AS src
INNER JOIN match_list AS bnd ON (src.key_a = bnd.key_a) AND (src.key_b = bnd.key_b)
WHERE src.ts <= bnd.needed_ts
GROUP BY
key_a,
key_b,
bnd.needed_ts
Query id: 2e8d8f1f-8b78-4dfc-9d1d-130a94360770
┌─key_a─┬─key_b─┬───────────needed_ts─┬──────────closest_ts─┬───────closest_value─┐
│ 14 │ 56 │ 2022-07-05 20:00:50 │ 2022-07-05 20:00:42 │ 4528928153456857409 │
│ 0 │ 103 │ 2022-07-01 00:01:50 │ 2022-07-01 00:01:31 │ 4673854066823742649 │
└───────┴───────┴─────────────────────┴─────────────────────┴─────────────────────┘
2 rows in set. Elapsed: 0.012 sec. Processed 16.39 thousand rows, 262.16 KB (1.31 million rows/s., 21.04 MB/s.)
```
But there is problem with PARTITION pruning (partially fixable via https://github.com/ClickHouse/ClickHouse/issues/38443) by simple disable it
And toDate(ts) condition which force us to define potential limit on how far we should look for nearest timestamp
**Additional context**
RIGHT table in JOIN used for filtering related https://github.com/ClickHouse/ClickHouse/issues/21047
Contributor guide
Research direction
Start by reproducing the provided ASOF JOIN example and compare it with the current workaround using indexHint and argMin. Read the related issues #38443 and #21047 for partition pruning and right-table filtering context; the work is done when index scanning can select relevant granules and nearest timestamps without requiring a manual date-range limit.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, sql
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100