目次


複雑なクエリーに対応したスター・スキーマ処理

Comments

はじめに

データ・ウェアハウジングがこれほど目ざましく成長しているのは、 けしてベンダが宣伝をしたからではなく、データ・ウェアハウスを使うことで、様々な企業が今まで手つかずの まま積み上げられていたデータの山から、いかに重要な情報を入手できるかを知ったためです。

データ・ウェアハウスを導入した企業の例が示すとうり、基幹システムで 企業に大きくプラスになった手法やツールは、多くの場合にデータ・ウェアハウスは役立ちません。 これは特に従来型のリレーショナル・データベース管理システム(RDBMS)に当てはまります。オンライン・ トランザクション処理(OLTP)向けシステムは、データ・ウェアハウジングが必要とする条件には容易に 対応できないからです。
特に、OLTPシステムではとてもうまく機能したデータ・モデルやスキーマも、 複雑なデータのアドホックな分析には適しているとはいえません。

データ・ウェアハウジングの経験を積んでいくことで、 複雑なクエリーに対応したもっと良いスキーマを見極めることができます。特に、スター・スキーマは、 直感的な設計が施されていることから、幅広く受け入れられてきました。
ところが、 従来のOLTPシステムはスター・スキーマの多次元性という特質に対応した設計がなされておらず、 残念ながらこのスキーマへ複雑なクエリーを投入した場合には大きく性能が落ちてしまいます。本資料では、 このような性能上の問題の原因および特質を指摘し、データ・ウェアハウス環境においてこれらの 問題点に対応すべく、レッドブリックが実現してきたテクノロジ・ファミリを紹介します。

スター・スキーマ
これまで永い年月をかけて、あらゆる企業において、給与支払名簿、 在庫管理や調達などで効率の高い業務系システムを実現してきました。業務系システムに最大限の効率を発揮させ、 多数の小型ながら同時に発生するリード/ライト要求を迅速処理可能なRDBMSスキーマを定義する方法が古くから知られています。
多くの場合、スキーマ定義は個々のレコードへのアクセス争奪を最小限に抑えつつ、その一方で業務上の要求に 効率よくマッピング可能なテーブルの定義に重点が置かれます。言い換えれば、業務系システムでは同時実行を 最小限にとどめ、インサート、更新、削除といった性能を最適化します。

これに対し、データ・ウェアハウスはデータベースにまったく別の働きを求めます。 一般に、データ・ウェアハウスは大型かつ複雑でアドホックな、しかもデータ集約型のクエリーを処理し なければなりません。これらシステムでは計算資源を消費する形態に大きな違いがあるばかりでなく、 システム上で実行される機能の特質上、データベース・スキーマの定義に基本的に異なるアプローチが必要です。

これらの相違点を明確にするため、簡単な例を挙げます。図1は、発注システム用の ごく普通のOLTPスキーマです。このスキーマは、個々の発注書(PO)を効率よく生成、更新、処理可能な業務系 システムの場合は極めて都合よく機能しますが、購買パターンの分析には適していると言えません。 たとえば、アナリストが、社名、商品コスト、購入元、仕向先をリストアップするクエリーを構造化しようとすると、 各種テーブルをナビゲートする方法を算出するまでにかなりの時間を費やさなければなりません。 つまりこのプロセスは直感的な処理が可能なものとは言えません。

図1. Typical OLTP Schema
図1. Typical OLTP Schemacture
図1. Typical OLTP Schemacture

データ・ウェアハウスでは、検索を中心としたデータの見方が新たに必要になり、 それを提供するのがスター・スキーマです。情報はファクト(fact)とディメンションすなわち次元(dimension) という2つのグループに分類できるというのがスター・スキーマの基本的な前提条件です。ファクトは分析される コア・データ要素を指します。
この例では、商品1つ1つの購入がファクトで、一方POSデータベースでは販売が ファクトです。また、ディメンション(次元)とは、そのファクトにまつわる属性を言います。 データ・ウェアハウスの例では、ディメンションは購入される商品項目および購入日であり、 一方POSデータベースでは、販売日および販売された商品項目です。
すべてではないまでも、 大部分の分析がこれらのディメンションに基づいて行われ、それ故に次元分析という用語が用いられています。

この2通りの情報分類に基づいて、図2に、発注書データベースの別のスキーマを示します。 1組のディメンション(SHIP_FROM、SHIP_TO、ITEM)を通じて特定のファクト(PURCHASES)を探すわけですから、 このスキーマに同じビジネス上の質問を投入するする方がずっと単純です。
また、重要なことですが、 標準的なスター・スキーマでは、ファクト・テーブルの方がそのファクトのどのディメンション・テーブルよりも ずっとサイズ的には大型です。このポイントは、本資料の中で後ほどスター・スキーマに関連する性能上の 問題を検討するうえで重要になります。

図2. Star Schema
図2. Star Schema

スター・スキーマは直感的な構造をもっているため、従来型のOLTPスキーマよりも データ・ウェアハウス環境への適性が高くなっています。データ・ウェアハウスは多量のアドホック・ クエリーに応答しなければなりません。データ・ウェアハウスの成否は、一部、クエリーの定式化が容易か どうかにかかっています。
アナリストが数時間にもわたり、相互に入り組んだテーブルをナビゲートする ことなど不可能だからです。スター・スキーマがデータ・ウェアハウス・アプリケーションに適したスキーマ として急速に受け入れられているのは、データ提示に直感的なアプローチを使用しているからです。

購買の例は比較的単純であり、他の実務アプリケーションはもっと複雑で、 共通のディメンション・テーブルを共有するリンクされた複数のファクト・テーブルが必要です。 複数のファクト・テーブルで拡張された場合に、スター・スキーマは医療やテレコム分野の最も複雑な 運用環境にも対応可能です。

スター・スキーマで発生し得る性能上の問題点

