🦆

DuckdbのBlog「Catching up with Windowing」について簡単な検証をしてみた

2025/02/12に公開

Blogリンク

https://duckdb.org/2025/02/10/window-catchup.html

概要

2025-02-10に上のブログが書かれた。内容は英語だったがWindow関数についての歴史やパフォーマンスについて書かれており面白い内容だったので簡単な要約と検証も兼ねてpythonでコードを書いてみました。

ウィンドウ関数に関するキャッチアップ

著者: リチャード・ウェズリー
公開日: 2025年2月10日

Window関数が導入された背景

  • 時系列データなどの処理は従来のSQLクエリでは非常に難しかった
    →不等号条件でのself-joinを含むから(計算量がめちゃくちゃ増えるなどのデメリット)
  • そのため1990年代後半にウィンドウリング操作が追加され始めた。
    →SQL:2003標準に追加された。

Duckdbではウィンドウ関数を割と早い段階から導入しているので今回は最近追加された機能について紹介するとのこと

DuckDB implements a number of modern windowing features
いくつかのモダンなウィンドウ関数に関する実装
boundary types

テーブルを作成

# フィールド	型	説明
# event	VARCHAR	イベント名(例: 200メートルバタフライ)
# athlete	VARCHAR	競技者名(例: マイケル・フェルプス)
# date	TIMESTAMP	イベントの開始時刻
# time	DECIMAL(18, 3)	アスリートのイベントにおけるタイム(秒)

検証用にこのテーブルをpythonとduckdbで以下のようなコードで作成した

import duckdb
import random
from datetime import datetime, timedelta
import time

# DuckDB接続
con = duckdb.connect(database=":memory:")

# テーブル作成
con.sql("""
CREATE TABLE events (
     event VARCHAR,
     athlete VARCHAR,
     date TIMESTAMP,
     time DECIMAL(18, 3)
);
""")

# イベント名と選手名のリスト
events_list = [
     '200メートルバタフライ', '100メートル自由形', '400メートル個人メドレー',
     '200メートル平泳ぎ', '1500メートル自由形', '100メートル背泳ぎ',
     '200メートル自由形', '400メートル自由形', '800メートル自由形',
     '100メートルバタフライ', '200メートル背泳ぎ', '200メートル個人メドレー'
]

athletes_list = [
     'マイケル・フェルプス', 'カイラ・アトキン', 'スチーブン・ミラー',
     'アリス・ジョンソン', 'ジョン・スミス', 'サラ・ジョンソン',
     'デビッド・リー', 'エミリー・スミス', 'ロバート・ブラウン',
     'リサ・ホワイト', 'ジェームズ・ウィルソン', 'アナ・ジョンソン'
]

# データ挿入(100万)
for i in range(1000000):
     event = random.choice(events_list)
     athlete = random.choice(athletes_list)
     date = datetime(2023, 8, 1) + timedelta(days=random.randint(0, 30), hours=random.randint(0, 23))
     time_rand = round(random.uniform(1.0, 20.0), 3)  # 1.0秒から20.0秒の間でランダムな時間を生成
     con.sql(f"""
     INSERT INTO events (event, athlete, date, time) VALUES
     ('{event}', '{athlete}', '{date}', {time_rand});
     """)

とりあえず時間計測用に百万行作成しているが動作確認だけしたい場合はrange(1000000)の部分を適当に変更してください。

GROUPSフレーミング

ROWS と RANGE と GROUPSについて

ROWS:指定した範囲の行のカウント 行のカウントだけなので速い

s_time = time.time()
rows_result = con.sql("""
SELECT
    *, 
    COUNT(athlete) OVER (
        PARTITION BY athlete 
        ORDER BY time 
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS count_within_athlete
FROM 
    events
""")
e_time = time.time()
print(rows_result)
print(e_time - s_time)
#0.00025463104248046875秒

RANGE:現在の行からウインドウの開始行までの範囲を指定している。

s_time = time.time()
range_result = con.sql("""
SELECT
    *, 
    COUNT(athlete) OVER (
        PARTITION BY athlete 
        ORDER BY time 
        RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS count_within_athlete
FROM 
    events
""")

print(range_result)
e_time = time.time()
print(e_time - s_time)
#0.348832368850708秒

GROUPS:同じアスリートの中の現在の行までの範囲

