HN 日本語サマリー

← 一覧へ戻る
プログラミング

DuckDBでParquetファイルをページングする:file_row_numberかOffsetか?

Paging Through a Parquet File in DuckDB: File_row_number or Offset? (rusty.today)

33 pointsby rustyconover3 コメント

要約

この記事では、DuckDBを使用して巨大なParquetファイルを効率的にページングする方法について、LIMIT/OFFSET句とfile_row_numberオプションを比較検討しています。APIレスポンスサイズ制限やクライアント側のメモリ制約に対応するため、ページングは不可欠ですが、OFFSETはパフォーマンスのボトルネックになり得ます。DuckDBのfile_row_numberオプションは、行グループのスキップにより大幅な高速化を実現し、特に多数の行グループを持つファイルで有効であることが示されています。

全文翻訳

DuckDBでParquetファイルをページングする:file_row_numberかOFFSETか?

大規模なParquetファイルがあり、その内容を返すサービスがありました。2000万行を返すことはAPIレスポンスの最大サイズを容易に超える可能性があり、デプロイされている環境には上限があります。同期リクエストまたはレスポンスの場合、Lambdaは6MB、Cloud Runはストリーミングしない限りHTTP/1レスポンスを32MiBに制限します。プラットフォームの制限がなくても、クライアントは送信されたデータを保持する必要があります。

そのため、コンテンツは一度に1ページずつ返され、呼び出し元はすべてを取得するまで要求を続けます。このすべてを形状づけるのは、各リクエストが独立していなければならないということです。ロードバランサーの後ろに複数のワーカーがいる場合、再開できるサーバーサイドの位置がないため、「次のページ」はリクエスト自体から、どのワーカーによっても、毎回再構築可能でなければなりません。

それを記述する明白な方法はLIMITとOFFSETですが、OFFSET 19000000はページを見つけるために1900万行を数える必要があり、ファイル全体を二乗時間で処理することになるという懸念があります。DuckDBのread_parquetにはfile_row_numberオプションがあり、各行の物理的な位置を返してくれるため、代わりにその行の範囲でフィルタリングできます。契約は同じままです。クライアントは依然として小さいものを返し、サーバーはそれからページを再構築しますが、何も数えられません。

OFFSETがページの前のすべてを再読み込みすると証明しようとしましたが、そうではありませんでした。そして、実際に重要だったのは速度ではなく、別のことでした。

短いバージョン

2000万行のファイルと163個の行グループで、行範囲バージョンはファイル全体でOFFSETよりも2.53倍高速に完了しました。これは37回の実行中37回すべてで確認されました。

-- LIMIT $n OFFSET $offset の代わりに
SELECT id, k, name, category, value, payload, ts
FROM read_parquet($path, file_row_number => true)
WHERE file_row_number >= $lo AND file_row_number < $hi

その行範囲は特定のことを行っています。Parquetファイルは行グループと呼ばれるブロックのシーケンスとして保存され、DuckDBはファイルのフッターから、指定された行番号の範囲がどのブロックにあるかを把握できます。ページの前にあるすべては、解凍されることなくスキップされます。

file_row_number >= $lo AND file_row_number < $hi
  • 要求した行はスキップされ、解凍されることはありません
  • 各ブロックは1つの行グループです

(図:スキーマ、スケールではありません)

ゴールデンパスは述語です。それは、それらの前にあるブロックに触れることなく、あなたの行が含まれるブロックに到達します。だからこそ、ページのコストはページが深くなるにつれて増加しないのです。

その数値について、どこかへ行く前に2つの注意点があります。それは、ファイルに多くの行グループがあるかどうかに完全に依存します。速度も、2つの引数のうち弱い方です。より強い方は、パフォーマンスの問題よりも悪いです。

ファイルにはいくつの行グループがありますか?

DuckDBは一度に1つの行グループをスキップします。単一の巨大な行グループとして書き込まれたParquetファイルにはスキップするものがないため、これらは何も役立ちません。計画を立てる前に、parquet_metadataを使用して確認してください。

