インデックス作成の概要

インデックスおよびそれがDSE Graphのパフォーマンスにどのように影響するかについて説明します。

DSE Graphは、頂点中心インデックスとグローバル・インデックスの2つのタイプのインデックスを実装します。頂点中心インデックスは、ローカルであり、1つの頂点に固有です。グローバル・インデックスは、頂点ラベルとプロパティに固有であり、グラフ全体を対象とします。すべてのインデックスは、大型分散グラフでのグラフ探索のパフォーマンスに影響します。

頂点中心インデックス作成(VCI)の概要

頂点中心インデックス(VCI:Vertex-Centric Index)は、高速グローバル検索のためにすべてのグラフ要素およびインデックス要素にグローバルに適用されるグローバル・インデックスとは異なり、1つの頂点に固有です。頂点中心インデックスは、インシデント・辺のラベルまたはプロパティに従って、1つの頂点のインシデント・辺と隣接する頂点をソートし、インデックスを作成します。頂点に対するクエリーがあると、すべてのインシデント・辺の線形スキャンを回避するために、頂点のインデックスが参照されます。探索はO(n)からO(1)またはO(log n)に減らすことができます。典型的なグラフ探索では多数の頂点に接触するので、インデックスを参照しないと、インシデント・辺をスキャンするたびにコストが増大します。

DSE Graphでは、頂点中心インデックスはマテリアライズド・ビュー(MV)テーブルとして保持されます。グラフでデータの書き込みまたは更新が行われると、Cassandraの読み取りリペア機能を利用する代わりに、インデックスが更新されます。MVテーブルを使用すると、書き込みレイテンシーは高くなりますが、グラフ探索の読み取りレイテンシーは低くなります。辺インデックスとプロパティ・インデックスは、頂点中心インデックスです。

頂点中心インデックスは、スーパーノードの問題の解決にも一役買います。スーパーノードとは、飛躍的に大きい数のインシデント・辺を持つ頂点のことです。通常示される例は、読者が持っているフォロワーの数(数百または数千)と、有名人が持っているフォロワーの数(数百万)の比較です。スーパーノードのインデックスをチェックするグラフ探索は、インデックス・テーブルを読み取るだけでも並外れた時間がかかります。頂点中心インデックスは、パーティション分割された頂点テーブル(PVT)とともに使用することにより、DSEクラスター全体に分散する複数のパーティションにインデックスを格納することができます。100万個以上の辺を持つ頂点の場合、単一のCassandraテーブルのストレージ制限のため、グラフのパーティション分割が必要です。さらに、インデックス・テーブルを分散させることで、グラフ探索の応答性能も向上します。

グローバル・インデックスの概要

インデックスは、探索クエリーのパフォーマンスに影響します。グラフ探索の開始点の数を減らすことにより、クエリー結果のレイテンシーを大幅に削減することができます。グラフ内のすべての頂点をチェックすることによって探索を開始する必要がある場合、正しい開始点を見つけるために時間を失います。開始頂点を特定できれば、その時間は必要なくなります。頂点ラベルとプロパティ値に基づき頂点の場所のインデックスを作成すると、パフォーマンスが向上します。

グローバル・インデックスでは、DSEの組み込みインデックス作成機能を使用します。DSE GraphはCassandraに格納されるため、Cassandraのセカンダリ・インデックス作成機能とマテリアライズド・ビューに基づく2つのタイプのインデックスが使用可能です。さらに、DSE Graphは全文インデックスおよび文字列インデックスについては、Apache Solrに基づくDSE Searchを利用できます。グローバル・インデックス作成は、これら3タイプのインデックスのどれを使用しても実行できます。選択するタイプはデータ自体によって異なります。インデックス検索のタイプはパフォーマンスにも影響します。

DSE Graphでもセカンダリ・インデックス作成は、Cassandraでのセカンダリ・インデックス作成と同じ原則に従います。このタイプのインデックスは、カーディナリティが低い値、または選択性が低い値のためのものです。選択性は、次の式を使用してカーディナリティから算出します。
選択性 = (カーディナリティ/行数) * 100%
通常、低いカーディナリティでは低選択性、高いカーディナリティでは高選択性という結果になります。国別の検索は、セカンダリ・インデックス作成に適した候補です。

マテリアライズド・ビュー・インデックス作成では、Cassandraのマテリアライズド・ビューを使用してデータを保存します。マテリアライズド・ビューとは、ベース・テーブルから生成されたテーブルのことで、ベース・テーブルとは異なるプライマリ・キーに基づくクエリーを提供します。このタイプのインデックスは、カーディナリティの高い値、ほぼ一意の値、または選択性が高い値に使用するのが最適です。マテリアライズド・ビューの検索では、ベース・テーブルの検索と同様な応答時間になりますが、データの書き込みには少々の時間のペナルティが伴います。

サーチ・インデックスは、DSE Searchで実装されたSolrインデックスに依存します。グラフ・データはCassandraテーブルに格納されるため、頂点ラベルごとに1つのSolrコアを使用できます。これらのインデックスは、この独自の特性のために、構文がセカンダリおよびマテリアライズド・ビュー・インデックスの場合とは異なります。検索によってインデックス付けされる頂点ラベルごとに、searchという名前の1つのサーチ・インデックスにすべてのプロパティを追加する必要があります。検索はDSE Searchで実装されるため、全文インデックスと文字列インデックスの2つのインデックスの選択肢があります。全文インデックスでは、トークン化に加えて、大文字/小文字の正規化のような二次処理が実行されます。全文インデックスは、テキストの部分一致が必要なクエリーに役立ちます。文字列インデックスは、Solrのファセット処理のように、文字列の完全一致検索が求められ、トークン化を行わないクエリーに役立ちます。このタイプのインデックスは、セカンダリ・インデックスのように低選択性の場合に最適です。

複合インデックス・キーは、DSE Graphでは現在サポートされていません。

インデックス作成の慣行

amountプロパティ上にセカンダリ・インデックスとサーチ・インデックスを作成する場合のように、同じプロパティ上に複数のインデックスを作成することができます。DSE Graphクエリー・オプティマイザーは、クエリーの処理時に適切なインデックスを自動的に使用します。必要に応じて、選択性に基づき、異なるプロパティ上に異なるインデックス・タイプを作成することができます。