多くの専門家の間で意見が一致しているように、スター・スキーマは データ・ウェアハウジング用の好ましいモデリング手法であり、スター・スキーマさえあればデータベースの 問題はほとんど解決されるものとお考えかも知れません。
残念ながら、そうではありません。 データ・ウェアハウスを実現してきた企業は、従来型のOLTPデータベース上に直感的なクエリー中心の スキーマを常駐させようと試みてきたものの、大きな障害に突き当たりました。それは性能の低下という問題です。

ペアワイズジョインの問題
従来型のOLTPデータベース・エンジンは、スター・スキーマに対して発行可能な多数の複雑な クエリーに対応できるように作られていません。特に、単一のクエリーでいくつかのテーブル から関連する情報を検索する必要性、すなわち「ジョイン処理」において大きな制限が課されています。
一般に、従来型のOLTPデータベースは一回の作業でテーブル2つをジョインします。複雑なジョインの場合に テーブル数が3つ以上になる場合、RDBMSでは作意的にクエリーを一連のペア単位のジョインに分ける必要があります。 ペア単位のジョインはOLTPシステムの単純な要求には適していますが、データ・ウェアハウス環境では十分に 機能することができません。

ペアワイズジョインの問題は、実例で示すのが早わかりです。 いま、スター・スキーマの例(図2)で、社名、購入価格、出荷元、仕向先、購入日のリストを 作成したい場合、COMPANY(社名)、PURCHASES(購入価格)、SHIP_FROM(出荷元都市)、 SHIP_TO(仕向先都市)、ITEM(問題の製品)、およびDATA(購入日)という6つのテーブルから データをジョインしなければならないことになります。
従来型のOLTPデータベースでは、 たとえばCOMPANYとPURCHASESという具合に最初にジョインするテーブルを選択しなければなりません。 こうして2つのテーブルがジョインされ、COMPANYにPURCHASESをジョインした中間結果が生成されます。 この中間結果とさらにSHIP_FROMという別のテーブルをジョインして、さらに別の中間ジョイン結果が生成されます。
このプロセスが継続され、4つの中間結果が生成された後に完全な結果が生成されます(図3参照)。 これらの中間結果は大がかりで、これを作成するコストも大きなものになります。

図3. Pair-Wise Joining
図3. Pair-Wise Joining

ジョインの順序の問題
ジョインの順番は、クエリー性能に大きく影響します。極端な例ですが、 ITEMとPURCHASESをジョインした結果がレコード1つだけの選択に終わった場合、その後のジョインでは この1つのレコードだけをジョインすることになります。
しかし、まずCOMPANYにPURCHASESがジョインされた場合、 中間結果はPURCHASEすべてに必ず1行が含まれることになります。ペア単位のジョイン順序の選択が このように性能に大きく影響することから、従来型のOLTPデータベースでは、これらジョインの実行に 最も適した順序を見つけるため莫大な作業量を浪費していることになります。

評価するべき組み合わせの数は、 ジョインされるテーブル数の増加とともに指数的に増えていきますから、ペア単位のジョインの ベストな順序を選択するという問題は、合理的な時間内に解決されるはずがありません。 N個のテーブル集合をペア単位でジョインする方法はN!1通りです。
たとえば、6テーブルのクエリーでは、6!=(6x5x4x3x2x1)=720の組み合わせがあります。 7テーブルのクエリーでは(7x6x5x4x3x2x1)=5,040通りの組み合わせになります。 10テーブルのクエリーではなんと3,628,800通りの組み合わせ、などなどです。

2つのテーブル間のジョインを評価する場合には、これらの数字は誤解を与えやすいものですが、 RDBMSでは、テーブルのジョインに対応した複数のジョイン・アルゴリズムが考えられますから、 あらゆる組み合わせについて、これらのアルゴリズムそれぞれを評価する必要があるかも知れません。
たとえば、可能なアルゴリズムとして5つのジョイン・アルゴリズムがあるとすれば、 10テーブルのクエリーの場合、データベースは10!x5=~18,000,000通りの組み合わせを評価しなければならない場合もあります。 従来型のOLTPデータベースではどれにも当てはまることですが、 重要なポイントとして、クエリーの実行が開始される前にペア単位のジョイン順序を確立しておかなければならない点です。
データベースがペア単位のジョインの組み合わせの評価に費やしている時間は、クエリーを実行するための時間ではなく、 したがってビジネス上の問いに解答を出してくれる時間とは全く無関係の時間です。

スター・スキーマのジョインの問題
こうして、ペア単位のジョインの組み合わせ数が多すぎて完全な評価ができないため、 従来型のOLTPデータベースでは、評価のために「関心のある(interesting)」サブセットをピックアップします。
これらのサブセットの選択方法はデータベースによりまちまちですが、一般に、直接関連をもつテーブルの 組み合わせをピックアップすることになります。スター・スキーマの例でご説明すれば、 ITEMとPURCHASESのジョインはinterestingですが、ITEMとCOMPANYのジョインはinterestingとは言えません。
この戦略は、相関関係をもつ豊富なテーブルのネットワークを収容した、従来型のOLTPスキーマではそれなりに うまく機能しますが、スター・スキーマに適用した場合、結果は悲惨です。

またデータ・ウェアハウスでは、関連するテーブルにだけ注意を向けても意味がありません。 なぜなら、標準的なスター・スキーマでは、他の大部分のテーブルに直接関係するテーブル1つだけがファクト・ テーブルになるからです。
したがって、ファクト・テーブルは当然最初のペア単位のジョインの候補に上がります。 残念ながら、ファクト・テーブルは一般にクエリーの中で最大のテーブルであり、この戦略を使えば、 必然的に極めて大型の中間結果セットを生成するペア単位ジョイン順序を選択することになります。
大型の中間結果セットが生成されれば、クエリー性能は大きな影響を受けます。さらに、 これらの大型中間セットは有効なスペースを占有するため、クエリー実行が継続できなくなってしまいます。

明らかに、これらの問題は複合型のスター・スキーマの場合に限り発生します。 リンクされた複数のファクト・テーブルにクエリーを投入すれば、それよりさらに大型の中間結果が返されてくることになります。

