(57)【特許請求の範囲】
【請求項１】
コンピュータソフトウェアによる情報を処理する方法であって、
１対１合致属性に関して２つのテーブルを結合するために、
データ記憶のための階層構造を提供することと、
２つの結合されるテーブルに対して、２つのハッシュテーブル及び２つの１エントリテーブルを割り当てることと、
ディスクからメモリにそれぞれ２つのテーブルのブロックを読み出すことと、
メモリブロックにおける前記２つのテーブルからのタプルを、それぞれ１エントリテーブルに読み出すことと、
結合キーにおいて双方の１エントリテーブル内のタプルを対称プロービングにより比較することと、
合致したタプルを出力するとともに、該合致したタプルを双方の１エントリテーブルから除去することと、
前記タプルの比較の結果、合致していないタプルを独自のハッシュテーブルに追加することと、
を含む、方法。
【請求項２】
単一のテーブルのための階層的なデータ記憶が、
前記構造の最下部に、タプルを有するブロックとしてテーブルをディスクに記憶するとともに、一度に１つのブロックをメモリに読み出すことと、
第２のレベルにおいて、ブロックをメモリに記憶するとともに、最上位レベルにおける前記比較の結果、合致しない全てのタプルをハッシュテーブルに追加することと、
最上位レベルにおいて、一度に単一のタプルを記憶し、結合キーを表すキー及び対応するタプルである値を含む１エントリテーブル内にタプルを記憶することと、
を含む、請求項１に記載の方法。
【請求項３】
ブロックが前記メモリ内に読み出され、且つ、前記２つのテーブルのタプルのデータ分布パターンにしたがって前記タプルが前記１エントリテーブルに読み出されると共に、前記データ分布パターンは、結合キーに基づいて前記２つのテーブルの前記タプルの順序を示す一方、各独立したテーブルの分布とは異なる前記２つのテーブルの分布間の関係を示している、請求項１に記載の方法。
【請求項４】
前記データ分布パターンは、３つのカテゴリー、すなわち、一貫した順序付け（ソートを用いる／用いない）、逆順序付け（ソートを用いる／用いない）及びランダム順序付けに分類される、請求項３に記載の方法。
【請求項５】
データ分布パターンは、データベース統計と、タプルの総数に対する合致したタプルの数の比である合致率のランタイム情報の双方に基づいて予測される、請求項３に記載の方法。
【請求項６】
データ分布パターン予測は、
前記２つのテーブルの統計について、データベースメタデータストアにクエリすることと、
前記２つのテーブルが、結合キーに関して同じ方法で又は逆に記憶されるか否かを判断することと、
データベース統計によってソート情報を提供することができない場合に、既に処理されたブロックの合致率に基づいてデータ分布パターンを決定することと、
を含む、請求項５に記載の方法。
【請求項７】
合致率のランタイム情報に基づくデータ分布パターン予測は、
別のテーブルからの別のブロックよりも小さな数のタプルを有するテーブルからメモリ内に読み出されるブロックとしてベースブロックを定義することと、
前記ベースブロックが処理された後に、該ベースブロックの現在の合致率を得ることと、
現在のブロック及び以前に処理されたブロックについての前記合致率に基づいて、後続のブロックのための予測合致率を計算することと、
予測合致率に基づいてデータ分布パターンを決定することと、
を含む、請求項５に記載の方法。
【請求項８】
対称プロービング及びハッシングを用いてタプルをハッシュテーブルに追加することは、
前記タプルを別の結合された関係の前記ハッシュテーブルに対しプローブすることと、
前記タプルについて、別のハッシュテーブル内に合致したタプルが存在するか否かをチェックすることと、
合致したタプルを出力するとともに、前記ハッシュテーブルから該合致したタプルを削除することと、
別のハッシュテーブル内に合致したタプルがない場合に、結合キーをハッシングすることによって、前記タプルを前記ハッシュテーブルに挿入することと、
を含む、請求項１に記載の方法。
【請求項９】
テーブルのブロック総数に対する、メモリ内に同時に保持することができるブロック数の比であるパラメーターαを用いてユーザーによってメモリ使用を調整するためのアルゴリズムを更に含む、請求項１に記載の方法。
【請求項１０】
１対１結合のために、前記アルゴリズムを元のアルゴリズムとして最初に実行することと、
前記メモリ使用がαの制限に達した後に、
対応するテーブルの前記ハッシュテーブルに対しタプルをプローブし、合致したタプルが存在するか否かを判断することと、
合致したタプルが見つかった場合に、メモリから合致したタプルを出力及び除去することと、
そうでない場合、
結合キーに基づいて、タプルを幾つかのバケットにパーティション化することと、
各バケット内のタプルを、該バケットがフルであるときにディスクに書き込むことと、
各バケットをメモリに読み出し、２つのテーブルの全てのタプルがバケットにパーティション化された後、前記元のアルゴリズムを１つずつ実行することと、
を更に含む、請求項９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース工学の分野に関し、より詳細には、結合技法(join technique)に関する。
【背景技術】
【０００２】
結合(join)は、リレーショナルデータベースシステムにおいて最も頻繁に用いられる動作である。結合は、各テーブルに共通の値を用いることによって２つ以上のテーブル（関係テーブル）からのレコード（タプル、行）を組み合わせる。テーブルＡにおけるレコードに対してテーブルＢにおける合致したレコード数に基づいて、結合動作は通例、１対１(one-to-one join)、１対多及び多対多等の異なる濃度(基数:cardinality)を有する。１対１結合は、各テーブル内の各タプルが、別のテーブルにおける最大で１つの合致したタプルを有することを示す。ハッシュ結合は、結合動作のための最も一般的なアルゴリズムのうちの１つである。ハッシュ結合は、２つのフェーズ、すなわちビルドフェーズ及びプローブフェーズを伴う。ビルドフェーズでは、ハッシュ結合はより小さな全体関係をディスクからメモリに読み出し、エントリが結合属性及びそのタプルからなるテーブルのためのハッシュテーブルをビルドする。ハッシュテーブルがビルドされると、ハッシュ結合はプローブフェーズを実行する。プローブフェーズでは、より大きな関係をスキャンし、ハッシュテーブル内を調べることによって、より小さな関係から関連する行を見つける。
【０００３】
結合動作は頻繁に用いられるが、主にファイルＩ／Ｏアクセスコストに起因して、最もコストが高いか又は時間がかかる動作でもある。特に、大きなテーブルが関与し、利用可能なメモリが制限されているとき、メモリ使用量を低減するために、更なる大きなＩ／Ｏアクセスが必要である。例えば、十分なメモリがある場合、２つのテーブル上のハッシュ結合アルゴリズムは、まず、より小さなテーブルをメモリ内に読み出し、そのレコードについてハッシュテーブルをビルドし、次に、より大きなテーブルを読み出し、ハッシュテーブル内を調べることによって、より小さなテーブルからの関連レコードを見つける。このため、このハッシュ結合アルゴリズムは、ディスクから２つのテーブルを一度読み出すことのみを含む。他方で、メモリが限られている場合、アルゴリズムはテーブル全体をメモリ内に読み出すことを回避しなくてはならず、このため、ブロックごとにテーブルを読み出し、これらのテーブルを、結合キーにおける同じハッシュ関数によりパーティション化し、これらのパーティションをディスクに書き込む。アルゴリズムは次に、パーティションの対をメモリ内にロードし、より小さなパーティション化されたテーブルのためのハッシュテーブルをビルドし、現在のハッシュテーブルとの合致を求め別のテーブルをプローブする。このため、このアルゴリズムは、２つのテーブルを二度読み出し、これらをディスクに一度書き込む必要がある。メモリが限られている場合、Ｉ／Ｏアクセスは、無限メモリの場合の３倍である。したがって、メモリ使用を低減することによって、Ｉ／Ｏコストを効果的に低減することができ、このため、計算時間を低減することができる。
【０００４】
近年、結合動作は、機械学習、ビジネスインテリジェント（business intelligent）及び自然言語処理等の多くの用途において広く用いられている。なぜなら、強力なＳＱＬ（構造化クエリ言語）及びそれらの高い性能に起因して、これらの分野においてデータベースシステムがますます用いられるようになっているためである。ビッグデータ解析のための重要なツールとしての機械学習は、ますます多くの注目を得ている。機械学習のためのプロセスは、主に、データ前処理、データ学習及び予測から構成される。多くのデータアナリストは、データベースシステムに頼ってデータ前処理を行い、人的干渉を低減し、より良好な性能を得る傾向にある。特徴量設計（feature engineering）は、前処理における最も重要なステップのうちの１つである。特徴量設計は特徴生成及び特徴組み合わせを含む。特徴生成は、ドメイン固有の動作を用いて未加工データから新たな特徴を生成するためのものであり、特徴組み合わせは、全ての新たに生成された特徴を組み合わせて学習フェーズの入力にするためのものである。リレーショナルデータベースにおいて、未加工データは、プライマリキー及び他の属性からなるテーブルとして記憶され、特徴は、同じプライマリキー及び対応する特徴からなる１つ又は複数のテーブルに記憶される。このため、特徴組み合わせは、実際、プライマリキーを用いた特徴テーブル及び元のテーブルに対する結合動作である。
【０００５】
特徴組み合わせにおける結合の特性は、結合キーが一意の値を有するプライマリキーであるため、１対１の合致である。そのような１対１の結合は、２つのテーブルが一意のキーにおいて結合されるときに一般的に生じる。別の例は、ビジネスインテリジェント用途において存在する。事前にビルドされたルーチンによってカバーされていないデータを新たなデータソースから取得することは、新たな列、行及びテーブルの追加等の、ＢＩ用途における一般的なタスクである。更なる列を追加するために、システムは通例、まず追加の列のための新たなテーブルを作成し、次に、一意の属性値に対し新たなテーブル及び古いテーブルの結合を実行して、データ粒度(granularity)を保持し、重複エラーを回避する。
【０００６】
このため、本発明は、そのような用途において効率的に用いることができる１対１結合を提供することを目標とする。本発明者らの知る限り、１対１結合に特化した良好な研究が存在しない。対称ハッシュ結合（ＳＨＪ：symmetric hash join）は、２つのテーブルのためにそれぞれ２つのハッシュテーブルを保持し、合致したレコードを可能な限り迅速に出力するという、本発明と同じ着想を共有する。一方、ＳＨＪでは、テーブル全体をメモリ内に保持することが依然として必要とされており、このため、大きなメモリが必要とされる。ＳＨＪの１つの最適化は、早期ハッシュ結合（ＥＨＪ：early hash join）であり、ＥＨＪは、ディスク内に書き込まれる幾つかのパーティションを選択するための方法、及び合致した結果の重複を回避するための方法を検討した。ＥＨＪは、主に、１対多及び多対多の結合を検討した。次に、ＥＨＪの改善である別の研究が、結合濃度（１対１、１対Ｎ、Ｎ対１、Ｎ対Ｎ）を自動的に検出するためのアルゴリズムを提案した。異なる結合濃度に基づいて、異なる重複検出方法が存在する。例えば、１対１の結合の場合、双方のテーブルのための合致したタプルは迅速に排除することができる。この着想は本発明に非常に類似しているが、依然として多くの差異がある。例えば、これらの研究は、データ分布を検討しておらず、このため、現在読み出されているレコードのための合致率を改善することができず、２つのテーブルが結合キーに対して一貫してデータベース内に記憶されているときにハッシュテーブルを作成することを回避することができない。加えて、これらの研究は、ユーザーが定義したパラメーターを用いてメモリの使用を制御することができない。
【０００７】
したがって、データ分布を検討して階層的な対称ハッシュ結合を用い、メモリ使用を低減し、このためプロセッサ及びＩ／Ｏのコストを最小にする効率的な１対１の結合アルゴリズムを提案する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、１対１の結合を実行し、限られたメモリを用いてより多くの計算が行われることを可能にするためにメモリ使用を低減することである。
【０００９】
本発明の別の目的は、メモリ使用を低減することによって、１体１の結合のためのディスクアクセスＩ／Ｏを低減することである。
【００１０】
本発明の更に他の目的及び利点は、部分的に自明であり、明細書及び図面から部分的に明らかとなるであろう。
【課題を解決するための手段】
【００１１】
本明細書において開示される方法は、メモリが限られている場合に、他の結合アルゴリズムよりも少ないメモリを消費し、このためディスクＩ／Ｏアクセスを低減する、１対１の結合のために特に設計された、階層的な対称ハッシュ結合とも呼ばれる改善されたハッシュ結合アルゴリズムである。１対１の結合は、機械学習用途及びビジネスインテリジェント用途におけるデータ解析、特に特徴量設計において広く用いられる。テーブル内のタプルごとに、別のテーブル内に最大で１つの合致するタプルが存在するという、１対１の結合の特性を利用することにより、本明細書に開示される方法は、１対のタプルが互いに合致するときに、この１対のタプルを迅速に出力及び除去する。この方法は、メモリ内に、ハッシュテーブルと、テーブルごとの１エントリテーブル（１−ＥＴ）とを保持する。データブロックがメモリに読み出される度毎に、次に、ブロックからのタプルが１−ＥＴにロードされる。開示される方法は、まず、双方の１−ＥＴ内のタプルを比較する。２つのタプルが合致する場合、これらのタプルは出力され、メモリから除去される。そうでない場合、それらはハッシュテーブルに挿入される。このプロセスは、２つのテーブルが結合キーに基づいてソートされるか又は一貫して記憶されるとき、結合結果がハッシュテーブルを一切構築することなく生成されることを可能にする。
【００１２】
開示される方法では、２つの１−ＥＴにおけるタプルが合致しないとき、これらのタプルは独自のハッシュテーブルにそれぞれ挿入される。その前に、各タプルが対応するテーブルのハッシュテーブルに対しプローブされ、これによって結合結果を生成し、次にこの結合結果を除去することができる。このため、ハッシュテーブルへのタプルの挿入が回避され、ハッシュテーブルのサイズが低減される。このプロセスによって、結合結果が、いずれかのテーブル全体を読み出す前に生成されることが可能になる。
【００１３】
開示される方法は、ユーザーがメモリ使用を調整することを可能にするためのαアルゴリズムを提供する。ユーザーが、パラメーターαをシステムに登録し、テーブルごとに最大でα個のブロックが同時にメモリ内に保持され得ることを示す。元のアルゴリズムを実行するときにそのような制限に達する場合、全てのタプルがバケットにパーティション化され、バケットがフルのときにディスクに書き込まれる。タプルがバケットにパーティション化される前に、タプルはまず別のテーブルのハッシュテーブルにプローブされ、合致するタプルが存在するか否かがチェックされる。存在する場合、合致するタプルが出力され、メモリから除去され、タプルをバケットにパーティション化する必要がない。２つのテーブルの全てのタプルがバケットにパーティション化された後、各バケットがメモリにロードされ、元のアルゴリズムを用いて１つずつ処理される。
【００１４】
開示される発明は、履歴ブロック合致情報に基づいてデータ分布の予測を通じてメモリ内のブロックのための合致率(matching rate)を増大させる。結合されるキーの順序に従って、開示される方法は、一貫した順序付け（consistent ordering）、ランダム順序付け（random ordering）及び逆順序付け（reverse ordering）を含む３種類のデータ分布を検討する。一貫した順序付けは、２つのテーブル内の結合キーの順序が同じであること、例えば、結合キーが同じ方法でソートされることを示す。特徴量設計では、２つのテーブルの結合キーが一貫した順序にあるがソートされていないことが一般的である。なぜなら１つのテーブルが通例、別のテーブルを取り出し、その属性のうちの幾つかに対し何らかの特徴生成関数を適用することによって生成されるためである。ランダム順序付けは、２つのテーブル内の結合キーの順序がランダムであることを示す一方、逆順序付けは、２つのテーブル内で順序が逆であることを示す。開示される方法は、全ての前の処理済みブロックの合致率を記録し、そのような情報を用いてデータ分布を予測する。データ分布のタイプが固定された後、ディスクからの２つのテーブルのためのブロックの読み出し及び現在のブロックから１−ＥＴへのタプルの読み出しの方法を調整することができる。この場合、開示される方法は、ブロックのための合致率を増大させ、このため、メモリ使用を更に低減させる。
【００１５】
本発明のより完全な理解のために、以下の説明及び添付の図面に対し参照が行われる。
【図面の簡単な説明】
【００１６】
【図１】開示される方法におけるデータの階層ストレージを示すブロック図である。
【図２】開示される方法の概観を示すブロック図である。
【図３】開示される階層的な対称ハッシュ結合アルゴリズムの全体を示す論理フロー図である。
【図４】開示される方法の動作における、ハッシュテーブルへのタプル挿入のプロセスを示す論理フロー図である。
【図５】メモリの制限がある場合の、αアルゴリズムを用いた、１対１の結合を実行するプロセスを示す図である。
【図６】異なるデータ分布パターンの例を示す図である。
【図７】開示される方法の動作におけるディスクからのテーブルのブロックにアクセスするプロセスを示すブロック図である。
【図８】開示される方法の動作における、２つのテーブルのためのデータ分布の予測プロセスを示す論理フロー図である。
【図９】異なるタイプのデータ分布の変形を示す図である。
【発明を実施するための形態】
【００１７】
本発明は、本発明及び図面の好ましい実施形態に係る以下の詳細な説明により、容易に理解することができる。
【００１８】
開示される方法は、リレーショナルデータベースに関する知見の下で説明される。例えば、データベース内のテーブル又は関係は、複数の列及び行を有する。行(row)は、レコード又はタプルと呼ぶこともできるのに対し、列(column)は属性と呼ぶことができる。タプルは、関係を形成するように共にグループ化することができる。開示される方法は、その値が幾つかの特定の用件を満たした共通の属性を有する様々なテーブルからのタプルを出力することを含む、データベース内の結合動作を説明する。
【００１９】
開示される方法は、関係Ｒが、そのタプルを複数のブロックに配置された状態で、ディスクのエリア内に記憶されると仮定する。Ｒのタプルを含むブロックは、システムに既知であり、ブロックを１つずつ得ることが可能である。各ブロックは互いに同じサイズを有するので、これらは、各タプルの大きさに従って、異なるテーブルについて異なる数のタプルを含むことができる。
【００２０】
階層的な対称ハッシュ結合アルゴリズム
Ａ．階層データストア
開示される方法において、データは、図１が示すような３レベル構造に記憶される。構造の最下部において、関係Ｒは、ディスク内のタプルを有するブロックとして表され、一度に１つのブロックがメモリに読み出される。このため、第２のレベルにおいて、メモリに既に読み出されたテーブルのブロック内のタプルが、ハッシュテーブルに記憶される。ハッシュテーブルは、キー及び値を有する複数のエントリを有する。各キーは、結合される属性（複数の場合もある）の値１０ａであり、各対応する値は、値１０ａを有するタプルである。一方、ブロック内の全てのタプルではなく、最上位レベルストレージの要件を満たさないタプルのみがハッシュテーブルに挿入され、これについては次のセクションにおいて詳細に説明される。最上位レベルストレージは、一度に単一のタプルのみを記憶することができる１エントリテーブル（１−ＥＴ）である。１−ＥＴにおけるエントリは、キー及び値を含む。ハッシュテーブル内のエントリと同様に、キーは、結合属性の値、又は結合される属性の複数の値の組み合わせであり、値は対応するタプルである。
【００２１】
Ｂ．アルゴリズム
開示される方法の基本的な着想が図２に示されている。第１に、各テーブル（Ｂｉ（Ｒ）及びＢｉ（Ｓ））からのブロックがメモリに読み出され、これらの２つのブロック（Ｔｐｉ（Ｒ）及びＴｐｉ（Ｓ））の各々からのタプルがそれぞれ１−ＥＴに読み出される。次に、２つの１−ＥＴ（１−ＥＴ（Ｒ）及び１−ＥＴ（Ｓ））内の２つのタプルが比較される。これらは、結合キーにおいて合致する場合、メモリから除去され、ユーザーに出力される。そうでない場合、２つのタプルがそれらの対応するハッシュテーブル（ＨＴ（Ｒ）及びＨＴ（Ｓ））に加えられる。タプルがハッシュテーブルに挿入される前に、タプルはまず、別のハッシュテーブルにプローブされ、合致したタプルが存在するか否かがチェックされる。このプロセスは、後に詳細に説明される。全てのタプルが処理された後、次のブロックがメモリに読み出され、任意のテーブルの全てのブロックが終了するまで、全プロセスが繰り返される。
【００２２】
アルゴリズムの詳細が論理フローチャート図３に示される。双方のテーブルからの２つのブロックは、常に同時に読み出されるとは限らない。２つのテーブルのブロック内のタプル数が常に同じであるとは限らないので、場合によっては、１つのブロックが終了する一方で、別のブロックからの幾つかのタプルがまだ処理されていないことがある。この場合、前のブロックが終了したテーブルからの次のブロックがメモリに読み出される。メモリに次のブロックを読み出すとともに１−ＥＴに次のタプルを読み出す方法は、次のセクションにおいて説明される。２つのタプルが１−ＥＴに読み出された後、各１−ＥＴのキーにおいて比較が行われる。それらが等しくない場合、タプルが対応するハッシュテーブルに追加される。開示される方法は、テーブルごとにハッシュテーブルを保持し、テーブルＲからのタプルがＲのハッシュテーブルに加えられる。タプルをハッシュテーブルに加えるためのアルゴリズムが図４に説明される。ＨＴ（Ｒ）及びＨＴ（Ｓ）は、それぞれ２つのテーブルＲ及びＳのためのハッシュテーブルである。Ｔｐｉ（Ｒ）として表されるＲからのタプルがＨＴ（Ｒ）に加えられるとき、これはまずＨＴ（Ｓ）に対しプローブされる。Ｔｐｊ（Ｓ）として表されるＨＴ（Ｓ）内の合致するタプルが存在する場合、これはＨＴ（Ｓ）から除去され、合致したタプルがユーザーに出力される。そうでない場合、結合キーのハッシングを行うことによって、Ｔｐｉ（Ｒ）がＨＴ（Ｒ）に挿入される。そのようなプロセスは、テーブル内の全てのタプルが出力されるまで繰り返される。
【００２３】
Ｃ．有限メモリのためのαアルゴリズム
重要なアルゴリズムが上記で説明された。一方、これは、より悪い状況において、テーブル全体をメモリ内に埋めることを必要とする。このため、有限メモリの場合、特に、小さいメモリの場合、上記のアルゴリズムは機能しない場合がある。開示される方法は、制限のあるメモリの問題に対処するためのαアルゴリズムを提供する。
【００２４】
αアルゴリズムの背後にある主要な着想は、メモリ使用を、ユーザーによって提供されるパラメーターαを通じて柔軟に調整することである。ユーザーは、データサイズ、データ分布パターン等のデータプロパティに基づいてシステムにαを登録する。αは、テーブルごとに最大でブロックαを同時にメモリ内に保持することができることを意味する。例えば、テーブルＲが合計１００個のブロックを有し、αが０．２である場合、Ｒの２０個のブロックのみを同時にメモリ内に保持することができる。換言すれば、メモリ内のブロックはハッシュテーブル内に記憶されるので、Ｒのためのハッシュテーブルのサイズは、ブロックサイズの２０倍よりも小さくするべきである。
【００２５】
図５は、αアルゴリズムの詳細を示す。最初に、アルゴリズムは、上記で説明した元のアルゴリズムとして機能する。２つのハッシュテーブル内に過度に多くのタプルが挿入された後、それらのサイズは、αによって定義される制限に達する。この場合、次回は新たなタプルをハッシュテーブル内にこれ以上加えない。ハッシュテーブルに加えられる傾向にある全ての後続のタプルは、結合キーに基づいて幾つかのバケットにパーティション化される。同じ結合キーを有する全てのタプルが同じバケット内にあることを確実にするために、２つのテーブルからのタプルは、同じ方法を用いてパーティション化されなくてはならない。テーブルＲからのタプルがバケットにパーティション化される前に、ハッシュテーブルＨＴ（Ｓ）に対しプローブされ、既にＨＴ（Ｓ）において合致したタプルを有するか否かをチェックする。有する場合、これ以上バケットにパーティション化される必要はなく、単に出力される。２つのテーブルからの全てのタプルがバケットにパーティション化された後、タプルは単一のバケットに属し、メモリにロードされ、処理される。全てのバケットは１つずつ処理され、各々について、元のアルゴリズムが用いられる。
【００２６】
データ分布に基づく最適化
Ａ．データ分布パターン
開示される方法におけるデータ分布は、結合キーに基づいて、２つのテーブルのタプルがどのように分布しているか、換言すれば、結合キーに基づくタプルの順序を意味する。これは、各独立したテーブルの分布ではなく、２つのテーブルの分布間の関係を示す。３種類のデータ分布、すなわち、一貫した順序付け（ＣＯ）、ランダム順序付け（ＲＯ）及び逆順序付け（ＥＯ）が考慮に入れられる。一貫した順序付けは、結合キーが、２つのテーブルについて同じ方法で順序付けされることを意味する。これは２つの事例、すなわち、２つのテーブルの結合キーを、昇順及び降順等の同じ順序でソートする、ソートを用いた一貫した順序付け（ＣＯｗＳ：consistent ordering with sort）と、結合キーがソートされていないが一貫した順序付けにある、ソートを用いない一貫した順序付け（ＣＯｗ／ｏＳ：consistent ordering without sort）を含む。後者は、２つのテーブルが同じ数のタプルを有することを必要とし、これは、特徴量設計の文脈では非常に一般的である。元のテーブルは通例、プライマリキーにおいてソートされないが、全ての生成されたテーブルは、プライマリキーにおいて元のテーブルと同じ順序を有する。ランダム順序付けは、２つのテーブルのタプルが、結合キーに基づいてランダムに分布されることを示す。最後に、逆順序付けは、２つのテーブルのタプルが結合キーに基づいて逆に配置されることを示す。一貫した順序付けにおけるように、結合キーは、逆にソートされているか（ソートを用いた逆順序付け（ＥＯｗＳ：rEverse Ordering with Sort））又は逆の順序でソートされていないか（ソートを用いない逆順序付け（ＥＯｗ／ｏＳ：rEverse Ordering without Sort））のいずれかとすることができる。図６は、データ分布パターンの幾つかの例を示す。
【００２７】
開示される方法におけるメモリ使用を低減するための本質的な着想は、合致したタプルを可能な限り迅速にエビクトする(即ち、退去させる)ことであるため、データ分布パターンは、メモリに既に読み出されたタプルのための合致率に大きく影響を及ぼし、このため、全体効率に影響を及ぼし得る。例えば、２つのテーブルが一貫した順序付けにあり、２つのテーブルからのブロックがメモリに同じように読み出される場合、テーブルのブロックＢｉ（Ｒ）からの各タプルが、別のテーブルの対応するブロックＢｉ（Ｓ）からの合致したタプルを見つけることができる。この場合、ブロックの全ての対について、全てのタプルが合致し、メモリから除去される。結果として、メモリの２つのブロックしか必要とされない。２つのテーブルが逆順序付けで分布し、それらからのブロックが依然として同じように読み出される場合、各テーブルの半分について、合致したタプルが見つからない。このとき、システムは、各テーブルの半分をメモリに保持する必要がある。したがって、データ分布パターンを認識することは非常に重要であり、ブロックを読み出す方法は、そのようなパターンを検討に入れるべきである。
【００２８】
データ分布パターンを考慮した開示方法のアーキテクチャが図７に示される。２つのコンポーネントが追加される。１つは、データベースメタデータストア及びランタイムアルゴリズムエグゼキューター（runtime Algorithm Executor）の双方から情報を得るデータ分布予測器である。別の追加コンポーネントは、データ分布予測器によって提供されるデータ分布パターンに基づいてディスクからのブロックにアクセスするブロック予測器である。これらの２つの予測器の詳細が次の２つのセクションにおいて記載される。
【００２９】
Ｂ．データ分布パターンの予測
開示される方法は、合致率のデータベース統計及びランタイム情報の双方に基づいてデータ分布パターンを予測する。図８に示すように、データ分布予測器はまず、２つのテーブルの統計(データ)について、データベースメタデータストアにクエリを行う。メタデータストアが、２つのテーブルが結合キーにおいて同じようにソートされていることを示す場合、データ分布パターンはソートを用いた一貫した順序付けに設定される。２つのテーブルが結合キーにおいて逆にソートされる場合、データ分布パターンは、ソートを用いた逆順序付けに設定される。そうではなく、メタデータストアからのそのような情報がない場合、開示されるアルゴリズムは、既に処理されたブロックの合致率に基づいてデータ分布パターンを予測する。
【００３０】
第１に、アルゴリズムは、このブロックが処理された後に、現在のブロックＢの合致率を得る。開示された方法において、Ｂは、より小さなタプルを有するテーブルからメモリ内に読み出されたブロックである。各テーブルのブロックサイズは固定であるため、各ブロックにおけるタプルの数は、２つのテーブルについて異なる。例えば、テーブルＲのブロック内に１０００個のタプルが存在する一方、テーブルＳのブロックにおいて１２００個のタプルが存在する場合、ブロックＢは、現在メモリ内に読み出されているテーブルＲの１つのブロックとして定義される。
【００３１】
現在のブロックＢのための合致率ＭＲｃｕｒは、以下の式によって計算される。
【数１】
0006418431.tif 000002
【００３２】
次に、後続のブロックＰＭＲのための予測合致率が、ＭＲｃｕｒと、前の処理されたブロックのための合致率ＭＲｐｒｅとに基づいて計算される。
【数２】
0006418431.tif 000003
【００３３】
予測される合致率が９０％よりも大きい場合、データ分布パターンはＣＯｗ／ｏＳであるとみなされる。アルゴリズムは、予測される合致率のみでなく、現在の予測データ分布パターンにも基づいて、これが逆順序付けであるか否かをチェックする。関数がＲｅｖｅｒｓｅＯｒｄｅｒｉｎｇ（ＰＭＲ）である場合、以下のように機能する。パターンがまだ決まっていない場合、換言すれば第１のブロックが処理されたばかりの場合、予測される合致率は１０％よりも小さく、アルゴリズムは、パターンを逆順序付けとして予測する。現在のパターンが逆順序付けであり、予測される合致率が９０％よりも大きい場合、パターンは依然として逆順序付けであるとみなされる。なぜなら、パターンが逆順序付けであると初めて予測された後に、開示される方法は、次のブロックを読み出す方法を変更し（これについては次のセクションで紹介する）、次のブロックの合致率が可能な限り大きくなるようにするためである。これは、次の段落において説明されるパターン変換規則と一貫している。最後に、データ分布パターンは、一貫した順序付けでも逆順序付けでもない場合、ランダム順序付けに設定される。その後、アルゴリズムは、前のブロックのための新たな合致率値を予測合致率に設定する。
【００３４】
図９に示すように、アルゴリズムは、異なるデータ分布パターン間の妥当な変換を生成する。予測は、より小さなブロックが処理された後に毎回行われるため、各予測の結果は変更される場合があり、これはパターン変換と呼ばれる。第１に、最初のステータス、換言すれば、初回のパターン予測から開始する変換１、２及び３について、上記で説明したように、予測合致率に基づいて目的パターン（destination pattern）が決まる。率が９０％よりも高いとき、これは一貫した順序付けに変換される。率が１０％未満のとき、これは逆順序付けに変換される。そうでない場合、パターンはランダム順序付けになる。次に、３つのパターンの各々が、それらのパターンの条件を満たした場合に、それ自体に変換することができる（４、５、６）。一貫した順序付け及びランダム順序付けの場合、それ自体への変換のための条件は変更されない。一方、逆順序付けの場合、それ自体への変換の条件は、１０未満の予測合致率ではなく、次のブロックの読み出しが逆順序付けの場合に変更される。最後に、一貫した順序付け及び逆順序付けがランダム順序付けに変換され得るが、逆の変換を行うことはできない。これは、ランダム分布データの場合、２つのテーブルのデータの小さな部分が一貫しているか又は逆の順序にあることが可能であるため、妥当である。
【００３５】
Ｃ．ブロック及びタプルアクセス戦略
データ分布のためのパターンが固定された後、開示されている方法は、ブロックにアクセスする方法を決定する。ブロックアクセスは、ディスクからメモリにブロックを読み出すことを意味する。このため、図７におけるブロック予測器は、データ分布パターンに基づいて、いずれのブロックが読み出されるべきかを決定する。
【００３６】
データ分布パターンが一貫した順序付けである場合（ソートを用いるか又は用いない）、予測器は、双方のテーブルの次の複数のブロックを連続して読み出す。２つのテーブルが逆順序付けにある場合、予測器は、２つのテーブルの次の複数のブロックを逆に読み出す。例えば、テーブルＲからの第１のブロックが読み出される一方、別のテーブルＳからの最後のブロックが読み出される。最終的に、２つのテーブルがランダムに分布している場合、双方のテーブルのためのブロックが連続して読み出される。通例、パターンが固定される前に、換言すれば、第１のブロックが処理される前に、予測器は、各テーブルのブロック１をメモリ内に読み出すことを決定し、次回からブロックアクセス方法を調整する。ソートを用いた一貫した順序付け及びソートを用いた逆順序付けを事前に（第１のブロックが処理される前に）知ることができるので、第１のブロックに正しい方法でアクセスすることができる。例えば、ソートを用いる逆順序付けのパターンの場合、予測器は、テーブルＲのブロック１及びテーブルＳからのブロックｎを読み出すことを決定する（テーブルＳについて合計ｎ個のブロックが存在すると仮定する）。ブロック番号、既に読み出されたブロック、現在の処理ブロック等を含むブロックの情報がメタデータストア内に保持される。予測器は、そのような情報に容易にアクセスし、決定を行うことができる。
【００３７】
各テーブルのブロックをメモリ内に読み出した後に、開示される方法は、各テーブルの１エントリテーブルにそれぞれ１つのタプルをロードする必要がある。そのようなプロセスは、いずれのタプルがいつ読み出されるべきかを決定するタプルアクセスと呼ばれる。
【００３８】
説明をより容易にするために、各々がｍ個のタプルを有するＢｉ（Ｒ）及びＢｉ（Ｓ）がメモリ内に読み出されたばかりであると仮定する。２つのテーブルが一貫した順序付けにある場合、タプルはＢｉ（Ｒ）及びＢｉ（Ｓ）からそれらの独自の１−ＥＴに順次読み出される。一方、２つのテーブルがソートされる場合、新たなタプルが毎回同時に１−ＥＴに読み出されるわけではない。例えば、Ｔｐｉ（Ｒ）及びＴｐｉ（Ｓ）は、この時点においてそれぞれ独自の１−ＥＴ内にある。それらは、合致する場合、出力され、Ｔｐｉ＋１（Ｒ）及びＴｐｉ＋１（Ｓ）が１−ＥＴに読み出される。昇順に関して、Ｔｐｉ（Ｒ）がＴｐｉ（Ｓ）よりも小さい場合、Ｔｐｉ（Ｓ）よりも小さくなくなるまで、Ｒからの次のタプルのみが連続して１−ＥＴに読み出される。降順の場合、これは反対の状況にあり、Ｔｐｉ（Ｒ）がＴｐｉ（Ｓ）よりも大きい場合、Ｔｐｉ（Ｓ）よりも大きくなくなるまで、Ｒからの次のタプルのみが連続して１−ＥＴに読み出される。２つのテーブルが逆順序付けにある場合、タプルはＢｉ（Ｒ）及びＢｉ（Ｓ）からそれらの独自の１−ＥＴに逆に読み出される。それらが逆の順序でソートされるとき、タプルを読み出す方法は、２つのテーブルを同じ順序でソートする状況に類似している。２つのテーブルがランダムな順序にある場合、開示される方法はこのステップをスキップする。なぜなら、２つのタプルが互いに合致する可能性が小さく、それによって比較が無意味で時間の無駄となるためである。
【図１】
0006418431.tif 000004
【図２】
0006418431.tif 000005
【図３】
0006418431.tif 000006
【図４】
0006418431.tif 000007
【図５】
0006418431.tif 000008
【図６】
0006418431.tif 000009
【図７】
0006418431.tif 000010
【図８】
0006418431.tif 000011
【図９】
0006418431.tif 000012