← AWSサービスの内部原理 コース
8. QueryとScanの内部差 — ハッシュで1発 vs 全部読む
QueryとScanの速度差の正体を、「ハッシュが使えるかどうか」から図で追っていきましょう。
①Queryはハッシュで1発
QueryPKの等値条件(=)が必須
単一の値を必ず与える(公式)キーをハッシュ
hash("Dog")
行き先が1つに定まる
パーティションA
パーティションB
ここだけ開くパーティションC
- ・ハッシュ表のO(1)ルックアップそのもの
- ・全体を探し回らず、1つのパーティションだけ読む
キー値が1つに決まればハッシュ計算で格納先も1つに定まる。だからQueryは探し回らない。
②パーティションの中はソート済み範囲走査
item collection同じPK値の項目群・ソートキー昇順で保存
ソートキーに範囲条件(begins_with / between / 大小)
範囲の手前
始点→終点を連続読み
範囲の先
- ・整列済み配列に対する範囲走査と同じ
- ・「ハッシュで1発」+「ソート済みを連続読み」の2段構え
ハッシュで絞った先はソートキー順に整列済み。範囲の始点から終点まで舐めるだけで済む。
③Scanは全部読んでから捨てる
ScanPK等値条件なし=ハッシュが使えない
全パーティションを順に開く
A 全項目
B 全項目
C 全項目
読み終わった後に適用
FilterExpression結果を返す前に捨てるだけ
課金はここまでに読んだ量で確定減った結果だけ返る
返却結果
- ・線形走査O(n):項目数に比例して時間もコストも増える
- ・フィルタの有無で消費読み取りキャパシティは同じ(公式)
- ・課金は読んだ項目の数とサイズで決まる(強整合は4KB=1RCU基準)
フィルタは全項目を読んだ後に効く。返る件数が減っても、読んだ量=課金される量は1ミリも減らない。
④パラレルスキャン=並列I/Oで上限回避
逐次Scan一度に1パーティションしか読めない
単一パーティションの最大スループットに制約TotalSegmentsで論理分割
Segment 0
Segment 1
Segment 2
Segment番号で担当を指定し同時に読む
ワーカー0スレッド or プロセス
ワーカー1スレッド or プロセス
ワーカー2スレッド or プロセス
- ・OSで学んだマルチスレッド/マルチプロセスの並列I/Oそのもの
- ・セグメント割当もPKのハッシュ基準。キー分布が偏ると空/重いセグメントが生じ、増やしても速くならないことがある
テーブルをセグメントに割り、複数の実行主体で同時に読むことで単一パーティションの上限を回避する。
⑤共通の制約:1MBページネーション
リクエスト1回最大1MB(フィルタ評価の前に適用)
続きがある場合
応答 + LastEvaluatedKey最後に評価した項目のキー
ExclusiveStartKeyに渡す
次のリクエスト続きから読む
LastEvaluatedKeyが無くなったら
終端
QueryもScanも1回のリクエストは最大1MB。巨大な結果を一度にメモリへ載せない、カーソル分割取得の定石。
⑥まとめ:全部、基礎から再導出できる
Queryハッシュで1パーティション+ソート済み範囲走査
速くて安いScan全項目を線形に読む O(n)
遅くて高い- ・パラレルスキャンが速い=並列実行で単一パーティションの上限を回避
- ・フィルタでコストが減らない=読んだ後に捨てるから
- ・正体はハッシュ表・整列済み範囲走査・線形走査・並列I/O
QueryとScanの差は、すでに学んだアルゴリズムとOSの基礎だけで説明がつく。