複雑なクエリーの場合の最適化テクノロジの限界
従来型のコスト・ベースのオプティマイザは、複雑なクエリーではうまく機能できません。 これらオプティマイザは、クエリー実行に先だってオペレータがクエリーのコストを予測可能であるという前提に立っています。 残念ながら、データ・ウェアハウス環境の複雑なクエリーでは、いつもこの前提条件が成立するとは限りません。

従来型OLTPデータベースは、データそのものから収集された統計値に基づきコストを予測します。

これら統計値は、データ・ウェアハウス環境ではごく普通に発生する複雑なクエリーに対し、 おおよその予測しか提供できません。
さらに悪いことに、初期のプロセスでまずい予測をしてしまうと、 後になってクエリーが進行するにつれ、それが大きく増幅されて大きな誤差・偏差が生じることになります。

各種ディメンション間で均一に分布していないデータであるデータ・スキューの 問題を例にとってみましょう。一般に、コスト・ベースのオプティマイザは、中間結果の大きさに基づいてコストを積算します。 こうして決定された値は、データ間の依存関係により混乱を発生する可能性があります。
たとえば、 カルフォルニア州に住む顧客のパーセントと全顧客に対するコンバーチブルを購入する顧客のパーセントが既知であるオプティマイザは、実際にはノースダコタ州やワシントン州より カリフォルニア州の売上げに対するコンバーチブルの比率が大きいにもかかわらず、変数が独立しているかのように動作します。

従来型のOLTPデータベースでたまたま最適なストラテジが得られたとしても、 コスト予測段階のミスで、結局その戦略を採用しないこともあるのです。

性能上の問題に対する見かけのソリューション

従来型のOLTPデータベース・プロバイダも、ここで我々が取り上げている性能上の 問題を避けて通ってきた訳ではなく、これらのクリティカルな問題にソリューションを提示し始めています。
ただし、データ・ウェアハウスを実現する立場から見て、それらソリューションは、 OLTPアプリケーションでRDBMSを大成功させたインフラそのものからの大きな制約を受けています。 それでもまずは、これら見かけのソリューションを理解し、その限界を知ることが肝要です。

もっと良いジョイン・ペアの選択
スター・スキーマのジョイン問題をいくらか緩和する一般的な最適化手法として、 ペアワイズジョイン順序の組み合わせ評価個数を増やすという方法が行われています。基本的な考え方は、 関連性のあるテーブルだけを選択するようペア単位のジョイン・ストラテジを仕向けようとするものです。

この機能を理解するには、まず関連性のないテーブルをジョインするとどうなるかを 理解しなければなりません。2つのテーブルがジョインされ、テーブルを「リンク」するカラムがない場合、 2つのテーブル内の行のあらゆる組み合わせが作り出されます。RDBMS式で言えば、これが「デカルト積」です。
たとえば、ITEMテーブルに(paper、tape)という2つの行があり、COMPANYテーブルに(Sears、KMart、Walmart) という3つの行があるとすると、デカルト積には、paper+Sears、tape+Sears、paper+KMart、tape+KMart、 paper+Walmart、それにtape+Walmartという6つの行が含まれることになります。通常、RDBMSではデカルト積を 理にかなったペア単位のジョイン候補とはみなしませんが、スター・スキーマではこれらデカルト積により検索性能が 向上する場合があります。

スター・スキーマのファクト・テーブルは一般にそのディメンション・テーブルよりずっと大型であるため、 デカルト積を生成することでクエリー性能がアップする場合があります。ジョインすべき関連性をもったテーブルを 選定するうえでの1つの問題は、ペア単位のジョインに際して早いうちからファクト・テーブルが選ばれることにあります。 しかしファクト・テーブルが大きいため、大型の中間結果が生成されることから、これは極めて不利な選択になり得ます。
別のケースとして、全ディメンション・テーブルのデカルト積が(連続するペア単位のジョインにより) 最初に生成された場合、ファクト・テーブルへのジョインは、最後の最後まで引き伸ばされることになります。 この方法のメリットは、大型のファクト・テーブルを中間ジョイン結果に収容する必要がないことです。
ただし重要なコスト発生源として、ディメンション・テーブルのデカルト積を生成する必要があることです。 デカルト積生成コストが、ファクト・テーブルを使用して中間結果を生成するコストを下回る限り、 この最適化には何らかのメリットがあります。

こうした単純な最適化手法が万能薬でないことは明かです。 スター・スキーマに対するクエリーは当然多テーブル間のジョインを伴いますが、RDBMSではそれを 人為的に1組のペア単位ジョインに細分化しています。
さらに悪いことに、この戦略が効果を発揮するのは、 選択されたディメンション行のデカルト積が、ファクト・テーブル内の行数よりずっと小さい場合に限られます。 例に挙げたスキーマでご説明すると、ITEM行が10,000、SHIP_FROM行が500、SHIP_TO行が500、 DATA行が3,000、COMPANY行が1,000ある場合、最終的に得られる中間結果は7,500兆2もの行になります。
これでは、恐らく最後まで処理を完了することは不可能で、RDBMSはもっと古いタイプのペア単位ジョイン・ オーダリングを使用しなければならないでしょう。デカルト・ジョインの増殖性のため、 最適化は比較的小さな問題の場合にしか役に立ちません。この最後のポイントが問題の核心に近い部分です。 「小さい」ことと「データ・ウェアハウス」は相反するのです。

並列処理によるスター・スキーマ性能の改善
従来型OLTPデータベース・ベンダの多くは、並列処理(parallelism)がデータ・ウェアハウスの 性能問題を解決するかのごとく語っています。表面的には、パラレリズムは、市場でますます普及しつつある、 高性能対称型マルチプロセシング(SMP:synmetric multiprocessing)や超並列プロセシング (SMP:massively parallel processing)に照らして魅力的に見えます。しかしビジネス・ユーザにとって、 並列処理は当面のデータ・ウェアハウジングRDBMSの重要な構成要素ではあるものの、 OLTP対応のRDBMSに課せられた制限を克服することは残念ながらできません。