数年の作業を経てインフラが進化し、v1.2.0以降に追加

s_time = time.time()
group_result = con.sql("""
SELECT
    *, 
    COUNT(athlete) OVER (
        PARTITION BY athlete 
        ORDER BY time 
        GROUPS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS count_within_athlete
FROM 
    events
""")

print(group_result)
e_time = time.time()
print(e_time - s_time)
#0.34781813621520996秒

ROWSとRANGEとGROUPSの違い

# 以下のようなデータがある場合...
# time	athlete
# 1.000	アリス・ジョンソン
# 1.001	アリス・ジョンソン
# 1.001	アリス・ジョンソン
# 1.002	アリス・ジョンソン

# ROWS:すべての行を個別にカウント
# 1.000: 1
# 1.001: 2
# 1.001: 3
# 1.002: 4

# RANGE:同じ値を含めてカウント
# 1.000: 1
# 1.001: 3 
# 1.001: 3
# 1.002: 4

# GROUPS:同じ値をまとめてカウント
# 1.000: 1
# 1.001: 2 (1.001 の行をまとめてカウント)
# 1.001: 2
# 1.002: 3 (1.002 の行をカウント)

フレーム除外(EXCLUDE)

EXCLUDEとCURRENT ROWで周囲の行の集約値を計算し、現在の行と比較できる。
この例では、アスリートのイベントにおけるタイムが、そのイベントの記録されたすべてのタイムの平均と比較されます(±10日間):

# SELECT
#     event,
#     date,
#     athlete,
#     avg(time) OVER w AS recent
# FROM results
# WINDOW w AS (
#     PARTITION BY event
#     ORDER BY date
#     RANGE BETWEEN 10 DAYS PRECEDING AND 10 DAYS FOLLOWING
#         EXCLUDE CURRENT ROW
# )
# ORDER BY event, date, athlete;

# 自分が作成したデータが悪かったのか以上のコードでは動かなかったので以下のコードで試した。
exclude_result = con.sql("""
SELECT
    event,
    date,
    athlete,
    AVG(time) OVER w AS recent
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL '10 days' PRECEDING AND INTERVAL '10 days' FOLLOWING
        EXCLUDE CURRENT ROW
)
ORDER BY event, date, athlete;
""")

EXCLUDEの四つのオプション・CURRENT ROW、GROUP、TIES、NO OTHERS

# 20日間の平均? ここ20日間の同じeventでの他の選手のタイム平均 その日のイベントは除外
# 同じイベント同じ日付の10 日に参加した選手がいない場合平均が計算できないのでnull
# CURRENT ROW: 現在の行のみを除外
exclude_result = con.sql("""
SELECT
    event,
    date,
    athlete,
    AVG(time) OVER w AS recent
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL '10 days' PRECEDING AND INTERVAL '10 days' FOLLOWING
        EXCLUDE CURRENT ROW
)
ORDER BY event, date, athlete;
""")

print(exclude_result)


# GROUP: 現在の行とその「仲間」(ORDER BY値が同じ行)を除外
# 現在の行とそのgroup(同じ日付の選手)を除外→用途によってgroupは変更可能
# この場合だと同じ日付に参加した他の選手がいない場合平均計算できないのでNULL
exclude_group_result = con.sql("""
SELECT
    event,
    date,
    athlete,
    AVG(time) OVER w AS recent
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL '10 days' PRECEDING AND INTERVAL '10 days' FOLLOWING
        EXCLUDE GROUP
)
ORDER BY event, date, athlete;
""")

print(exclude_group_result)



# TIES: 現在の行を除外せず、すべての仲間行を除外(両側に穴を作る)
#逆に同じ日の別選手は除く
exclude_ties_result = con.sql("""
SELECT
    event,
    date,
    athlete,
    AVG(time) OVER w AS recent
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL '10 days' PRECEDING AND INTERVAL '10 days' FOLLOWING
        EXCLUDE TIES
)
ORDER BY event, date, athlete;
""")

print(exclude_ties_result)


# NO OTHERS: 何も除外しない(デフォルト)
#除外なし
no_others_result = con.sql("""
SELECT
    event,
    date,
    athlete,
    AVG(time) OVER w AS recent
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    RANGE BETWEEN INTERVAL '10 days' PRECEDING AND INTERVAL '10 days' FOLLOWING
)
ORDER BY event, date, athlete;
""")

