Bound the sorted-scan merge by how many files' key ranges overlap

オープン
  • 何か問題がありますか？
#71 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
15/100
issue の種類
機能追加
明瞭さ
明確に書かれている
活発さ
停滞
技術スタック
rust
領域
backend, databases

調査の方向性

Start with IcebergDataSource and StreamingMergeBuilder, then review DataFusion's split_groups_by_statistics for the overlap grouping approach. The issue says per-file column statistics on FileScanTask and an iceberg-rust revision bump are prerequisites; the maintainer is preparing that change. Done means sorted scans bound the merge by maximum file range overlap, preserve sort-key and null ordering, and safely handle missing or promoted-type bounds; this work is already underway.

索引モデルが issue の本文から書いたものです。

説明

With iceberg.execution.preserve_data_ordering, #55 merges one reader per data file with every file open at once, so iceberg.execution.max_merge_files_per_partition caps the number of files. A sorted table with many small commits goes over the cap and loses its order, even when most of its files don't overlap.

The plan is to bound the merge by overlap instead of file count. IcebergDataSource would read each file's bounds and null counts for the sort columns, sort the files by their first key in output order, and put each file after the first chain whose last file ends at or before it. DataFusion's split_groups_by_statistics does the same. Each chain is read one file at a time, the chains are k-way merged, and max_merge_files applies to the number of chains, which equals the maximum overlap depth. A table whose files don't overlap then merges nothing.

Cases that need care:

  • Files are compared over every claimed sort key, not just the leading one. With a tie on the leading key, comparing only that key could put one file's rows ahead of the other's when the second key says otherwise.
  • Under NULLS FIRST a file with nulls can only start a chain, and under NULLS LAST it can only end one. A missing null count on an optional column counts as nulls.
  • Descending keys swap the bounds.
  • Truncated string bounds stay correct; they just overlap more.
  • A file with missing bounds, or a bound typed differently from the column after a type promotion, gets a chain of its own. With no bounds at all, the scan behaves exactly as after #55.
  • Listing every file at planning time also needs a cap of its own.

This needs per-file column statistics on FileScanTask, which iceberg-rust doesn't carry today. That change is apache/iceberg-rust#3422, in PR apache/iceberg-rust#3424. Once it merges, this needs a bump of the iceberg-rust rev.

Related: In https://github.com/apache/datafusion-comet/pull/5331#discussion_r3830848772, @mbutrovich proposed admitting unopened files from a priority queue ordered by min bound. That bounds open readers by the same overlap depth and opens files later, which helps LIMIT, but it needs a custom merge operator. Chains reuse StreamingMergeBuilder, so I'd start there and keep admission as a possible next step.

I'm working on this and will put up the PR here once #55 and the iceberg-rust change have merged.

主要言語
Rust
スター
30
フォーク
30
平均マージ
3日 19時間
マージ済み PR（30日）
15

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

apache/datafusion-iceberg のほかの issue

apache/datafusion-iceberg の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。