並列処理により、ユーザは単一クエリーの実行時間を短縮(スピードアップ)するか、 または実行時間を悪化させずに付加作業を処理(スケールアップ)するか、そのいずれかを実現可能です。
スピードアップは、クエリーが処理しなければならないデータ量を増やさないままコンピュ−ティング・ リソース(CPUやディスク)を追加することで実現されています。また、スケールアップを図るには、 クエリーに十分な量のコンピュ−ティング・リソースを追加投入し、クエリーが処理しなければならない 追加データ分を補償します。
ほとんどのデータベースが何らかの形の並列クエリー機能を装備しており、 様々なレベルでこれらの目的を達成することができます。

しかし、この方法は商用情報システムで不可欠な基本的なコストパフォーマンス という判断基準を完全に無視しています。
旧型のフォース・ジョイン・ストラテジに適用された場合、 並列処理の世界では、問題に対しふんだんにコスト(コンピュ−ティング・リソース)をつぎ込み、 なんとか適正な処理時間を達成することで性能上の問題を解決しようとしています。例を挙げてご説明しましょう。

最高のペアワイズアルゴリズムが、あるマルチテーブル・クエリーを500秒で 処理できるものと仮定します。このアルゴリズムが完全に並列化可能であるとすると、 プロセッサ10台のSMPシステムがあれば、このクエリーを50秒で処理完了できることになります。
別のやり方はあるものの、この方法でも悪くはありません。たとえば、マルチテーブル・ジョインを 処理するためにペアワイズジョイン・アルゴリズムより10倍の効率をもった「スーパー・アルゴリズム」 があるとしましょう。
このスーパー・アルゴリズムは、プロセッサ1台だけでこのクエリーを50秒で処理可能です。 プロセッサ10台のシステムにこの並列化されたスーパー・アルゴリズムを適用すれば、 このクエリーはなんとわずか5秒で処理可能です。

明らかに、スーパー・アルゴリズムに歩があります。 プロセッサ10台のシステムの場合と同じ50秒の性能を得るわけですが、残りのプロセッサ9台分のコストが節約できますし、 または残りのプロセッサを使用して他のクエリーを実行することもできます。
事実、ここで行った分析では、あまりにもバラ色過ぎる従来型データベースの絵を描いています。
なぜなら従来型システムでは、プロセッサの追加台数分に完全に見合っただけのスケールアップは不可能であり。 現存する従来型OLTPデータベースは、すべて並列処理にまつわるオーバヘッドが発生するため、 直線的なスケールアップは期待できません。たとえば、10 CPUから20 CPUにスケールアップしても、 60分かかるクエリーを45分に短縮することしかできません(期待値として50%でも実際には25%だけのスピードアップ)。
CPU数を増やせばそれに伴って問題は悪化し、極端な場合、CPUを増やすことで実際にクエリー処理を低速化してしまう ケースすらあります。

さらに、OLTP並列処理システムでは、パラレル・オン・デマンドとも言うべき、 クエリーに対応した適切な並列度を自動的に適用するストラテジはありません。
たとえば、あるクエリーでは 低並列度の方がメリットがあり、プロセッサ数を増やしても性能は上がらず、逆にリソースを無駄にする場合がありますし、 またクエリーによっては、投入可能な全プロセッサがほぼ有効に使用できる場合もあります。
これらOLTPシステムでは、クエリーによりケースバイケースで適正な並列度を微調整するという作業は、 すべてデータベース利用者に委ねられています。明らかに、この手法はオペレータすなわち人間の介在に、 そしてその技量に大きく依存しています。

最後に、並列処理はシステムのその他のアクティビティから切り離して考えるべきではありません。
システムの使用頻度が比較的低い場合は、他のクエリーや業務の実行に与える影響は小さく、 確かに並列度を高くすることができますが、システムの稼動率が高い場合、並列度の高さを要求する クエリーを投入すれば、他のシステム利用者のパフォーマンスはシャットダウンされてしまいます。 生産環境で並列処理を使用する場合、並列度決定の一環として、システム資源というもっと大きな問題を分析すべきです。

ビット・ベクトル・スター・ジョイン

ジョイン処理を高速化する別の技法として、一部データベースでは ビット・ベクトル「スター」ジョインという方法を使用します。このジョイン技法は、多ビット・ ベクトル・インデックスを処理してジョイン処理を高速化しようというものです。
一部の従来型データベース・ベクトルではこの種のビットマップ・インデックスおよび処理を追加して、 性能向上を提供しようとしています。

従来型のBツリー・インデックスという手法では、あり得るカラム値それぞれに 対し行IDのリストを維持します。この技術は多くのOLTPシステムではうまく機能しますが、行IDのリストが 長くなり、これらのリスト上で複雑な処理を実行するには多大なCPU時間が必要です。
たいていは、 ビットマップ・インデックスの方がずっと効率的に情報を格納します。

ビットマップ・インデックスのメリットは、実のところ、 特に制約条件が重なった場合の処理速度にあります。一連のビットマップ・インデックス上での 論理演算(ANDやORなど)実行プロセスは、特に行IDの複数リスト上で類似したプロセスを実行する 場合と比較して、実行効率は高くなっています。

ビット・ベクトル・スター・ジョインは、クエリー内での様々な制約条件に かなった行のビットマップ・リストを作成し、次いで新ビットマップ用の行を、全制約条件にかなった 全行にインタセクトします。この種の処理は、Bツリー・インデックスの長い行IDリストを処理することに比べれば、 ずっと効率的です。

ビット・ベクトル・ジョインは、多次元ジョインに対する興味深いソリューションですが、 このアプローチ自体、数多くの制約条件をもっています。

  • ビット・ベクトル・スター・ジョインは一部クラスのクエリーではうまく機能しますが、 複雑なクエリーに対する全方位のソリューションにはなりません。
  • データ・スキューの問題には対応していません。
  • クエリーに対し適切な並列度を調整する機能はありません。
  • 従来型のコスト・ベースのオプティマイザの予測問題には対応していません。
  • このストラテジはビット・ベクトル・インデックスを使用しているため、 これらインデックスの制約条件をそっくり受けてしまうことになります。たとえば、従来型のベクトル・ インデックスは、ドメイン値が小数の場合にしかうまく機能せず、その結果、ビット・ベクトル・ ターゲット・ジョインは、この種のカラムでしかうまく機能できません。