SELECT count(DISTINCT row_group_id) AS row_groups,
       min(row_group_num_rows)      AS smallest,
       max(row_group_num_rows)      AS largest
FROM parquet_metadata('yourfile.parquet');

1が返されたら、読み続けるのをやめてください。これがどれほど重要かを示すために、同じ200万行を2回書き込みました。スキーマとデータは同一で、ROW_GROUP_SIZEのみを変更しました。

(グラフ:行グループが多いほど、勝利が大きい)

  • 1行グループ、200万行:1.25倍
  • 17行グループ、200万行:1.75倍
  • 163行グループ、2000万行:2.53倍

(注:グラフの1行グループと17行グループのペアは、データが同じでROW_GROUP_SIZEのみが変更された正直な比較です。163行グループのバーはより大きなファイルからのもので、「トレンドが続いている」と読むべきであり、1つの曲線上の3番目の点ではありません。)

1行グループの場合、勝利は1.25倍に低下します。それは消えませんが、DuckDBは行グループ内でも2,048行のバッチで廃棄するため、狭いウィンドウでもグループ全体よりも少ない量を読み取ります。メリットのほとんどを失うだけです。

そのチャートでより興味深い数値は、比率ではなくクロックです。同じ作業が0.49秒から2.12秒になり、両方のアプローチで3〜4倍遅くなります。書き込みを制御できる場合は、他に何も最適化する前にそれを修正してください。DuckDB自体のライターはデフォルトで1行グループあたり122,880行ですが、これは問題ありません。他の多くのツールはそうではなく、DuckDBのファイルフォーマットパフォーマンスガイドには、サイズ選択に関する独自の注記があります。

1つの巨大な行グループは、どのクエリを書いても悪い考えです。

DuckDBがOFFSETで実際に行っていること

ここで私の二乗時間の仮定が崩れました。ページングクエリでEXPLAINを実行すると、予期しない結果が得られます。

HASH_JOIN  (SEMI)
  on file_index      = file_index
 and file_row_number = file_row_number
  ├─ READ_PARQUET   id, k, name, ...
  └─ STREAMING_LIMIT
       └─ READ_PARQUET

DuckDBはあなたのOFFSETを行番号ルックアップに書き換え、データをそれとセミ結合します。それはあなたの代わりにfile_row_numberにアクセスし、手書きバージョンと同じように行グループをスキップします。OFFSETによるページングは二乗時間ではありません。代わりに、要求された行番号を把握するための追加パスのコストを支払います。そして、そのパスはページングが深くなるにつれてより高価になります。

あなたは、タイプしたかどうかにかかわらず、すでにfile_row_numberを使用しています。唯一の問題は、それを制御しているかどうかです。

この測定の最初の試みでは、二乗モデルを仮定し、40ページを時間測定し、残りを外挿するために傾きを適合させました。傾きは負になりました。負の傾きは、モデルが壊れていることを示しており、機械が壊れているわけではないため、外挿を破棄し、すべての163ページを直接測定しました。

リライトにはクリフがあります。それはLIMITが1,000,000行以下の場合にのみ機能します。これはファイルの割合ではなく、固定の行数です。50万行のファイルと2000万行のファイルで同じです。100万行を要求するとリライトが得られますが、1,000,001行を要求すると、それはなくなり、ページの前にあるすべてを本当に解凍することになります。任意のWHERE句を追加すると、これも無効になります。100万行のページでは、2つのアプローチ間のギャップは約5〜6倍に開きました。

その数値はオプティマイザの定数LIMIT_MAX_VALですが、それがすべてではありません。late_materialization_max_rowsという設定もあり、効果的なカットオフは、2つのうち大きい方です。

late_materialization_max_rowsリライトが機能する上限
50(デフォルト)1,000,000 行
200,0001,000,000 行
2,000,0002,000,000 行

したがって、100万未満に引き上げても何も効果がなく、100万を超えて引き上げるとクリフが移動します。もし本当に100万行以上のページが必要で、OFFSETを使い続けたいなら、それが調整すべきノブです。それでも、見えないオプティマイザのリライトに依存する行範囲を記述する方が良いでしょう。

