Zenn
🐥

様々なIndicesについて

2023/11/08に公開
#
storage
#
index
tech

Primary Key Index & Secondary Index

Storage Engine(Hash Inex, LSM-Tree, B-Tree)の記事にて、
Key-Value Indexについて説明しているが、これはPrimary Key の Indexのようなもの

Primary-Key

  • Relational DB Table中の1行, Document DBの1document, Graph DBの1頂点 を一意(Unique)に特定する

Secondary Index(非クラスタ化インデックス)

RDBでは、Foregin-Keyが具体例として挙げられる.
Key-Value indexから容易に構築可能.
異なる点は、Secondary Keyはuniqueではないため、同じkeyを持つ行(やdocumentや頂点)が複数存在し得る.

  • 複数keyが存在する場合の対処方法は以下の2つ
    1. Index内のそれぞれの値をマッチする行の識別子のリストにすること
      • 例えば、colorというカラムに対するSecondary Indexを考えると、redという値に対して、それにマッチするすべての行の識別子のリストがインデックスに格納される
      • メリット: 同じキー値を持つ複数の行を効率的に検索できる
      • デメリット: データの更新や削除が頻繁に行われる場合、インデックスのメンテナンスが複雑になる可能性がある
    2. それぞれのKeyに行の識別子を追加してKeyをuniqueにすること
      • 例えば、colorというカラムの値redと、行の識別子ID:123を組み合わせて、red|ID:123のようなユニークなキーを作成する
      • メリット: インデックスのメンテナンスがシンプルになる.また、インデックスのサイズが小さくなる可能性がある
      • デメリット: 検索時には行の識別子を取り除く処理が必要となり、この処理がオーバーヘッドとなる可能性がある

どちらかを対応することにより、B-Treeやlog-structuredなIndexをSecondary Indexとして利用することが可能

クエリによるデータの取得

クエリが検索するのはindex中のkeyで、結果は以下の2種類のどちらからか取得する

  1. 探していたdisk上の行(document, 頂点): ディスク上のデータ構造(LSM-Tree, B-Tree, ...etc)
    • データがdisk上の特定の場所に物理的に格納されている場所
  2. ヒープファイル上に存在する行(document, 頂点)
    • データが特定の順序なく格納されているファイル
      • Indexはヒープファイル内の特定の行の場所を示す情報を持っているため、クエリはindexを使用してヒープファイル上の正確な場所を特定してデータを取得する

一貫性の保証:
Database Systemは、トランザクションの完了後にデータの一貫性を保証することが多い
これは、ACIDプロパティの一部として確実に行われる
したがって、トランザクションがコミットされた後、ヒープファイルと他のデータ構造の間に差異が存在することは通常ない
(トランザクションの途中/システム障害のクラッシュ時には一時的な差異が生じる可能性がある)

ヒープファイルについて

追記のみ行われるような仕様になっているケース
新しいデータで後から上書きができるように削除された行を追跡するような仕様になっているケース
それぞれ存在する

  • メリット
    • 複数のSecondary Indexがある場合、データが複製されるのを避けられる
      • それぞれのIndexはヒープファイルを参照するだけであり、実際のデータが保存される場所は1つ
    • Keyの変更を伴わない値の更新の場合、ヒープファイルのアプローチは非常に効率的になる可能性がある
      • 新しい値が古い値より大きくなければ、元の場所でrecordを上書きすることができるため
  • デメリット
    • Keyの更新が伴い、Keyの新しい値が古い値より大きくなれば、ヒープ中に十分に空きがある場所へrecordを移動しなければならなくなるため、状況は複雑になる
      • 対策: ヒープ中の新しい場所をさすように全てのindexを更新するか、ヒープ中の元の場所に移転先を指すポインタを残すことで対応可能

クラスタ化Index

クラスタ化インデックスは、データベーステーブルの物理的な順序を制御するインデックス
つまり、このインデックスの順序は、ディスク上での実際のデータの順序と一致する.

Indexからヒープファイルに至る過程でホップ数が追加されることは、読み取りのパフォーマンス的には微妙になり得る.
上記のようなケースでは、Index付けされた行を直接Index内に保存することが望ましいケースがある(=クラスタ化Index).
-> キーの順序に従って、実際のデータも物理的にディスク上に保存されることを示す
※ インデックスからヒープファイルやディスク上のデータを参照する際の間接的なステップを「ホップ」と呼ぶ

  • 例: InnoDBについて
    • tableのPrimary Keyは必ずクラスタ化Indexになる
    • Secondary Indexは (ヒープファイル中の場所ではなく)Primary Keyへの参照になる(Secondary Index = 非クラスタ化インデックス)
      • Secondary Indexに対して、複数のdataが紐づく場合、複数のPrimary Keyへの参照となる

データを複製する場合、クラスタ化インデックス、カバーリングインデックスを利用することで読み取り速度を向上させることは可能になるが、
ストレージは余分に必要になり、書き込みにはオーバーヘッドが生じる