つまりビット・ベクトル・スター・ジョインは複雑なクエリー処理を扱う1方法ではあるものの、 データ・ウェアハウスが生成する複雑なクエリーに対する全方位的ソリューションを提供するものではあり得ないのです。

レッドブリックのスター・スキーマ処理テクノロジ・ファミリ
ここまでご説明した段階で、RDBMSはデータ・ウェアハウスにとっては頼りない候補で、 RDBMS以外のソリューションを求めなければならないとお考えかもしれません。しかし実は、リレーショナル・モデルは データ・ウェアハウジングによく適しているのです。
SQLの標準化、それに豊富なツールと専門技術が利用可能になっているおかげで、 RDBMSがデータ・ウェアハウスのデータ・リポジトリに向けた当然の選択であるということが裏付けられています。

そこで必要になるのは、データ・ウェアハウス・データベースに対する複雑なクエリーの 効率的な処理方法、すなわちこれまでに述べてきた多くの問題に左右されない方法です。データ・ ウェアハウジング環境で要求される複雑なクエリー処理は、スター・スキーマへの全方位的で柔軟な アプローチを前提としています。
レッドブリックのRDBMSは、もともとすべてがデータ・ウェアハウジング 環境に対応するよう設計されているため、ユニークな存在として 位置づけられています。レッドブリックはユニークな高性能インデックス、先進の最適化技法、 それに精度の高いジョイン処理アルゴリズムの組み合わせを実現したことでマルチテーブル・ジョインの 問題に対応可能になりました。

レッドブリックはデータ・ウェアハウジング専業であり、多次元ジョインに対して 提供するテクノロジの幅広さと洗練度において、他社の追随を許さないスキーマ・ソリューションを提供します。

  • レッドブリックのユニークなSTARjoin処理
  • スター・スキーマ処理技法を補完するTARGETjoinテクノロジ
  • それぞれのクエリーに対し最良のストラテジを選択する斬新な コストベースのオプティマイザによるインクリメンタルな動的最適化手法
  • TARGETindexの先進ビットマップ・インデックス技術
  • パラレル・オン・デマンドによるインテリジェントな並列処理で、性能の最適化多次元ジョインに対応した多数の高性能代替方式。

さらにそれらの中から最適なものを選択するための先進オプティマイザの提供を通じて、 Red Brick Warehouseは広範囲にわたりジョイン問題を解決し、最適なパフォーマンスを実現します。
レッドブリックは、一連のスター・スキーマ処理ソリューションを準備していることで、 予測不能のクエリー、大きく変化するユーザ負荷、スキューされたデータなどと言った、 実世界での性能上の問題に対応できる柔軟性を確立しています。

レッドブリックのソリューションから1つや2つのコンポーネントを 提供するだけでは十分とは言えないでしょう。
データ・ウェアハウス環境で 要求される柔軟性とパフォーマンスを提供するには、オールラウンドな、完全に統合化されたソリューションが必要です。

次に、レッドブリックのスター・スキーマ処理ソリューションのコンポーネントを順にご紹介します。

レッドブリックのSTARjoin
レッドブリックのSTARjoinは、高速・単一パスの並列処理対応マルチテーブル・ジョインです。 レッドブリックのユニークなSTARjoin技法は、従来型のOLTPデータベース製品では解決できない問題を克服します。
さらに、ジョインするテーブルが2つだけの場合でも、STARjoinの手法は、 従来型OLTPデータベースが実装しているジョイン手法とはひと味違います。これらの違いから、 他に類を見ないジョイン処理性能を実現しています。

STARjoinの利点をはっきりと理解するには、 クエリー性能をアップするためのインデックス化という旧来の手法と比べて見るのがよいでしょう。 クエリー処理を高速化するためにインデックスを利用する手法は、RDBMS全製品に古くから組み込まれた標準的な機能です。
テーブル内の選択されたカラム上にインデックスが定義され、クエリーがこれらのカラムだけに 制限されている場合、RDBMSはこのインデックスを使用して極めて迅速に問題の行を特定することができます。 同様な方法で、レッドブリックのRDBMSはSTARindexと呼ばれる特化されたインデックスの作成をサポートし、 ジョイン性能を飛躍的に向上させています。

レッドブリックのRDBMSは、ジョイン処理に対応したこれら特別のインデックスを サポートしている唯一のRDBMSです。STARindexは他のどのRDBMSが提供するインデックス構造とも異なった 構造を採用しています。言い換えれば、従来型のBツリーまたはビットマップ・インデックスをどう組み合わせて使っても、 レッドブリックがSTARindexで提供するメリットを得ることはできません。

STARindexはファクト・テーブルの1つ以上の外部キー・カラムに生成されます。 カラム値を、その値をもった行リストに変換する情報として格納する従来型のインデックスとは異なり、 STARindexは、ファクト・テーブルのディメンションを、それらのディメンションを含んだ行に関係づける 圧縮された情報として格納しています。
STARindexはスペース効率が極めて高いため、最高速に構築され、 維持可能です。STARjoinアルゴリズムはSTARindexを利用して、特定のジョインに必要な行すべてを効率よく特定できます。

従来型のOLTPデータベースが通常サポートしている複合キー・ インデックスと比較してみれば、STARjoinがどのように効率的にSTARindexを使用できるかがご理解いただけます。 これらの複合インデックスは、インデックス付けされるテーブル内の2つ以上のカラム値で構成されます。
これらのインデックスが定義され、クエリーがこれらのカラム値を参照するとき、インデックスはターゲット行を 極めて速い速度で選択可能です。同様に、STARindexが存在することで、レッドブリックのRDBMSは、 特定のディメンション・セットが関心をもつファクト・テーブルのターゲット行はどれかを迅速に特定できます。
また、STARindexは外部キー上に構成されているため、STARindexを使用可能なクエリーの型については 前提条件となるものは何もありません。言い換えれば、STARindexは実行可能なクエリーの種類やジョインの 型に制限を加えることなく、関連性のあるテーブルをジョインするクエリーを加速します。

