🦆
DuckDB Update & Blog reading #7:ウィンドウ関数、挿入ソートについて

2025/05/17に公開
 まえがきDuckDB の公式ブログが2件ほど更新されていたので調べたり検証してみました。🙌

以下のような内容について書かれていました。
1.時系列データの分析時「区間」を使用するための有用なウィンドウ関数四種類
2.DuckDBの挿入ソートにおける高速化のための仕組みについて
https://duckdb.org/2025/05/02/stream-windowing-functions.html

https://duckdb.org/2025/05/14/sorting-for-fast-selective-queries.html
上から順にいきます。

 1-1:概要アムステルダム中央駅の鉄道サービスデータを使用して、タンブリングウィンドウ、ホッピングウィンドウ、スライディングウィンドウ、セッションウィンドウを使う内容でした。
ディメンション（エンティティに関する情報：名前、住所、シリアルナンバーなど）とファクト（エンティティに関連するイベント：クリック、販売、銀行取引、IoT デバイスからの読み取りなど）に分類して操作してるみたいです。

この四つのウィンドウ関数をタイムスタンプ付きファクトデータに適用して時系列の分析や前処理をやってました。

今回はデータベース接続できなかったので要所のみまとめます。(サーバーエラーになってしまったので...)

 1-2:タンブリングタンブリングウィンドウは固定の時間間隔で、特定の時間単位レベル（年、日、時間など）での要約を計算する...ということみたいです。

具体的にどういった区切り方かというと、
9:00-10:00 の区間のようなもので 9:00 を含み、10:00 は含まない。
なので区間同士は重ならず隙間もない
すべての区間は同じ長さ

というような具合です。
こういった処理するには date_trunc 関数というものを使用するみたいです。
SELECT
    date_trunc('hour', station_service_time) AS window_start,
    window_start + INTERVAL 1 HOUR AS window_end,
    count(*) AS number_of_services
FROM ams_traffic_v
WHERE year(station_service_time) = 2024
GROUP BY ALL
ORDER BY 1;
これはブログ上のコードです。

date_trunc内で区切る時間間隔(ここでは1時間)を指定しその区間内のデータを丸め？ています。

(たとえば9時12分のようなデータは9時のデータとして扱われる。)

window_endを1時間後に指定しその区間をグループ化しのデータを全てカウントしています。
同じようにタイムバケットという方法があります。
SELECT
    time_bucket(
        INTERVAL 15 MINUTE, -- bucket width
        station_service_time,
        INTERVAL 0 MINUTE -- offset
    ) AS window_start,
    window_start + INTERVAL 15 MINUTE as window_end,
    count(*) AS number_of_services
FROM ams_traffic_v
WHERE year(station_service_time) = 2024
GROUP BY ALL
ORDER BY 1;
time_bucket ではオフセットで開始時間を選べるみたいです。(例えば9:15分のように)

この例では間隔が15分となっています。
date_trunc は標準的な時間単位（年、月、日、時間、分、秒）のような間隔しか使えないが、

time_bucket はより柔軟なバケット幅（例：15 分、45 分、7 時間など）を指定できます。

 1-3:ホッピング次にホッピングというウィンドウ関数についてみていきます。

さっきのタンブリングとは違ってこれは重複してもOKです。

具体的には

ホッピングサイズ: ウィンドウの開始時刻間で経過する時間量（例: 5 分ごとに開始）

ウィンドウサイズ (window size): 各ウィンドウがカバーする時間の範囲（例: 15 分間隔）

という別々のサイズを使用します。

なのでウインドウとホッピングが被ることがあってこれで重複を許容しています。
WITH time_range AS (
    SELECT
        range AS window_start,
        window_start + INTERVAL 15 MINUTE AS window_end
    FROM range(
        '2024-01-01 00:00:00'::TIMESTAMP,
        '2025-01-01 00:00:00'::TIMESTAMP,
        INTERVAL 5 MINUTE -- ホッピングサイズ
    )
)
これは9時台だと
| 開始時間          | 終了時間          |
|------------------|------------------|
| 9:00             | 9:15             |
| 9:05             | 9:20             |
| 9:10             | 9:25             |
| 9:15             | 9:30             |
| 9:20             | 9:35             |
| ...              | ...              |
のようになります。

 1-4:スライドスライディングウィンドウは重複する区間ですが、ホッピングウィンドウとは異なり、分析対象の時間列から動的に生成されます。