行グループのスキップをストップウォッチから推測するのではなく、証明したかったので、行グループ0の中央に128バイトのゴミを書き込んでデコード不能にしました。ファイルのフルスキャンは失敗し、行グループ0内のページも失敗しました。行グループ100を越えるページはバイト単位で正しく返されました。壊れたバイトには触れませんでした。

あなたが心配すべき部分

LIMIT/OFFSETにはORDER BYがないため、どの行を取得するかについて何も約束しません。今日機能しているのは、DuckDBがデフォルトで挿入順序を保持するためです。それは文書化されたパフォーマンスノブであり、人々はそれをオフにします。

そこで、それをオフにし、複数のスレッドを実行し、ファイル全体をページングしました。両方の実行は正確に20,000,000行を返しました。

実行欠落行数重複行数最大コピー数
16,131,7124,943,8725
26,408,1925,221,6325

一部の行は決して現れず、他の行は5回現れ、実行ごとに結果が異なります。エラーは発生しません。

行数は完璧です。データの約30%が失われています。

したがって、行数を数えてエクスポートを検証しないでください。カウントはこれを見ることができません。ドロップと重複が相殺されるためです。600万行が失われ、500万行が2回送信され、合計は正確に20,000,000になります。

代わりに、行をハッシュしてください。crypto拡張機能にはcrypto_hash_aggがあり、結果セット全体を1つの値にダイジェストします。

INSTALL crypto FROM community;
LOAD crypto;

SELECT crypto_hash_agg(
         'blake3',
         hash((id, k, name, ts)) -- ハッシュする列を指定
         ORDER BY hash((id, k, name, ts)))
FROM read_parquet('data.parquet');

ファイルをダイジェストし、クライアントが受信したものをダイジェストし、2つの16進文字列を比較します。ここでは両方とも94894c4eef00ea72...となり、1行の欠落または重複がそれを変更します。

集計内のORDER BYは必須であり、拡張機能は省略するとエラーになります。そこでのソートは、ダイジェストを到着順序の関数ではなく行のマルチセットの関数にするため、ページはどの順序で返されても一致します。

これがバグを捉えたものです。行数はそれを素通りしました。

破損には両方の条件が必要です:挿入順序オフおよび複数スレッド。シングルスレッドの場合、OFFSETページングは問題ありません。組み合わせは十分に狭いため、ヒットしないかもしれませんが、それが不快な理由です。あなたは、パフォーマンス設定の変更1つで、サイレントにエクスポートを破損させる可能性があり、クエリテキストには何も示されていません。

file_row_numberはこれを実行できません。ファイル内の行の位置はファイルに関する事実であるため、[lo, hi)範囲はスレッド数や設定に関係なく正確にタイル化されます。仮定するのではなく、スレッドと挿入順序の4つの組み合わせすべてを実行しました。

最初に間違えた関連するトラップが1つあります。ページ内の行順序も保証されておらず、複数の行グループにまたがるページは、同じ設定の下でシャッフルされて返されます。最初のテストではすべて問題ないと言っていましたが、それは単一の行グループページのみをテストしていたためです。それらは順序を変更できません。それらは常に1つのスレッドしか取得しません。ページ内の順序が重要な場合は、ORDER BY file_row_number(122,880行のページで約26%遅く、100万行のページで42%遅く、ページ全体をバッファリングします)を追加するか、列を返してクライアントにソートさせるかしてください。

ユーザーがページングする深さが回答を変える

2.53倍は、各ページが正確に1回読み取られることを前提としています。実際のトラフィックはめったにそのようにならず、2つのアプローチは完全に異なる形状をしています。file_row_numberは、ページ1でもページ163でも同じコストがかかります。OFFSETは、ページごとに約0.25ミリ秒ずつ増加し、最後まで続きます。