STARindexと従来型マルチカラム・インデックスとの間には、ほとんど類似点はなく、 1つの重要な相違点は、マルチカラム・インデックスがテーブル1つだけを参照するのに対し、 STARindexは複数のテーブルを参照する唯一のインデックスだということです。
また、別の相違点として、マルチカラム・ インデックスの場合、クエリーが複合インデックス内の全カラム上に制限されない場合、指定されたカラムが リーディング・サブセットでない限りこのインデックスを完全に使用することはできません。
たとえば、 インデックス(A、B、C)は、A+B+C、A+B、またはAだけのどれかが制限されていれば使用可能ですが、 A+Cが制限されている場合には使用できません。
STARindexの場合、これと同じような状況として、 クエリーが必ずしもSTARindex内で定義された全テーブルを参照するとは限らない場合が考えられます。
ただし、マルチカラム・インデックスとは異なり、レッドブリックのRDBMSは制約条件の組み合わせや順序とは 無関係にSTARindexを使用できます。したがって、各種の分析に使用可能であり、結果として制約条件処理の 異なるパターンが生成されます。

ここで、ファクト・テーブルにジョイン可能な、ディメンション・テーブルの 完全なデカルト積を生成する、従来型OLTPデータベース手法をもう一度考えてみましょう。デカルト積の 大きさに制限があるため、この手法は、当然ながら中程度の大きさのディメンション・テーブルの場合 でもうまく機能できません。
しかし、全デカルト積を生成するというペナルティなしで、ディメンション・ テーブルをファクト・テーブルに効率よくジョインできるとしたらどうでしょう。
どんな従来型OLTPデータベース手法をもはるかに上回る性能をもった、世界最高のジョイン・テクノロジが 誕生することになります。この結果、生み出されたのがSTARjoinです。

STARjoinが一見不可能な局面で機能を果たせる理由は、STARindexのおかげで、 STARjoinならデカルト積のどの領域に問題の行が含まれているかを迅速に特定できる (Bツリー・インデックスが問題のカラム値を含む行を素早く特定する方法と類似した方法で)からです。 STARjoinアルゴリズムは問題の行が含まれる領域でデカルト積を生成し、行のない地域でのデカルト積の 生成はパスします。

簡単な例をあげれば、COMPANYディメンション・テーブルに100行が含まれているとすると、 デカルト積1つは100の会社それぞれに対して行を生成することになります。しかし、他のディメンション値の 特定のセットに対し、ファクト・テーブルにこれら会社のうち2社だけのデータしか格納されていない場合でも、 必要のない98通りの組み合わせをやむを得ず生成しなければならないことになります。 STARjoinならSTARindexのおかげで、対象となる会社は2社だけであることを知り、 これら2社に対応するデカルト積だけを生成します。

図4. STARIndex
図4. STARIndex

TARGETjoin
レッドブリックのSTARスキーマ処理のもう1つのキー・コンポーネントとなるのがTARGETjoinテクノロジです。 TARGETjoinは単純なビット・ベクトル・スター・ジョイン技術をかつてないほど洗練したものです。 この洗練こそ、実世界のデータ・ウェアハウス処理にとって必要不可欠なものです。

TARGETjoinとは、レッドブリックRDBMSに既に組み込まれた高性能・ 低メンテナンスのビット・ベクトル化インデックス・テクノロジであるTARGETindexを使用するジョイン手法です。 TARGETjoinは洗練されたマルチテーブル・ジョイン処理を使用し、多様なクエリーを解決します。 TARGETjoinがもたらす代表的なメリットを以下に列挙します。

  • TARGETjoinはレッドブリックのTARGETindexを使うジョインテクノロジです。 TARGETindexは単純なビットマップ・インデックスに比べて多くの長所がありますが、いくつかを以下に示します。
    • 適応化インデックス作成テクノロジを採用。これによりインデックスはどんなデータ・スキューにも最適化可能。
    • あらゆるカーディナリティのデータに対応したインデックス・ファミリ。
    • ストレージ・スペースやロードの更新時間という点でオーバヘッドを極少化。
    • 実行時間再発行および早期exit最適化で圧倒的な性能を発揮。
  • TARGETjoinは、ファクト・テーブル内の外部キー上にTARGETindexを生成する以外に特別な事前チューニングは不要。
  • TARGETjoinは多種多様なクエリーを柔軟に処理可能。

TARGETjoinテクノロジは、ファクト・テーブル内の対象外部キー上にTARGETindexが 存在することを前提としています。TARGETjoinはディメンション・テーブルとTARGETindexを使用して、 クエリー内の各制約条件に対する行リストを作成し、次いでこれらリストをインターセクトして、 ファクト・テーブルから検索する行のリストを作成します。

例を挙げてご説明します。あるクエリーを投入して、売上げまたは販売部門毎の 5月の$2,000超の購入をリストアップすることにします。
クエリーは顧客、項目およびデータ・ディメンションを 絞り込んで、PURCHASESというファクト・テーブルを参照します。

PURCHASESテーブル内で項目キー、顧客キーおよび日付キー上にTARGETindexがあると 仮定すると、TARGETjoinは以下の順に動作します。

  • ITEMテーブルから、$2,000超の項目を見つける。
  • これら項目とPurchasesテーブル内の項目キー上のTARGETindexとをジョインし、 この制約条件に適合した行のリストを作成する。
  • 上記2ステップを、クエリー内の他の制約条件についても実行する。
  • 結果として得られたリストをインターセクトする。全リスト上で発生した 行はすべての条件を満足しており、したがって売上げテーブルから検索されなければならない。
  • この行リストをディメンション・テーブルの対象行とジョインし、すべての結果を得る。