クラスタ化インデックスが速くなる理由

  • Diskアクセス特性
    • データが物理的に連続して配置されている場合、一度ディスクヘッドが正しい位置に移動すると、連続的なデータの読み取りは非常に高速
    • 一方、データがディスク上の異なる場所に散らばっている場合、各データの読み取りごとにシークが必要となり、パフォーマンスが低下(データへのポインタのみだとランダム参照になる)
  • 連続的な読み取りの効率性
    • クラスタ化インデックスのキーの順序に従ってデータが物理的に配置されている場合、範囲クエリや順序付けされた結果セットの取得など、連続的なデータの読み取りが非常に効率的
  • ポインタのオーバーヘッド
    • クラスタ化インデックスの場合、インデックスキーとデータへのポインタ（または参照）が格納
    • このポインタを使用して実際のデータの場所を特定し、データを読み取る必要がある
    • この間接的なステップは、クラスタ化インデックスの直接的なデータアクセスに比べてオーバーヘッドとなり得る

References

複合Index

上記までは、単一keyを値をmappingするindexだったが、
table中の複数の列(あるいはドキュメントの複数のfield)に対するクエリを行う場合、十分でない(以下のクエリなど)

  • 連結Index
    • データの物理的な順序がインデックスのKeyの順序と一致するインデックス
    • つまり、インデックスとデータが一緒に格納される
  • 多次元Index
    • 複数の属性またはキーに基づいてデータをインデックス化する方法
    • 空間データベースや多次元データを扱う場合に特に役立つ
      • 2次元（例: X, Y座標）や3次元（例: X, Y, Z座標）など、複数の属性に基づいてデータをインデックス化
      • 空間的なクエリ（例: ある範囲内のすべての点を検索する）が高速になる
      • R-treeやK-d treeなどの特定のデータ構造が多次元インデックスの実装に使用される
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004

曖昧Index for 全文検索

ここまでのIndexは、使用するデータがすべて厳密なものであり、Keyの厳密な値を使ってクエリを行ったり、
ソート順序を持つKeyの範囲に対してクエリを行うことを前提としていた

-> 上記のようなIndexでは、スペルミスを含む単語のような類似のKeyを探すことができない

全文検索エンジンでは、
ある単語を検索するとその対象に同意語を含めることが可能
文法条の語の変化を無視することが可能
同じドキュメント中で複数の語が近くにあることを検索することが可能
そのため、テキストの言語解析に基づいて他にも様々な機能をサポートすることが一般的

Lucene

特定の編集距離内にある語をテキストから検索できる.
語の辞書にSSTableに似た構造を利用している

  • Keyを探す必要があるソート済みのファイル中で、オフセットをクエリに教えてくれる小さなインメモリのインデックスが必要
  • このインメモリのインデックスは、LevelDBでは一部のキーからなる疎なインデックスだが、Luceneではtrieに似たキー内の文字に対する有限状態オートマイン

Transaction Process or Analytic Process

現在DBの利用用途は、Online Transaction Processing(OLTP)だけではなく、
大量のデータに対する分析をする用途で利用されていることが増えている.

OLTP(Online Analytic Process) OLAP(Online Analytic Process)
主な読み取りパターン Queryごとに少数レコードをKeyに基づいてfetch 大量レコードを集計
主な書き込みパターン ユーザーの入力によるランダムアクセスと低レイテンシの書き込み Bulk Import(ETL(=Extract-Transform-Load)) or Event Stream
主な利用主体 Web Applicationのエンドユーザー 経営判断をするアナリスト
データの内容 ユーザーの最新の状態 時間の経過とともに生じた履歴
データサイズ GB ~ TB TB ~ PB(ペタバイト)
  • Transaction Process
    • log-structuredはファイルの追記&古くなったファイルの削除
      • LSM-Tree, LevelDB, Cassandra, HBase, Lucene
    • InPlaceで更新を行う考え方は、diskを更新可能な固定サイズのPageの集合として扱う
      • B-Treeなど
  • Analytics Process
    • RedShift, ApacheHive, SparkSQL
      • これらは全て列指向のDB

列指向Storage

  • 同じようなデータが列に集まるため圧縮率が高くなる
  • ベクトル化の処理(Vectorized Processing)
    1. クエリエンジンはCPUのL1キャッシュにうまく収まる圧縮された列のデータのチャンクを取る
    2. 密な(関数を呼び出しを行わない)ループ内で処理を繰り返すことが可能
    • 圧縮された列のデータのチャンクを直接処理できるようにして、AND/OR演算を可能にしている

列ストレージにおけるソート順序

  • 最もシンプルなのは、行が挿入された順序で保存していくこと
    • 新しい行の挿入はそれぞれの列ファイルへの追記だけ
  • SSTableのように順序を強制して、これをIndexの仕組みとして扱うことも可能

列ストレージへの書き込み

列指向であれば、ソートされたテーブルの途中に列を挿入したいとなった時、全ての列ファイルを書き直す必要が出る
なので、LSM-Treeのような書き込みを行う.

  1. 全ての書き込みはインメモリストアに送られる
  2. ソート済みの構造に追加されてdiskへの書き込みに備える(LSM-Tree)
    • インメモリストアげ行指向or列指向なのかは問題にはならない
  3. 十分な書き込みが蓄積されれば、disk上の列ファイルとmerge
  4. 1度に新しいファイルに書き出される

Discussion