WIP: Optimize PK lookup for queries that match exact PK range#12277
WIP: Optimize PK lookup for queries that match exact PK range#12277CurtizJ merged 2 commits intoClickHouse:masterfrom
Conversation
30f8244 to
2436956
Compare
CurtizJ
left a comment
There was a problem hiding this comment.
Looks ok.
BTW, is it possible to support case, when continuos prefix of primary key is in WHERE clause, but not only when there is whole primary key?
Also 2 tests are failing.
|
My first version was to allow a prefix of a PK to engage this. E.g. if PK is
But the following isn't:
Is that what you mean? If so, I can totally make it happen. |
|
Yes, I meant that. |
060ac97 to
f22b382
Compare
|
I've added support for PK prefix matches and reorganized code a bit to increase code reuse. Tests should be happy now, the problem was twofold:
I've also added some trace logging with amount of matching steps performed, which I intend to add some tests on. Perhaps it can be integrated with Let me know what you think. |
ffc62b4 to
23b76a3
Compare
Existing code that looks up marks that match the query has a pathological
case, when most of the part does in fact match the query.
The code works by recursively splitting a part into ranges and then discarding
the ranges that definitely do not match the query, based on primary key.
The problem is that it requires visiting every mark that matches the query,
making the complexity of this sort of look up O(n).
For queries that match exact range on the primary key, we can find
both left and right parts of the range with O(log 2) complexity.
This change implements exactly that.
To engage this optimization, the query must:
* Have a prefix list of the primary key.
* Have only range or single set element constraints for columns.
* Have only AND as a boolean operator.
Consider a table with `(service, timestamp)` as the primary key.
The following conditions will be optimized:
* `service = 'foo'`
* `service = 'foo' and timestamp >= now() - 3600`
* `service in ('foo')`
* `service in ('foo') and timestamp >= now() - 3600 and timestamp <= now`
The following will fall back to previous lookup algorithm:
* `timestamp >= now() - 3600`
* `service in ('foo', 'bar') and timestamp >= now() - 3600`
* `service = 'foo'`
Note that the optimization won't engage when PK has a range expression
followed by a point expression, since in that case the range is not continuous.
Trace query logging provides the following messages types of messages,
each representing a different kind of PK usage for a part:
```
Used optimized inclusion search over index for part 20200711_5710108_5710108_0 with 9 steps
Used generic exclusion search over index for part 20200711_5710118_5710228_5 with 1495 steps
Not using index on part 20200710_5710473_5710473_0
```
Number of steps translates to computational complexity.
Here's a comparison for before and after for a query over 24h of data:
```
Read 4562944 rows, 148.05 MiB in 45.19249672 sec., 100966 rows/sec., 3.28 MiB/sec.
Read 4183040 rows, 135.78 MiB in 0.196279627 sec., 21311636 rows/sec., 691.75 MiB/sec.
```
This is especially useful for queries that read data in order
and terminate early to return "last X things" matching a query.
See ClickHouse#11564 for more thoughts on this.
23b76a3 to
d9d8d02
Compare
Conditions that are outside of PK are marked as `unknown` in `KeyCondition`, so it's safe to allow them, as long as they are always combined by `AND`.
This runs PK lookup and skipping index stages on parts in parallel, as described in ClickHouse#11564. While ClickHouse#12277 sped up PK lookups, skipping index stage may still be a bottleneck in a select query. Here we parallelize both stages between parts. On a query that uses a bloom filter skipping index to pick 2,688 rows out of 8,273,114,994 on a two day time span, this change reduces latency from 10.5s to 1.5s.
|
Hi @bobrik , sorry for reopening this pr after a long time. This is a nice optimisation, however, I'm curious why it doesn't apply when key condition has monotonic function chain? |
|
I don't remember what wasn't working with monotonic function chains. You are welcome to implement it. |
Changelog category:
Changelog entry:
Optimize PK lookup for queries that match exact PK range.
Detailed description / Documentation draft:
Existing code that looks up marks that match the query has a pathological case, when most of the part does in fact match the query. The code works by recursively splitting a part into ranges and then discarding the ranges that definitely do not match the query, based on primary key.
The problem is that it requires visiting every mark that matches the query, making the complexity of this sort of look up O(n).
For queries that match exact range on the primary key, we can find both left and right parts of the range with O(log 2) complexity.
This change implements exactly that.
To engage this optimization, the query must:
Consider a table with
(service, timestamp)as the primary key.The following conditions will be optimized:
service = 'foo'service = 'foo' and timestamp >= now() - 3600service in ('foo')service in ('foo') and timestamp >= now() - 3600 and timestamp <= nowThe following will fall back to previous lookup algorithm:
timestamp >= now() - 3600service in ('foo', 'bar') and timestamp >= now() - 3600service = 'foo'Note that the optimization won't engage when PK has a range expression followed by a point expression, since in that case the range is not continuous.
Trace query logging provides the following messages types of messages, each representing a different kind of PK usage for a part:
Number of steps translates to computational complexity.
Here's a comparison for before and after for a query over 24h of data:
This is especially useful for queries that read data in order
and terminate early to return "last X things" matching a query.
See #11564 for more thoughts on this.