このソリューションがもたらすメリットは柔軟性の高さです。 必要条件として要求されるのは条件はただ1つ、TARGETindexがファクト・テーブルの外部キー上に存在することだけです。 ビットマップ・リストのインターセクトは効率の高い操作です。ファクト・テーブルから対象行を検索するだけで、 TARGETjoinはファクト・テーブルとの間の入/出力を大幅に減少させます。

レッドブリックのパラレル・オン・デマンド
あるプロセスが並列処理に対応しており、オプティマイザが適切に実現可能な場合、 並列処理は複雑なクエリーの実性能を高めます。しかし、単純なクエリーの場合や、並列プロセスに 容易に分解できないクエリーの場合、並列処理を行った結果大きなオーバヘッドが発生するケースもあります。
レッドブリックの「パラレル・オン・デマンド」テクノロジは、最適な並列度であるか否かについてクエリーを 分析します。複雑なクエリーの場合は並列処理の必要性は高くなり、単純な処理の場合は必要性は低くなります。 レッドブリックの製品にはこの最先端並列処理テクノロジが組み込まれています。

レッドブリックのデータベースは、必要な場合に事実上無制限の並列度を 発揮する能力をもっています。たとえば、STARjoinはもともと並列化可能です。 相互間で調整が効く範囲で作業を複数の独立プロセスに分割することができます。
分割されたそれぞれのプロセスに対してそれ自身の作業用「ジョイン・スペース」が付与され、 これをさらに任意の個数のスペースに分割することができます。その結果、任意個数の並列作業割当が可能になり、 作業間で調整を行う必要はありません。こうしてスケールアップのための完全なレシピが出来上がります。

レッドブリックのパラレル・オン・デマンド技術は、 並列度を動的に設定することができないOLTPシステムとは対照的です。たとえば、 ほぼ同一の2つのクエリーを考えてみます。最初のクエリーでは、5月のおもちゃのトラックの全購入数を選択し、 DATESとPRODUCTSテーブルをSALESテーブルにジョインします。
2番目のクエリーも最初のと同じですが、 このクエリーでは5月のおもちゃの全購入数を求めます。このクエリーもDATESとPRODUCTテーブルを SALESテーブルにジョインします。

レッドブリックのアナライザは、2番目のクエリーの方で自動的に高い並列度を起動します。 その理由は、2番目のクエリーではおもちゃというカテゴリに入る全製品を選択しており、一方、 最初のクエリーはおもちゃのトラックだけを探しているため並列度が低いからです。ほとんどの従来型RDBMSでは、 こうしたクエリーに対し前もって適切な並列度を選定しておかなければなりません。
この場合、実際のところ、 ユーザは、最適な性能を実現するためにクエリー毎に並列度を微調整しなければなりません。

しかしレッドブリックのインテリジェントなパラレル・オン・デマンドの機能は もっと進んでいます。クエリーだけに注目するのではなく、現在のシステム資源の利用効率をチェックします。
システムの大部分が空き状態の場合、メリットが出るとなれば並列度を高めますが、 システムが高稼動の場合には並列度を抑えます。こうした制御を行うことで、 複雑な大型クエリーのためにシステムが他のクエリーをシャットダウンするという事態を防止し、 システム稼動が低い場合には可能な限りのベスト・パフォーマンスを得ることができます。
クエリーのもつ要件に加えてシステム資源を考慮することで、レッドブリックのパラレル・オン・デマンド技術は、 個々のクエリーの実行性能だけでなく、システム全体としてのベスト・パフォーマンスを確保することができます。

インクリメンタルな動的クエリー最適化
前述したように、従来型のコストベース最適化手法は、複雑なスキーマではうまく機能できません。 そこでレッドブリックでは、従来型OLTPデータベース・ベンダとは大きく異なるアプローチを選んで この問題に対応しています。
それはデータ・ウェアハウジング環境での複雑なクエリーにもっともふさわしいアプローチです。

レッドブリックのデータベースは、インクリメンタル最適化モデルに対応した唯一のRDBMSであり、 クエリーのどの部分が合理的に予測可能であるかを決定してから実行に移すというのが基本的な考え方です。
このステップの実行結果(予測値ではありません)を使用して、次のステップを予測し、予測誤差を次々と 波及させるという問題を取り除きます。さらに、実際のデータが統計値に基づく期待と大きく異なる場合、 クエリー実行中であってもプランを変更可能です。一例として、レッドブリックのRDBMSではこの技法を使用し、 ジョインされるディメンション・テーブル内の行数が確定された後に、適切なSTARindexを選択します。 その結果、予測値が頼りのどんなアプローチより、はるかに優れたインデックス選択が可能です。

レッドブリックのSTARスキーマ処理性能

レッドブリックの幅広いSTARスキーマ処理テクノロジは、 様々な状況下で他に類を見ないジョイン性能を提供します。
STARindexはインデックスのマッチしたクエリーに対し、 卓越したパフォーマンスを提供します。TARGETjoinテクノロジは、STARindexが存在しない、 またはインデックスがクエリーにマッチしない状況下で優れたソリューションを提供します。

レッドブリックのSTARスキーマ処理の性能上のメリットをもっと深く理解していただくため、 次の例を考えてみて下さい。発生し得るITEM数が500、COMPANYが200、DATESが300、 それにPURCHASESが1,000,000がデータベースに収容されているとしましょう。さらに、 特定のクエリーでITEMを50、COMPANIESを20、それにDATESを30選択し、 最終的にPURCHASESレコード1,000を選択するものとしましょう(データの分布は均一で、 データ・スキューはないものとします)。

ペアワイズのジョイン
この例で、従来型のペアワイズジョイン選択は、次のようになります。

PURCHASES+ITEMのジョイン、(PURCHASES+ITEM)+DATEのジョイン、(PURCHASES+ITEM+DATE)+COMPANYのジョイン

最初のジョインでは約100,000行が生成され、次のジョインでは約10,000行が生成され、 最後のジョインでは1,000行が生成されることになります。したがって、このクエリーを処理するために 生成される行数合計は111,000になります。

