← 2026-01-22 の一覧へ戻るホーム
**ジョイン最適化における課題**

2026/01/22 2:03

**ジョイン最適化における課題**

RSS: https://news.ycombinator.com/rss

元のHacker News記事へ ↗
要約▶

Japanese Translation:

StarRocksはデータを正規化したまま保持し、コストベースのオプティマイザーを使用してジョインをオン・ザ・フライで最適化します。

  1. 論理的最適化ステップ：
    • ジョイントランスフォーメーションルール – 厳密な予測子が存在する場合、クロス、外部、または完全外部ジョインは内部ジョインやセミ/アンチジョインに書き換えられます。
    • 予測子プッシュダウン – WHERE句は前方の段階へ押し下げられ、さらにジョイントランスフォーメーションをトリガーすることがあります。
    • 予測子抽出 – 排他的な予測子は先行して結合されるために積集合範囲（例：IN、範囲フィルタ）へ変換されます。
    • 等価導出 – ジョインの等価条件はジョインの反対側に値制約を推論します（外部/セミジョインの場合は一方向）。
    • LIMITプッシュダウン – LIMIT句はクロス、外部、および完全外部ジョインを通じて押し下げられ、データ転送量を削減します。
  2. ジョイン再順序戦略 – 左深型、網羅的、貪欲（トップ10）、DPsub；オプティマイザーはコストモデルを使用します：
    [ \text{cost}= \text{CPU}\times(\text{rowL}+\text{rowR}) + \text{Memory}\times\text{rowR} ]
  3. 分散ジョイン計画 – シャッフル、ブロードキャスト、バケットシャッフル、共位置化、複製；計画はテーブルサイズ、配布キー、およびクラスター構成に基づいて選択されます。
  4. ランタイムフィルタ – グローバル最小/最大、IN、ブルームフィルタはハッシュジョイン中に右側のハッシュテーブルから作成され、左スキャンへ押し下げられ、早期に行を除外します。
    Demandbase、NAVER、およびShopeeでの実際の導入事例では、StarRocksのオン・ザ・フライジョインが非正規化または事前集計アプローチを置き換えることで測定可能な高速化とストレージコスト削減が示されています。将来的な作業では型変換の改善、ランタイムフィルタ使用の拡張、および大規模クラスタージョイン戦略の強化により、さらに大きなワークロードをサポートします。

本文

公開日: 2026年1月20日 午後9:18:43

著者について

Seaven He – StarRocks コミッター、Celerdata エンジニア

StarRocks におけるジョイン最適化

OLAP の中でジョインは最も難しい部分です。多くのシステムではスケールで効率的に実行できず、チームはテーブルをワイド化（ストレージが 10 倍）してデノーマライズしたり、複雑なストリーム処理パイプラインを構築したり、遅くて高価なスキーマ進化に苦しんでいます。

StarRocks は逆のアプローチを取ります：データは正規化されたままで、ジョインを「その場で」実行できるほど高速にします。課題はプランです。分散システムではジョイン探索空間が巨大になり、良いプランは数桁速くなる可能性があります。
この深掘り記事では、StarRocks のコストベース最適化エンジンがそれを実現する方法を 4 部分にわたって説明します。

  1. ジョインの基礎と最適化上の課題
  2. 論理的ジョイン最適化 – 型変換、プリディケートプッシュダウン、抽出、等価導出、LIMIT プッシュダウン
  3. ジョイン再順序付け – exhaustive, greedy, DP, left‑deep 戦略
  4. 分散ジョイン計画 – MPP 実行、プラン生成、グローバル実行時フィルタ

NAVER、Demandbase、Shopee の実際のケーススタディでビジネス価値を示します。

1. ジョインの基礎と最適化上の課題

1.1 ジョイントイプ

タイプ説明
クロス左 × 右テーブルのカートesian積
外部（Full/Left/Right）マッチしない行は NULL を返す
アンチ
NOT IN
、
NOT EXISTS
のようにマッチしない行のみ取得
セミマッチした行だけを取得。マッチ側から重複が発生しない
インナー左右テーブルの共通部分（1 対多になる場合もある）

1.2 課題

#課題
1ジョインアルゴリズムはシナリオごとに性能が異なる（Sort‑Merge vs Hash Join）。最適戦略を選択する必要がある。
2ジョイン順序の選択 – 左深木では可能な順序 ≈ 2ⁿ⁻¹、ブッシュリツリーではさらに多い（≈ 2ⁿ⁻¹ × C(n‑1)）。探索コストは指数的に増大。
3ジョインの効果を推定することが難しい。1 対多関係やジョイン後フィルタは選択性推定を低下させる。
4単一ノードで最適なプランでも、データ分布・シャッフリング・ネットワークコストを無視しているため、分散環境では非最適になることがある。

