一覧DB-07-3 · インデックスと実行計画

統計情報と実行計画

PythonからSQLiteとDuckDBを使います。SQLiteで統計の平均と偏り、更新後の古い統計、索引付きネステッドループを確認します。DuckDBではEXPLAINの予想と実行後の行数を並べ、ハッシュ結合・範囲の結合の計画を調べます。show_planは計画JSONから演算子・条件・行数を表示する補助関数です。

説明

実行計画にある推定行数は、条件に合う行を実際に数えた値ではありません。統計と推定方法に基づく予想です。分布の偏りや更新によって実件数と差が生まれ、結合方法の判断にも影響します。

1偏りのある100行を作る

SQLiteでhotが90件、coldが10件の表と索引を用意します。

import sqlite3
from pprint import pprint
sq = sqlite3.connect(':memory:', isolation_level=None)
sq.executescript('CREATE TABLE events(id INTEGER PRIMARY KEY,kind TEXT); CREATE INDEX events_kind ON events(kind);')
sq.

executemany同じ追加文へ複数の値を渡す('INSERT INTO events VALUES(?,?)', [(i, 'hot' if i<90 else 'cold'90件と10件の偏り

) for i in range(100)])
pprint(sq.execute('SELECT kind,COUNT(*) FROM events

GROUP BY kind実際の件数を数える ORDER BY kind').fetchall())

kindは二種類ですが、件数は均等ではありません。executemanyは同じINSERTへ各組の値を渡します。ここでの?は値のプレースホルダーです。

2索引統計の平均と実件数

ANALYZEで統計を採取します。

sq.execute('ANALYZE')統計を採取


pprint(sq.execute("SELECT idx,stat FROM

sqlite_stat1索引の基本統計

 WHERE idx='events_kind'").fetchall())
pprint(sq.execute("SELECT COUNT(*) FROM events WHERE

kind='cold'少数側の実件数").fetchall())

statの100 50は、索引の総件数100と同じ先頭キー値を持つ平均件数50を表します。一方、coldは10件です。平均の50は各値の実件数ではありません。実際の計画は、利用可能な他の統計や推定規則も使います。

3追加後も古い統計が残る

hotを900行追加します。

sq.executemany('INSERT INTO events VALUES(?,?)', [(i, 'hot') for i in range(100,1000)900件のhotを追加

])
pprint(sq.execute("

SELECT stat保存統計を再確認

 FROM sqlite_stat1 WHERE idx='events_kind'").fetchall())
pprint(sq.execute('SELECT kind,

COUNT(*)現在の件数 FROM events GROUP BY kind ORDER BY kind').fetchall())

統計は100 50のまま、実際はcold10・hot990です。保存データが変わったことと、ANALYZEの統計が更新されたことは同じではありません。古い統計での計画判断が適切とは限らない理由です。

4再採取しても偏りは平均だけでは表せない

もう一度ANALYZEします。

sq.execute('ANALYZE')更新後の統計を取り直す


pprint(sq.execute("SELECT stat FROM sqlite_stat1 WHERE idx='events_kind'").fetchall())

1000 500へ更新されます。しかしcoldの実件数は10なので、平均500との隔たりは残ります。統計を新しくすればすべての値を正確に予想できる、という意味ではありません。どの粒度の情報を持つ統計かも確認します。

5内側を繰り返し走査する結合

三顧客と四注文を作り、観察用に顧客を外側へ固定して自動索引を無効にします。

sq.executescript('PRAGMA automatic_index=OFF自動的な索引生成を止めて観察

; CREATE TABLE customers(id INTEGER PRIMARY KEY); CREATE TABLE orders(id INTEGER PRIMARY KEY,customer_id INTEGER); INSERT INTO customers VALUES(1),(2),(3); INSERT INTO orders VALUES(101,1),(102,1),(103,2),(104,NULL);')
query = 'SELECT c.id,o.id FROM customers c

CROSS JOIN orders o顧客を外側に固定

 WHERE o.customer_id=c.id'
pprint([row[3] for row in sq.execute(

'EXPLAIN QUERY PLAN '+query各ループの探索方法

)])
pprint(sq.execute(query+' ORDER BY c.id,o.id').fetchall())

外側がSCAN c、内側がSCAN oです。ネステッドループは外側の一行ごとに内側の一致を探します。この単純な全走査では3顧客×4注文が候補になり、結果は三組です。CROSS JOINはここでは結合順を固定する観察用の指定で、一般には最適化による順序選択も使います。

6内側の索引で一致範囲を探す

注文のcustomer_idへ索引を付けます。

sq.execute('CREATE INDEX orders_customer ON orders(customer_id)内側の対応キーの索引

')
pprint([row[3] for row in sq.execute(

'EXPLAIN QUERY PLAN '+query内側がSEARCHへ変わるか確認

)])
pprint(sq.execute(query+' ORDER BY c.id,o.id').fetchall())

外側はSCAN c、内側はSEARCH o USING COVERING INDEXです。顧客ごとに注文の全行を見直す代わりに、その顧客IDの索引範囲を探せます。結果の三組は変わりません。内側の探索方法で、同じネステッドループの負担も変わります。

7DuckDBの推定行数を取得する

DuckDBにはhot900件・cold100件の別の表を作ります。

import duckdb
from plan_tools import show_plan
db =

duckdb.connect(':memory:'別のDuckDB接続を作る

, config={'threads': 1})
db.execute("CREATE TABLE events AS SELECT i AS id,CASE WHEN

i<9001000件のうち900件をhotにする

 THEN 'hot' ELSE 'cold' END AS kind FROM range(1000)t(i)")
db.execute('ANALYZE events')
cold_query = "SELECT id FROM events WHERE kind='cold'"

show_plan(db, cold_query)実行前の計画を表示

この計画ではSEQ_SCANのEstimated Cardinalityが500です。これはcoldの行数の予想であり、まだ実測行数を表示していません。

8EXPLAIN ANALYZEで実測と照合する

同じSQLを実行し、演算子の実際の出力行数も表示します。

show_plan(db, cold_query, analyze=TrueSQLを実行し実測の行数も表示)

TABLE_SCANのactual_rowsは100、scanned_rowsは1000です。推定500に対し、条件を満たして出力したのは100行でした。出力行数と走査した行数も異なります。EXPLAIN ANALYZEはSQLを実行するので、単なる計画表示との違いに注意します。

9等号結合のハッシュ結合計画

10行の参照表と1000行の明細を作ります。

db.execute('CREATE TABLE dim AS SELECT i AS id FROM range(10)参照表の10行

t(i)')
db.execute('CREATE TABLE facts AS SELECT i AS id,

i%10 AS dim_id各参照先を100回ずつ使う

 FROM range(1000)t(i)')
join_query = 'SELECT f.id,d.id FROM facts f JOIN dim d ON

f.dim_id=d.id等号の結合条件

'
show_plan(db, join_query)

HASH_JOINと等号の結合条件が表示されます。一般にハッシュ結合では片側のキーから検索用のハッシュ表を作り、他方のキーで候補を探して元の値を照合します。この例はdim_idが0～9を繰り返すため、全1000明細に相手があります。

10結合結果の推定と実測

結合を実行して各演算子の行数を表示します。

show_plan(db, join_query, analyze=True結合の実測行数

)
print(db.execute("

SELECT COUNT(*) FROM (結果件数を別に数える"+join_query+")").fetchone())

結合の実測は1000行、別のCOUNTも1000です。計画の推定行数とは差があります。ハッシュ結合でも、キーの重複や未一致があると出力件数は入力件数と一致しないため、条件と各演算子の行数を合わせて確認します。

11範囲条件では別の結合方式になる

等号を小なりへ変えます。

range_query = 'SELECT f.id,d.id FROM facts f JOIN dim d ON f.dim_id<d.id一致ではなく範囲の対応

show_plan(db, range_query, analyze=True)条件変更後の方式と行数


print(db.execute('SELECT COUNT(*) FROM ('+range_query+')').fetchone())

この条件と大きさではPIECEWISE_MERGE_JOINとなり、結果は4500行です。dim_idが0なら相手は1～9の9行、1なら8行、…、9なら0行で、各値が100件あるため100×(9+8+…+0)=4500です。等号のハッシュ照合と同じ方法を、そのまま範囲条件へ使うわけではありません。

12ハッシュの区画が同じでもキーの等号を確認する

二つの区画に分ける簡単な例で、候補と実際の一致を表示します。

keys = [1, 3, 4]
buckets = {0: [k for k in keys if

k%2説明用の区画番号

==0], 1: [k for k in keys if k%2==1]}
probe = 3
print('buckets:', buckets)
print('candidates:',

buckets[probe%2]同じ区画の候補

)
print('matches:', [k for k in buckets[probe%2]

if k==probe元のキーの等号で確認])

キー1と3は同じ区画1に入りますが、probe=3に一致するのは3だけです。区画が同じことはキーが同じことを保証しません。ここでのk%2は衝突の意味を説明するための二区画の例で、DuckDBが内部で使うハッシュ関数や区画数を表していません。

まとめ

基本統計の平均は値ごとの実件数と異なり、更新後の古さと分布の偏りを確認します。

ネステッドループは内側の索引利用で探索負担が変わります。

計画の推定・実測・走査行数と、結合条件を対応させて結果を説明します。

操作履歴と解説を振り返れます。

対応表・資料

計画表示の項目
項目	意味
Estimated Cardinality	演算子が出力する行数の予想
actual_rows	実行時に演算子が出力した行数
scanned_rows	走査演算子が読んだ行数
SEARCH / SCAN	SQLiteでの範囲探索と全体の走査
HASH_JOIN	等号キーのハッシュ照合を使う結合
PIECEWISE_MERGE_JOIN	この例で範囲条件に選ばれた結合方式

Python / SQLite・DuckDB 2.0.0

import sqlite3
from pprint import pprint
sq = sqlite3.connect(':memory:', isolation_level=None)
sq.executescript('CREATE TABLE events(id INTEGER PRIMARY KEY,kind TEXT); CREATE INDEX events_kind ON events(kind);')
sq.executemany('INSERT INTO events VALUES(?,?)', [(i, 'hot' if i<90 else 'cold') for i in range(100)])
pprint(sq.execute('SELECT kind,COUNT(*) FROM events GROUP BY kind ORDER BY kind').fetchall())

[('cold', 10), ('hot', 90)]

sq.execute('ANALYZE')
pprint(sq.execute("SELECT idx,stat FROM sqlite_stat1 WHERE idx='events_kind'").fetchall())
pprint(sq.execute("SELECT COUNT(*) FROM events WHERE kind='cold'").fetchall())

[('events_kind', '100 50')]
[(10,)]

sq.executemany('INSERT INTO events VALUES(?,?)', [(i, 'hot') for i in range(100,1000)])
pprint(sq.execute("SELECT stat FROM sqlite_stat1 WHERE idx='events_kind'").fetchall())
pprint(sq.execute('SELECT kind,COUNT(*) FROM events GROUP BY kind ORDER BY kind').fetchall())

[('100 50',)]
[('cold', 10), ('hot', 990)]

sq.execute('ANALYZE')
pprint(sq.execute("SELECT stat FROM sqlite_stat1 WHERE idx='events_kind'").fetchall())

[('1000 500',)]

sq.executescript('PRAGMA automatic_index=OFF; CREATE TABLE customers(id INTEGER PRIMARY KEY); CREATE TABLE orders(id INTEGER PRIMARY KEY,customer_id INTEGER); INSERT INTO customers VALUES(1),(2),(3); INSERT INTO orders VALUES(101,1),(102,1),(103,2),(104,NULL);')
query = 'SELECT c.id,o.id FROM customers c CROSS JOIN orders o WHERE o.customer_id=c.id'
pprint([row[3] for row in sq.execute('EXPLAIN QUERY PLAN '+query)])
pprint(sq.execute(query+' ORDER BY c.id,o.id').fetchall())

['SCAN c', 'SCAN o']
[(1, 101), (1, 102), (2, 103)]

sq.execute('CREATE INDEX orders_customer ON orders(customer_id)')
pprint([row[3] for row in sq.execute('EXPLAIN QUERY PLAN '+query)])
pprint(sq.execute(query+' ORDER BY c.id,o.id').fetchall())

['SCAN c', 'SEARCH o USING COVERING INDEX orders_customer (customer_id=?)']
[(1, 101), (1, 102), (2, 103)]

import duckdb
from plan_tools import show_plan
db = duckdb.connect(':memory:', config={'threads': 1})
db.execute("CREATE TABLE events AS SELECT i AS id,CASE WHEN i<900 THEN 'hot' ELSE 'cold' END AS kind FROM range(1000)t(i)")
db.execute('ANALYZE events')
cold_query = "SELECT id FROM events WHERE kind='cold'"
show_plan(db, cold_query)

SEQ_SCAN | Table=memory.main.events | Filters=(kind = 'cold') | Estimated Cardinality=500

show_plan(db, cold_query, analyze=True)

TABLE_SCAN | Table=memory.main.events | Filters=(kind = 'cold') | Estimated Cardinality=500 | actual_rows=100 | scanned_rows=1000

db.execute('CREATE TABLE dim AS SELECT i AS id FROM range(10)t(i)')
db.execute('CREATE TABLE facts AS SELECT i AS id,i%10 AS dim_id FROM range(1000)t(i)')
join_query = 'SELECT f.id,d.id FROM facts f JOIN dim d ON f.dim_id=d.id'
show_plan(db, join_query)

PROJECTION | Estimated Cardinality=909
  HASH_JOIN | Join Type=INNER | Conditions=dim_id = id | Estimated Cardinality=909
    SEQ_SCAN | Table=memory.main.facts | Estimated Cardinality=1000
    SEQ_SCAN | Table=memory.main.dim | Estimated Cardinality=10

show_plan(db, join_query, analyze=True)
print(db.execute("SELECT COUNT(*) FROM ("+join_query+")").fetchone())

PROJECTION | Estimated Cardinality=909 | actual_rows=1000
  HASH_JOIN | Join Type=INNER | Conditions=dim_id = id | Estimated Cardinality=909 | actual_rows=1000
    TABLE_SCAN | Table=memory.main.facts | Estimated Cardinality=1000 | actual_rows=1000 | scanned_rows=1000
    TABLE_SCAN | Table=memory.main.dim | Estimated Cardinality=10 | actual_rows=10 | scanned_rows=10
(1000,)

range_query = 'SELECT f.id,d.id FROM facts f JOIN dim d ON f.dim_id<d.id'
show_plan(db, range_query, analyze=True)
print(db.execute('SELECT COUNT(*) FROM ('+range_query+')').fetchone())

PROJECTION | Estimated Cardinality=2021 | actual_rows=4500
  PIECEWISE_MERGE_JOIN | Join Type=INNER | Conditions=dim_id < id | Estimated Cardinality=2021 | actual_rows=4500
    TABLE_SCAN | Table=memory.main.facts | Estimated Cardinality=1000 | actual_rows=1000 | scanned_rows=1000
    TABLE_SCAN | Table=memory.main.dim | Estimated Cardinality=10 | actual_rows=10 | scanned_rows=10
(4500,)

keys = [1, 3, 4]
buckets = {0: [k for k in keys if k%2==0], 1: [k for k in keys if k%2==1]}
probe = 3
print('buckets:', buckets)
print('candidates:', buckets[probe%2])
print('matches:', [k for k in buckets[probe%2] if k==probe])

buckets: {0: [4], 1: [1, 3]}
candidates: [1, 3]
matches: [3]

演習完了