デカルト・ジョイン
デカルト積手法では、ITEMが50、COMAPIESが20、DATESが30で、50x20x30=3,000行が 生成されることになります。このデカルト積は直接PURCHASESテーブルにジョインできますので、 最終的に1,000行が生成されることになり、このときのコスト合計は処理数30,000+1,000=31,000行です。

TARGETjoin
TARGETjoinではペアワイズの処理と同数の行(111,000)が生成されますが、 ビット・ベクトル処理は一般に行そのものを実際にジョインする場合より1桁高速化されます。 その理由は、行IDリストではなく、簡単な操作が可能なビット列を処理しているからです。 したがって、TARGETjoinは、11,000行を生成するジョイン方式に匹敵することになります。

STARjoin
うまく制限を設けたSTARjoinを使用すれば、実際に、PURCHASESテーブルの 選択された行に存在する組み合わせよりわずかに多いだけの組み合わせが生成されます。 つまり、10%程度多いだけで、このときのコスト合計は、1,000+(1,000x10%)=1,100行です。

行数を使ってクエリーをコスト化するのは原始的な方法かもしれませんが、 アプローチ間の相対コストという考え方を提供してくれます。この例では、デカルト積手法は単純なペア 単位の手法よりざっと3.5倍の効率が得られますが、STARjoinならさらにデカルト手法の28倍の効率が得られ、 ペアワイズ手法と比べると、なんと101倍もの効率アップになります。

複雑なスキーマ

これまでの説明では比較的単純なスター・スキーマの例を取り上げてきました。 しかし実世界のデータ・ウェアハウジング・スキーマは多くの場合もっと複雑です。 レッドブリックのテクノロジ・ファミリは単純なスキーマだけでなく、複雑なスキーマも処理します。

一例として、1つ以上の共通ディメンション付きの多数ファクト・テーブルを もったスキーマを考えてみます。
多くの場合、このようなスキーマに対して処理されるクエリーは、 対応するディメンションにファクト・テーブルを関係付けるだけでなく、ファクト・テーブル相互間の 関係付けを行います。STARindexはこのようなタスクに最適です。特に、多数ファクト・テーブルの ジョインは、ジョインされるテーブルのSTARindexに選択的にアクセスして実行可能ですから最終結果として、 複雑なジョインを、従来型OLTPデータベースでは考えられないスピードで処理します。
事実、 これらの複雑なスキーマは、従来型OLTPにはまったくフィットしません。複雑なスキーマでは、 単一ファクト・テーブル・スキーマの倍以上の問題に対応できなければならないからです。

図5に、マルチファクト・テーブル・スター・スキーマを示します。
図5に、マルチファクト・テーブル・スター・スキーマを示します。
図5に、マルチファクト・テーブル・スター・スキーマを示します。

PURCHASESファクト・テーブルでは項目の購入が追跡され、 SALESファクト・テーブルでは同一項目の売上げが追跡されます。
それぞれのファクト・テーブルには、 これらファクトの分析に適したディメンションが設けられています。2つのファクト・テーブルが共通の ディメンションITEMを共有します。この共有化により、アナリストは2つのファクト・テーブルを関係づけ、 「特定の項目の組み合わせは、それらの同じ項目の売上げと比較してどうなのか」といった質問を投入することができます。
この複雑なスキーマは従来型のRDBMSには越えられないハードルとなりますが、 レッドブリックのSTARjoinテクノロジなら難なく実行可能です。

統合化のパワー

レッドブリックのテクノロジ・ファミリの強みは、 高度に最適化が施されたジョイン手順とインテリジェントな並列処理機能の両方が統合 された形で利用できる点にあります。うまく定義されたSTARindexはクリティカルなクエリーに対して最適性能を提供し、 また外部キー上のTARGETindexは、多種多様なクエリーでTARGETjoinを実行可能にします。 レッドブリックのインクリメンタルな動的オプティマイザは、クエリーそれぞれに対し最良の アルゴリズムを自動的に選択します。
レッドブリックのインテリジェントなパラレル・オン・デマンドは、 並列処理環境での最適なパフォーマンスを実現し、それぞれのクエリーに対して最も効率よくハードウェアを活用します。

まとめ

データ・ウェアハウス・システムにはOLTPシステムのものとは異なるスキーマが必要です。 なぜならデータ・ウェアハウスは、大量データ上のアドホックで、多くの場合複雑なクエリーに対して、迅速な応答を 返さなければならないからです。

データ・ウェアハウスは集中・集約的なアドホック・クエリーをサポートする必要がありますが、 スター・スキーマはこの種の要求に極めて適しています。OLTPデータベースは、データ・ウェアハウスに要求される スキーマおよび処理には本質的に適していません。
OLTPベンダによる性能上の問題に対する取り組みは、 残念ながら強靭なデータ・ウェアハウス環境が求める総合的で柔軟なソリューションを提供するまでには至っていません。

レッドブリックのRDBMSは、スター・スキーマ・ジョイン処理に対応した業界最先端の 広範囲で内容の濃いソリューションとして、データ・ウェアハウジングの理想的な選択です。
レッドブリックRDBMSの複雑な複数ファクト・テーブル・スキーマ処理能力は、適切な並列度を割り当て、 データのリアルな特質に基づきSTARindexやその他のスター・スキーマを動的に選択可能であり、 データ・ウェアハウジング業界にあってユニークな存在です。

脚注

  1. おおのきよし、Guy M. Lohman共著"Measuring the complexity of Join Enumeration in Query Optimization"、proceedings of the 16th VLDB Conference、オーストラリア、ブリスベーン、1990年8月13〜16。
  2. 10,000x500x500x3,000x1,000=~7,500兆
    実際には、これらのデータベースはこの場合にこのアプローチを用いることはなく、 代わりにペア単位ジョインまたは他の方法を選択します。これらの例は、大型ディメンション・ テーブルの場合のこのアプローチの有効性に限界があることを明示するものです

ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Information Management
ArticleID=326092
ArticleTitle=複雑なクエリーに対応したスター・スキーマ処理
publish-date=11262004