はじめに
前回は、ハッシュ結合における具体的な並列化方法を説明しました。今回は、これまで説明してきたアルゴリズムの性能を定量的に見積ってみます。
データ処理性能の見積り
これまで、第6回では、選択処理のアルゴリズムとしてスキャン（Scan）と索引スキャン（Index Scan）について、第7回と第8回では、結合処理のアルゴリズムとしてソートマージ結合とハッシュ結合について、それらの並列化方法を説明してきました[1]。ここでは、それらのデータ処理の性能を定量的に見積り、すなわち、当該アルゴリズムの複雑さ（計算量）や処理量を数値化し、それらを比較してみようと思います。
まずは、前提条件を整理しておきます。
- RとSの2つのデータが存在
- R、Sは複数の計算機に均等に分割されており、各計算機においてはN個のレコード（タプル）から構成
- R、Sのそれぞれのレコードのサイズ（RecordSize）は同一
- データを処理する各計算機は性能は同一
すなわち、ひとまず理想的な環境を想定します。この場合においては、複数の計算機により並列にデータ処理を行うものの、当該データ処理の性能を見積もるうえでは、1台の計算機における処理量や処理時間に着目すればよいこととなります。
選択処理の性能見積り
初めに、選択処理のアルゴリズムであるスキャンと索引スキャンにおけるレコードアクセス回数と計算量を見てみましょう。対象データをRとします。
スキャンの場合は、すべてのデータを走査するので、レコードの取得個数に限らずN回のレコードアクセスを行います。すなわち、（時間）計算量はO(N)です。
一方、索引スキャンにおいては、レコードアクセスの都度にN個のエントリを有する索引にアクセスする必要があるため、1つのレコードを取得するには、logN回の索引へのアクセスと1回のデータ（実表）へのアクセスが必要であり[2]、よって、n個のレコードにアクセスする場合は、nlogN＋n回のレコードアクセスが必要です。すなわち、計算量はO(nlogN)です。
このとき、Nが100である場合は、スキャンにおける計算量は100となり、索引スキャンの場合は10nとなるため、選択処理のアルゴリズムとしては、nが10より小さい場合は索引スキャン、nが10より大きい場合はスキャンを選ぶことがレコードアクセス回数のうえでは望ましいと考えられます。
結合処理の性能見積り
次に、結合処理のアルゴリズムであるソートマージ結合とハッシュ結合における計算量を見てみましょう。並列結合処理においては、通常、結合キーによる再分割が行われますが、再分割後のデータも均等に分割されるものとします。
ソートマージ結合においては、RとSをそれぞれ整列するためにO(NlogN)とO(MlogM)を要し、当該整列データをマージするためにそれぞれO(N)とO(M)を要するので、計算量はO(NlogN+MlogM+N+M)、すなわち、O(MlogM+NlogN)となります。一方、ハッシュ結合においては、それぞれ1回ずつデータを読み出せばいいので、計算量はO(N+M)です。計算量上においては、ハッシュ結合がソートマージ結合よりも高速（少ない処理量）であることがわかります。
計算量はあくまでも処理の複雑性をざっくり表したものです。しかし、実際には、データ処理は二次記憶からデータを読み出して、当該データに対してCPUで演算などをするため、正確にデータ処理の性能（およびそれを完了するのにかかる処理時間）を見積もるには、二次記憶へのI/O量やCPUの処理量（クロック数）を考慮し、特に並列データ処理においてはネットワークI/O量も考慮に入れる必要があります。
たとえば、二次記憶へのI/Oが支配的である状況を想定し、二次記憶へのI/O量により結合処理の実行時間を見積もってみましょう。ソートマージ結合においては、通常は、RとSのそれぞれにおいて、ある適当なサイズの塊（チャンク）を二次記憶からメモリ上に読み込み、当該データをクイックソートなどにより整列し、当該整列データを二次記憶に書き出し、整列済みのそれぞれチャンクをマルチウェイでマージしながら結合を行うため、それぞれ 3N*RecordSizeと3M*RecordSize のI/O量が必要であり、すなわち総計のI/O量は (3N+3M)*RecordSize です。たとえば、秒間D（Bytes）をデータを読み出せる場合は、I/Oにかかる実行時間は (3N+3M)*RecordSize/D となります。
一方、ハッシュ結合においては、通常は、Rを読み出してハッシュ表をメモリ上に構築し、Sを読み出してハッシュ表を参照する場合は、それぞれN*RecordSizeとM*RecordSizeのI/O量が必要であり、すなわち総計のI/O量は (N+M)*RecordSize と考えられ、同様にI/O量にかかる実行時間は (N+M)*RecordSize/D と見積ることができます。ソートマージ結合と比較して、ハッシュ結合は二次記憶のI/O量においても少ないことがわかります。
ただし、ハッシュ表のすべてをメモリ上に格納できずに、たとえばノード内においてGrace Hash Joinを行う必要がある場合は、Rにおいては、Nに加えて、ハッシュ表の書き出しと読み出しが余計にかかる場合があるでしょう。ハッシュ表と読み出しと書き出しにおけるI/O量は、N*RecordSizeより小さいことが想定されるので、R側のI/O量はたかだか3N*RecordSize程度となると想定できるため、そのような場合であっても、ソートマージ結合よりは少ないI/O量で処理できる可能性が高いと考えられます。
データ処理性能の見積りにおける注意点
これまでは、理想的な環境を想定してデータ処理性能の見積りを行ってきましたが、実際には、計算機（ハードウェア）やデータの特性に合わせて行うことが重要です。
たとえば、二次記憶が非常に遅い計算機においては、実際に処理にかかる時間は二次記憶装置へのI/O時間が支配的となるため、二次記憶へのI/O量（またはI/O回数）により性能を見積もりさえすればそれで十分である可能性がありますが、そうでない場合は、CPUにおける処理量も合わせて考慮する必要があるでしょう。
また、先ほどの選択処理における計算量やI/O量による性能見積りでは、ハードウェアの特性をまったく考慮しておらず、スキャンにおいても索引スキャンにおいてもレコードのアクセスコストは同一であると想定していました。しかし実際には、二次記憶装置であるハードディスクドライブにおいては、同じレコード数をアクセスする場合、シーケンシャルに読むほうがランダムに読むよりも圧倒的に速いため、索引スキャンがスキャンと比較して有効である問い合わせの領域は、計算量のみで導出したものと比べて小さくなる可能性があります。
加えて、特に並列データ処理においては、実際には、各計算機に均等にデータを分割することは困難です。すなわち、各計算機における処理量には少なからず偏りが生じえます。また、一般的に、結合を行う場合においては、結合キーには偏りがあり、本連載の第7回、第8回において紹介した動的負荷分散方式を用いたとしても、各計算機における処理量を均等にすることは難しいと考えられます。たとえば、事前に、データにおける各属性ごとの値とその値の出現頻度からなるヒストグラムなどが得られる場合は、このようなデータの偏りをある程度考慮し、事前の性能見積りに活用できる可能性があります。
おわりに
今回は、これまで説明してきたアルゴリズムの性能を定量的に見積り、比較しました。次回は、これらの性能見積りを用いて行うクエリ最適化について説明する予定です。