print(no_others_result)

QUALIFY句

SQL計算順序について
例えば集約(SUMなど)は行レベルの式(+など)の後に計算されます。
WHEREは行レベルの計算に使用され、HAVINGはGROUP BYの後に適用されるなどなど。

OVER関数の結果のフィルタリングについて

WITH句の共通テーブル式(CTE)にクエリを入れる

# -- 各イベントの3番目に速いタイムを見つける
s_time = time.time()
over1 = con.sql("""
WITH windowed AS (
    SELECT
        event,
        athlete,
        time,
        row_number() OVER w AS r
    FROM events
    WINDOW w AS (
        PARTITION BY event
        ORDER BY time
    )
)
SELECT event, athlete, time
FROM windowed
WHERE r = 3;

""")

print(over1)
e_time = time.time()
print(e_time - s_time)
#0.26172375679016113秒

ウィンドウ関数をフィルタリングするためのQUALIFY句

# QUALIFYでWINDOW関数に直接フィルタリングできる!
s_time = time.time()
over2 = con.sql("""
SELECT event, athlete, time
FROM events
WINDOW w AS (
    PARTITION BY event
    ORDER BY time
)
QUALIFY row_number() OVER w = 3;

""")
print(over2)
e_time = time.time()
print(e_time - s_time)
#0.2621743679046631秒

どちらも速度的には同じ?

集約修飾子

ウィンドウリングの文脈でも役立ついくつかの修飾子(FILTER、DISTINCT、およびORDER BYを引数として使用すること)

FILTERはかなり直感的で、他の修飾子は効率的に実装するのが難しい。

以下の各行計算のような遅い実装も可能(オプティマイザの無効化?)
すべての値を再読み込みする。
不要な値をフィルタリングする。
重複を取り除くためにハッシュテーブルに格納する。
結果をソートする。
集約関数に送信して結果を得る。
この方法で実装したものもあります(最適化をオフにすることでアクセスできますが、非常に遅いです)。

重複削除について

DISTINCT修飾子を使用してフレーム内の重複を除外できます:

-- 特定の時点における異なるアスリートの数をカウント

# distinct = con.sql("""
# SELECT count(DISTINCT athlete) OVER (ORDER BY date) FROM events;
# """)
# print(distinct)

-- それらの異なるアスリートをリストに連結

# distinct2 = con.sql("""
# SELECT list(DISTINCT athlete) OVER (ORDER BY date) FROM events;
# """)
# print(distinct2)

ORDER BY修飾子を使用して、順序ソート

-- タイムを達成または上回ったアスリートのアルファベット順リストを返す

# distinct3 = con.sql("""
# SELECT list(athlete ORDER BY athlete) OVER (
#     PARTITION BY event, date
#     ORDER BY time DESC
# )
# FROM events;
# """)
# print(distinct3)

時間を出したアスリートを除外したい場合:

組み合わせると遅い実装?

# -- 各タイムを上回ったアスリートのアルファベット順リストを返す
# SELECT list(athlete ORDER BY athlete) OVER (
#     PARTITION BY event, date
#     ORDER BY time DESC
#     EXCLUDE CURRENT ROW
# )
# FROM results;

# 計算できないので以下で代用
# distinct4 = con.sql("""
# SELECT list(athlete ORDER BY athlete) OVER (
#     PARTITION BY event, date
#     ORDER BY time DESC
#     ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
#     EXCLUDE CURRENT ROW
# )
# FROM events;
# """)
#遅くなるかもと言った内容だったが検証しても速度が遅くならなかったので要検証

関数修飾子

ORDER BY修飾子+非集約ウィンドウ関数(フレーミング)

各イベントの時系列における現在の世界記録保持者を計算


SELECT
    event,
    date,
    first_value(time ORDER BY time DESC) OVER w AS record_time,
    first_value(athlete ORDER BY time DESC) OVER w AS record_holder
FROM results
WINDOW w AS (
    PARTITION BY event
    ORDER BY date
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
)
ORDER BY event, date;

すべての非集約ウィンドウ関数(dense_rankを除く)は、現在 ORDER BY 引数をサポート しており、ORDER BY 引数が指定された場合、パーティション全体ではなくフレームを使用するようになる。

フレーム全体を使用するなら明示的にRANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWINGの使用する必要がある。

Discussion