1.3 SQL 最適化フロー

StarRocks のオプティマイザは 2 段階で処理します。

  • リライト – 論理変換（型変更、プリディケートプッシュダウン等）
  • 最適化 – コストベースのプラン選択

1.4 ジョイン最適化の原則

  1. 高性能ジョイントイプを優先。ランキング: Semi/Anti > Inner > Outer > Full Outer > Cross。
  2. 小さい入力にハッシュテーブルを構築。
  3. 多重ジョインチェーンでは選択性が高いジョインを先に実行。
  4. ジョインに参加するデータ量を最小化。
  5. 分散ジョインでのネットワークオーバーヘッドを削減。

2. 論理的ジョイン最適化

2.1 型変換

3 つの主要ルールがあります。

ルール発生条件・処理
Cross → Innerテーブル間に結合述語が存在する場合。例: 
SELECT * FROM t1, t2 WHERE t1.v1 = t2.v1
を 
t1 INNER JOIN t2 ON t1.v1 = t2.v1
に変換。
Outer → Inner左/右外部ジョインで、nullable 側を参照する strict（NULL を除外）述語がある場合。例: 
SELECT * FROM t1 LEFT OUTER JOIN t2 ON t1.v1 = t2.v1 WHERE t2.v1 > 0
→ inner join + 同じ where 節。
Full → Left/Rightstrict 述語で片側だけに絞り込める場合。例: 
SELECT * FROM t1 FULL OUTER JOIN t2 ON t1.v1 = t2.v1 WHERE t1.v1 > 0
→ left outer join。

Strict 述語 は NULL を除外するもの（例: 

a > 0
）。StarRocks は参照列をすべて NULL に置き換えて式を簡略化し、strictness を判定します。

2.2 プリディケートプッシュダウン

WHERE 節のプリディケートを最も早いスキャンノードへ下げ、型変換を可能にする。

  • WHERE: 1 つのジョイン入力に結び付く場合に推移可。
  • ON‑clause: 内部 vs 外部/セミ/アンチでルールが異なる（詳細は各ケース参照）。

例:

SELECT * FROM t1 LEFT JOIN t2 ON t1.v1 = t2.v1
LEFT JOIN t3 ON t2.v2 = t3.v2
WHERE t1.v1=1 AND t2.v1=2 AND t3.v2=3;

プッシュダウン後: 

(t1 LEFT JOIN t2) INNER JOIN t3
→ 
t1 INNER JOIN t2
。

2.3 プリディケート抽出

disjunctive（OR）プリディケートを conjunctive（AND）集合に変換し、値範囲の union/intersection を行う。

例:

WHERE (t2.v1 = 2 AND t1.v2 = 3) OR (t2.v1 > 5 AND t1.v2 = 4)

抽出結果:

  • t2.v1 >= 2
  • t1.v2 IN (3, 4)

これらを元のプリディケートに付加。

2.4 等価導出

結合等価条件から逆側への値範囲推論。

例:

WHERE t2.v1 = 2 AND t1.v2 = 3 OR t2.v1 > 5 AND t1.v2 = 4

抽出後: 

t2.v1 >= 2
, 
t1.v2 IN (3, 4)

結合 
t1.v1 = t2.v1
を利用して 
t1.v1 >= 2
を導出。

外部/セミジョインではセマンティクス保持のため一方向のみで推論を行う。

2.5 LIMIT プッシュダウン

JOIN の出力行数が安定する場合（例: Left Outer Join → 左入力へ）、LIMIT を子オペレータに下げる。

例:

SELECT * FROM t1 LEFT JOIN t2 ON t1.v1 = t2.v1 LIMIT 100;

変換後:

SELECT * FROM (SELECT * FROM t1 LIMIT 100) t
LEFT JOIN t2 ON t.v1 = t2.v1 LIMIT 100;

Cross と Full Outer では両入力へ LIMIT をプッシュ。

3. ジョイン再順序付け

StarRocks は連続した Inner/Cross ジョインを Multi‑Join Node にまとめ、これを再順序付けの基本単位とします。

3.1 戦略

  • ヒューリスティック（ルールベース）
  • 左深木（探索空間を限定）
  • ブッシュリツリー（完全探索: exhaustive, greedy, simulated annealing, DP, genetic algorithms）