ちょっとわかりにくかったので例を...

例えば9:23:45にデータがあれば、9:08:45～9:23:45の15分間を分析できるというわけですね良い。
SELECT
    station_service_time - INTERVAL 15 MINUTE AS window_start, -- window size
    station_service_time                      AS window_end,
    count(service_sk) OVER (
        ORDER BY station_service_time
            RANGE
                BETWEEN INTERVAL 15 MINUTE PRECEDING -- window size
                AND CURRENT ROW
    ) AS number_of_services
FROM ams_traffic_v
ORDER BY 3 DESC, 1
LIMIT 5;

 1-5:セッション最後のセッションウィンドウとは？

区間と区間の間に隙間時間があるようなデータを扱う方法です。
SELECT
    service_sk,
    station_service_time,
    lag(station_service_time) OVER (
        PARTITION BY station_service_time::DATE
        ORDER BY station_service_time
    ) AS previous_service_time,
    date_diff('minute', previous_service_time, station_service_time) AS gap_minutes
FROM ams_traffic_v
WHERE hour(station_service_time) BETWEEN 6 AND 23
例えばこのクエリではlagで時系列に並んだデータの直前のデータを取得してつぎのdate_diffで現在のデータとの差分を最終的に選択し、区間を設定しています。

 2-1:概要DuckDB でのデータ挿入時のソートによる高速なクエリ実現に関する記事でした。

具体的にはデータをロード時にソートすることで、選択的な読み取りクエリの速度を 10 倍向上させているらしく、これはDuckDB の自動 min-max インデックス（ゾーンマップとも呼ばれる）によるものみたいです。データを読み取りで使用することがDuckDBはとても多いのでこれのおかげで色々助かっている部分がありそうです。

具体的には書き込み時に少し時間をかけてデータを整理（ソート）して、後の読み取りを大幅に高速化しているとのこと...!

 2-2. DuckDBのデータベースの内部構造DuckDBのデータベースにはデータ本体だけではなく「Catalog Tables」（カタログテーブル）があり、ここにはデータベースの構造に関する情報...ようはメタデータが保存されています：
列ごとにデータを保存(カラムナー形式)しているが、テーブルを「行グループ」と呼ばれる行の塊に分割しています。(デフォルトでは、各行グループは122,880行)

そしてこの各行グループには、そのグループ内のデータに関するメタデータが保存されるようになってます。
この行グループは以前のブルームフィルターの仕組みを書いた公式ブログにも出てきていましたね。

前はParquetの高速化において実際のデータを読み込まず、軽いメタデータを読むことで処理を速くしているという仕組みでした。

https://zenn.dev/amana/articles/b88aeb1a165cd1

 2-3:ゾーンマップこのを「ゾーンマップ」または「min-maxインデックス」と呼ばれるものに、行グループ内のその列の最小値と最大値が含まれています。

SQL クエリを受け取ると、まずメタデータをチェックします。そして存在する可能性がない場合、DuckDB はそのロウグループ全体のデータの読み取りをスキップして高速化しています。

全体ソートしていればスキップできる行グループは増えます。1月のデータを取得したい場合日付順に並んでいれば、1月のデータを含む行グループ以外は全部スキップできます。

しかし全体にまばらに、例えば全ての行グループに1月のデータがあったら全部の行グループを読まないといけません...

 2-4:戦略的にスキップするということでこのゾーンマップというメタデータを使用した高速化を使うために、書き込みの際にソートしておきましょうということになります。
例えば
SELECT * FROM sales 
WHERE region = 'Tokyo';
というようなregionの指定が最も多いならこれでソートをしておくのが最も良いということになります。(複数フィルターするなら全てのフィルターに使用する列をソートしておく)
複数の異なる列でフィルタリングするワークロードの場合、カーディナリティ（一意の値の数）が最も低い列から先にソート...例えば、一意の customer_id の前に、広範な customer_type でソートすると役立つということみたいです。

