ClickHouse / ClickHouse/ClickHouse

Index scan optimization for ASOF JOIN

Open
#38,444 0 comments 3 reactions 0 assignees View on GitHub
comp-joins external feature
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.