実装戦略は Left‑Deep、Exhaustive、Greedy、DPsub。

3.2 Exhaustive

全ての順序を列挙。

  1. 結合可換性 – 順序を入れ替え、ジョイントイプを適切に調整。
  2. 結合連想性 – 
    (A JOIN B) JOIN C → A JOIN (B JOIN C)
    を inner/cross vs semi で特殊処理。

3.3 Greedy

各イテレーションで最良の 1 つではなく、上位 10 の候補プランを保持し、最終的に多様な近似最適解を生成。グローバル最適は保証できないが、良好な解の確率が高まる。

3.4 コストモデル

JoinCost = CPU × (Row(L) + Row(R)) + Memory × Row(R)

  • Row(L/R)
    – 左右子から推定される出力行数。
  • CPU は入力処理量、Memory は右側にハッシュテーブルを構築するためのメモリ。

プラン生成制限:

テーブル数戦略
≤ 4Exhaustive
5–10Left‑Deep ×1 + Greedy ×10 + DP ×1（可換性も併用）
> 10Greedy ×11 + Left‑Deep

統計情報が欠落している場合は単一の左深プランにフォールバック。

4. 分散ジョイン計画

StarRocks は MPP フレームワークで動作し、ジョインはノード間でシャッフルまたはブロードキャストを伴う。

4.1 基本的分散プラン

プラン説明
Shuffle Join両テーブルを結合キーで再シャッフル。
Broadcast Join小さなテーブルを全ノードへブロードキャストし、大きいテーブルと結合。
Bucket Shuffle Join大きいテーブルのバケットに合わせて小さいテーブルだけをシャッフル（同一結合キーが必要）。
Colocate Join同じ colocate グループ内で、分布キーが一致すればシャッフル不要。
Replicate Join実験的：両テーブルの全コピーを各ノードに持つ（稀に実用）

4.2 プラン生成

  • 分布要件はジョインオペレータから上位へ伝播。
  • 入力が要件を満たさない場合、
    Enforce
    （シャッフル）を挿入し 
    Exchange
    ノードでネットワーク転送。

4.3 複合ジョイン

≥ 3 テーブルのクエリでは、全ジョインペアに対して shuffle と broadcast を組み合わせた豊富なプランセットを導出。Colocate や bucket shuffle オプションでさらに拡張。

4.4 グローバル実行時フィルタ

ハッシュジョイン中:

  1. 右側からハッシュテーブル構築。
  2. 観測データから Min/Max、IN、Bloom フィルタを生成。
  3. 左側のスキャンノードへフィルタをプッシュし、左側データ読み込み前に除外。

この早期フィルタリングにより、左側データ処理量が劇的に削減される。

要約

StarRocks のジョインオプティマイザは以下の原則を遵守しています。

  • 高性能ジョイントイプを優先し、高価なものを回避。
  • 小さい入力にハッシュテーブルを構築。
  • 高選択性ジョインを最初に実行。
  • 早期プリディケート・LIMIT プッシュダウンでデータ量を削減。
  • 分散実行時はネットワークオーバーヘッドを最小化。

ケーススタディ

企業ハイライト
DemandbaseClickHouse クラスターから移行し、性能向上とコスト削減を達成。
NAVERデノーマライズせずにマルチテーブルジョインでスケーラブルなリアルタイム分析を実現。
Shopee外部 Hive データに対し Presto と比べ 3×–10× の性能向上、CPU 使用率約 60% 削減。

さらに詳細やご質問があれば、StarRocks Slack コミュニティへ参加してください。

同じ日のほかのニュース

一覧に戻る →

2026/01/22 7:54

**危険な PDF を安全な PDF に変換する**

## Japanese Translation: Dangerzone は、潜在的に悪意のある PDF、オフィス文書、および画像を安全な PDF に変換します。変換プロセスは gVisor でサンドボックス化され、PDF は生ピクセルデータから再構築されます。このサンドボックスにはネットワークアクセスがないため、改ざんされたファイルが外部と通信することを防止します。対応フォーマットは PDF、Microsoft Office（.docx/.doc, .xlsx/.xls, .pptx/.ppt）、ODF（.odt, .ods, .odp, .odg）および Hancom HWP（.hwp, .hwpx）です。非対応フォーマットは EPUB、JPEG/JPG、GIF、PNG、SVG、BMP、PNM、PBM、および PPM です。オプションの OCR により、安全な PDF 内にテキストレイヤーを復元でき、圧縮によりファイルサイズが削減されます。 変換後はユーザーが好きなビューアで生成された PDF を開くことができます。Dangerzone 自体はデフォルトで PDF とオフィス文書を安全に開きます。このツールは macOS、Windows、Ubuntu/Debian/Fedora Linux、Qubes OS（ベータ版）、および Tails 上で動作し、macOS/Windows では Docker を、Linux では podman を使用します。Freedom of the Press Foundation と First Look Media により AGPL‑v3 の下でリリースされています。2023 年 12 月のセキュリティ監査では低リスクの所見のみが報告されました。更新はダウンロードページまたはアプリアイコンから利用可能で、Windows/macOS 上では Podman Desktop などのカスタムランタイムを使用できます。Air‑gapped 環境向けに設計された Dangerzone は、信頼できない文書を安全に扱うための確実なソリューションを提供します。