具体的には

ケース1: customer_idでまずソートした場合

10万件のデータをcustomer_idでソートすると、各行グループ（仮に1万行ずつ）は次のようになります：
行グループ1: customer_id: 0001～1000の顧客
  - customer_type: 「個人」「法人」「政府」が混在
  - ゾーンマップ: customer_type: 最小="個人", 最大="政府"

行グループ2: customer_id: 1001～2000の顧客
  - customer_type: 「個人」「法人」「政府」が混在
  - ゾーンマップ: customer_type: 最小="個人", 最大="政府"

... （以下同様）
結果：WHERE customer_type = '個人'というクエリでは、すべての行グループを読み込む必要がある。なぜなら、どの行グループも「個人」「法人」「政府」のすべてを含む可能性がある。
ケース2: customer_typeでまずソートした場合

同じデータをcustomer_typeでまずソートすると：
行グループ1～3: customer_type: 「個人」のみ
  - ゾーンマップ: customer_type: 最小="個人", 最大="個人"

行グループ4～5: customer_type: 「法人」のみ
  - ゾーンマップ: customer_type: 最小="法人", 最大="法人"

行グループ6: customer_type: 「政府」のみ
  - ゾーンマップ: customer_type: 最小="政府", 最大="政府"
結果：WHERE customer_type = '個人'というクエリでは、行グループ1～3だけを読み込めば良い。行グループ4～6は完全にスキップできます。

おそらくこういうことだと思います...!
ただし、タイムスタンプでの並べ替えを行う場合、タイムスタンプは非常に高いカーディナリティを持つことが多いのでタイムスタンプを最も近い週、月、または年に丸めてから他の列でソートする方が有益かもしれません。

 2-5:小さな挿入は避ける小さなバッチや1行ずつデータを挿入すると、データは主に挿入時間順に並んでしまうのでソートが崩れるので避けた方が良いとのことです。

なので大きめのバッチごとに行った方がよいです。

 2-6:チャンクごとのソート処理しかし大きなテーブルに対するソートはメモリ（またはディスクスピル）の量が多いためチャンク分けして処理した方が良いです。複数の SQL 文を通じてテーブルを部分的に処理することで、各 SQL は特定のチャンクにフィルタリングされます。SQL にはループ構造がないため、これはホスト言語（Python、Jinja テンプレートなど）で処理されます。
CREATE OR REPLACE TABLE sorted_table AS
    FROM unsorted_table
    WITH NO DATA;

for chunk in chunks:
    INSERT INTO sorted_table
        FROM unsorted_table
        WHERE chunking_column = chunk
        ORDER BY other_columns...;
これにより、最初はチャンク列でソートし、次に他の列でソートする効果があります。実行に時間がかかる場合がありますが（データはチャンクごとに一度スキャンする必要があるため）、メモリ使用量はかなり少なくなる可能性があります。

 2-7:文字列のソートは最初の数文字だけでVARCHAR列のゾーンマップに文字列値の最小と最大の最初の8バイトだけを格納しています。そのため、最初の8バイト（8つのASCII文字）以上をソートする必要はありません！(😦)

DuckDB のラディックスソートアルゴリズム...というらしいですが

具体的には以下のようなクエリが有効です。
CREATE OR REPLACE TABLE sorted_table AS
    FROM unsorted_table
    ORDER BY varchar_column_to_sort[:8];

 まとめ今回は色々な技術について理解を深めることができました。

いっぺんには理解できないと思うのでゆっくり時間をかけたいと思います!
まえがき

1-1:概要

1-2:タンブリング

1-3:ホッピング

1-4:スライド

1-5:セッション

2-1:概要

2-2. DuckDBのデータベースの内部構造

2-3:ゾーンマップ

2-4:戦略的にスキップする

2-5:小さな挿入は避ける

2-6:チャンクごとのソート処理

2-7:文字列のソートは最初の数文字だけで

まとめ

Discussion