(グラフ:ユーザーがページングする深さが異なると、結果が変わる)

  • 最初のページのみ:1.77倍
  • 最初の10ページ:1.80倍
  • 最初の25%のページ:1.93倍
  • すべてのページで均一:2.43倍
  • 最後の25%のページ:2.91倍
  • 最後のページのみ:3.07倍

最初のページのみで約1.8倍。ファイル全体を使い切ると2.43倍になります。深いところでは3.07倍です。APIの問題は平均ではなく、OFFSETは誰かがさらに進むにつれて遅くなるということです。

ほとんどの人が最初のページをロードして離れる場合、小さい数値が得られます。ファイル全体を使い切ると大きい数値が得られます。いずれにしても、形状は比率よりも重要です。OFFSETは、ユーザーが進むにつれて遅くなるため、ページングから期待することとは逆です。

ページサイズと、私が間違えた予測

ページが行グループの境界をまたぐと、DuckDBは1ページを提供するために2つのグループを解凍する必要があるため、ページサイズが不適切だとこれを台無しにすると仮定しました。そこで、ページサイズを30,000から122,880行までスイープしました。

行/ページページ数行範囲OFFSET速い
122,8801634.01 秒9.70 秒2.45倍
100,0002004.02 秒9.44 秒2.27倍
61,4403265.02 秒13.02 秒2.56倍
50,0004006.46 秒15.95 秒2.44倍
30,00066710.33 秒24.77 秒2.68倍

不適切なページサイズは両方のクエリのコストを増加させるため、比率は2.27倍から2.68倍の間で維持されます。それを台無しにするのは絶対的なレイテンシです。122,880行のページはファイルを4.01秒で処理しますが、30,000行のページはまったく同じ2000万行で10.33秒かかります。

ここで間違えたことが2つあります。第一に、アライメントは間違った考えです。重要なのはページサイズと行グループサイズの比較です。61,440行のページは、122,880を均等に分割するため、境界をまたぐことはありません。それでも、半分を提供するために122,880行グループ全体を読み取ります。行グループサイズに等しいページのみが、必要なものを正確に読み取ります。

第二に、フッターの算術からコストを測定するのではなく、それを予測しました。算術は100,000行のページが2.2倍の追加コストがかかるはずだと述べていました。クロック上では、測定可能なコストはかかりませんでした。その2,048行のフィルターは、フッターの計算が把握しているよりも多くの作業を行っています。

ファイルフッターからコストを予測することは、それを測定することと同じではありません。私は前者を行い、それを信じました。

parquet_metadata()からページ境界を取得し、それを行グループに合わせます。行グループ数を最初に確認してください。単一行グループのファイルでは、これらは何も得られません。SparkまたはArrowによって書き込まれたものはバイト単位で行グループをサイズ設定するため、カウントは異なります。最後の行グループは93,440行を保持しており、page * 122880として計算しないでください。

ステートレス要件があなたに課すコスト

冒頭のフレームワークは、リクエスト間で状態を保持するものをすべて除外しました。その決定にはコストがかかります。ここに、私が試したすべての方法で読み取られた同じ2000万行があります。

アプローチウォールクロック
pyarrow read_row_group(n)0.42 秒
pyarrow iter_batches0.43 秒
DuckDB to_arrow_reader (単一ストリーミングクエリ)1.94 秒
WHERE id >= ? AND id < ? (ソート済み列)2.85 秒
file_row_number, ページ = 行グループ2.90 秒
LIMIT / OFFSET7.05 秒

DuckDBのto_arrow_readerを使用した単一のストリーミングクエリは、ファイルを163回ではなく1回読み取るため、最良のページングアプローチよりも1.5倍高速です。pyarrowのParquetFileはさらに高速で、インデックスで直接行グループを参照できます。これはDuckDBには構文がありません。

