ClickHouseがさらに怠惰に、そして爆速に！遅延マテリアライズでマジ？
引用元：https://news.ycombinator.com/item?id=43763688
この最適化で､大量のデータセットからランダムサンプル取る時､特に大きな値のcolumnで劇的なスピードアップが見込めるはず｡基本のSQLレシピはLIMIT clauseでサンプル行を決めるから､この最適化でデータセットが絞り込まれるまでcolumnの読み込みを遅らせるってことだね｡ClickHouseの人､この最適化が効くか検証してほしいな｡
確認してみたよ｡ちゃんと動くね｡https://pastila.nl/?002a2e01/31807bae7e114ca343577d263be7845…
サンクス！5倍も速くなった｡columnが小さいから､そこまで期待してなかったけど､いいね｡
検証済み｡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 query_plan_max_limit_for_lazy_materialization (default value 10) って設定でLIMIT nのnを制御できるよ｡
質問させて｡なんでdefault limitがこんなに低いの？lazy materializationのデメリットって何？どんなクエリでlazy materializationが性能を悪化させるか知りたいな｡
limit値が大きいと､ランダムI/Oが多くなる可能性があるからじゃないかな｡ClickHouseが通常シーケンシャルに読み込むよりも予測できない順序で読み込むことになる｡articleにある例みたいな特殊なケースでは有利だけど､実際にはそうでもないってことだと思う｡
マジ感謝です！チェックしてくれてありがとうね｡
ORDER BYとLIMITの後にcolumnをmaterializeするから､サンプリングクエリには最適化が効くはず｡でも､randomization functionが早期評価を強制するかも｡ベンチマークで両方試す価値あり｡
ClickHouseマジで好き｡最近見つけたんだけど､今まで使ってた最適化されてないソリューションと比べて､マジ最高｡めっちゃ速いし､CLIも使いやすい｡
ClickHouseはずっと軽視してたんだよね｡だって､めっちゃローレベルじゃん｡信頼できるシステム作るには､内部構造を知り尽くしてないとダメそうだし｡問題起きた時､ディスク上のファイルを直接操作する必要があるDBなんて､他に知らないし｡でも､見てみたら､マジで速い｡raw speedのために最適化されてるって感じ｡
ClickHouseってマジで大人のLEGOみたいに感じるの、めっちゃわかるわー。データ構造とかデータストレージのレイアウトを自分で設計できるのに、全部自分で実装しなくてもいいのが最高。大規模なシステムで作業してるなら、こういうシステムがマジで欲しいんだよね。
めっちゃわかる。PostgresとかMicrosoft SQL Serverの経験しかない俺でも、テキストファイルからリアルデータを読み込んで、午後のうちにClickHouseを使いこなせるようになった。ドキュメントもソフトウェアのパフォーマンスもマジですごいと思った。
SQLみたいなシンタックスで、全部普通のDBみたいに使えるのがマジで助かる。もちろん、裏では全然違う動きしてるんだけど、新しいデータモデルを使うために新しいことを色々覚えなくていいのはマジで良いアプローチだと思う。新しい言語を作る理由もわかるけど、ClickHouseのトレードオフはマジで正解だと思うわ。
数年前はClickHouseって「レガシー」で「かさばる」ってイメージで、「大企業」が使うものって感じだったのに、最近はマジで変わったよね。こんな場所で議論されるようになったんだから、すごい進化だわ。
2017年から2023年の間に、プライバシーの問題でGoogle Analyticsの競合がいっぱい出てきて、その多くが最初はPostgresとかMySQLを使ってたけど、ClickHouseに乗り換えたか、最初からClickHouseを選んだんだよね。スケールが全然違うからね。少なくとも2021年までには、ClickHouseの実力は有名だったはず。レガシーとかかさばるとか、そういうイメージはなかったと思う。HNでもClickHouseの記事はよくフロントページに上がってたし。あと、UmamiがついにClickHouseをサポートするらしい！Postgresも必要みたいだけど、スケールはめっちゃ良くなるはず。[1] https://github．com/umami-software/umami/issues/3227
レガシーとかかさばるとかじゃないけど、エンタープライズ向けって感じだったのかも？ClickHouseを聞いた時の反応が、Oracleを聞いた時と似てた気がする。
ヘビーデューティーって感じかな？でも、ClickHouseがYandexから出たものだから、懐疑的な人も多かった気がする。しかも、戦争の前からね。
ClickHouseはそういう評判だったよね。でも、2021年にYandexからスピンアウトしたんだよ。それが新しい開発の波を起こして、めっちゃ良くなったんだよね。
なるほど、それで色々納得だわ。
ClickHouseってduckdbとかpolarsと比べてどうなの？
この分野は動きが早いから、詳しい分析もすぐ古くなっちゃうんだよね。でも、1年半くらい前のこの記事はすごく良くまとまってるよ。→https：//bicortex.com/duckdb-vs-clickhouse-performance-compar…
DuckDBって、ClickHouseみたいに書き込みに最適化された独自のストレージ持ってないんだよね。Parquetとか他のフォーマットから読み込むのがメイン。既存のファイルの上で分析するならいいんだけど、リアルタイム分析には向かないかも。ClickHouseはそっち向けだけど、スタンドアロンサービスになっちゃうのが難点。
いやいや、DuckDBにも独自のフォーマットあるよ。（書き込みに強いかは知らないけど、たぶんそうだと思う。）
DuckDBはネイティブで同時書き込みできないんだよね。DuckDBの設計思想的に。詳しくはここ見て→https：//duckdb.org/docs/stable/connect/concurrency.html#writ…
できるけど、パフォーマンスはイマイチらしいよ。→https：//github.com/duckdb/duckdb/discussions/10161
まあ、よく分かんないけど。でもOLAPの世界じゃ、その議論は古いんだよね。今はパフォーマンスが劇的に良くなってる可能性もあるかも。
Clickhouseはネットワークサーバーで、duckdbとpolarsはインプロセスデータベース。例えるならpostgres vs sqlliteみたいな感じ。
chdbってのもあるよ。
materializationオプションとは関係ないけど、この記事の「1億5千万の値をソートして上位3件を70msで返す」って部分に目が留まった。カラム指向DBだと特定のカラムだけ読み込めばいいから速いんだね。それにメモリ使用量も少ないし！この記事すごく分かりやすいし、勉強になった。
1億5千万個の整数を70msでソートするのが驚くべきことじゃないってのはわかるけど、そもそもそんな大量の整数をソートすること自体にビックリだわ。クエリは上位3つを見つけてソートして返すんだよね。これなら、見つけた上位3つを保持してリストをスキャンするだけで済むじゃん。メモリの速度とほぼ同じで、追加のストレージもほぼ不要なはず。Clickhouseがこの最適化をしてるかは知らんけど。一般的に、n個の要素からk番目に良いものをO(n)で見つけられるし、上位k個を再度スキャンするのも簡単。ミューテートがダメなら、別のデータ構造に上位k個を保存すればO(n log k)でできる。もっと良い方法もあるかもだけど。
もっとコメントを表示（1）
上位3つを保持してスキャンする方法だと、正確性が保証されないんじゃない？ユニークな値を全部追跡しないと、一番多い値を捨ててしまう可能性があるよ。Wikiの記事は、最小値について書いてあるみたいだし。
上で言及されてるmax-heapアルゴリズムは正しいよ。最初にk個の値を入れて、その後は最大要素を覗き見する。現在の値が最大要素より小さければ、最大要素を追い出して新しい要素を入れる。このストリーミングtop-kアルゴリズムは、leetcodeの面接とかアプリでよく使われるよ。
過剰なクラウドホスト上の遅いVMのせいでエンジニアリングがおかしくなってる気がする。MacBookからでもホストできることたくさんあるのに。スタートアップなら最初の数年はミニPCで十分だよ。
quickselectを擁護するわけじゃないけど、遅延データ処理フレームワークで、データはマテリアライズされてるけどソートされてない「遅延ソートされたデータカラム」って概念があるかもね。誰かが“LIMIT k”したら、quickselectが使える。トレードオフは色々あるけど、kがキャッシュに収まるくらい小さいなら、quickselectは競争力がないと思う。
k=3ならheapは使わないな。heapはコンパクトだけど局所性が悪いから、キャッシュの外だと性能が出ないかも。
一番多かったk個じゃなくて、最大のk個だと読み間違えたのが失敗だった。
一番多いk個はマジで面白い問題だよね。定数スペースで1回のパスで解決できないからね！https://en.wikipedia.org/wiki/Streaming_algorithm#Frequent_e…
quickselectは複数回のパスが必要で、heapはO(n log k)の時間が必要。でも、O(n)の時間とO(k)のスペースでトップk個を見つけられるよ。バッファを2*k個まで保持して、ストリームを1つずつスキャンする。バッファが一杯になったら、quickselectでk個に減らす。
ざっくり計算してみよう。1億5千万個のu32整数は600MB。最近のSSDなら14,000MB/sでシーケンシャルリードできるから、600MBの読み込みは43ms。DDR4メモリなら25GB/sだから24ms。L1/L2キャッシュなら1TB/s。CPUが32個あるから、L1/L2の帯域幅は32TB/s。600MBを0.018msで処理できる。70msの予算があれば、166回処理できる。quickselectみたいなランク選択アルゴリズムはO(N)だから、70msで600MBを処理するのは全然可能。
max-heapみたいなの使わずに、どうやって効率的に一番ダメな要素を追跡するんだろ？これ面白いアルゴリズムだね。前に見たことある気がするけど、どこで見たか思い出せない。どこで知ったの？
125 MiB/sのSSD使ってるって言ってるけど、このカラムってユニークな値が47500個くらいしかないみたいだね。多分、投票がゼロか1件のレビューが多いんだろうな。このカラムは圧縮されてるから、もっと早くロードできるのかも。
もしxがworstより大きかったら、worst = x
確かにそうだね。データ領域が小さいと、1億6千万の値の中に重複が多いから、データはかなり圧縮できるはず。
macbookの話をするな！クラウドなら数百GiBのRAMが使えるんだよ。Macbookで同じことしようとしたら、クラウドの料金より高くなる。
なんでそれが面白いんだ？最悪のケースは、n個中n-1個がユニークな要素で、最後の要素が重複する場合だよね。それだとO(n)のスペースが必要になるのは避けられない。どの要素が一番多いかわからないから、全部保持しなきゃいけない。
え？このアルゴリズムは、最小と最大で完全に左右対称だし、完全に正しくて一般的だよ。ユニークな値の問題が理解できない。問題を示す最小限の入力を教えて。
記事に70 Mbのストレージを使ってるって書いてあった。もしソートされてたら（つまりインデックスだったら）、もっと少ないスペースで済むはず。でも、70 msで125 MiB/sのSSDを使って70 Mbのデータをロードできたのが理解できない。
計算能力だけ見れば、ほぼ正しい（クラウドホストはオーバープロビジョニングされてないから、CPUとかメモリとかディスクは全部使える）。でも、計算能力だけじゃなくて、データベースとかキャッシュとかメッセージブローカーとかスケジューラーとか、メール送信とか、色々必要になるんだよ。FOSSソフトで自作できるけど、時間がかかる。お金があるなら既製のサービスを使った方がいい。時間がないなら自作も勉強になる。
それが根本的な原因だとは思えないな。ClickHouseとかSnowflakeは、オーバープロビジョニングされたクラウドの遅いVM上で動いてるけど、めちゃくちゃ効率的だよ。要は最適化次第。問題は、エンジニアのほとんどが、単純なコードに対して過剰なプロビジョニングをして、非効率な4次言語を使って、5種類の無駄な（個人的には）抽象化の上に構築していること。
なるほどねー。maxとかminとかsumを保持するのは簡単だよね。insertだけなら。削除はまとめてやるから、その時に線形コスト払ってbucketを作り直せばいいし。うちの場合はもっと簡単で、bufferの中で一番悪いelementはpruningの時にしか更新されないんだ。最初k個は特別扱いだけど、それ以外はworstより良いelementしかinsertしないから、更新する必要ないんだよね。
set membershipの線形空間の下限にも同じような議論が当てはまるよね。でも、こういう線形下限があるから、sublinearな近似テクニックを探すモチベーションになるんだよね(Bloom filterとかfingerprint tableは実際にはsublinearじゃないけど)。
mutableじゃないstreaming inputなら、O(k)の追加メモリだけでunsorted top kをO(n)で取得できるアルゴリズムがあるよ。2kのbufferを維持して、mutable unsorted top kを動かして、小さい方の半分を捨てて、次のk個をstreamすればいいんだ。sortは最後にすればいいし。
それ引用してるやつ、全然違う問題を解いてるじゃん。一般的なmost common kを求めるものじゃないよ。
あー、そっか。evictはbottom halfをpruningする時だけだ。
もしかしたらそういうoptimizationがあるから、~600MBのintegerに対して3.59 MiBのpeak memory usageなのかもね。
最終的な行セットに含まれない可能性のある列値を持つ行がないデータブロックを読み込む必要はない。すべてのgranuleのすべての列に、そのgranule内で見られる最小値と最大値を含むヘッダーがある場合、ClickHouseは列データを読み込む必要なく、granuleごとに列ヘッダーのみを読み取って確認できる。
「遅いクエリ」と「速いクエリ」に関する最新の直感は、過小評価されているソフトウェアエンジニアリングのスキルだと思う。こういうブログを読むだけでも価値がある。
true/falseを返すequalityなら、これで正確性が保証されるね。best/biggest/smallest valueが3つありえるなら、このテクニックは使えるよ。
ごめん、wikiの記事を完全に読み間違えてコメントしちゃった。もっと注意深く読んだら、自分が間違ってたことに気づいた。特にtop 3 most common valueについて考えてたんだ。
Late Materializationって概念、19年も前からあったんだね。マジか。https://dspace.mit.edu/bitstream/handle/1721.1/34929/MIT-CSA…
もっとコメントを表示（2）
columnar/vectorized executionも同じようなもんでしょ。OLAPのワークフローにはそれが“正しい”データ処理だって昔から知られてたけど、ここ数年でやっと“主流”になった感じ（ほとんどarrowのおかげ）。ClickHouseが今頃採用するのはちょっとなー。でも、analytics処理で標準じゃないのは残念。
ClickHouseの方がApache Arrowより前からあるよ。
C-storeの考え方が全然浸透してない気がする。ClickHouseの場合は、オープンソースのブートストラップ型プロジェクトだったから仕方ないかもだけど。資金注入で基本的な再設計してるみたいだし。でも、Verticaをゆっくり再実装するのはビジネスモデルとしてどうなんだろ。
ClickHouseにWSLとかLinuxの仮想マシンいらないWindowsネイティブ版があれば、DuckDBより人気出ると思うんだよね。MySQLがPostgreSQLよりずっと人気だった理由の一つは、Windowsインストーラーがあったからだし。
ClickHouseってDuckDBよりすでに人気あるんじゃないの？
GitHubのスター数はDuckDBが28kで、ClickHouseが40kだから、かなり近いね。でも、HNだとDuckDBの方がよく話題に上がってる気がする。
サーバーとかデータベースって、だいたいLinuxで動いてるイメージだけど。
確かにそうかもね。でもWindowsはデスクトップとラップトップの71%で動いてるんだよ[1]。自分の経験だと、アプリって最初は簡単なデスクトップで作られて、成功したらサーバーに移行することが多い。自分はanalyticsの仕事してるけど、ロックダウンされたWindowsデスクトップで、MySQL、MariaDB、PostgreSQL、DuckDBとか全部試せた。ClickHouseはまだ試せてない。これは自分の経験ね。[1]https://en.wikipedia.org/wiki/Usage_share_of_operating_syste…
それもそうだけど、デスクトップがロックダウンされてたら、インストールに必要な管理者権限がない場合もあるよね（特にDRMとかライセンス使うソフト）。だからWindows版があっても動かせないかも。
ClickHouseは組み込みもできるの忘れずにね。Duckにすぐ飛びつくのは hypeのせいかも(試すたびにバグだらけ)。https://clickhouse.com/blog/chdb-embedded-clickhouse-rocket-
Chdbマジ最高だけどduckdbも良いよね
Clickhouseはパフォーマンスへのこだわりがハンパない、現代エンジニアリングの傑作だね。
空港のドラマはさておき、最高の休暇にするためにeReaderに最高のコンテンツを詰め込むぞ！技術情報と図解が素晴らしいだけでなく、物語が織り込まれているのが良いよね。
ClickHouseとStarRocks[0]って比較した人いる？数ヶ月前はStarRocksの方がJoin性能が良かった気がするけど、今はどうなんだろう？[0] https://www.starrocks.io/
ClickBenchにベンチマークがあるよ！https://benchmark.clickhouse.com/#eyJzeXN0ZW0iOnsiQWxsb3lEQi…
でもclickbenchにはJoinがないじゃん…
ClickHouseみたいなDBを見ると、row-basedなDBは何か間違ってるんじゃないかって思っちゃう。btreeインデックスを使ってもこのスピードには全然届かないもん。transactionは強いけどね。現代のマシンの速さに驚くよ。データセットも圧縮すればもっと小さくできたはず。Cloudflareの記事で暗号化が無料（decryptの方が速い）っていうのがあったけど、それと同じだね。compute engine (chdb) はマジで使える。
row-basedなDBが何か間違ってるわけじゃないよ。target workloadが違うんだ。Row-based -＞ OLTP -＞ “user_id = XYZ のorder tableからレコード全体を取得する”Column-based -＞ OLAP -＞ “order table から月/年ごとの注文合計金額を計算する”
user idでフィルタリングするのもめっちゃ速いと思うよ。トランザクションが遅くなる原因のほとんどだよね。isolation levelとか、古いデータを読んだ時のエラーとかさ。違いは分かるけど、カラムのコピーを持つindex構造でも、read/writeレートに近いものがないのが残念だよね。似たようなパーティショニングでwrite/readレートが改善されるのは知ってるけど、この規模じゃないんだよなー。
もしかしたら、最近流行りの“new SQL”ハイブリッドデータベース(HTAP)に興味あるかもね。TiDBが一番有名な例かな。
この分野じゃまだ経験不足なのかもだけど、この仕組みを読んだ感じだと、当然の最適化だと思うんだよね。違うかな？でも、ClickHouseが業界リーダーなのは間違いないよね。
当たり前の解決策ほど、正しく実行するのが難しいんだよね。これを実現するために必要なコードは、めっちゃ複雑か、書くのに時間がかかった(テストも)。あるいは両方かな。
これって有名な最適化手法の１つで、“late materialization”って呼ばれてるんだよね。この戦略を含む、大きな戦略セットだよ。Late materializationはカラムストアと同じくらい古いんだ。
これがサブクエリとかCTEにどれだけ影響するか気になるな。
Apache Druidってまだこの分野で使われてるのかな？最近全然聞かないけど。ClickHouseを選ぶ理由ってなんだろう？
もしくはApache Doris…私も気になる。
