DuckDB Update & Blog reading #1:Bloom Fileter ・ver 1.21
まえがき
DuckDBのブログ更新の頻度がすごいですね...!
今まで単発気味に記事投稿していたのですが、ちょっと追いつけなくなりそうになってます🫠
そこで今回からDuckDBのブログについてや追加機能で気になったものをピックアップして試したりするまとめ記事を投稿しようと思います。
Parquet Bloom Filters in DuckDB を調べながら読み解く
について所々の単語について自分で調べながら読んでいきます。
(解釈が間違っている可能性があります。)
ブルームフィルター(Bloom filters)
Bloomは一般的には花がいっぱい咲いていてなんというか華やかな印象がある言葉で、こういう機械的な処理に付けられているのが意外でした。(broom(ホウキ)かともおもったが綴りが違うので...)
どうも考案者のBurton Howard Bloomさんの名前から付けられたらしいです。(1970年考案...!)
このフィルターはParquetファイルの列選択時に効果を発揮してるみたいです。
Parquetファイルの列検索手法
ブルームフィルターの前にParquetファイルの列検索手法について解説されています。
Parquetファイルには実はデータを検索しやすいようなindex情報があるらしいです。
そこには行グループ(Parquet内でチャンク分けされてるグループ)の各列の 最小値と最大値などが記録されてます。
以下のようなデータ
ID 名前 年齢
1 田中 25
2 鈴木 30
3 高橋 35
4 山田 40
がある時にindexには、年齢の最小値 → 25 年齢の最大値 → 40
という情報が既に入ってます。
なので例えば「年齢が 50 のデータを検索したい!」という指示が飛んできた時に、indexを読めば
「50はないから飛ばすよ」 と判断して、その行グループを読み飛ばせます。
こういった方法で速度向上をしているらしいです。😳
ソートされているなら全体のデータに対して年齢が50のデータを効率よく検索できます。
じゃあ列内全体で値の順番がランダムになってたらどうなるか。
#データがソートされている場合
行グループ1：10～30歳 → 「20歳はこの範囲内」→ 読み込む
行グループ2：31～50歳 → 「20歳はこの範囲外」→ スキップ
行グループ3：51～70歳 → 「20歳はこの範囲外」→ スキップ
ランダムなデータの場合：
行グループ1：10～65歳（様々な年齢が混在）→ 「50歳はこの範囲内」→ 読み込む
行グループ2：12～68歳（様々な年齢が混在）→ 「50歳はこの範囲内」→ 読み込む
行グループ3：11～70歳（様々な年齢が混在）→ 「50歳はこの範囲内」→ 読み込む
...といったことになってしまう場合があります。なので速度向上が見込めません...
ユニーク値が少ない時にこういった状況を回避するためにParquetは辞書型で検索もしたりできるようにしているみたいです。(dictionary encoding)
しかし行グループの途中で辞書エンコーディングから通常のエンコーディングに切り替えられたりするみたいです。(なので辞書だけ読んで判断しても実は値が含まれていたり...)
また辞書は列データの一部として保存されているので結局その辞書を読むのに、列データをほぼ全体を読み込むのと同じぐらいかかるそうです。
ブルームフィルター
これの解決のために2018年にParquet用のブルームフィルターが追加された。
これのおかげで、
「含まれていない」という判断は 100%正確
「含まれている」という判断は時々間違える（偽陽性）
という判断が各行グループの各列ごとにできるみたいです。
このフィルターの読み込み方は以下です。
「bloom_filter_offset」にブルームフィルターがどこにあるかの情報があるので読む。
→
そこでまず「BloomFilterHeader」というヘッダー(「Thrift」という形式でエンコード（符号化）)を読む。(フィルターの長さなどを含む)
→
実際のブルームフィルターのデータ（magic bytes of the Bloom filter）を読む。
といった流れです。
ブルームフィルターの仕組み自体は複雑らしく効率的に判断できる特殊なデータ構造...みたいです。(いつか原理を深掘りできたらと思いますが...)
ただこのブルームフィルターにも問題があるみたいです。
ブルームフィルターのサイズ情報（bloom_filter_length）は必須ではないらしく位置情報だけあったり(Sparkなど)、ブルームフィルターが複数の場所に散らばっている可能性があったり、各ブルームフィルターに別々のメタデータヘッダーがついてたり...ということでちょっと効率が悪いらしいです。
DuckDBにおけるブルームフィルター
DuckDB 1.2.0でブルームフィルターの読み書きが実装されました。🙌
- 書き込み機能
以下のデータで使用可能
Integer：(TINYINT, UTINYINT, SMALLINT, USMALLINT, INTEGER, UINTEGER, BIGINT, UBIGINT)
：FLOAT, DOUBLE
String types：VARCHAR、BLOB
ネストされた型（リスト、構造体、配列）は未実装
DuckDBが行グループの特定の列に辞書エンコーディングを使用する時、ブルームフィルターが書き込まれます。
DICTIONARY_SIZE_LIMITというパラメータで作成する辞書サイズを変更できます。
(デフォルト値:行グループサイズの10%)
偽陽性を少なく保つためにはブルームフィルターを大きくする必要があります
デフォルトでは、偽陽性率を1%（0.01）に設定しています
つまり、100回「値があるかも」と言ったとき、平均して1回は間違いがある設定です
この比率はBLOOM_FILTER_FALSE_POSITIVE_RATIOというパラメータで変更できます
偽陽性率を下げると（例：0.1%にする）フィルターは大きくなりますが、より正確になります
偽陽性率を上げると（例：5%にする）フィルターは小さくなりますが、間違いが増えます
- 読み込み機能
読み取り機能ではフィルター述語（例：WHERE a = 42）を使ってブルームフィルターがあればそれを調べる。と言う流れで行グループスキップします。
ユーザーはブルームフィルターが含まれているか以下のmetadataで確認可能とのこと。
bloom_filter_offset:ブルームフィルターの位置
bloom_filter_length:ブルームフィルターのサイズ
parquet_bloom_probe:
指定されたファイルと列のブルームフィルターによってどの行グループが除外されるかを実際に確認。
parquet_bloom_probe('file.parquet', 'col1', 42)は、の各行グループに、列col1の値42が各行グループに確実に存在しないかどうかを示すテーブルを返します。
DuckDBにおけるブルームフィルター実践
※ブログ内コードをpythonで実装
10種類の値（0, 100, 200, ..., 900）で各値は1,000万回繰り返されている（合計1億行）&
ランダムに配置されているデータを作成。
行グループサイズはこちらで1,000万行に設定
import duckdb
import pandas as pd
con = duckdb.connect(database=":memory")
# 最初にブルームフィルター付きのファイルを作成
con.sql("""
COPY (
FROM range(10) r1, range(10_000_000) r2
SELECT r1.range * 100 AS r
ORDER BY random()
)
TO 'filter.parquet'
(FORMAT parquet, ROW_GROUP_SIZE 10_000_000);
""")
print(con.sql("""
SELECT r, count(*)
FROM 'filter.parquet'
GROUP BY r
ORDER BY r;
"""))
結果
┌───────┬──────────────┐
│ r │ count_star() │
│ int64 │ int64 │
├───────┼──────────────┤
│ 0 │ 10000000 │
│ 100 │ 10000000 │
│ 200 │ 10000000 │
│ 300 │ 10000000 │
│ 400 │ 10000000 │
│ 500 │ 10000000 │
│ 600 │ 10000000 │
│ 700 │ 10000000 │
│ 800 │ 10000000 │
│ 900 │ 10000000 │
├───────┴──────────────┤
│ 10 rows 2 columns │
└──────────────────────┘
こんどは DICTIONARY_SIZE_LIMIT を 1 にしてブルームフィルターを無効化してます。
con.sql("""
COPY (
FROM range(10) r1, range(10_000_000) r2
SELECT r1.range * 100 AS r
ORDER BY random()
)
TO 'nofilter.parquet'
(FORMAT parquet, DICTIONARY_SIZE_LIMIT 1, ROW_GROUP_SIZE 10_000_000);
""")
print(con.sql("""
SELECT r, count(*)
FROM 'nofilter.parquet'
GROUP BY r
ORDER BY r;
"""))
結果
┌───────┬──────────────┐
│ r │ count_star() │
│ int64 │ int64 │
├───────┼──────────────┤
│ 0 │ 10000000 │
│ 100 │ 10000000 │
│ 200 │ 10000000 │
│ 300 │ 10000000 │
│ 400 │ 10000000 │
│ 500 │ 10000000 │
│ 600 │ 10000000 │
│ 700 │ 10000000 │
│ 800 │ 10000000 │
│ 900 │ 10000000 │
├───────┴──────────────┤
│ 10 rows 2 columns │
└──────────────────────┘
辞書エンコーディングを使用せず、したがってブルームフィルターも使用せず、ファイルのサイズも前回の88 MB(自環境では92MB)より大きくなり、181 MB になります。(自環境では186MB)
501という値を以下のように検索して時間計測。
start = time.time()
print(con.sql("""
SELECT sum(r) FROM 'filter.parquet' WHERE r = 501;
"""))
end = time.time()
print(end - start)
start = time.time()
print(con.sql("""
SELECT sum(r) FROM 'nofilter.parquet' WHERE r = 501;
"""))
end = time.time()
print(end - start)
結果
┌────────┐
│ sum(r) │
│ int128 │
├────────┤
│ NULL │
└────────┘
0.0025947093963623047
┌────────┐
│ sum(r) │
│ int128 │
├────────┤
│ NULL │
└────────┘
0.3185422420501709
501という値はこのデータに存在しないのですが、それを検索するのにブルームフィルターを使用した場合は0.002秒くらいになりました...速度にかなり差がでますね。
また以下のコードでメタデータ確認しています。(FROMを先頭にする書き方って前からできましたっけ...?)
print(con.sql("""
FROM parquet_metadata('filter.parquet')
SELECT row_group_id, stats_min, stats_max,
bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;
"""))
結果
┌──────────────┬───────────┬───────────┬─────────────────────┬─────────────────────┐
│ row_group_id │ stats_min │ stats_max │ bloom_filter_offset │ bloom_filter_length │
│ int64 │ varchar │ varchar │ int64 │ int64 │
├──────────────┼───────────┼───────────┼─────────────────────┼─────────────────────┤
│ 0 │ 0 │ 900 │ 92539679 │ 47 │
│ 1 │ 0 │ 900 │ 92539726 │ 47 │
│ 2 │ 0 │ 900 │ 92539773 │ 47 │
│ 3 │ 0 │ 900 │ 92539820 │ 47 │
│ 4 │ 0 │ 900 │ 92539867 │ 47 │
│ 5 │ 0 │ 900 │ 92539914 │ 47 │
│ 6 │ 0 │ 900 │ 92539961 │ 47 │
│ 7 │ 0 │ 900 │ 92540008 │ 47 │
│ 8 │ 0 │ 900 │ 92540055 │ 47 │
│ 9 │ 0 │ 900 │ 92540102 │ 47 │
├──────────────┴───────────┴───────────┴─────────────────────┴─────────────────────┤
│ 10 rows 5 columns │
└──────────────────────────────────────────────────────────────────────────────────┘
各行ごとに47byteのブルームフィルターが付けられていて計500byteのデータが元データに付与されています。
次はブルームフィルターなしのデータのメタデータ確認です。
print(con.sql("""
FROM parquet_metadata('nofilter.parquet')
SELECT row_group_id, stats_min, stats_max,
bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;
"""))
┌──────────────┬───────────┬───────────┬─────────────────────┬─────────────────────┐
│ row_group_id │ stats_min │ stats_max │ bloom_filter_offset │ bloom_filter_length │
│ int64 │ varchar │ varchar │ int64 │ int64 │
├──────────────┼───────────┼───────────┼─────────────────────┼─────────────────────┤
│ 0 │ 0 │ 900 │ NULL │ NULL │
│ 1 │ 0 │ 900 │ NULL │ NULL │
│ 2 │ 0 │ 900 │ NULL │ NULL │
│ 3 │ 0 │ 900 │ NULL │ NULL │
│ 4 │ 0 │ 900 │ NULL │ NULL │
│ 5 │ 0 │ 900 │ NULL │ NULL │
│ 6 │ 0 │ 900 │ NULL │ NULL │
│ 7 │ 0 │ 900 │ NULL │ NULL │
│ 8 │ 0 │ 900 │ NULL │ NULL │
│ 9 │ 0 │ 900 │ NULL │ NULL │
├──────────────┴───────────┴───────────┴─────────────────────┴─────────────────────┤
│ 10 rows 5 columns │
└──────────────────────────────────────────────────────────────────────────────────┘
NULLになっていることが確認できます。
またparquet_bloom_probeでどこに値があるかどうかの確認もできます。
print(con.sql("""
FROM parquet_bloom_probe('filter.parquet', 'r', 500);
"""))
┌────────────────┬──────────────┬───────────────────────┐
│ file_name │ row_group_id │ bloom_filter_excludes │
│ varchar │ int64 │ boolean │
├────────────────┼──────────────┼───────────────────────┤
│ filter.parquet │ 0 │ false │
│ filter.parquet │ 1 │ false │
│ filter.parquet │ 2 │ false │
│ filter.parquet │ 3 │ false │
│ filter.parquet │ 4 │ false │
│ filter.parquet │ 5 │ false │
│ filter.parquet │ 6 │ false │
│ filter.parquet │ 7 │ false │
│ filter.parquet │ 8 │ false │
│ filter.parquet │ 9 │ false │
├────────────────┴──────────────┴───────────────────────┤
│ 10 rows 3 columns │
└───────────────────────────────────────────────────────┘
ファイルが遅いネットワーク接続を介して読み込まれる場合や、行グループが特に大きく、かつクラスター化されていない少数の個別値がある場合...などで有効です!
英語勉強用
- What if a column's data is randomly shuffled?
「列のデータがランダムにシャッフルされている場合はどうなりますか？」
と言う意味。What if を使わなすぎてわからなかった。「これどうなるの？」というのを聞きたくてまずWhat if という単語が出てきて あとは普通の受け身文をつなげたみたいな使い方なら慣れそうか。
Gems of DuckDB 1.2
Installation Script on Linux and macOS
DuckDB は UNIX 系システムで、下記のようにインストール可能となった。
curl https://install.duckdb.org | sh
オペレーティングシステムとアーキテクチャを判断し、最新リリースのタグを取得し、存在しない場合は最新の DuckDB バイナリを~/.duckdb/cli にダウンロードするとのこと。
Signed Binaries on Windows
Windows 向けの署名済みバイナリ
v1.2.1 から、DuckDB Windows コマンドラインクライアント用にデジタル署名されたバイナリを提供。→署名済みバイナリが要件となる環境でも DuckDB を実行できます。
デジタル署名とは、そのソフトウェアが正規の開発元から提供されたものであることを証明する電子的な署名で、これがあることでWindows上でセキュリティ設定が厳しい環境でもDuckDBを実行できるように!(意外と影響がありそうなアップデート)
OR / IN フィルタのプッシュダウン
バージョン 1.2.0 から、DuckDB はフィルタプッシュダウンに OR および IN 式をサポート
フィルタプッシュダウンとは、処理効率を高めるデータベース最適化技術の一つで
これがDuckDBのOR とINでもサポートされるようになったようです。
-f コマンドラインフラグ
duckdb -f script.sql
こういった -fをつけることでsqlファイルを直接読めるように!
これは以下と同等です：
allowed_directories / allowed_paths オプション
allowed_directories & allowed_paths で、DuckDB が特定のディレクトリやファイル（それぞれ）にアクセスすることを制限!
以下のコードでは/tmp ディレクトリのみを使用するように設定してます。
SET allowed_directories = ['/tmp'];
SET enable_external_access = false;
FROM read_csv('test.csv');
これで別ファイル(test.csv)をみに行こうとするとエラーが出ます。
sum(BOOLEAN)
BOOLEAN 式を CASE 式でラップすることなく、直接その合計を出せる。
SELECT sum(l_extendedprice > 500) FROM lineitem;
Excel Extension
X(旧:Twitter)上でも話題になっていましたがExcelのデータが以下のコードで読めるようになりました。(以前はINSTALLとLOADが必要だった)
FROM read_xlsx('test.xlsx', header = true);
自分は以前はINSTALLができない環境だったのでこのアップデートは便利だと思いました。(ただExcelのデータはこちらで整形しないといけないパターンが多いのであまり多用する場面が出ないことを祈ります。😅)
以上他にもいくつかあるみたいなので公式で確認してください🙏
英語勉強用
-
What if a column's data is randomly shuffled?
「列のデータがランダムにシャッフルされている場合はどうなりますか？」
と言う意味。What if を使わなすぎてわからなかった。「これどうなるの？」というのを聞きたくてまずWhat if という単語が出てきて あとは普通の受け身文をつなげたみたいな使い方なら慣れそうか。 -
heavily leverages this
めちゃくちゃこれ使ってるという感じか -
eliminate row groups
行グループ除外 -
incurred most of the cost of reading the column
列読み込みのコストのほとんどを負担してしまってる -
currently redundant
現在は冗長 -
reasonable first approximations
妥当な初期近似値 -
constant-comparison
x == 5 みたいな比較文 -
automatically exclude all row groups
自動で全行グループを除外
Discussion