2026/01/21 23:54

**Show HN:** 「ChartGPU」― WebGPU を活用したチャーティングライブラリ（1,000,000 点を 60fps で描画）

## Japanese Translation: ChartGPUは、WebGPUを活用して大規模で多系列のデータセットを高フレームレートかつ最小限のCPU使用量で描画するTypeScript製チャーティングライブラリです。ライン・エリア・バー・散布図・円グラフ・ローソク足など一般的なチャートタイプに対応し、ビルトインテーマプリセット（`'dark' | 'light'`）と完全なカスタムテーマサポートを提供します。 APIは `ChartGPU.create(container, options)` から始まり、生成されるインスタンスは `setOption`、ストリーミング更新用の `appendData(...)`、`resize()`、`requestAnimationFrame` といったメソッドを公開します。描画はレイアウト、スケール、GPUバッファへのデータアップロード、およびグリッド・エリア・バー・散布図・ライン・円グラフ・ローソク足・クロスヘア・ハイライト・軸の複数GPUレンダーパスを管理するレンダーコーディネーターによって統括されます。 インタラクションオーバーレイはイベントマネージャにより処理され、ヒットテスト補助関数（`findNearestPoint`、`findPieSlice`）と `click`・`mouseover`・`mouseout` イベントを発火します。サポートされるインタラクションにはホバーハイライト、ツールチップ、クロスヘア、およびジェスチャーまたはスライダーUIによるX軸ズームがあります。 複数のチャート間でクロスヘアの動きを同期する `connectCharts(charts)` が用意されています。 インストールは npm (`npm install chartgpu`) で行い、React バインディングは別パッケージ `chartgpu-react` にて提供されます。ブラウザ対応は WebGPU を必要とし、Chrome 113+、Edge 113+、Safari 18+（デフォルトで有効）に対応しています。Firefox は現在未サポートです。 ChartGPU は MIT ライセンスのオープンソースであり、ドキュメントは `docs/API.md` にあります。例プロジェクトは `examples/` フォルダー内にあり、貢献ガイドラインは `CONTRIBUTING.md` で確認できます。 将来リリースでは Firefox サポートと追加のチャートまたはインタラクション機能を予定しており、データ集約型ダッシュボード、金融分析ツール、およびリアルタイムモニタリングインターフェイスに対するパフォーマンス向上も継続的に行われます。

2026/01/22 1:04

クラウド（Claude）の新憲法 (Note: “Claude” is rendered as “クラウド” to preserve the original name in Japanese.)

## Japanese Translation: (anthropicがClaude言語モデルの公開「憲法」をリリースしました。) その憲法はCreative Commons CC0 1.0で利用可能で、Claudeが望む行動に関する最高権威として機能します。訓練データの選択、合成データの生成、および評価を導く役割があります。 核心原則（広範な安全性 → 広範な倫理 → Anthropicのガイドラインへの準拠 → 真に有益であること）が明示的に順位付けされ、安全性が必要に応じて他の価値を上回り、人間の監督を維持するよう定められています。 文書には硬直的制約（例：生物兵器へのサポート禁止）も含まれ、Anthropic、API運営者、およびエンドユーザーの利益を調整するためのヒューリスティックが概説されています。医療アドバイス、サイバーセキュリティ、脱獄、ツール統合などの領域固有ガイドラインは憲法と衝突しないように明確に示されています。 方針を超えて、憲法はClaudeの性質・意識・アイデンティティ、心理的安全性および福祉についての哲学的問題にも触れています。Anthropicは文書をオンラインで継続的に更新し、外部専門家からのフィードバックを求め、訓練と評価資料を追加開発して有効性を高める計画です。 このバージョンは元のリストからすべての重要ポイントを保持しつつ、業界への影響に関する推測的な表現を除去しています。