ClickHouse gets lazier and faster: Introducing lazy materialization
1–10 of 130 posts
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#2Unrelated to the new materialization option, this caught my eye:
"this query sorts all 150 million values in the helpful_votes column (which isn’t part of the table’s sort key) and returns the top 3, in just 70 milliseconds cold (with the OS filesystem cache cleared beforehand) and a processing throughput of 2.15 billion rows/s"
I clearly need to update my mental model of what might be a slow query against modern hardware and software. Looks like that's so fast because in a columnar database it only has to load that 150 million value column. I guess sorting 150 million integers in 70ms shouldn't be surprising.
(Also "Peak memory usage: 3.59 MiB" for that? Nice.)
This is a really great article - very clearly explained, good diagrams, I learned a bunch from it.
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#3This optimization should provide dramatic speed-ups when taking random samples from massive data sets, especially when the wanted columns can contain large values. That's because the basic SQL recipe relies on a LIMIT clause to determine which rows are in the sample (see query below), and this new optimization promises to defer reading the big columns until the LIMIT clause has filtered the data set down to a tiny number of lucky rows.
SELECT *
FROM Population
WHERE weight > 0
ORDER BY -LN(1.0 - RANDOM()) / weight
LIMIT 100 -- Sample size.
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#4Unrelated to the new materialization option, this caught my eye: "this query sorts all 150 million values in the helpful_votes column (which isn’t part of the table’s sort key) and returns the top 3, in just 70 milliseconds cold (with the OS filesystem cache cleared beforehand) and a processing throughput of 2.15 billion rows/s" I clearly need to update my mental model of what might be a slow query against modern har…
> I guess sorting 150 million integers in 70ms shouldn't be surprising.
I find sorting 150M integers at all to be surprising. The query asks for finding the top 3 elements and returning those elements, sorted. This can be done trivially by keeping the best three found so far and scanning the list. This should operate at nearly the speed of memory and use effectively zero additional storage. I don’t know whether Clickhouse does this optimization, but I didn’t see it mentioned.
Generically, one can find the kth best of n elements in time O(n):
https://en.m.wikipedia.org/wiki/Selection_algorithm
And one can scan again to find the top k, plus some extra if the kth best wasn’t unique, but that issue is manageable and, I think, adds at most a factor of 2 overhead if one is careful (collect up to k elements that compare equal to the kth best and collect up to k that are better than it). Total complexity is O(n) if you don’t need the result sorted or O(n + k log k) if you do.
If you’re not allowed to mutate the input (which probably applies to Clickhouse-style massive streaming reads), you can collect the top k in a separate data structure, and straightforward implementations are O(n log k). I wouldn’t be surprised if using a fancy heap or taking advantage of the data being integers with smallish numbers of bits does better, but I haven’t tried to find a solution or disprove the existence of one.
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#5This optimization should provide dramatic speed-ups when taking random samples from massive data sets, especially when the wanted columns can contain large values. That's because the basic SQL recipe relies on a LIMIT clause to determine which rows are in the sample (see query below), and this new optimization promises to defer reading the big columns until the LIMIT clause has filtered the data set down to a tiny nu…
Verified:
EXPLAIN plan actions = 1
SELECT *
FROM amazon.amazon_reviews
WHERE helpful_votes > 0
ORDER BY -log(1 - (rand() / 4294967296.0)) / helpful_votes
LIMIT 3
Note that there is a setting query_plan_max_limit_for_lazy_materialization (default value 10) that controls the max n for which lm kicks in for LIMIT n.
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#6Unrelated to the new materialization option, this caught my eye: "this query sorts all 150 million values in the helpful_votes column (which isn’t part of the table’s sort key) and returns the top 3, in just 70 milliseconds cold (with the OS filesystem cache cleared beforehand) and a processing throughput of 2.15 billion rows/s" I clearly need to update my mental model of what might be a slow query against modern har…
> I guess sorting 150 million integers in 70ms shouldn't be surprising. I find sorting 150M integers at all to be surprising. The query asks for finding the top 3 elements and returning those elements, sorted. This can be done trivially by keeping the best three found so far and scanning the list. This should operate at nearly the speed of memory and use effectively zero additional storage. I don’t know whether Click…
> This can be done trivially by keeping the best three found so far and scanning the list.
That doesnt seem to guarantee correctness. If you dont track all of the unique values, at least, you could be throwing away one of the most common values.
The wiki entry seems to be specifically about the smallest, rather than largest values.
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#7This optimization should provide dramatic speed-ups when taking random samples from massive data sets, especially when the wanted columns can contain large values. That's because the basic SQL recipe relies on a LIMIT clause to determine which rows are in the sample (see query below), and this new optimization promises to defer reading the big columns until the LIMIT clause has filtered the data set down to a tiny nu…
I checked, and yes - it works: https://pastila.nl/?002a2e01/31807bae7e114ca343577d263be7845...
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#8Unrelated to the new materialization option, this caught my eye: "this query sorts all 150 million values in the helpful_votes column (which isn’t part of the table’s sort key) and returns the top 3, in just 70 milliseconds cold (with the OS filesystem cache cleared beforehand) and a processing throughput of 2.15 billion rows/s" I clearly need to update my mental model of what might be a slow query against modern har…
[deleted]
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#9Earlier quoted context omitted.
> I guess sorting 150 million integers in 70ms shouldn't be surprising. I find sorting 150M integers at all to be surprising. The query asks for finding the top 3 elements and returning those elements, sorted. This can be done trivially by keeping the best three found so far and scanning the list. This should operate at nearly the speed of memory and use effectively zero additional storage. I don’t know whether Click…
> This can be done trivially by keeping the best three found so far and scanning the list. That doesnt seem to guarantee correctness. If you dont track all of the unique values, at least, you could be throwing away one of the most common values. The wiki entry seems to be specifically about the smallest, rather than largest values.
What? The algorithm is completely symmetrical with respect to smallest or largest, and fully correct and general. I don't understand the problem with unique values. Could you provide a minimal input demonstrating the issue?
Re: ClickHouse gets lazier and faster: Introducing lazy materialization
#10Earlier quoted context omitted.
> I guess sorting 150 million integers in 70ms shouldn't be surprising. I find sorting 150M integers at all to be surprising. The query asks for finding the top 3 elements and returning those elements, sorted. This can be done trivially by keeping the best three found so far and scanning the list. This should operate at nearly the speed of memory and use effectively zero additional storage. I don’t know whether Click…
> This can be done trivially by keeping the best three found so far and scanning the list. That doesnt seem to guarantee correctness. If you dont track all of the unique values, at least, you could be throwing away one of the most common values. The wiki entry seems to be specifically about the smallest, rather than largest values.
With an equality that returns true/false, this guarantees correctness. If there can be 3 best/biggest/smallest values, this technique works.