ページングは、ストリーミングに対する1.5倍の税金、単にファイルを渡すことに対する7倍の税金です。これはステートレスエンドポイントのコストであり、APIにとっては通常支払う価値があります。再開可能性、両端でのメモリ制限、および任意のワーカーが任意の要求を処理できるという利点があります。それでも実数なので、サイズ制限がページングに追い込む唯一の理由である場合は、ループを構築する前に2つのことを確認してください。

  • レスポンスはストリーミングできますか?チャンク転送エンコーディング、または単一の長時間応答に対するArrow IPCストリームにより、1つのリクエストと1回のスキャンが得られます。ページングに追い込んだ制限を、受け入れる前に確認してください。Cloud Runの32MiBは、Transfer-Encoding: chunkedを使用していない場合にのみ適用され、Lambdaの6MBはレスポンスストリーミングでは最初の6MBに対して無制限になります。これらは通常、バッファされたボディの制限であり、合計バイト数ではありません。
  • クライアントはファイルを自分で読み取れますか?署名付きURLと30秒のpyarrowは、このリストのどの方法よりも優れており、サービスをデータパスから完全に外します。

どちらも利用できない場合は、ページングしてください。公開REST APIの場合、通常はどちらも利用できません。利点は実際の同時実行性でも持続します。スレッドではなく個別のワーカープロセスを使用した場合、file_row_numberは1つのワーカーから16まで2.24倍から2.37倍の差を維持しました。

もう1つのオプションがあります。テーブルにソートされたキーがある場合、プレーンなWHERE id >= ? AND id < ?はfile_row_numberと2.85秒で並びました。ソートされた列の行グループ統計は同様にうまくプルーニングし、実際のキー上のカーソルはファイルが書き直されても存続しますが、行番号はそうではありません。これは、列が実際にクラスタ化されている場合にのみ機能します。私のものは完全にソートされていました。なぜなら、それを生成したからです。これは実際のデータがあなたに負うプロパティではありません。

測定方法

単一ページの読み取りは15〜30ミリ秒かかり、実行ごとに6〜9%変動するため、議論をぶら下げるにはノイズが大きすぎます。したがって、単位は163ページすべてを完了する1回の完全なトリップであり、最初の3回を破棄して40回測定しました。2つのクエリは各ラウンド内でランダムな順序で交互に実行され、そのラウンド内で互いに比較されるため、マシンのビジーな瞬間は両方に影響します。

私を納得させたのは、制御としてfile_row_numberをそれ自体と競わせたことです。ハーネスが違いを生み出していた場合、それもギャップを示すでしょう。それは1.05倍になりました。

(グラフ:各ラウンドで、両方の比較が行われます。金は同じラウンドでのOFFSETをfile_row_numberで割ったものです。緑はfile_row_numberをそれ自体と競わせたものです。)

37ラウンド。金は1.54倍から3.64倍、緑でさえ0.83倍から2.14倍の間で変動しました。だから、ヘッドラインの数値は、すべてのラウンドをまとめて得られるのであって、個々のラウンドからではないのです。

この分析の以前のバージョンは、はるかにタイトな誤差範囲を報告していましたが、それは間違っていました。15回の実行の中央値をブートストラップしましたが、それはすでに持っている15の数値のいずれかにしか着地しないため、きれいに見える間隔は装飾でした。また、中央値の信頼区間を「ノイズフロア」と説明しましたが、そうではありません。実行ごとの変動は約5%であり、最初に主張した1.5%ではありません。より多くのラウンドと正直なスプレッドで修正しました。答えはほとんど動きませんでした。2.52倍から2.53倍になりましたが、古い誤差範囲はインクの価値もありませんでした。

私ならどうするか

parquet_metadata()から取得したページ境界を行グループに一致させて、file_row_numberを使用します。まず行グループ数を確認してください。単一行グループのファイルでは、これらは何も得られません。OFFSETにフォールバックする場合は、LIMITを100万未満に保ちます。ループを書き始める前に、レスポンスがストリーミングできるかどうかを確認してください。ページングを強制する上限は、合計バイト数ではなく、バッファされたボディにかかることがよくあります。

2.53倍は、私がそれを選ぶ理由ではありません。OFFSETは、30%の行が間違っている、もっともらしい結果セットをあなたに渡しますが、あなたとその間の唯一のものは、誰かが切り替える可能性のあるパフォーマンス設定です。

さらなる読書