Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

ClickHouse gets lazier and faster: Introducing lazy materialization

clickhouse.com

Post reply on HN
Print view View original

11–20 of 130 posts

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#11

Post by Akronymus »

recursive wrote: post #9
Akronymus wrote: post #6

Earlier quoted context omitted.

> 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?

I cant because I completely misread the wiki article before commenting and have now read it more carefully and realized I was wrong. Specifically I went in thinking about top 3 most common value.

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#12

Post by senderista »

Akronymus wrote: post #6
amluto wrote: post #4

Earlier 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.

The max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the streaming context because it requires random access and in-place mutation.)

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#13

Post by baq »

simonw wrote: post #2

Unrelated 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…

Slow VMs on overprovisioned cloud hosts which cost as much per month as a dedicated box per year have broken a generation of engineers.

You could host so much from your macbook. The average HN startup could be hosted on a $200 minipc from a closet for the first couple of years if not more - and I'm talking expensive here for the extra RAM you want to not restart every hour when you have a memory leak.

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#14

Post by Akronymus »

senderista wrote: post #12
Akronymus wrote: post #6

Earlier quoted context omitted.

> 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.

The max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the strea…

My failure was misreading it as most common k rather than max k.

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#15

Post by senderista »

Akronymus wrote: post #14
senderista wrote: post #12

Earlier quoted context omitted.

The max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the strea…

My failure was misreading it as most common k rather than max k.

Most common k is super-interesting because it can't be solved in one pass in constant space!

https://en.wikipedia.org/wiki/Streaming_algorithm#Frequent_e...

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#16

Post by tmoertel »

tschreiber wrote: post #5
tmoertel wrote: post #3

This 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 Lazily read columns: review_body, review_headline, verified_purchase, vine, total_votes, marketplace, star_rating, product_category, customer_id, product_title, product_id, product_parent, review_date, review_id Note that there is a setting query_plan_max_li…

Awesome! Thanks for checking :-)

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#18

Post by amluto »

senderista wrote: post #12
Akronymus wrote: post #6

Earlier quoted context omitted.

> 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.

The max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the strea…

To be fair to quickselect, I can imagine a lazy data processing framework having a concept of a lazily sorted data column where the actual data has been materialized but it’s not in sorted order yet. Then someone does “LIMIT k” to it, and the framework can go to town with quickselect.

As noted a couple times in this thread, there are all kinds of tradeoffs here, and I can’t imagine quickselect being even close to competitive for k that is small enough to fit in cache. Quickselect will, in general, scan a large input approximately twice. For k = 3, the answer fits in general-purpose registers or even in a single SIMD register, and a single scan with brute force accumulation of the answer will beat quickselect handily and will also beat any sort of log-time heap.

(In general, more advanced and asymptotically better algorithms often lose to simpler brute force algorithms when the parameters in question are smallish.)

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#19

Post by senderista »

amluto wrote: post #18
senderista wrote: post #12

Earlier quoted context omitted.

The max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the strea…

To be fair to quickselect, I can imagine a lazy data processing framework having a concept of a lazily sorted data column where the actual data has been materialized but it’s not in sorted order yet. Then someone does “LIMIT k” to it, and the framework can go to town with quickselect. As noted a couple times in this thread, there are all kinds of tradeoffs here, and I can’t imagine quickselect being even close to com…

Yeah, obviously I wouldn't bother with a heap for k=3. A heap has good compactness but poor locality, so I guess it wouldn't perform well out of (some level of) cache.

Re: ClickHouse gets lazier and faster: Introducing lazy materialization

#20

Post by tmoertel »

zX41ZdbW wrote: post #7
tmoertel wrote: post #3

This 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...

Thanks! That's a nice 5x improvement. Pretty good for a query that offers only modest opportunity, given that the few columns it asks for are fairly small (`title` being the largest, which isn't that large).
Post reply on HN