(57)【要約】システムは、コーディネータノードと、コーディネータノードと通信しているワーカノードとを含む。各ワーカノードは、データブロックを記憶する。各データブロックは、半構造化形式でデータを有し、各データブロックは、クエリ言語によって解釈可能な表形式への半構造化形式のデータの変換を規定する関連外部テーブル宣言を有する。コーディネータノードによって実行されるクエリプロセッサは、クエリ言語クエリに応答して、分散型クエリプランを生成する。分散型クエリプランは、サブクエリを含む。サブクエリは、ワーカノードのうちの選択されたワーカノードによって実行される。選択されたワーカノードは、クエリ言語クエリに応答して、外部テーブル宣言を使用して半構造化形式のデータを分散型データベースの表形式に変換し、表形式データを提供する。
2015531937.tif 000002
【特許請求の範囲】
【請求項１】
コーディネータノードと、
前記コーディネータノードと通信している複数のワーカノードであって、各ワーカノードは、データブロックを記憶し、各データブロックは、半構造化形式でデータを有し、各データブロックは、クエリ言語によって解釈可能な表形式への前記半構造化形式の前記データの変換を規定する関連外部テーブル宣言を有する、ワーカノードと、
前記コーディネータノードによって実行されるクエリプロセッサであって、前記クエリプロセッサは、クエリ言語クエリに応答して分散型クエリプランを生成し、前記分散型クエリプランは、サブクエリを含む、クエリプロセッサと
を備え、
前記サブクエリは、前記複数のワーカノードのうちの選択されたワーカノードによって実行され、
前記選択されたワーカノードは、前記クエリ言語クエリに応答して、外部テーブル宣言を使用して半構造化形式のデータを分散型データベースの表形式に変換し、表形式データを提供する、システム。
【請求項２】
前記コーディネータノードは、前記選択されたワーカノードからの前記表形式データをマージしてクエリ結果を提供する、請求項１に記載のシステム。
【請求項３】
各サブクエリは、関連データブロックに関連付けられている、請求項１に記載のシステム。
【請求項４】
前記クエリプロセッサは、各サブクエリを、前記関連データブロックを含むワーカノードに向かわせる、請求項３に記載のシステム。
【請求項５】
前記コーディネータノードは、外部テーブルメタデータを維持し、前記外部テーブルメタデータは、前記表形式を特徴付ける、請求項１に記載のシステム。
【請求項６】
前記クエリプロセッサは、前記外部テーブルメタデータにアクセスして前記分散型クエリプランを作成する、請求項５に記載のシステム。
【請求項７】
前記コーディネータノードは、前記データブロックについてのメタデータを維持し、前記メタデータは、前記複数のワーカノードにわたる前記データブロックの場所を含む、請求項１に記載のシステム。
【請求項８】
前記クエリプロセッサは、前記データブロックについての前記メタデータにアクセスして前記分散型クエリプランを作成する、請求項７に記載のシステム。
【請求項９】
前記クエリプロセッサは、代替ネットワーク入力／出力コストを評価して前記分散型クエリプランを作成する、請求項１に記載のシステム。
【請求項１０】
前記クエリプロセッサは、前記データブロックについての統計を評価して前記分散型クエリプランを作成する、請求項１に記載のシステム。
【請求項１１】
前記クエリプロセッサは、前記複数のワーカノードの間で１つ以上のデータブロックをコピーするコマンドを発行して前記分散型クエリプランを実行する、請求項１に記載のシステム。
【請求項１２】
前記クエリプロセッサは、前記データブロック内の前記データを再パーティション化して前記分散型クエリプランを実行する、請求項１に記載のシステム。
【請求項１３】
データブロックは、前記複数のワーカノードにわたって複製される、請求項１に記載のシステム。
【請求項１４】
データブロックは、テキストファイルとして記憶されている、請求項１に記載のシステム。
【請求項１５】
データブロックは、バイナリファイルとして記憶されている、請求項１に記載のシステム。
【請求項１６】
前記選択されたワーカノードは、前記データブロックについての統計を評価してサブクエリプランを作成する、請求項１に記載のシステム。
【請求項１７】
前記選択されたワーカノードは、データブロックインデックスを評価してサブクエリプランを作成する、請求項１に記載のシステム。
【請求項１８】
前記クエリ言語クエリは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）クエリである、請求項１に記載のシステム。
【請求項１９】
前記クエリ言語サブクエリは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）クエリである、請求項１に記載のシステム。
【請求項２０】
ネットワークワーカノード上にデータブロックを記憶することであって、前記データブロックは、半構造化形式でデータを有する、ことと、
前記データブロックをクエリ言語によって解釈可能な表形式への前記半構造化形式の前記データの変換を規定する関連外部テーブル宣言と関連付けることと、
クエリ言語クエリに応答して分散型クエリプランを生成することであって、前記分散型クエリプランは、サブクエリを含む、ことと、
前記サブクエリを前記ネットワークワーカノードのうちの選択されたワーカノードに向かわせることと、
前記選択されたワーカノードにおいて前記サブクエリを実行することであって、実行することは、前記クエリ言語クエリに応答して、前記外部テーブル宣言を使用して半構造化形式のデータを表形式に変換し、表形式データを生成することを含む、ことと、
前記表形式データをマージしてクエリ結果を生成することと
を含む、コンピュータ実装方法。
【請求項２１】
各サブクエリを関連データブロックに関連付けることをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項２２】
各サブクエリを前記関連データブロックを含むワーカノードに向かわせることをさらに含む、請求項２１に記載のコンピュータ実装方法。
【請求項２３】
外部テーブルメタデータを生成することをさらに含み、前記外部テーブルメタデータは、前記表形式を特徴付ける、請求項２０に記載のコンピュータ実装方法。
【請求項２４】
前記外部テーブルメタデータにアクセスして前記分散型クエリプランを作成することをさらに含む、請求項２３に記載のコンピュータ実装方法。
【請求項２５】
前記データブロックについてのメタデータを生成することをさらに含み、前記メタデータは、前記ネットワークワーカノードにわたる前記データブロックの場所を含む、請求項２０に記載のコンピュータ実装方法。
【請求項２６】
前記データブロックについての前記メタデータにアクセスして前記分散型クエリプランを作成することをさらに含む、請求項２５に記載のコンピュータ実装方法。
【請求項２７】
代替ネットワーク入力／出力コストを評価して前記分散型クエリプランを作成することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項２８】
前記データブロックについての統計を評価して前記分散型クエリプランを作成することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項２９】
１つ以上のデータブロックをコピーするコマンドを発行して前記分散型クエリプランを実行することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３０】
前記データブロック内の前記データを再パーティション化して前記分散型クエリプランを実行することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３１】
データブロックは、前記ネットワークワーカノードにわたって複製される、請求項２０に記載のコンピュータ実装方法。
【請求項３２】
テキストファイルとしてデータブロックを記憶することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３３】
バイナリファイルとしてデータブロックを記憶することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３４】
前記データブロックについての統計を評価してサブクエリプランを作成することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３５】
データブロックインデックスを評価してサブクエリプランを作成することをさらに含む、請求項２０に記載のコンピュータ実装方法。
【請求項３６】
前記クエリ言語クエリは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）クエリである、請求項２０に記載のコンピュータ実装方法。
【請求項３７】
前記クエリ言語サブクエリは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）クエリである、請求項２０に記載のコンピュータ実装方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の引用）
本願は、米国特許出願第１３／６００，１２６号（２０１２年８月３０日出願）を基礎とする優先権を主張する。該出願の内容は、参照により本明細書に引用される。
【０００２】
（発明の分野）
本発明は、概して、ソフトウェアベースのデータの記憶および読み出しに関する。より具体的には、本発明は、外部テーブルを伴う分散型データベースを動作させるための技法に関する。
【背景技術】
【０００３】
分散型データベースは、データのパーティションが、個別的な計算リソースにわたって分散される、データベースである。分散型データベースは、同一の物理的場所に位置する複数のコンピュータ内に実装され得るか、または相互接続されたコンピュータのネットワークを経由して、分散させられ得る。分散型データベースは、インターネット、企業内イントラネットまたはエクストラネット、あるいは他のネットワーク上のネットワークサーバ上に常駐することができる。
【０００４】
データベースは、データの問い合わせされることが可能である前に、データをモデル化してロードするようにユーザに要求する。これは、近年、外部テーブルの概念を導入した、ＰｏｓｔｇｒｅＳＱＬによって若干変化した。この変化で、ユーザは、現在、半構造化外部データソースからデータを読み取る拡張機能を定義することができる。オンラインエンサイクロペディアＷｉｋｉｐｅｄｉａは、関係データベースまたは他の形態のデータテーブルに関連付けられるデータモデルの形式的構造に一致しないが、それでもなお、意味要素を分離して、データ内のレコードおよびフィールドの階層化を実施するためのタグまたは他のマーカを含む構造化データの形態として、半構造化データを特徴付ける（ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｓｅｍｉ−ｓｔｒｕｃｔｕｒｅｄ＿ｄａｔａを参照）。
【０００５】
外部テーブル拡張機能は、半構造化データを表形式に変換し、次いで、これは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）等の標準クエリ言語を使用して問い合わせされることができる。以下の一般コード形式が、外部テーブルを作成するために使用され得る。
【０００６】
ＣＲＥＡＴＥ  ＦＯＲＥＩＧＮ  ＴＡＢＬＥ  ［  ＩＦ  ＮＯＴ  ＥＸＩＳＴＳ  ］  ｔａｂｌｅ＿ｎａｍｅ  （  ［
｛ｃｏｌｕｍｎ＿ｎａｍｅ  ｄａｔａ＿ｔｙｐｅ［  ＮＵＬＬ  │  ＮＯＴ  ＮＵＬＬ］｝
［，・・・］
［）
ＳＥＲＶＥＲ  ｓｅｒｖｅｒ＿ｎａｍｅ
［ＯＰＴＩＯＮＳ（ｏｐｔｉｏｎ‘ｖａｌｕｅ’［，・・・］）］
このコードは、以下のパラメータを使用する。“ＩＦ  ＮＯＴ  ＥＸＩＳＴＳ”は、同一の名称を伴う関係がすでに存在する場合に、エラーをスローしないことを規定する。“ｔａｂｌｅ＿ｎａｍｅ”は、作成されるテーブルの名称である。“ｃｏｌｕｍｎ＿ｎａｍｅ”は、新しいテーブルの中に作成される列の名称である。“ｄａｔａ＿ｔｙｐｅ”は、列のデータタイプである。“ＮＯＴ  ＮＵＬＬ”は、列がヌル値を含むことを許されないことを示す。“ＮＵＬＬ”は、列がヌル値を含むことを許されることを示す。“ｓｅｒｖｅｒ＿ｎａｍｅ”は、外部テーブルのための既存のサーバの名称である。“ＯＰＴＩＯＮＳ（ｏｐｔｉｏｎ‘値’［，・・・］）”は、新しい外部テーブルに関連付けられるオプションを規定する。許されるオプション名および値は、外部テーブルに関連付けられる外部データラッパに特有である。これらのオプションは、外部データラッパのバリデータ機能を使用して正当性を立証される。
【０００７】
以下の外部テーブル宣言は、“ｍｕｓｉｃ”と呼ばれるテーブルをインスタンス化する。
【０００８】
ＣＲＥＡＴＥ  ＦＯＲＥＩＧＮ  ＴＡＢＬＥ  ｍｕｓｉｃ［
ｃｏｄｅ      ｃｈａｒ（５）  ＮＯＴ  ＮＵＬＬ，
ｔｉｔｌｅ    ｖａｒｃｈａｒ（４０）  ＮＯＴ  ＮＵＬＬ，
ｄｉｄ    ｉｎｔｅｇｅｒ  ＮＯＴ  ＮＵＬＬ，
ｄａｔｅ＿ｐｒｏｄ  ｄａｔｅ，
ｋｉｎｄ    ｖａｒｃｈａｒ（１０），
ｌｅｎ    ｉｎｔｅｒｖａｌ  ｈｏｕｒ  ｔｏ  ｍｉｎｕｔｅ
）
ＳＥＲＶＥＲ  ｍｕｓｉｃ＿ｓｅｒｖｅｒ
ＯＰＴＩＯＮＳ（ｆｏｒｍａｔ‘ｔｅｘｔ’，ｆｉｌｅｎａｍｅ‘／ｈｏｍｅ／ｕｓｅｒ／ｍｕｓｉｃ．ｔｘｔ’，ｄｅｌｉｍｉｔｅｒ‘：’，ｎｕｌｌ‘’）；
このテーブル作成コマンドは、単純に、データベース内に外部テーブルのメタデータを記憶し、これらのメタデータは、列名、列タイプ、および列オプションを含む。この特定のコマンドはまた、ディスク上のテキストファイルを新たに作成された外部テーブルに関連付け、このテキストファイル内のデータを解析するために必要とされるオプションを規定する。
【０００９】
ｍｕｓｉｃテーブルがインスタンス化されると、テキストファイルのコンテンツは、実際にデータをデータベースにロードすることなく問い合わせされることができる。むしろ、データは、持続的にその半構造化形式のままである。ＳＱＬクエリをサポートするために、外部テーブルがインスタンス化されるにすぎない。
【００１０】
したがって、Ａｐａｃｈｅログファイルのための拡張機能を定義し、クエリ時間にログファイルを解析するための拡張機能を書き込み、データへのクエリを実行することができる。ユーザはまた、インターネットまたは他のデータベース上のデータにアクセスする拡張機能を書き込むこともできる。
【００１１】
問題は、ユーザが１つの外部データソースを１つのテーブルに関連付けることしかできないことである。したがって、ユーザが１日につき２４個の（１時間毎の）Ａｐａｃｈｅログファイルを受信する場合には、ユーザは２４個の外部テーブルを作成する必要がある。したがって、クエリ処理が困難になる。さらに、多数のウェブサーバが、Ａｐａｃｈｅログファイルを並行して生成していることがあり、これらのログファイルを処理することは、典型的には、単一のデータベースサーバの能力を超えて拡張するリソースを必要とする。
【００１２】
前述を考慮すると、外部テーブルを伴う分散型データベースを動作させるための効率的な技法を提供することが望ましいであろう。より具体的には、分散型データベース内の半構造化データのクエリ言語クエリのための技法を提供することが望ましいであろう。
【発明の概要】
【課題を解決するための手段】
【００１３】
システムは、コーディネータノードと、コーディネータノードと通信しているワーカノードとを含む。各ワーカノードは、データブロックを記憶する。各データブロックは、半構造化形式でデータを有し、各データブロックは、クエリ言語によって解釈可能な表形式への半構造化形式のデータの変換を規定する関連外部テーブル宣言を有する。コーディネータノードによって実行されるクエリプロセッサは、クエリ言語クエリに応答して、分散型クエリプランを生成する。分散型クエリプランは、サブクエリを含む。サブクエリは、ワーカノードのうちの選択されたワーカノードによって実行される。選択されたワーカノードは、クエリ言語クエリに応答して、外部テーブル宣言を使用して半構造化形式のデータを分散型データベースの表形式に変換し、表形式データを提供する。
【００１４】
コンピュータ実装方法は、ネットワークワーカノード上にデータブロックを記憶することを含む。データブロックは、半構造化形式でデータを有する。データブロックは、クエリ言語によって解釈可能な表形式への半構造化形式のデータの変換を規定する関連外部テーブル宣言に関連付けられる。分散型クエリプランが、クエリ言語クエリに応答して生成される。分散型クエリプランは、サブクエリを含む。サブクエリは、ネットワークワーカノードのうちの選択されたワーカノードに向かわせられる。サブクエリは、選択されたワーカノードにおいて実行される。実行は、クエリ言語クエリに応答して、外部テーブル宣言を使用して半構造化形式のデータを表形式に変換し、表形式データを生成することを含む。表形式データは、クエリ結果を生成するようにマージされる。
【図面の簡単な説明】
【００１５】
本発明は、付随の図面と関連して検討される、以下の発明を実施するための形態と併せて、より完全に理解される。
【図１】図１は、本発明のある実施形態に従って構成される、システムを図示する。
【図２】図２は、本発明のある実施形態に関連付けられる処理動作を図示する。
【図３】図３は、本発明のある実施形態に従って行われる、外部テーブルメタデータ同期化動作を図示する。
【図４】図４は、本発明のある実施形態による、外部テーブルメタデータおよびデータブロック場所の同期化を図示する。
【図５】図５は、本発明のある実施形態による、クエリ実行の実施例を図示する。
【発明を実施するための形態】
【００１６】
類似参照番号は、図面のいくつかの図全体を通して、対応する部分を指す。
【００１７】
図１は、本発明のある実施形態に従って構成される、システム１００を図示する。システム１００は、分散型データベースを実装する、コーディネータノード１０２と、一組のワーカノード１０４＿１から１０４＿Ｎとを含む。コーディネータノード１０２は、マスタノードであり得るか、またはマスタノードにアタッチされ得る（図示せず）。有線または無線ネットワーク接続１０６が、コーディネータノード１０２とワーカノード１０４とを連結する。
【００１８】
コーディネータノード１０２は、バス１１４を介して、一組の入力／出力デバイス１１２に接続される中央処理ユニット１１０等の標準的構成要素を含む。入力／出力デバイス１１２は、キーボード、マウス、ディスプレイ、プリンタ等を含み得る。ネットワークインターフェース回路（ＮＩＣ）１１６もまた、バス１１４に接続され、ネットワーク接続１０６を通して、ワーカノード１０４へのアクセスを提供する。メモリ１２０もまた、バス１１４に接続される。メモリ１２０は、開示される動作を実装するための実行可能な命令を記憶する。特に、メモリは、以下に開示される分散型データベース動作を実装するための実行可能な命令を含むコーディネータノードモジュール１２２を記憶する。一実施形態では、コーディネータノードモジュール１２２は、以下に論じられるように、クエリプロセッサ１２４と、外部テーブルメタデータ１２６とを含む。
【００１９】
各ワーカノード１０４も、中央処理ユニット１６０、バス１６２、入力／出力デバイス１６４、およびネットワークインターフェース回路１６６等の標準的構成要素を含む。各ワーカノードコンピュータ１０４はまた、ワーカノードモジュール１７２の形態における実行可能な命令を伴う、メモリ１７０を含む。ワーカノードモジュール１７２は、コーディネータノードモジュール１２２からのコマンドに応答する、実行可能な命令を含む。そのようなコマンドは、以下に論じられるように、分散型データベースパーティションの記憶、アクセス、複製、および重複に関連する。追加のコマンドは、データから洞察を導き出すように分散型データベースパーティションにクエリを行うことに関する。一実施形態では、ワーカノードモジュール１７２は、データブロック１７４を含む。いくつかのデータブロックが、半構造化データである一方で、他のデータブロックは、構造化され得る（すなわち、表形式データまたはデータベーステーブル）。ワーカノードモジュール１７２はまた、外部テーブル宣言１７６も含む。外部テーブル宣言の各々は、半構造化データブロックから外部テーブルをインスタンス化するために使用される。
【００２０】
システム１００はまた、１つ以上のクライアントコンピュータ１８０を含み得る。各クライアントコンピュータ１８０は、分散型データベースの関連付けられたユーザを有する。クライアントコンピュータ１８０はまた、中央処理ユニット１９０、バス１９４、入力／出力デバイス１９２、およびネットワークインターフェース回路１９６等の標準的構成要素を含む。各クライアントコンピュータ１８０はまた、クライアントモジュール１９９の形態における実行可能な命令を伴うメモリ１９８を含む。クライアントモジュール１９９は、分散型データベースにアクセスするために使用される、ブラウザであり得る。代替として、クライアントモジュール１９９は、分散型データベースと相互作用するための専用アプリケーションであり得る。本専用アプリケーションは、Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ（ＳＱＬ）、Ｏｐｅｎ  Ｄａｔａｂａｓｅ  Ｃｏｎｎｅｃｔｉｖｅｌｙ（ＯＤＢＣ）、およびＪａｖａ（登録商標）−ｂａｓｅｄ  Ｄａｔａｂａｓｅ  Ｃｏｎｎｅｃｔｉｖｉｔｙ（ＪＤＢＣ）等の標準的プロトコルを通して、分散型データベースと通信し得る。最後に、クライアントモジュール１９９は、ワーカノード１０４上で実行され、データアップロード動作の間のデータ転送のコストを削減し得る。
【００２１】
システム１００は、公知の分散型データベース構成に関連付けられた多くの属性を含み得るが、システム１００は、基本的に、モジュール式データブロックのその概念化を通して、従来技術の分散型データベース構成と根本的に異なる。各モジュール式データブロックは、分散型データベースに関連付けられたデータのセグメントを保持する。コーディネータノード１０２は、モジュール式データブロックを定義し、種々のワーカノード１０４へのモジュール式データブロックの分散を管理する。各モジュール式データブロックは、５ギガバイト以下のサイズを有する。これは、データをワーカノードにパーティション化し、したがって、データベースパーティションサイズにハードな限界を課さない従来技術の分散型データベースと対照的である。その結果、従来技術のシステムは、約１００ギガバイト〜約１０，０００ギガバイトのサイズに及ぶ、分散型データベースパーティションを有する。さらに、従来技術では、単一ワーカノードは、分散型データベースからのデータの単一パーティションを保持する。対照的に、本発明では、各ワーカノード１０４は、パーティション化されたデータの２５個以上のモジュール式データブロックを保持する。
【００２２】
パーティション化は、異なる独立部分への論理データベースの分割である。各パーティションは、複数のノードにわたって拡散され得る。ローカルノードにおけるユーザは、ローカルトランザクションをそのパーティションに対して行なうことができる。開示されるモジュール式データブロックは、パーティションであるが、モジュール式データブロックという用語は、分散型データベースの従来技術の実装と比較して、サイズ区別を強調するために使用される。本構成は、リソース障害の場合、およびリソースがシステムに追加されるとき、利点を有する。これらの利点は、以下の共有に係る出願、すなわち、それぞれ、２０１２年１月６日に出願された、第１３／３４５，６２０号、第１３／３４５，６２１号、第１３／３４５，６２５号、および第１３／３４５，６２６号に記載され、その各々は、参照することにより本明細書に組み込まれる。
【００２３】
本発明の実施形態によると、ユーザは、分散型外部テーブルを定義することを許され、モジュール式データブロックは、ＰｏｓｔｇｒｅＳＱＬにおける１つの外部データソースに対応する。次いで、ユーザは、典型的なＳＱＬクエリを実行し、データベースは、これらのクエリをより小さいクエリにパーティション化し、これらのより小さいクエリをワーカノードにプッシュ配信し、それらを外部データソース上で実行し、結果をマージする。データベースはまた、最小／最大パーティションプルーニング、結合プルーニング、結合順選択等の最適化も適用する。
【００２４】
したがって、本発明の実施形態は、個々のパーティション（またはデータブロック）として外部データソースをモデル化する。パーティションに関するメタデータは、ノードのうちの１つ（例えば、コーディネータノードまたはマスタノード）の上で維持される。クエリ言語クエリは、各々が外部データソース上で作動する、より小さいクエリに分割される。
【００２５】
本実施形態の主要な利点は、分散型およびローカルクエリ計画と実行との間の明確な分離である。第１に、分散型クエリプロセッサは、クエリのための代替クエリプランを考慮し、異なるプランに関連付けられるネットワーク入力／出力（Ｉ／Ｏ）コストを比較する。例えば、クエリが４つのテーブルを結合する場合、クエリプランナは、結合順の６つの組み合わせを考慮し、各結合順のネットワークＩ／Ｏコストを決定し、最も効率的なクエリプランを構築する。次いで、分散型クエリプロセッサは、クエリ実行プランを決定し、クエリをより小さいサブクエリにパーティション化し、サブクエリをワーカノードに向かわせる。サブクエリ自体が典型的なＳＱＬクエリであり得るため、次いで、ワーカノードは、これらのサブクエリをローカルで計画して実行することができる。この段階で、ワーカノードは、データブロックインデックスおよび統計を考慮し、それらのディスクＩ／Ｏコストに従ってサブクエリを計画し、それらを効率的に実行することができる。
【００２６】
加えて、一実施形態では、本システムは、外部データソースがワーカノードにとってローカルであるという制約を課す。つまり、サブクエリは、外部データソースがそのノード上にすでに存在する場合、ワーカノードに送信されるのみである。結果として、サブクエリは、ローカルディスクから基礎的データを直接読み取り、いかなるデータもネットワークにわたってシャッフルされることを要求しない。
【００２７】
有利には、ユーザは、データベースにロードする前に、構造化または半構造化データをモデル化または解析する必要がない。ユーザは、単に、データを解析するための拡張機能を書き込む必要のみがある。したがって、データセット全体は、ＳＱＬ等のクエリ言語を通して即時にアクセス可能となる。
【００２８】
図２は、本発明のある実施形態に関連付けられる処理動作を図示する。半構造化形式のデータを伴うデータブロックが記憶される２００。データブロックは、ワーカノード１０４上に記憶される。構造化形式のデータブロックもまた、分散型データベースの一部分を形成し得る。半構造化形式のデータを伴うデータブロックについては、外部テーブル宣言との関連付けが行われる２０２。例えば、上記で議論されるタイプの外部テーブル宣言が使用され得る。
【００２９】
次いで、サブクエリによる分散型クエリプランが生成される２０４。つまり、受信されたクエリが、異なるワーカノード１０４上で実行されるサブクエリを有するクエリプランを形成するように処理される。例えば、テーブル結合を伴うサブクエリを用いるある場合において、データブロックは、分散型クエリプランを効率的に実行するために、ワーカノード１０４にわたって移動または再パーティション化される必要があり得る。例として、１つの大きいテーブルおよび１つの小さいテーブルを結合する、分散型クエリプランについては、小さいテーブルのデータブロックは、サブクエリを実行することに先立って、全てのワーカノード１０４にわたって複製され得る。同様に、分散型クエリプランが２つの大きいテーブルの間の結合を伴う場合、サブクエリ自体は、異なるテーブル次元（テーブル列）にブロックデータを再パーティション化する分散型実行基本要素を組み込み得る。
【００３０】
サブクエリが計画されると、次いで、それらは、選択されたワーカノードに向かわせられる２０６。次いで、サブクエリは、外部テーブル宣言を頼りにすることによって実行される２０８。例えば、第１のサブクエリが、第１のワーカノードに送信され、第１のワーカノードは、第１の半構造化データブロックからデータを読み取り、データを第１のテーブルの表形式に変換し、第１のテーブルの表形式データに対して第１のサブクエリを実行するために第１の外部テーブル宣言を使用する。同時に、第２のサブクエリが、第２のワーカノードに送信され、第２のワーカノードは、第２の半構造化データブロックからデータを読み取って変換し、第２のサブクエリを実行するために第２の外部テーブル宣言を使用する。
【００３１】
次いで、サブクエリ結果からの表形式データが、クエリ結果を生成するようにマージされる２１０。コーディネータノード１０２のクエリプロセッサ１２４は、この動作を実装し得る。
【００３２】
図３は、外部テーブル宣言およびコーディネータノードも有する、Ｈａｄｏｏｐ  Ｆｉｌｅ  Ｓｙｓｔｅｍ（ＨＤＦＳ）クラスタを図示する。本実施例では、マスタノード３００は、ＨＤＦＳマスタであり、ＨＤＦＳマスタは、ワーカノードにわたるブロックの割付を制御し、ブロック場所についてのメタデータを保ち、これらのデータブロックに対するＨａｄｏｏｐジョブを実行することに役立つ。ワーカノード１０４＿１、１０４＿２、および１０４＿３は、これらのデータブロックを記憶し、また、これらのブロックに対してＨａｄｏｏｐタスクを実行する。しかしながら、これらのタスクは、プログラミング言語で書かれる必要があり、並列プログラミングパラダイムＭａｐＲｅｄｕｃｅ（登録商標）に従うべきである。
【００３３】
分析をより容易にするために、クエリ言語を使用してデータを分析することができる。しかしながら、クエリ言語は、典型的には、組計算法のために設計され、したがって、半構造化データは、表形式で表される必要がある。この表現のために、外部テーブル宣言およびラッパが使用される。例えば、ワーカノード１０４＿１は、データブロック３０２および３０４を有する。半構造化データを伴うデータブロックの場合、関連外部テーブル宣言がある。ローカルメタデータ１２６は、外部テーブル宣言上で維持される。本実施例では、ブロック３０２のための外部テーブル宣言が、ライン３１２で示されている一方で、ブロック３０４のための外部テーブル宣言は、ライン３１４で示されている。
【００３４】
これらの宣言は、ワーカノードが個々のデータブロックに対するサブクエリを実行することを可能にする。システムの全体の上でクエリを実行するために、コーディネータノード１０２はまた、システム内のデータブロックのネットワーク場所を把握する必要もある。このメタデータは、連続的に、または規則的な間隔で、マスタノード３００から同期化されることができ、またはコーディネータノード１０２は、この情報を再構築するように、ワーカノード１０４＿１、１０４＿２、および１０４＿３をポーリングすることができる。コーディネータノード１０２がブロックメタデータを有すると、次いで、クエリプロセッサ１２４は、クエリをサブクエリにパーティション化し、これらのサブクエリをワーカノードに向かわせることができる。例えば、クエリプロセッサは、例示的クエリを、データブロック３０２および３０４に対して実行する必要がある２つのサブクエリにパーティション化し、実行するためにそれらをワーカノード１０４＿１に向かわせる。次いで、ワーカノード１０４＿１は、表形式データに対するこれらのサブクエリを実行するために外部テーブル宣言３１２および３１４を使用し、コーディネータノード１０２を通してこれらの結果を返す。
【００３５】
本実施例では、ブロックデータは、テキストのみのファイルとしてＨＤＦＳにすでにロードされており、これらのブロックのメタデータは、ＨＤＦＳマスタノードから同期化される。別の実施形態では、基礎的データは、バイナリファイルとしてＭｏｎｇｏＤＢシャードまたはチャンクの中で存続し、それらのメタデータは、ＭｏｎｇｏＤＢ  ｃｏｎｆｉｇサーバから同期化される。代替実施形態では、ブロックデータは、通常ログファイルを表し、これらのデータは、既存のシステムによって管理されない。次いで、ユーザは、外部テーブルを作成し、これらのファイルについてのメタデータをコーディネータノードにアップロードする。３つ全ての実施例では、基礎的データの形式が知られており、ブロック場所についてのメタデータがコーディネータノードにアップロードされる限り、コーディネータノードは、クエリ言語を通して基礎的データをアクセス可能にすることができる。
【００３６】
図４は、マスタノード３００およびコーディネータノード１０２に関連付けられたメタデータの一実施形態を図示する。マスタノード３００は、ブロック識別情報４００、およびブロックの関連場所４０２、４０４を維持する。場所４０２がノード１０４＿１に対応する一方で、場所４０４は、図３のノード１０４＿２に対応する。ブロック識別４０６は、ブロック７４に対応し、場所４０８は、この場合は、図３のノード１０４＿３上にある。ブロック識別４１０は、ブロック８０に対応し、場所４１２は、この場合は、図３のノード１０４＿上にある。
【００３７】
コーディネータノード１０４は、メタデータの種々の形態を保ってもよい。例えば、ライン４１４は、最小および最大タイムスタンプ値によるパーティション識別を図示する。ライン４１６は、一組の関連最小および最大タイムスタンプ値を伴う図３のブロック７１を図示する。これらのタイムスタンプ値は、ユーザによって手動で規定され得、外部ソースからフェッチされ得、またはブロックデータを問い合わせることによって自動的にコーディネータノード１０４によって収集され得る。図４の他のメタデータは、パーティションの場所に関する。例えば、ライン４１８は、ブロック７１がノード１（図３の１０４＿１）上にあることを示し、ライン４２０は、ブロック７１がノード２（図３の１０４＿２）上にもあることを示す。
【００３８】
図５は、ワーカノード１０４によって行われる処理を図示する。ワーカノード１０４は、ブロック７１に対応するローカルテーブルに対するＳＱＬサブクエリ５００を受信する、ローカルクエリプロセッサ５５０を含む。本実施例では、ＳＱＬサブクエリは、カテゴリ別にグループ化されるように、特定の日付後のウェブページビューを要求する。ローカルクエリプロセッサ５５０は、矢印５０１で示されるように、ローカル外部テーブルメタデータ１２６にアクセスする。本実施例では、ローカル外部テーブルメタデータ１２６は、テーブルタイプが外部テーブルであることを規定する、入力５０２を含む。関連外部テーブル宣言は、ライン５０４で規定される。外部テーブルオプションは、ライン５０６で規定される。外部テーブル場所は、ライン５０８で定義される。この場合、ファイルパスが、ページビューウェブサーバログを規定する。入力５１０は、外部テーブルの構造を定義する。次いで、関連メタデータが、矢印５１２で示されるように、ローカルクエリプロセッサ５５０に返される。
【００３９】
ローカルクエリプロセッサ５５０は、外部テーブル宣言および外部データラッパ５１４を使用して、サブクエリの最適なプランを生成する。外部データラッパ５１４は、ウェブサーバログ５１８内の半構造化データを表形式５１６に変換する。表形式は、サブクエリに応答して表形式データを提供する。本実施例では、ローカルクエリプロセッサ５５０は、ウェブサーバログのデータを反復するように順次テーブルスキャンを選択し、関数呼び出し５２０および５２２を用いて次のタプルを求める。次いで、外部データラッパ５１４は、タプル５２４および５２６を返す。ローカルクエリプロセッサ５５０は、表形式データをマージし、そのフィルタリングおよびグルーピング動作を適用し、サブクエリ結果５２８を提供する。
【００４０】
データ５１８が、その元の形式でノード１０４において処理されることに留意されたい。データ５１８は、統合され、次いで、後にコーディネータノードにおいて処理される必要がない。さらに、ＪＡＶＡ（登録商標）またはある他の言語へのＳＱＬの変換ではなく、ＳＱＬを使用して、データ５１８が処理されることに留意されたい。
【００４１】
ＭａｐＲｅｄｕｃｅ（登録商標）等の並列プログラミングパラダイムを使用してクエリを実行することとは対照的に、クエリをより小さいＳＱＬサブクエリにパーティション化するという本アプローチは、３つの明確な利点を有する。第１に、ＭａｐＲｅｄｕｃｅ（登録商標）等のパラダイムは、高レベルクエリプロセッサからデータブロック場所を抽出する。その結果、４つのテーブルを結合するクエリが、３つのＭａｐＲｅｄｕｃｅ（登録商標）結合ジョブを生成する一方で、ブロック場所を把握しているクエリプロセッサは、単一のステップでクエリを実行し得る。
【００４２】
サブクエリでＳＱＬを使用することの第２の利点は、該言語ですでに利用可能である豊富な組のユーザ定義された関数である。対照的に、クエリをＭａｐＲｅｄｕｃｅ（登録商標）ジョブに変換することはまた、数学演算、文字列操作、データおよび時間フォーマット、パターン合致等のための関数を実装することも必要とし得る。
【００４３】
最後に、ＳＱＬサブクエリは、ワーカノードレベルで顕著な性能利点をもたらす。これらのワーカノードにおける外部データラッパは、データブロックインデックスを利用し、データを処理するための代替クエリプランおよびプランコストをデータベースに知らせ、また、基礎的データについての統計を収集することもできる。これは、ＳＱＬサブクエリを実行するために必要とされるディスクＩ／Ｏを顕著に最小化する。対照的に、ＭａｐＲｅｄｕｃｅ（登録商標）プログラミングパラダイムは、主に、データセット全体を常に連続的に処理するように設計されている。
【００４４】
ＳＱＬがもたらす、これらの全ての利点の結果として、１つの可能性は、その半構造化形式からデータを変換し、それをＭａｐＲｅｄｕｃｅ（登録商標）ベースのシステムから分散型データベースシステムに規則的にロードすることを伴う。比較すると、ネイティブ半構造化データおよび関連外部テーブル宣言の開示される方法の使用は、データベーステーブルにデータをロードすること、およびネットワークにわたるデータ重複およびデータシャッフリングの関連費用を回避する。さらに、開示されるアプローチは、基礎的データの変化により容易に適応する。例えば、新しいフィールドが半構造化データに追加されるとき、それをデータベースに直接ロードすることは、この新しいフィールドの値を中間ファイルに放出するために変換スクリプトを必要とする。対照的に、外部データラッパは、ユーザが新しいフィールドを含むように外部テーブルのスキーマを変更すると、基礎的データからこのフィールドをすぐに取り出すことができる。
【００４５】
したがって、開示される技法は、半構造化データにアクセスするためにクエリ言語を使用することを可能にするために、外部テーブルを使用する。有利には、１つのシステムからデータをエクスポートし、それを別のシステムにインポートする必要がない。例えば、一実施形態では、ＭｏｎｇｏＤＢが、リアルタイム更新に使用され得る一方で、Ｈａｄｏｏｐは、バッチ分析ジョブに使用される。現在の技法を使用する場合、同一のデータセットに対するＭｏｎｇｏＤＢおよびＨａｄｏｏｐの組み合わせは、高価なオプションを必要とする。１つのオプションは、Ｈａｄｏｏｐジョブが理解することができる形式で、ＭｏｎｇｏＤＢからＨａｄｏｏｐへデータを複製することである。別のオプションは、ＭｏｎｇｏＤＢにおいてＨａｄｏｏｐの実行基本要素を実装することである。第１のオプションが、テラバイト単位のデータの移動を必要とする一方で、第２のオプションは、ＭｏｎｇｏＤＢ上で多くのコードを実装するためにプログラマを必要とする。
【００４６】
対照的に、開示される技術の場合、単純に、１つのシステムが理解する形式から、別のシステムが理解する形式へデータを変換するように、外部データラッパを書き込む必要がある。外部データラッパは、２つのシステムの間で同期化されるメタデータによって達成される。メタデータは、データがそれのものであるかのように、第２のシステムがデータにアクセスすることができるように、ネットワークにわたるブロック場所を含む。さらに、第２のシステムによって使用される実行基本要素は、計算が分散型データにプッシュ配信されるものである場合、ワーカノード上でアクセス可能である必要がある。
【００４７】
本発明の実施形態は、他のデータ記憶部からブロックメタデータをフェッチし、メタデータをコーディネータノードおよび／またはマスタノードにアップロードする、アプリケーションを含む。後に、半構造化データに対するＳＱＬクエリを実行することができる。本発明の技法はまた、テキストのみのファイルとともに使用され得る。
【００４８】
本発明の実施形態は、種々のコンピュータ実装動作を行なうために、その上にコンピュータコードを有する、コンピュータ読み取り可能なストレージ媒体を伴う、コンピュータストレージ製品に関する。媒体およびコンピュータコードは、本発明の目的のために、特別に設計および構築されたものであり得、またはコンピュータソフトウェア技術分野における当業者に周知かつ利用可能な種類であり得る。コンピュータ読み取り可能な媒体の実施例として、ハードディスク、フロッピー（登録商標）ディスク、および磁気テープ等の磁気媒体；ＣＤ−ＲＯＭ、ＤＶＤ、およびホログラフィックデバイス等の光学媒体；磁気光学媒体；ならびに特定用途向け集積回路（「ＡＳＩＣ」）、プログラマブル論理デバイス（「ＰＬＤ」）、ならびにＲＯＭおよびＲＡＭデバイス等のプログラムコードを記憶および実行するように特別に構成される、ハードウェアデバイスが挙げられるが、それらに限定されない。コンピュータコードの実施例として、コンパイラによって生成されるような機械コード、およびインタープリタを使用して、コンピュータによって実行される、高次コードを含むファイルが挙げられる。例えば、本発明の実施形態は、ＪＡＶＡ（登録商標）、Ｃ＋＋、または他のオブジェクト指向プログラミング言語および開発ツールを使用して、実装され得る。本発明の別の実施形態は、機械実行可能ソフトウェア命令の代わりに、またはそれと組み合わせて、有線回路内に実装され得る。
【００４９】
前述の説明は、説明目的のために、本発明の完全理解を提供するために具体的専門用語を使用した。しかしながら、具体的詳細が本発明を実践するために要求されないことが、当業者に明白となるであろう。したがって、本発明の具体的実施形態の前述の説明は、例証および説明目的のために提示される。それらは、包括的である、または本発明を開示される精密な形態に限定することを意図するものではない。明らかに、多くの修正および変形例が、前述の教示に照らして、可能性として考えられる。実施形態は、本発明の原理およびその実践的用途を最も良く説明するために選定および説明され、それによって、他の当業者が、想定される特定の使用に好適な種々の修正を伴って、本発明および種々の実施形態を最も良く利用することを可能にする。以下の請求項およびその均等物は、本発明の範囲を定義することが意図される。
【図１】
2015531937.tif 000003
【図２】
2015531937.tif 000004
【図３】
2015531937.tif 000005
【図４】
2015531937.tif 000006
【図５】
2015531937.tif 000007
【国際調査報告】
2015531937.tif 000008