(57)【要約】本発明の開示は、大規模データストレージに対する効率的な問い合わせ処理、より具体的には、結合操作に関する効率的な問い合わせ処理を可能にする、列ベースのデータ符号化構造の問い合わせに関する。最初に、リアルタイムでの非常に効率的で高速な問い合わせ応答をすでに可能にした、列ベース編成ならびに様々な圧縮およびデータパッキング技法に従ってデータを表した、コンパクトな構造が受け取られる。コンパクトな列指向の構造によって可能にされたすでに高速な問い合わせに加えて、メモリ内での問い合わせ処理のためのスケーラブルで高速なアルゴリズムが提供され、このアルゴリズムは、結合操作で使用するためのやはり列指向の補助的なデータ構造を構成し、さらに、コンパクトなデータ構造の列指向の特性ばかりでなく、メモリ内データ処理およびアクセスの特性も利用する。
2012504824.tif 000002
【特許請求の範囲】
【請求項１】
データを処理するための方法であって、
少なくとも１つのデータストア内のデータに対する少なくとも１つの結合操作に関する問い合わせに応答して、前記少なくとも１つのデータストア内の前記データの異なる列に対応する整数符号化および圧縮を施された値系列として、データのサブセットを受け取るステップ５１０と、
前記少なくとも１つの結合操作に関わる列に対応する非デフォルト値をローカルキャッシュが含むかどうかを決定することを含む、前記少なくとも１つの結合操作の少なくとも１つの結果セットを決定するステップ５２０と、
前記少なくとも１つの結合操作に関わる列に対応する非デフォルト値を前記ローカルキャッシュが含む場合、前記少なくとも１つの結果セットを決定するときに、前記非デフォルト値を代わりに使用するステップ５３０と
を備えることを特徴とする方法。
【請求項２】
前記少なくとも１つの結果セットの少なくとも１つの結果を、第２の問い合わせに関連する代用のために、前記ローカルキャッシュ内に保存するステップ５４０
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記保存するステップ５４０は、メモリ内への前記少なくとも１つの結果のロックレス保存を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記決定するステップ５２０は、前記問い合わせによって定義される前記操作を、複数のプロセッサと、前記系列から分割した対応する数のセグメントとを用いて並列化するステップを含み、各セグメントは、少なくとも１つの異なるプロセッサによって処理されることを特徴とする請求項１に記載の方法。
【請求項５】
問い合わせ処理を開始する前に、前記ローカルキャッシュにデフォルト値を設定するステップ
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記設定するステップは、問い合わせ処理を開始する前に、前記ローカルキャッシュにマイナス１（「−１」）の値を設定するステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記代わりに使用するステップ５３０は、前記少なくとも１つの結果セットを決定するときに、前記値系列内の対応する列をスキャンする代わりに、前記非デフォルト値を代わりに使用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記少なくとも１つの結合操作に関わる列に対応するデフォルト値を前記ローカルキャッシュが含む場合、前記少なくとも１つの結果セットの少なくとも１つの結果を取り出すために、前記値系列内の前記対応する列を処理するステップ６６０
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項９】
前記受け取るステップ５１０は、データの前記サブセットをリレーショナルデータベースから受け取るステップを含み、前記データの前記異なる列は、前記リレーショナルデータベースの列に対応することを特徴とする請求項１に記載の方法。
【請求項１０】
請求項１に記載の方法を実行するためのコンピューター実行可能命令を備えることを特徴とするコンピューター可読媒体。
【請求項１１】
問い合わせ処理のための方法であって、
問い合わせに応答して、１組のテーブルを表す少なくとも１つのデータストア内のデータの異なる列に対応する整数符号化と圧縮を施された値系列として取り出された、コンパクト化されたデータのセグメントによって共用されるレイジーキャッシュを生成するステップ６１０と、
少なくとも１つのデータストア内のデータに対する少なくとも１つの結合操作に関する問い合わせに応答して、前記少なくとも１つのデータストアに対する少なくとも１つの結合操作に関する前記レイジーキャッシュを参照して前記問い合わせを処理するステップ６２０とを含み、
前記処理するステップ６２０は、前記１組のテーブルの少なくとも１つのテーブルから少なくとも１つのデータ値を、前記問い合わせ処理の存続期間にわたって、前記少なくとも１つのデータ値の潜在的な再利用のための所定のアルゴリズムに従って、前記レイジーキャッシュに追加するステップを含む
ことを特徴とする方法。
【請求項１２】
前記生成するステップ６１０は、データの前記異なる列に対応する前記値系列に対応する値を有する少なくとも１つのベクトルに従って、前記レイジーキャッシュを編成するステップを含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記処理するステップ６２０は、前記値系列をスキャンするステップをさらに含み、前記処理するステップは、前記１組のテーブルの少なくとも１つのテーブルから少なくとも１つのデータ値を、前記問い合わせ処理の存続期間にわたって、前記少なくとも１つのデータ値の潜在的な再利用のための所定のアルゴリズムに従って、前記レイジーキャッシュに追加するステップを含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記処理するステップ６２０は、前記値系列からの外部キーデータＩＤ（識別情報）を前記レイジーキャッシュに対するインデックスとして使用するステップを含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記処理するステップ６２０は、外部キーデータＩＤに対応する前記レイジーキャッシュの値がデフォルト値であるかどうかを決定するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記レイジーキャッシュの前記値が前記デフォルト値である場合、前記値系列に対する前記少なくとも１つの結合操作を実行することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記レイジーキャッシュの前記値が前記デフォルト値でない場合、前記値系列に対する前記少なくとも１つの結合操作をスキップし、前記外部キーデータＩＤに対応する前記レイジーキャッシュの前記値を代わりに使用することを特徴とする請求項１４に記載の方法。
【請求項１８】
前記処理するステップ６２０は、結果セットを受け取るステップを含み、前記結果セットの少なくとも１つの結果を、整合性のためにロックを必要としないコアプロセッサデータタイプの原子操作として前記レイジーキャッシュに書き込むステップをさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１９】
請求項に記載の方法を実行するための手段を含むことを特徴とするコンピューティングデバイス。
【請求項２０】
データを処理するためのデバイスであって、
前記データの異なる列に対応する整数符号化と圧縮を施された値系列として受け取ったデータのサブセットを保存し、かつ前記異なる列に対応する値のベクトルを保存するための、高速内部メモリストレージ２３０と、
前記データの前記サブセットに対する問い合わせを処理し、与えられた列について前記ベクトル内にデフォルト値が見出された場合、データの前記サブセットに対する前記問い合わせに関わる少なくとも１つの結合操作をスキップし、代わりに、前記少なくとも１つの結合操作のために前記ベクトルの値を代わりに使用する、少なくとも１つのクエリプロセッサ２５０と
を備えることを特徴とするデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の開示は一般に、大量のデータに対する問い合わせに関連する効率的な列ベースの結合（ｊｏｉｎ）操作に関する。
【背景技術】
【０００２】
従来のデータ問い合わせシステムに関する背景について例示すると、サーバーコンピューターが、長期間にわたって、データの多数の記録またはトランザクションを収集している場合など、大量のデータが、データベースに保存されている場合、時として、他のコンピューターが、そのデータまたはそのデータの目標とするサブセットにアクセスすることを望むことがある。そのような場合、他のコンピューターは、１つまたは複数のクエリオペレータ（ｑｕｅｒｙ  ｏｐｅｒａｔｏｒ）を介し、望むデータを求めて問い合わせを行うことができる。この点に関して、歴史的には、リレーショナルデータベースが、この目的のために進化し、そのような大量のデータを収集するために使用されており、問い合わせを行うクライアントの代わりに、リレーショナルデータベースまたは１組の分散データベースからデータを検索するための、データベース管理ソフトウェアに命令する、様々な問い合わせ言語が発達した。
【０００３】
従来、リレーショナルデータベースは、フィールドを有する、レコードに対応する、行に従って編成されている。例えば、第１の行は、第１の行のレコードを定義する、列に対応するそのフィールドのための様々な情報（名前１、年齢１、住所１、性別１など）を含むことができ、第２の行は、第２の行のフィールドのための様々な異なる情報（名前２、年齢２、住所２、性別２など）を含むことができる。しかし、従来は、膨大な量のデータに対する問い合わせ、またはクライアントによるローカルな問い合わせもしくはローカルなビジネス情報のための膨大な量のデータの検索は、それらがリアルタイムまたは準リアルタイムの要件を満たすことができないという点で限界があった。特に、クライアントがサーバーの最新データのローカルコピーを有することを望む場合、ネットワーク帯域幅が制限され、クライアントのキャッシュストレージが制限されていると、サーバーからのそのような大量のデータの転送は、現在のところ多くのアプリケーションにとって非実用的である。
【０００４】
さらなる背景について例示すると、アーキテクチャの一部としてリレーショナルデータベースを用いる場合、異なる行を異なるレコードとして概念化することが便利であるため、これまでのところ、データセットのサイズを縮小するための技法は、リレーショナルデータベースを編成する方法の性質上、行に焦点を合わせたものであった。言い換えると、１つの行上にレコードのすべてのフィールドをまとめておくことによって、行情報は、各レコードを維持し、集約データのサイズを縮小するための従来の技法は、符号化自体の一部として、フィールドをまとめていた。
【０００５】
したがって、データサイズ縮小と問い合わせ処理速度の同時の向上を達成するソリューションを提供することが望ましい。大量のデータに対する非常に効率的な問い合わせをもたらす方法で圧縮を適用することに加えて、さらに、同じまたは同様の問い合わせが実行されることが予想できる問い合わせ環境において、改良されたデータ問い合わせ技法を提供することが望ましい。この点に関して、様々なデータ集約的アプリケーションによって多くの問い合わせが実行される環境において、同じまたは同様のデータまたはデータのサブセットが、１組の別個の問い合わせに関わりをもつ場合、結果を再利用しようと試みることが望ましい。
【０００６】
より具体的には、問い合わせ処理において、高い割合で、問い合わせは、複数のテーブルからの結果セットを組み合わせるという目標を達成するために、複数のテーブルを結合する必要性を含む。例えば、販売データが販売テーブルに保存され、製品詳細は製品テーブルに保存されている場合、アプリケーションは、製品カテゴリによって分類された販売を報告することを望むことがある。ＳＱＬでは、これは、「ｓｅｌｅｃｔ  ｆｒｏｍ」構文として、
Ｓｅｌｅｃｔ  ｐｒｏｄｕｃｔ＿ｃａｔｅｇｏｒｙ，  ｓｕｍ（ａｍｏｕｎｔ）  ｆｒｏｍ  ｓａｌｅｓ  ｉｎｎｅｒ  ｊｏｉｎ  ｐｒｏｄｕｃｔ  ｏｎ  ｓａｌｅｓ．ｓｋｕ＝ｐｒｏｄｕｃｔ．ｓｋｕ
のように表現することができる。
【０００７】
上記の例の場合、結合操作を満たす従来の方法は、ハッシュ結合（ｈａｓｈ  ｊｏｉｎ）操作、マージ結合（ｍｅｒｇｅ  ｊｏｉｎ）操作、およびネストされたループ結合（ｎｅｓｔｅｄ  ｌｏｏｐ  ｊｏｉｎ）操作を含む。ハッシュ結合は、ＳＫＵ（在庫管理単位（ｓｔｏｃｋ  ｋｅｅｐｉｎｇ  ｕｎｉｔ））からｐｒｏｄｕｃｔ＿ｃａｔｅｇｏｒｙによって、製品テーブルに関してハッシュ構造を構築し、このハッシュ構造を調べて、販売テーブルのすべてのＳＫＵを検索する。マージ結合は、販売レコードと製品テーブルの両方をＳＫＵによってソートし、その後、２つのセットを同期を取りながらスキャンする。ネステッドループ結合は、販売テーブル内の各行について、製品テーブルをスキャンし、すなわち、ネステッドループ結合は、販売テーブル内の行毎に、製品上で問い合わせを実行する。しかし、これらの従来の方法は、例えばネステッドループ結合などは、特に効率的なわけでもなく、またはプロセスの前工程において著しいオーバヘッドを導入し、それは大量のデータに対するリアルタイム問い合わせ要件にとって望ましくないことがある。したがって、データ集約的アプリケーション環境における大量のデータに対する問い合わせのための高速で拡張性のあるアルゴリズムが望まれる。
【０００８】
今日のリレーショナルデータベースおよび対応する問い合わせ技法についての上述の難点は、従来システムの問題のいくつかの概要を提供することを意図したものにすぎず、網羅的であることは意図していない。従来システムの他の問題、およびそれに対応する本明細書で説明される様々な非限定的な実施形態の利益は、以下の説明を検討することでさらに明らかとなろう。
【発明の概要】
【課題を解決するための手段】
【０００９】
以下のより詳細な説明および添付の図面に記載の例示的で非限定的な実施形態の様々な態様についての基本的および概略的な理解を可能にする助けとして、本明細書では、簡略化された要約が提供される。しかし、この要約は、広範または網羅的な概要としては意図されていない。そうではなく、この要約の唯一の目的は、以下に記載の様々な実施形態についてのより詳細な説明の導入部として、簡略化された形式で、いくつかの例示的で非限定的な実施形態に関するいくつかの概念を提示することである。
【００１０】
大規模データストレージに対する効率的な問い合わせ処理、より具体的には、結合操作に関する効率的な問い合わせ処理を可能にする、列ベースのデータ符号化構造の問い合わせの実施形態が説明される。最初に、リアルタイムでの非常に効率的で高速な問い合わせ応答をすでに可能にした、列ベース編成ならびに様々な圧縮およびデータパッキング技法に従ってデータを表した、コンパクトな構造が受け取られる。コンパクトな列指向の構造によって可能にされたすでに高速な問い合わせに加えて、メモリ内での問い合わせ処理のための拡張性のあるで高速なアルゴリズムが提供され、このアルゴリズムは、結合操作で使用するための補助的なデータ構造を構成し、さらに、コンパクトなデータ構造の列指向の特性ばかりでなく、メモリ内データ処理およびアクセスの特性も利用する。
【００１１】
上記および他の実施形態が、以下でさらに詳細に説明される。
【図面の簡単な説明】
【００１２】
様々な非限定的な実施形態が、添付の図面を参照してさらに説明される。
【００１３】
【図１】一実施形態によるキャッシュを形成するための一般的なプロセスのフロー図である。
【図２】問い合わせの処理に関連して使用される補助キャッシュ２４０の形成を説明するブロック図である。
【図３】列編成を横断する多数の行を処理する負荷を分担するために、問い合わせに関連して受け取った列データのメモリ内クライアント側処理の作業を複数のコア間に分割できることを示す図である。
【図４】問い合わせ処理中に列指向のコンパクト化されたデータ構造のセグメントにわたって補助キャッシュを使用できることを示すブロック図である。
【図５】本明細書で説明されるような、レイジーキャッシュ（ｌａｚｙ  ｃａｃｈｅ）を使用して、問い合わせのいくつかの結合操作をスキップする技法の適用を示す第１のフロー図である。
【図６】本明細書で説明されるような、レイジーキャッシュを使用して、問い合わせのいくつかの結合操作をスキップする技法の適用を示す第２のフロー図である。
【図７】列ベースの符号化技法と、符号化データに対する問い合わせのメモリ内クライアントサイド処理とを示す概略的なブロック図である。
【図８】列ベースの符号化技法を利用する符号化装置の例示的で非限定的な実施を示すブロック図である。
【図９】列ベースの符号化を大規模データに適用するための例示的で非限定的なプロセスを説明するフロー図である。
【図１０】レコードがそれぞれのフィールドに分割され、その後、同じタイプのフィールドが直列化されてベクトルを形成した、原データの列ベース表現を示す図である。
【図１１】レコードデータの列化（ｃｏｌｕｍｎｉｚａｔｉｏｎ）を例示する非限定的なブロック図である。
【図１２】ディクショナリ符号化の概念を示す非限定的なブロック図である。
【図１３】値符号化の概念を示す非限定的なブロック図である。
【図１４】ハイブリッド圧縮技法の一態様において適用されるビットパッキングの概念を示す非限定的なブロック図である。
【図１５】ハイブリッド圧縮技法の別の態様において適用されるランレングス符号化の概念を示す非限定的なブロック図である。
【図１６】列ベースの符号化技法を利用する符号化装置の例示的で非限定的な実施を示すブロック図である。
【図１７】一実施による、列ベースの符号化を大規模データに適用するための例示的で非限定的なプロセスを示すフロー図である。
【図１８】代替圧縮技法を適用するための節約アルゴリズムの閾値の任意選択的な適用を含む、貪欲なランレングス符号化圧縮アルゴリズムを実行する方法の例を示す図である。
【図１９】代替圧縮技法を適用するための節約アルゴリズムの閾値の任意選択的な適用を含む、貪欲なランレングス符号化圧縮アルゴリズムを実行する方法の例を示す図である。
【図２０】貪欲なランレングス符号化圧縮アルゴリズムをさらに示すブロック図である。
【図２１】ハイブリッドランレングス符号化およびビットパッキング圧縮アルゴリズムを示すブロック図である。
【図２２】総ビット節約分析に基づいて適応的に異なるタイプの圧縮を提供するハイブリッド圧縮技法の適用を示すフロー図である。
【図２３】本発明の開示の様々な実施形態による、データの全体サイズを縮小する列ベースの符号化のサンプル性能を示すブロック図である。
【図２４】純粋領域から不純領域への移行および不純領域から純粋領域への移行に関して、列ベースの符号化データに適用できるバケット化（ｂｕｃｋｅｔｉｚａｔｉｏｎ）プロセスを示す図である。
【図２５】一実施形態による、列のバケット化に関する不純性レベルを示す図である。
【図２６】クエリ／スキャンオペレータの、現在のクエリ／スキャンに関連する列内に存在する異なるタイプのバケットに対応するサブオペレータへの効率的な分割を示す図である。
【図２７】結果の純粋バケットがデータの行の５０％を越える場合の、列ベースの符号化の能力を示す図である。
【図２８】標準化された方法でデータに対する問い合わせを指定するための問い合わせ言語のための例示的で非限定的なクエリ構築ブロックを示す図である。
【図２９】ネットワークを介して利用可能な大規模データに対する消費クライアントデバイスによって要求されたサンプルクエリの代表的な処理を示す図である。
【図３０】様々な実施形態による、列に従ってデータを符号化するためのプロセスを示すフロー図である。
【図３１】１つまたは複数の実施形態による、整数系列をビットパッキングするためのプロセスを示すフロー図である。
【図３２】列ベースのデータ表現に対して問い合わせを行うためのプロセスを説明するフロー図である。
【図３３】本明細書で説明された様々な実施形態を実施できる、例示的で非限定的なネットワーク環境を表すブロック図である。
【図３４】本明細書で説明された様々な実施形態の１つまたは複数の態様を実施できる、例示的で非限定的なコンピューティングシステムまたは動作環境を表すブロック図である。
【発明を実施するための形態】
【００１４】
概要
これ以降のロードマップについて一言すると、最初に、様々な実施形態の概要が説明され、その後、例示的で非限定的な任意選択的な実施が、補足的な背景および理解のために、より詳細に説明される。その後、ハイブリッド圧縮技法を介してランレングス符号化（ｒｕｎ  ｌｅｎｇｔｈ  ｅｎｃｏｄｉｎｇ）とビットパッキング（ｂｉｔ  ｐａｃｋｉｎｇ）の性能利益を適応的にトレードオフする実施形態を含む、大量のデータをパッキングするための列ベースの符号化に関するいくつかの補足的な背景が説明される。最後に、様々な実施形態を適用することができる、いくつかの代表的なコンピューティング環境およびデバイスが説明される。
【００１５】
背景技術において説明したように、なによりも、従来システムは、現在の圧縮技法の限界、ネットワークを介した送信の帯域幅の限界、およびローカルキャッシュメモリの限界のせいで、膨大な量のデータをサーバーまたは「クラウド」内の他のデータストアからメモリ内に非常に高速に読み込むという課題に適切に対処していない。この問題は、リアルタイム要件を有する様々な異なるデータ集約的アプリケーションによって多くの問い合わせが実行される場合に深刻さを増す。
【００１６】
したがって、様々な非限定的な実施形態では、データを同時にコンパクト化および編成して、データに対する後のスキャン／検索／問い合わせ操作を著しく効率的にする、大量のデータの効率的な列指向の符号化に加えて、ある技法が適用される。様々な実施形態では、問い合わせが行われたときに、将来の問い合わせに情報提供するために、補助的な列指向のデータ構造が、ローカルキャッシュメモリ内に生成され、初めに複雑なデータ構造を生成するために著しいオーバヘッドを導入することなく、時間が経つにつれて問い合わせをより高速にする。
【００１７】
一実施形態では、最初に、オーバヘッドが無視できる程しか生じないステップによって、「レイジー」キャッシュが形成される。次に、どこでミスが発生しても、問い合わせの最中にキャッシュにデータが投入され、その後、結果セットの導出に関連して、キャッシュが使用される。
【００１８】
補助的なデータ構造およびコンパクト化されたデータ構造はともに、データの列ベースのビューに従って編成されるので、コンパクト化されたデータ構造の列に適用される結合操作において、妥当な場合には、ローカルキャッシュメモリ内に表された結果で迅速に代用することができるため、データの再利用が効率的に達成され、与えられた問い合わせに関わる結果の全体的により高速でより効率的な結合をもたらす。
【００１９】
補助キャッシュを用いた列ベースのデータのデータ結合
概要において言及したように、列指向の符号化および圧縮を大量のデータに適用して、データをコンパクト化すると同時に、データに対する後のスキャン／検索／問い合わせ操作を著しく効率的にするようにデータを編成することができる。様々な実施形態では、そのような列指向の符号化およびスキャン技法に加えて、データのコンパクトな符号化の列指向特性ばかりでなく、メモリ内特性も利用する、スケーラブルで高速なアルゴリズムが提供される。
【００２０】
一実施形態では、図１に示されるように、最初に、コンパクトな列指向のデータ構造１００が受け取られ、データ構造１００上では、次のセクションにおいて詳細に説明されるスキャン技法に従って、問い合わせを処理することができる。一般に、データ集約的環境において問い合わせ処理をスピードアップするため、１１０において、オーバヘッドが無視できる程しか伴わないステップによって、「レイジー」キャッシュが形成される。一実施形態では、レイジーキャッシュは、開始時に、初期化されていない、すなわち未初期化のベクトルとして構成される。次に１２０において、ミスが発生した場合、問い合わせの最中にキャッシュにデータが投入される。次に１３０において、結果セット１４０の導出に関連して、キャッシュが使用される。
【００２１】
この点に関して、従来のシステムに含まれる高コストの前工程のソートまたはハッシュ操作が回避されるので、大量のデータに対する問い合わせに含まれる結合操作の実行は、本明細書で提示される様々な実施形態において効率的に行われる。
【００２２】
コンパクト化された列指向の構造を使用するシステムが、全体として、図２に示されている。列指向のコンパクト化された構造２３５が、問い合わせを満たすために、大規模データストア２００から取り出される。列ベースの符号化器２１０は、データ消費器２２０のコンポーネント２５０による高速復号およびスキャンのために、伝送ネットワーク２１５を介してメモリ２３０において受け取られる、ストレージ２００からのデータを圧縮する。列指向のコンパクト化された構造２３５は、以下でより詳細に説明される技法に従って符号化および圧縮された列値に対応する、１組の圧縮された列系列である。
【００２３】
一実施形態では、上述の技法に従って圧縮された列が、消費クライアントシステム上のメモリ内にロードされた場合、データは、図３に示されるように、列Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６の各々を横断するように区分化されて、セグメント３００、３０２、３０４、３０６などを形成する。この点に関して、各セグメントは、数億またはそれ以上の行を含むことができるので、並列化が、例えば、問い合わせに従ってデータを処理またはスキャンする速度を向上させる。各セグメントは別々に処理されるが、各セグメントの結果は集約されて、完全な１組の結果を形成する。
【００２４】
図４に示されるように、最初に、レイジーキャッシュ４２０が、高速な問い合わせが実行されるデータ消費器４００のメモリ４３０内に形成される。一実施形態では、示されるように、レイジーキャッシュ４２０は、コンパクト化された列指向のデータ構造の異なるセグメント４１０、４１２、４１４、．．．、４１８によって共用される。セグメントは、以下で説明されるように、マルチプロセッサ基盤上のスキャンに関連して使用される並列化の単位でもある。したがって、この点に関して、様々な実施形態によれば、補助キャッシュ４２０は、以下でより詳細に説明される結合操作に関する処理ショートカットを生成するために、復号器および問い合わせプロセッサ４４０によって使用することができ、セグメント４１０、４１２、４１４、．．．、４１８にわたって使用することができる。
【００２５】
一実施形態では、キャッシュ４２０は、−１で初期化され（初期化されず）、これは低コストの操作である。その後、アプリケーションが製品カテゴリによって分類された販売を報告することを望むことがある「背景技術」で与えられた例の状況では、問い合わせの存続期間にわたって、キャッシュ４２０は、必要な場合だけであるが、製品テーブルからマッチしたデータＩＤをデータ投入されるようになる。例えば、販売テーブルが、例えば顧客テーブルなど、別のテーブルによって大幅にフィルタリングされた場合、ベクトル内の行の多くは、未初期化のままである。これは、クロステーブルフィルタリングの利益（ｃｒｏｓｓ−ｔａｂｌｅ  ｆｉｌｔｅｒｉｎｇ  ｂｅｎｅｆｉｔ）を達成するので、従来のソリューションにまさる性能利益を表す。
【００２６】
レイジーキャッシュへのデータ投入に関して、スキャンが行われる場合、例えば、本明細書で使用される例におけるｓａｌｅｓ．ｓｋｕなどの、外部キーデータＩＤが、レイジーキャッシュ４２０のレイジースキャンベクトルに対するインデックスとして使用される。値が−１である場合、セグメント４１０、４１２、４１４、．．．、４１８の適切な列を用いて、実際の結合が行われる。したがって、オンザフライで関係の走査が発生し、例えば、今の例におけるｐｒｏｄｕｃｔ＿ｃａｔｅｇｏｒｙなど、対象とする列のデータＩＤが取り出される。他方、値が−１でない場合、それは、ｊｏｉｎ句をスキップして、代わりに、その値を利用できることを意味し、大幅な性能上の節約をもたらす。別の利益は、メモリ４３０のベクトルへの書き込みは、コアプロセッサデータタイプの原子操作であるので、従来のデータベースにおけるように、ロッキングを実行する必要がないことである。−１の値が変更される前に、ｊｏｉｎが２回解決されることがあるが、これは一般に、稀なケースである。したがって、レイジーキャッシュからの値で、実際の列値を代用させることができる。時間が経つにつれて、より多くの問い合わせがデータ消費器４００によって実行されるので、キャッシュ４２０の値は増加する。
【００２７】
図５は、本明細書で説明されるような、レイジーキャッシュを使用して、問い合わせのいくつかの結合操作をスキップする技法の適用を示すフロー図である。コンパクトな列指向のデータ構造５００を受け取った後、５１０において、データのサブセットが、データストア内のデータの異なる列に対応する整数符号化と圧縮を施された値系列として受け取られる。５２０において、結合操作の結果セットは、結合操作に関わる列に対応する任意の非デフォルト値をローカルキャッシュが含むかどうかを決定することによって決定される。５３０において、結合操作に関わる列に対応する非デフォルト値をローカルキャッシュが含む場合、結果セットを決定するときに、任意の非デフォルト値が代わりに使用される。５４０において、結果セットの結果が、さらなる問い合わせ、または同じ問い合わせの他の結合操作における代用のために、ローカルキャッシュ内に保存される。
【００２８】
図６は、本明細書で説明されるような、レイジーキャッシュを使用して、問い合わせのいくつかの結合操作をスキップする技法の適用を示す別のフロー図である。コンパクトな列指向のデータ構造６００を受け取った後、６１０において、レイジーキャッシュが生成され、レイジーキャッシュは、問い合わせに応答して、データの異なる列に対応する整数符号化と圧縮を施された値系列として取り出された、コンパクト化されたデータのセグメントによって共用される。６２０において、問い合わせに応答して、結合操作を含む問い合わせが、レイジーキャッシュを参照して処理される。
【００２９】
６３０において、コンパクト化された値系列がスキャンされ、問い合わせ処理の存続期間にわたって、データ値の再利用のための所定のアルゴリズムに従って、テーブルからレイジーキャッシュにデータ値が投入される。一実施形態では、所定のアルゴリズムは、６４０において、外部キーデータＩＤに対応するレイジーキャッシュの値が、デフォルト値（例えば−１）であるかどうかを決定することを含む。デフォルト値でない場合、６５０において、レイジーキャッシュ内のデータ値を使用することができ、すなわち、レイジーキャッシュ内において、−１の値は、潜在的な再利用のために置き換えられていた。デフォルト値である場合、６６０において、値系列に対する実際の結合を実行することができる。
【００３０】
本明細書で使用される「レイジー」という語は、多くの先行作業を前もって実行する必要がなく、代わりに、キャッシュには時間が経つにつれてデータが投入され、必要であれば、キャッシュは与えられたシステムによって処理された問い合わせと整合性をもつという概念を指す。内部メモリキャッシュの非限定的な利点は、キャッシュがロックレス（ｌｏｃｋｌｅｓｓ）であることであり、加えて、キャッシュは、セグメント（並列化の単位、図３〜図４参照）にわたって共用することができる。したがって、問い合わせを処理する様々なアプリケーションによってデータ投入できる、クロスディメンジョンフィルタードキャッシュ（ｃｒｏｓｓ  ｄｉｍｅｎｓｉｏｎ  ｆｉｌｔｅｒｅｄ  ｃａｃｈｅ）が提供される。結果として、例えば、結合操作を含むフィルタリングされた問い合わせの、速度およびスケーラビィティが、１桁だけ増加する。
【００３１】
列ベースのデータ符号化に関する補足的な背景
概要において言及したように、様々な実施形態では、列指向の符号化および圧縮を大量のデータに適用して、データをコンパクト化すると同時に、データに対する後のスキャン／検索／問い合わせ操作を著しく効率的にするようにデータを編成することができる。様々な実施形態では、符号化および圧縮を開始するにあたり、最初に原データが、列化されたデータのストリームとして再編成され、圧縮およびスキャンプロセスが、レイジーキャッシュを取り巻く補足的な背景のための、以下で提示される様々な非限定的な例を参照して説明される。
【００３２】
例示的で非限定的な一実施形態では、（例えば、すべての名字を１つの系列に、またはすべての発注書注文番号を別の系列にするなど、例えば、データの列のフィールドを直列化して）原データを、１つの値系列が各列に対応する、１組の値系列に列化した後、データは、ディクショナリ符号化（ｄｉｃｔｉｏｎａｒｙ  ｅｎｃｏｄｉｎｇ）、値符号化（ｖａｌｕｅ  ｅｎｃｏｄｉｎｇ）、または後先いずれかのディクショナリ符号化と値符号化の両方によって「整数化」されて、一律に表された列毎の整数系列を形成する。この整数化ステージは、一律に表された列ベクトルをもたらし、テキスト文字列などの長いフィールドがデータに記録される場合は特に、それ自体で著しい節約を達成することができる。次に、すべての列を検査して、圧縮ステージは反復的に、列ベクトルの組全体において最も大きな全体的サイズ節約をもたらすいずれかの列のランにランレングス符号化を適用する。
【００３３】
言及したように、パッキング技法は、列ベースであり、優れた圧縮を提供するばかりでなく、コンパクト化された整数列ベクトルがクライアントサイドに送信されると、圧縮技法それ自体が、データの迅速な処理の助けとなる。
【００３４】
様々な非限定的な実施形態では、図７に示されるように、大規模データストレージ７００をコンパクト化し、しかもデータに対する結果のスキャン／検索／問い合わせ操作を著しく効率的にするための、列ベースの符号化器／圧縮器７１０が提供される。データ処理ゾーンＣのデータ消費デバイス７２０による問い合わせに応答して、圧縮器７１０は、データ伝送ゾーンＢの伝送ネットワーク７１５を介して、問い合わせに関連する圧縮された列を送信する。データは、メモリストレージ７３０に送信され、したがって、関連する列の復元は、データ処理ゾーンＣの復号器およびクエリプロセッサ７４０によって、非常に高速に実行することができる。この点に関して、効率的な処理の付加的なレイヤーのために、問い合わせに関連する復元された列によって表される行に、バケットウォーキング（ｂｕｃｋｅｔ  ｗａｌｋｉｎｇ）が適用される。反復的な動作が一緒に実行されるように、バケットウォーキングの最中には、行の類似性が利用される。以下でより詳細に説明されるように、本発明の技法が、１９６Ｇｂ  ＲＡＭを有する標準的または市販のサーバーを用いて、大量のウェブトラフィックデータまたはトランザクションデータなどの、現実世界のサンプルデータに適用される場合、従来システムの能力と比べて天文学的に飛躍した毎秒約１．５テラバイトのデータで、ハードウェアコストを著しく削減させて、サーバーデータの問い合わせ／スキャンが達成される。
【００３５】
圧縮できる特定のタイプのデータは、いずれか特定のタイプのデータに決して限定されることはなく、膨大なデータの大規模スキャンに依存するシナリオの数も、同様に限定されることはないが、リアルタイムビジネス情報アプリケーションにおいて、これらの技法をビジネスデータまたは記録に適用する商業的な重要性は、疑いようもない。リアルタイム報告および動向識別は、圧縮技法によって達成される問い合わせ処理速度のとてつもない進歩によって、まったく新しいレベルに導かれる。
【００３６】
符号化器の一実施形態が全体として、図８に示されており、８００において、原データが受け取られ、またはストレージから読み取られ、その時点で、８１０において、符号化装置および／または符号化ソフトウェア８５０が、データを編成する。８２０において、列ストリームが、一律のベクトル表現に変換される。例えば、整数符号化を適用して、名前または場所などの個々のエントリを整数にマッピングすることができる。そのような整数符号化技法は、ディクショナリ符号化技法とすることができ、ディクショナリ符号化技法は、２倍〜１０倍だけデータを縮小することができる。追加的または代替的に、値符号化がさらに、１倍〜２倍のサイズ縮小を提供することができる。これによって、８２０において、列毎に整数のベクトルが残される。そのような性能の向上は、コンパクト化されるデータに影響され、したがって、そのようなサイズ縮小範囲は、異なるステップの相対的な性能についてのおおよその目安を与えるための非限定的な推定として与えられているにすぎない。
【００３７】
その後、８３０において、符号化された一律の列ベクトルをさらにコンパクト化することができる。一実施形態では、すべての列にわたって最も頻出する値または値の発生を決定するランレングス符号化技法が適用され、その場合、その値についてのランレングスが確定され、ランレングス符号化の利益が限界的になるポイント、例えば、列内で繰り返し出現する整数値がたかだか６４回しか発生しなくなるポイントに至るまで、処理が反復される。
【００３８】
別の実施形態では、ランレングス符号化の適用から得られるビット節約が検査され、反復プロセスの各ステップにおいて、並べ替えの適用およびランレングスの確定を通して最大のビット節約を達成する列が、複数の列の中から選択される。言い換えると、目標は、できるだけ少ないビットで列を表すことであるので、各ステップにおいて、ビット節約は、最大の節約を提供する列において最大化される。この点に関して、ランレングス符号化は、それだけでも、例えば１００倍以上など、著しい圧縮改善を提供することができる。
【００３９】
別の実施形態では、８３０において、ビットパッキングとランレングス符号化の組合せを利用するハイブリッド圧縮技法が適用される。２つの技法の節約の可能性を検査する圧縮分析が適用され、例えば、ランレングス符号化が、不十分な正味のビット節約しかもたらさないと思われる場合、列ベクトルの残りの値に対しては、ビットパッキングが適用される。したがって、１つまたは複数の基準に従って、ランレングス節約が最低水準にあると決定されると、アルゴリズムは、列の残りの相対的に孤立した値のために、ビットパッキングに切り替わる。例えば、列内で表される値が相対的に孤立した場合（孤立していない値または反復する値がすでにランレングス符号化された場合）、それらの値に対しては、ランレングス符号化の代わりに、ビットパッキングを適用することができる。８４０において、出力は、上述の技法に従って符号化および圧縮された列値に対応する、１組の圧縮された列系列である。
【００４０】
図９は全体として、原データ９００の入力で開始するフロー図によって、上述の方法を説明している。９１０において、言及したように、従来システムのようにレコードの各フィールドを一緒に保持するのではなく、原データ９００の列に従って、データが再編成される。例えば、図１０に示されるように、各列は、系列Ｃ１００１、Ｃ１００２、Ｃ１００３、Ｃ１００４、Ｃ１００５、Ｃ１００６など、独立の系列を形成する。このデータが小売り取引データである場合、例えば、列Ｃ１００１は、製品価格の文字列とすることができ、列Ｃ１００２は、購入日付の文字列を表すことができ、列Ｃ１００３は、店舗所在地を表すことができ、以降も同様である。列ベースの編成は、コンピューターシステムによって収集されたほとんどの現実世界データは、表される値に関して、それほど多様ではないことを考慮して、データタイプ内の本質的な類似性を維持する。９２０において、列ベースのデータは、１つまたは複数の変換を施されて、一律に表された列ベースのデータ系列を形成する。一実施形態では、ステップ９２０は、ディクショナリ符号化および／または値符号化を介して、各列を整数データの系列に縮小する。
【００４１】
９３０において、列ベースの系列は、ランレングス符号化プロセスと、任意選択的にビットパッキングを用いて圧縮される。一実施形態では、ランレングス符号化プロセスは、すべての列の中で最も高い圧縮節約を達成する列の列データ値系列を並べ替える。したがって、ランレングス符号化が最も高い節約を達成する列が、ランレングス符号化によって置き換えられる共通の値をグループ化するために並べ替えられ、その後、並べ替えられたグループに対して、ランレングスが確定される。一実施形態では、ランレングス符号化アルゴリズムは、すべての列にわたって反復的に適用され、各ステップにおいて、各列を検査して、最も高い圧縮節約を達成する列を決定する。
【００４２】
ランレングス符号化を適用する利益が、ビット節約が不十分、または節約が閾値を下回るなど、１つまたは複数の基準に従って、限界的または最低水準になった場合、それを適用する利益は、それ相応に低下する。その結果、アルゴリズムは停止することができ、または各列内のランレングス符号化によって符号化されていない残りの値に対して、ビットパッキングを適用して、それらの値についての必要メモリをさらに低下させることができる。組合せでは、ランレングス符号化とビットパッキングのハイブリッド技法が、有限または制限された数の値が列内で表される場合は特に、列系列を強力に縮小することができる。
【００４３】
例えば、「性別」フィールドは、男性と女性の２つのフィールド値を有するだけである。ランレングス符号化を用いた場合、上で説明されたような原データの列ベース表現に従ってデータが符号化されているのであれば、そのようなフィールドは、非常に簡潔に表すことができる。これは、背景技術において説明された、行に焦点を合わせた従来の技法は、実質的に、各レコードのフィールドを一緒に保持することによって、列データの共通性を断ち切るためである。「２１」などの年齢値の次に来る「男性」は、値「男性」または値「女性」の次に来る値「男性」ほど良好には圧縮されない。したがって、列ベースのデータ編成は、効率的な圧縮を可能にし、プロセスの結果は、１組の別個の、一律に表され、コンパクト化された、列ベースのデータ系列９４０である。
【００４４】
図１１は、実際のデータに基づいた、列化プロセスの一例を与えている。図１１の例は、４つのデータレコード１１００、１１０１、１１０２、１１０３についてのものだが、本発明はテラバイトのデータに適用できるのであるから、これは、説明の簡素化のためである。一般的に言うと、コンピューターシステムによってトランザクションデータが記録される場合、それは、一般にレコードを受け取った時間順に、レコード毎に記録される。したがって、データは、各レコードに対応する行を実質的に有する。
【００４５】
図１１では、レコード１１００は、値「Ｊｏｎ」１１１１を有する名前フィールド１１１０と、値「５５５−１２１２」１１２１を有する電話番号フィールド１１２０と、値「ｊｏｎ＠ｇｏ」１１３１を有する電子メールフィールド１１３０と、値「２  １st  Ｓｔ」１１４１を有する住所フィールド１１４０と、値「Ｗａｓｈ」１１５１を有する州フィールド１１５０とを有する。
【００４６】
レコード１１０１は、値「Ａｍｙ」１１１２を有する名前フィールド１１１０と、値「１２３−４５６７」１１２２を有する電話番号フィールド１１２０と、値「Ａｍｙ＠ｗｏ」１１３２を有する電子メールフィールド１１３０と、値「１  ２nd  Ｐｌ」１１４２を有する住所フィールド１１４０と、値「Ｍｏｎｔ」１１５２を有する州フィールド１１５０とを有する。
【００４７】
レコード１１０２は、値「Ｊｉｍｍｙ」１１１３を有する名前フィールド１１１０と、値「７６５−４３２１」１１２３を有する電話番号フィールド１１２０と、値「Ｊｉｍ＠ｓｏ」１１３３を有する電子メールフィールド１１３０と、値「９  Ｆｌｙ  Ｒｄ」１１４３を有する住所フィールド１１４０と、値「Ｏｒｅｇ」１１５３を有する州フィールド１１５０とを有する。
【００４８】
レコード１１０３は、値「Ｋｉｍ」１１１４を有する名前フィールド１１１０と、値「９８７−６５４３」１１２４を有する電話番号フィールド１１２０と、値「Ｋｉｍ＠ｔｏ」１１３４を有する電子メールフィールド１１３０と、値「９１  Ｙ  Ｓｔ」１１４４を有する住所フィールド１１４０と、値「Ｍｉｓｓ」１１５４を有する州フィールド１１５０とを有する。
【００４９】
行表現１１６０が列化されて、再編成された列表現１１７０になった場合、各々が５つのフィールドを有する４つのレコードを有する代わりに、フィールドに対応する５つの列が形成される。
【００５０】
したがって、列１は、値「Ｊｏｎ」１１１１、その次に値「Ａｍｙ」１１１２、その次に値「Ｊｉｍｍｙ」１１１３、その次に値「Ｋｉｍ」１１１４を有する名前フィールド１１１０に対応する。同様に、列２は、値「５５５−１２１２」１１２１、その次に値「１２３−４５６７」１１２２、その次に値「７６５−４３２１」１１２３、その次に値「９８７−６５４３」１１２４を有する電話番号フィールド１１２０に対応する。列３は、値「ｊｏｎ＠ｇｏ」１１３１、その次に値「Ａｍｙ＠ｗｏ」１１３２、その次に値「Ｊｉｍ＠ｓｏ」１１３３、その次に値「Ｋｉｍ＠ｔｏ」１１３４を有する電子メールフィールド１１３０に対応する。同様に、列４は、値「２  １st  Ｓｔ」１１４１、その次に値「１  ２nd  Ｐｌ」１１４２、その次に値「９  Ｆｌｙ  Ｒｄ」１１４３、その次に値「９１  Ｙ  Ｓｔ」１１４４を有する住所フィールド１１４０に対応する。列５は、値「Ｗａｓｈ」１１５１、その次に値「Ｍｏｎｔ」１１５２、その次に値「Ｏｒｅｇ」１１５３、その次に値「Ｍｉｓｓ」１１５４を有する州フィールド１１５０に対応する。
【００５１】
図１２は、本明細書で説明される実施形態によって利用されるような、ディクショナリ符号化の非限定的な例を説明するブロック図である。市の典型的な列１２００は、値「Ｓｅａｔｔｌｅ」、「Ｌｏｓ  Ａｎｇｅｌｅｓ」、「Ｒｅｄｍｏｎｄ」などを含むことができ、そのような値は、何回も繰り返すことがある。ディクショナリ符号化を用いた場合、符号化された列１２１０は、値に対して一意な整数など、異なる各値に対するシンボルを含む。したがって、テキスト「Ｓｅａｔｔｌｅ」を何回も表す代わりに、整数「１」が保存され、こうしたほうが、はるかにコンパクトである。より頻繁に繰り返される値は、最もコンパクトな表現（最も少数のビット、最も少数のビット内の変化など）へのマッピングを用いて列挙することができる。値「Ｓｅａｔｔｌｅ」は、ディクショナリ１２２０の一部として、相変わらず符号化に含まれるが、「Ｓｅａｔｔｌｅ」は、何回も表す代わりに、１回だけ表せばよい。ディクショナリ１２２０によってもたらされる追加ストレージは、符号化された列１２１０のストレージ節約を大きく上回る。
【００５２】
図１３は、本明細書で説明される実施形態によって利用されるような、値符号化の非限定的な例を示すブロック図である。列１３００は、販売数量を表し、小数を含む典型的なドルおよびセントの表現を含み、これは、浮動小数点数ストレージに関わる。ストレージをよりコンパクトにするため、値符号化によって符号化された列１３１０は、浮動小数点値の代わりに、記憶するのにより少ないビットしか必要としない整数を用いて値を表すために、１０の倍数、例えば１０2が乗じられていることがある。同様に、値を表す整数の数値を小さくするために、変換を適用することができる。例えば、２，０００，０００、１８５，０００，０００など、ある列の値が一貫して１００万で終わる場合、そのすべてを１０6で除算して、値をよりコンパクトな表現である２、１８５などに小さくすることができる。
【００５３】
図１４は、本明細書で説明される実施形態によって利用されるような、ビットパッキングの非限定的な例を示すブロック図である。列１４００は、ディクショナリ符号化および／または値符号化によって整数化された注文数量を表すが、その値を表すために、行当たり３２ビットが確保される。ビットパッキングは、セグメント内の値に対して最小数のビットを使用しようと努める。この例では、列１４１０を形成するために適用されるビットパッキングの第１のレイヤーのために、１０ビット／行を使用して、値５９０、１１０、６８０、３２０を表すことができ、これは著しい節約を表す。
【００５４】
ビットパッキングは、第２のパッキング列１４２０を形成するために、共通する１０のべき乗（または他の数）を取り除くこともできる。したがって、例におけるように、値が０で終わる場合、それは、注文数量を表すのに使用される３ビット／行は必要がないことを意味しており、ストレージ構造は、７ビット／行に縮小される。ディクショナリ符号化と同様に、１０の何乗が使用されたかなど、データを列１４００に戻すために必要とされるメタデータによるいかなる増加ストレージも、ビット節約を大きく上回る。
【００５５】
第３のパッキング列１４３０を形成するビットパッキングの別のレイヤーとして、６８などの値を表すには７ビット／行を要するが、最小値は１１であるので、範囲を１１だけシフトする（各値から１１を減算する）ことができ、その場合、最大値は６８−１１＝５７であり、６ビットで表せる値は２6＝６４個あるので、この値は６ビット／行のみで表すことができることが理解できよう。図１４は、特定の順序のパッキングレイヤーを表しているが、レイヤーは、異なる順序で実行することができ、または代替的に、パッキングレイヤーは、選択的に取り除くこと、もしくは他の知られたビットパッキング技法で補足することができる。
【００５６】
図１５は、本明細書で説明される実施形態によって利用されるような、ランレングス符号化の非限定的な例を示すブロック図である。示されるように、注文タイプを表す列１５００などの列は、値が反復しているので、ランレングス符号化を用いて、効果的に符号化することができる。列値ランテーブル１５１０は、注文タイプを注文タイプのランレングスにマッピングする。テーブル１５１０のメタデータの表現には僅かな変化は許されるが、基本アイデアは、ランレングス符号化は、ランレングスが１００である場合、５０倍の圧縮を与えることができるというものであり、これは、同じデータセットについて、ビットパッキングが一般に提供できる利得よりも優れている。
【００５７】
図１６は、図７〜図１０の技法が統一符号化および圧縮技法の様々な実施形態に総合された、本明細書で提供される実施形態の一般的なブロック図である。原データ１６００は、列編成１６１０によって、列ストリームとして編成される。ディクショナリ符号化１６２０および／または値符号化１６３０が、上で説明されたようなそれぞれのサイズ縮小を提供する。その後、ハイブリッドＲＬＥおよびビットパッキングステージにおいて、圧縮分析１６４０が、ランレングス符号化１６５０を適用するか、それともビットパッキング１６６０を適用するかを決定するときに、すべての列にわたって見込まれるビット節約を検査する。
【００５８】
図１６は、図１７のフロー図でさらに詳しく説明される。１７００において、原データが、本質的な行表現によって受け取られる。１７１０において、データが、列として再編成される。１７２０において、最初にディクショナリ符号化および／または値符号化を適用して、データを縮小する。１７３０において、上で説明されたようなハイブリッドＲＬＥおよびパッキング技法を適用することができる。１７４０において、圧縮と符号化が施された列ベースのデータ系列が保存される。その後、圧縮と符号化が施された列ベースのデータ系列の全部または一部に対してクライアントが問い合わせを行った場合、１７５０において、影響される列が、要求クライアントに送信される。
【００５９】
図１８は、ハイブリッド圧縮技法の圧縮分析を実行する例示的な方法のブロック図である。例えば、ヒストグラム１８１０は、列１８００から計算され、値の発生頻度または個々のランレングスの発生頻度を表す。任意選択的に、数が少なく、ランレングス利得が最低水準になり得る、値の再発に対して、ランレングス符号化が適用されないように、閾値１８１２を設定することができる。代替的または追加的に、ビット節約ヒストグラム１８２０は、値の発生頻度を表すばかりでなく、ハイブリッド圧縮モデルの圧縮技法の一方または他方を適用することによって達成される総ビット節約も表す。加えて、ランレングス符号化の利益がその技法を適用するほど著しく十分ではなくなる境に線を引くために、やはり任意選択的に、閾値１８２２を適用することができる。列のそれらの値に対しては、代わりに、ビットパッキングを適用することができる。
【００６０】
加えて、任意選択的に、列１８００のランレングス符号化を適用する前に、最多数の同様の値をすべてグループ化するように、列１８００を並べ替えて、列１８３０とすることができる。この例では、これは、ランレングス符号化のためにＡを一緒にグループ化し、２つのＢ値については頻度も総ビット節約もランレングス符号化を正当化しないので、Ｂはビットパッキングのために残しておくことを意味する。この点に関して、並べ替えは、レコードデータの足並みをそろえておくために、他の列にも適用することができ、または列固有のメタデータを介して、ランレングス符号化の並べ替えをどのように元に戻すかを記憶しておくこともできる。
【００６１】
図１９は、圧縮分析が同様の列１９００に適用される同様の例を示しているが、ランレングスの置換当たりのビット節約が変更されているため、今では、ハイブリッド圧縮分析によって、２つのＢ値に対してもランレングス符号化を実行することが正当化され、それも、２つのＢ値はより高い正味のビット節約をもたらすので、１０個のＡ値よりも前に実行することが正当化される。この点に関して、様々な料理が盛られた１０枚の異なる皿の中から選択する大食漢にも似て、ランレングス符号化の適用は、各ステップにおいて反復的に、すべての列にわたって最も高いサイズ縮小利得を求める点で「貪欲」である。図１３と同様に、説明されたようなランレングス符号化を適用するか、それともビットパッキングを適用するかについての決定を行うために、頻度のヒストグラム１９１０および／またはビット節約ヒストグラム１９２０のデータ構造を構築することができる。また、ＲＬＥを求めるか、それともビットパッキングを求めるかを決定するときに、任意選択的な閾値１９１２および１９２２を使用することができる。並べ替えられた列１９３０は、ランレングス符号化がより長いランレングスを確定するのを助け、したがって、より大きなランレングス節約を達成する。
【００６２】
図２０は、各ステップにおいて、最も高いビット節約が達成される場所を、すべての列にわたって検査し、任意選択的に、ランレングス節約を最大化するように列を並べ替えて、列２０３０、２０３２などとすることを含むことができる、ランレングス符号化の「貪欲な」態様を示している。あるポイントにおいて、値が相対的に孤立するために、ランレングス節約が相対的に僅かとなることがあり、そのポイントにおいて、ランレングス符号化は停止する。
【００６３】
ハイブリッドの実施形態では、残りの値の範囲に対しては、ビットパッキングが適用され、図２１にそれが示されている。この点に関して、ハイブリッド圧縮技法を適用する場合、並べ替えられた列２１００は、一般には繰り返し現れる値と、相対的に孤立した値とにそれぞれ対応する、ＲＬＥ部分２１１０と、ビットパッキング部分２１２０とを含む。同様に、並べ替えられた列２１０２は、ＲＬＥ部分２１１２と、ＢＰ部分２１２２とを含む。
【００６４】
図２２に示される一実施形態では、ハイブリッドアルゴリズムが、２２００において、ビットパッキングからのビット節約と、ランレングス符号化からのビット節約を計算し、次に２２１０において、ビットパッキングからのビット節約とランレングスからのビット節約を比較または検査し、どちらの圧縮技法が、２２２０において、ビット節約を最大化するかを決定する。
【００６５】
上述の符号化および圧縮技法の例示的な性能は、現実世界のデータサンプル２３０１、２３０２、２３０３、２３０４、２３０５、２３０６、２３０６、２３０７、２３０８において達成できる著しい利得を示しており、特定の大規模データサンプルにおける値の相対反復回数にとりわけ依存する性能向上は、約９倍から９９．７倍の範囲にある。
【００６６】
図２４は、本明細書の様々な実施形態において説明された、列化プロセス、符号化プロセス、および圧縮プロセスの最終結果を表すブロック図である。この点に関して、各列Ｃ１、Ｃ２、Ｃ３、．．．、ＣＮは、ランレングス符号化が適用された同種の反復値を有する領域と、図において「Ｏｔｈｅｒｓ」または「Ｏｔｈ」とラベル付された、列内の異種の値のグループを表す他の領域とを含む。判例に示されるように、ランレングスによって定義された同一の反復値を有する領域は、純粋領域２４２０であり、多様な値を有する領域は、不純領域２４１０である。この点に関して、目で列を「上から下に辿る」と、本明細書で説明された圧縮技法の内在する利益として、データに対する新しい見方が出現する。
【００６７】
すべての列にわたって、不純領域２４１０から純粋領域２４２０への、または純粋領域２４２０から不純領域２４１０への最初の移行ポイントにおいて、第１行からその移行ポイントの行までの行として、バケットが定義される。この点に関して、バケット２４００は、点線によって示されるように、列を下方に辿りながら、すべての移行ポイントにおいて定義される。バケット２４００は、移行と移行の間の行によって定義される。
【００６８】
図２５は、特定の行における純粋領域と不純領域の数に基づいた、バケットのために定義された用語体系を示している。純粋バケット２５００は、不純領域をもたないバケットである。単一不純性バケット２５１０は、バケット内の行において１つの不純領域をもつバケットである。２重不純性バケット２５１０は、バケット内の行において２つの不純領域をもつバケットである。３重不純性バケットは、３つもち、以降も同様である。
【００６９】
したがって、例示的なデータロードプロセスの最中、データは、符号化され、圧縮され、後の効率的な問い合わせに適した表現で保存され、圧縮技法には、セグメント内でデータ分布を探し、ＲＬＥ圧縮をビットパッキングよりも頻繁に使用するように試みる技法を使用することができる。この点に関して、ＲＬＥは、圧縮および問い合わせの両方について、以下の利点を提供する。（Ａ）ＲＬＥは一般に、ビットパッキングよりも著しく少ないストレージしか必要としない、（Ｂ）ＲＬＥは、Ｇｒｏｕｐ  Ｂｙ、フィルタリング、および／または集計などの問い合わせ構築ブロック操作を実行しながら、データの範囲を効率的に「早送り（ｆａｓｔ  ｆｏｒｗａｒｄ）」する能力を含み、そのような操作は、列として編成されたデータに対する効率的な操作に数学的に変形することができる。
【００７０】
様々な非限定的な実施形態では、１度に１つの列セグメントを、同じセグメント内の別の列をソートする時までにソートする代わりに、圧縮アルゴリズムは、データ分布に基づいて、データの行をクラスタ化し、それによって、セグメント内でのＲＬＥの使用を増加させる。本明細書で使用される場合、「バケット」という用語は、行のクラスタを表すために使用され、疑問を回避するために言うと、この用語は、明確に定義されたＯＬＡＰ（オンライン分析処理（ｏｎｌｉｎｅ  ａｎａｌｙｔｉｃａｌ  ｐｒｏｃｅｓｓｉｎｇ））およびＲＤＢＭＳの概念である「パーティション」という用語とは異なると見なされるべきである。
【００７１】
上で説明された技法が効果的であるのは、データ分布には偏りがあり、大量のデータには一様分布はめったに存在しないという認識のためである。圧縮関連用語で言うところの算術符号化（Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ）は、これを利用し、全体としてより少ないビットを使用するという目標のもと、頻繁に使用される文字はより少ないビットを使用して表し、頻繁に使用されない文字はより多くのビットを使用して表す。
【００７２】
ビットパッキングを用いる場合、より高速のランダムアクセスのため、固定サイズのデータ表現が利用される。しかし、本明細書で説明された圧縮技法は、また、ＲＬＥを使用する能力も有し、ＲＬＥは、出現頻度がより高い値に対してより少ないビットを使用する方法を提供する。例えば、元のテーブル（説明の簡素化のために１つの列Ｃｏｌ１を含む）が以下のようである場合、
【００７３】
【表１】
2012504824.tif 000003
【００７４】
圧縮後、Ｃｏｌ１は以下のようになり、ランレングス符号化が適用される第１の部分と、ビットパッキングが適用される第２の部分とに分割される。
【００７５】
【表２】
2012504824.tif 000004
【００７６】
上から分かるように、最も多い共通値１００のオカレンスは、押し潰されてＲＬＥになるが、出現頻度が低い値は、依然として固定幅のビットパッキングストレージ内に保存される。
【００７７】
この点に関して、データパッキングの上述の実施形態は、２つの異なるフェーズ、すなわち、（１）バケット化を決定するためのデータ分析、および（２）バケット化レイアウトに準拠したセグメントデータの再編成を含む。これらの各々は、以下の例示的なさらなる詳細において説明される。
【００７８】
バケット化を決定するためのデータ分析に関して、目標は、セグメント内のできるだけ多くのデータをＲＬＥによってカバーすることである。そのようなものとして、このプロセスは、「より厚い」列を、すなわち、問い合わせの最中により頻繁に使用される列ではなく、大きな濃度（ｃａｒｄｉｎａｌｉｔｙ）を有する列を好むという偏りがある。使用ベースの最適化も適用することができる。
【００７９】
別の単純な例では、説明のために、以下の小さなテーブルが使用される。現実には、そのような小さなテーブルを圧縮する利益には価値がない傾向があるため、上で説明された圧縮の範囲内には、そのようなテーブルは一般に含まれない。また、圧縮は符号化が実行された後に行われ、値自体ではなく、一実施形態ではデータＩＤ（識別子）を用いて動作するので、そのような小さなテーブルは一般に含まれない。したがって、行番号の列も説明のために追加されている。
【００８０】
【表３】
2012504824.tif 000005
【００８１】
すべての列にわたって、バケット化プロセスは、セグメントデータ内で最も大きなスペースを占める単一の値を見つけることによって開始する。図１８および図１９に関連して上で言及したように、これは、各列についての簡単なヒストグラム統計を使用して、例えば以下のように行うことができる。
【００８２】
【表４】
2012504824.tif 000006
【００８３】
この値が選択されると、この値のすべてのオカレンスが連続して発生して、ＲＬＥランの長さを最大化するように、セグメント内の行が論理的に並べ替えられる。
【００８４】
【表５】
2012504824.tif 000007
【００８５】
一実施形態では、同じ行に属するすべての値は、同じインデックスをもつ各列セグメント内に存在し、例えば、ｃｏｌ１［３］およびｃｏｌ２［３］はともに、第３行に属する。これを保証することで、各アクセスのたびにマッピングテーブルを介したインダイレクション（ｉｎｄｉｒｅｃｔｉｏｎ）のコストを招くことなく、同じ行内の値への効率的なランダムアクセスを提供する。したがって、貪欲なＲＬＥアルゴリズムまたはハイブリッドＲＬＥおよびビットパッキングアルゴリズムの適用について説明される実施形態では、１つの列内で値を並べ替える場合、これは、他の列セグメント内の値も同様に並べ替えられることを含意する。
【００８６】
上述の例では、今では、２つのバケット｛１，２，４，６，７｝および｛３，５｝が存在する。言及したように、本明細書で適用されるＲＬＥは、貪欲なアルゴリズムであり、これは、アルゴリズムが、大域的な最適を見出すことを目論んで、各ステージにおいて局所的に最適な選択を行う、問題解決メタヒューリスティック（ｐｒｏｂｌｅｍ  ｓｏｌｖｉｎｇ  ｍｅｔａｈｅｕｒｉｓｔｉｃ）に従うことを意味する。最大のバケットを見出す第１のフェーズの後、次のフェーズは、次に大きいバケットを選択し、そのバケット内でプロセスを繰り返すことである。
【００８７】
【表６】
2012504824.tif 000008
【００８８】
今では、行がしかるべく再編成された場合、３つのバケット｛２，７｝、｛１，４，６｝、｛３，５｝が存在する。最大のバケットは、第２のバケットであるが、そこには反復値は存在しない。第１のバケットは、すべての列がＲＬＥランからなり、残りの値は孤立しており、そのため、Ｃｏｌ１において得られるさらなるＲＬＥ利得は存在しないことが分かる。｛３，５｝のバケットに目を向けると、ＲＬＥに変換できる別の値１２３１が存在している。面白いことに、１２３１は直前のバケットにも現れており、１２３１が一番下になるように、そのバケットを並べ替えて、次のバケットの先頭と融合させる準備をすることができる。次のステップは以下をもたらす。
【００８９】
【表７】
2012504824.tif 000009
【００９０】
上述の例では、今では、４つのバケット｛２，７｝、｛６，４｝、｛１｝、｛３，５｝が存在する。データをさらに変形することはできないので、プロセスは、次のフェーズであるセグメントデータの再編成に進む。
【００９１】
上の図では行も同様に並べ替えたが、性能上の理由で、バケットの決定は、各列セグメント内でデータを並べ替える動作から、統計に純粋に基づくことができる。各列セグメント内でデータを並べ替える動作は、利用可能なコアに基づいて、ジョブスケジューラを使用して、並列化することができる。
【００９２】
言及したように、上述の技法の使用は、小さなデータセットについては実際的ではない。顧客データセットの場合、上述の技法は、しばしば数万ステップにも及び、これには時間がかかる。アルゴリズムの貪欲性のため、スペース節約の大部分は、最初の数ステップにおいて生じる。最初の２、３千ステップの間に、節約されるスペースのほとんどがすでに節約されている。しかし、圧縮データのスキャン側で観察されるように、僅かな圧縮利得であっても、問い合わせの最中には恩恵を得られるので、パッキングされた列内におけるＲＬＥの存在は、問い合わせの最中に著しい性能上昇を与える。
【００９３】
１度に１つのセグメントが処理されるので、複数のコアを使用して、データをデータソースからセグメント内に読み込むのに要する時間と、先のセグメントを圧縮するのに要する時間をオーバラップさせることができる。従来の技術を用いた場合、約１００Ｋ行／秒のレートでリレーショナルデータベースから読み込むとすると、８Ｍ行のセグメントは約８０秒かかり、それは、そのような作業に利用可能な時間としては、相当な長さである。任意選択的に、一実施形態では、先のセグメントのパッキングは、次のセグメントのデータが利用可能になると、停止させることもできる。
【００９４】
列ベースのデータ符号化の処理
言及したように、列ベースの符号化のための様々な実施形態に従ってデータを編成する方法は、データの消費サイドにおける効率的なスキャンに役立ち、メモリ内で選択された数の列に対して非常に高速に処理を実行することができる。上述のデータパッキングおよび圧縮技法は、行符号化の最中の圧縮フェーズを更新し、スキャンは、インテリジェントな符号化を利用する問い合わせオプティマイザおよびプロセッサを含む。
【００９５】
スキャンおよび問い合わせ機構は、ビジネス情報（ＢＩ）問い合わせに対して効率的に結果を返すために使用することができ、上述のデータパッキングおよび圧縮技法によって生成されたクラスタ化レイアウトのために設計され、増やされたＲＬＥ使用のために最適化され、例えば、問い合わせ処理中に、問い合わせのために使用される列のうちの相当数が、ＲＬＥを使用して圧縮されていることが期待される。加えて、高速スキャンプロセスは、列ストアに対する行方向問い合わせプロセッサの代わりに、列指向の問い合わせエンジンを導入する。そのようなものとして、（ＲＬＥデータではなく）ビットパッキングデータを含むバケットにおいてさえも、データ局所性による性能利得を大きくすることができる。
【００９６】
上述のデータパッキングおよび圧縮技法ならびに効率的なスキャンの導入に加えて、非常に効率的な方法で、以下のことを、すなわち、問い合わせにおける「ＯＲ」スライス、および関係が指定された複数のテーブル間の「結合」をサポートすることができる。
【００９７】
上で暗に示したように、スキャン機構は、セグメント群が、図２４に示されるように、１つのセグメントにわたって広がり、「純粋な」ＲＬＥランまたは「不純な」他のビットパッキングストレージ内に列値を含むバケットを含むことを仮定する。
【００９８】
一実施形態では、スキャンはセグメントに対して起動され、キーは、１度に１つのバケットを処理することである。バケット内では、スキャンプロセスは、問い合わせ仕様に応じて、いくつかのフェーズで、列指向の処理を実行する。第１のフェーズは、どの列領域が純粋であり、どの領域が不純であるかについての統計を収集することである。次に、フィルターを処理することができ、それに続いて、Ｇｒｏｕｐ  Ｂｙ操作を、それに続いて、プロキシ列（ｐｒｏｘｙ  ｃｏｌｕｍｎ）の処理を行うことができる。次に、別のフェーズとして、集計を処理することができる。
【００９９】
先に言及したように、スキャンのための本明細書で提示された実施形態は、行指向の同様の従来システムの代わりに、列指向の問い合わせ処理を実施することに留意されたい。したがって、これらのフェーズの各々について、実行される実際のコードは、（１）操作される列がランレングス符号化されているかどうか、（２）ビットパッキングのために使用された圧縮タイプ、（３）結果は疎か、それとも密かなどに対して特有とすることができる。集計については、（１）符号化タイプ（ハッシュか、それとも値か）、（２）集計関数（ｓｕｍ／ｍｉｎ／ｍａｘ／ｃｏｕｎｔ）など、さらなる考察を考慮に入れる。
【０１００】
したがって、一般にスキャンプロセスは、図２６の形式に従い、様々な標準の問い合わせ／スキャンオペレータ２６００の問い合わせ結果は、すべてのバケット行の関数である。問い合わせ／スキャンオペレータ２６００は、実際には、フィルター、Ｇｒｏｕｐ  Ｂｙ、プロキシ列、および集計が、互いに別々に、いくつかのフェーズで処理されるように、数学的に分割することができる。
【０１０１】
この点に関して、処理ステップの各々のために、２６１０において、バケットウォーキングプロセスによるバケットの異なる純粋性に従って、オペレータが処理される。結果として、すべてのバケット行に対して汎用的でコストのかかるスキャンを行う代わりに、本明細書で説明された符号化および圧縮アルゴリズムの作業によって導入された異なるバケットの特殊性を用いた場合、それによって、結果は、純粋パケット、単一不純性バケット、２重不純性バケットなどの処理の集約結果となる。
【０１０２】
図２４は、バケットのサンプル分布と、圧縮アーキテクチャの能力を示しており、処理数学を簡単な演算に変形できるので、純粋バケットに対して実行される処理が最速であり、それに続いて、単一不純性バケットが２番目に最速であり、以降の不純性が増していくバケットについても同様である。さらに、驚くほど多数のバケットが純粋であることが見出された。例えば、図２９に示されるように、問い合わせに６つの列が関わる場合、各列が約９０％の純粋性を有するならば（値の約９０％が、同様のデータであるために、ランレングス符号化を用いて表されることを意味する）、約６０％のバケットは純粋であり、約１／３は単一不純性であり、約８％は２重不純性であり、残りは単に１％を占めるにすぎない。純粋バケットの処理は最速であり、単一不純性バケットおよび２重不純性バケットの処理もまだ非常に高速であるので、不純性が３以上の領域を有する「より複雑な」処理は、最低に維持される。
【０１０３】
図２８は、サンプルの「列によるフィルター」問い合わせ構築ブロック２８０２、サンプルの「列によるグループ化」問い合わせ構築ブロック２８０４、およびサンプルの「列による統合」問い合わせ構築ブロック２８０６など、いくつかのサンプルの標準的な問い合わせ構築ブロックを有する、サンプル問い合わせ２８００を示している。
【０１０４】
図２９は、列選択による帯域幅削減のさらなる態様を示すブロック図である。サンプル問い合わせ２９００を検討すると、すべての列２９２０のうち、たかだか６つの列２９１０が関係するだけであり、したがって、非常に効率的な問い合わせのためには、６つの列だけをローカルＲＡＭにロードしさえすればよいことが分かる。
【０１０５】
したがって、本明細書では、様々な実施形態が説明された。図３０は、３０００において、データの異なるデータフィールドに対応する１組の列ベースの値系列に従ってデータを編成することを含む、データを符号化するための一実施形態を示している。その後、３０１０において、１組の列ベースの値系列が、ディクショナリ符号化および／または値符号化などの、少なくとも１つの符号化アルゴリズムに従って、１組の列ベースの整数値系列に変換される。その後、３０２０において、１組の列ベースの整数系列が、１組の列ベースの整数系列に適用される貪欲なランレングス符号化アルゴリズム、もしくはビットパッキングアルゴリズム、またはランレングス符号化とビットバッキングの組合せを含む、少なくとも１つの圧縮アルゴリズムに従って圧縮される。
【０１０６】
一実施形態では、ＲＬＥ（ランレングス符号化）圧縮を適用するか、それともビットパッキング圧縮を適用するかを決定するために、整数系列が分析され、それには、ＲＬＥ圧縮とビットパッキング圧縮のビット節約を比較分析して、最大ビット節約を達成する場所を決定することが含まれる。プロセスは、最大ビット節約を達成する場所を決定する助けとなる、ヒストグラムを生成することも含むことができる。
【０１０７】
別の実施形態では、図３１に示されるように、ビットパッキング技法は、３１００においてデータの列を表す整数値系列の部分を受け取ることと、ビットパッキングによって見込まれる縮小の３つのステージとを含む。３１１０において、データフィールドを表すのに必要とされるビットの数に基づいて、データを縮小することができる。３１２０において、整数系列の部分のすべての値にわたって共有されるいずれかのべき乗を除去することによって、データを縮小することができる。３１３０において、ある範囲にわたる整数系列の部分の値をオフセットすることによっても、データを縮小することができる。
【０１０８】
別の実施形態では、図３２のフロー図に示されるように、３２００において、問い合わせに応答して、データのサブセットが、データの異なる列に対応する整数符号化と圧縮を施された値系列として取り出される。その後、３２１０において、データのサブセットの整数符号化と圧縮を施された値系列のいずれかにおいて生じる圧縮タイプの変化に基づいて、データのサブセットにまたがる処理バケットが定義される。次に、３２２０において、効率的な問い合わせ処理のために、処理される現在のバケットのタイプに基づいて、問い合わせ操作が実行される。操作は、メモリ内で実行することができ、マルチコアアーキテクチャにおいては並列化することができる。
【０１０９】
異なるバケットは、（１）すべての系列にわたるバケット内の異なる部分の値が、すべてランレングス符号化圧縮に従って圧縮され、純粋バケットとして定義されるバケット、（２）１つを除くすべての部分がランレングス符号化に従って圧縮され、単一不純性バケットとして定義されるバケット、または（３）２つを除くすべての部分がランレングス符号化に従って圧縮され、２重不純性バケットとして定義されるバケットを含む。
【０１１０】
改善されたスキャンは、最も純粋なバケットについては特に、様々な標準の問い合わせオペレータおよびスキャンオペレータをはるかに効率的に実行することを可能にする。例えば、バケットウォーキング技法が適用され、処理がバケットタイプに基づいて実行される場合、論理ＯＲ問い合わせスライス操作、関係が指定された複数のテーブル間の問い合わせ結合操作、フィルター操作、Ｇｒｏｕｐ  Ｂｙ操作、プロキシ列操作、または集計操作はすべて、より効率的に実行することができる。
【０１１１】
例示的なネットワーク環境および分散環境
本明細書で説明された列ベースの符号化および問い合わせ処理の様々な実施形態が、コンピューターネットワークの一部としてまたは分散コンピューティング環境内に配備でき、任意の種類のデータストアに接続できる、任意のコンピューターまたは他のクライアントもしくはサーバーデバイスとの関連で実現できることが、当業者であれば理解できよう。この点に関して、本明細書で説明された様々な実施形態は、任意の数のメモリまたはストレージユニットと、任意の数のストレージユニットにおいて発生する任意の数のアプリケーションおよびプロセスを有する、任意のコンピューターシステムまたは環境において実現することができる。これは、リモートストレージまたはローカルストレージを有する、ネットワーク環境または分散コンピューティング環境内に配備された、サーバーコンピューターおよびクライアントコンピューターを含む環境を含むが、それに限定されない。
【０１１２】
分散コンピューティングは、コンピューティングデバイスおよびシステムの間の通信交換によって、コンピューターリソースおよびサービスの共用を提供する。これらのリソースおよびサービスは、情報の交換、ファイルなどのオブジェクトのキャッシュストレージおよびディスクストレージを含む。これらのリソースおよびサービスは、負荷バランシング、リソースの拡張、および処理の特化などのために、複数の処理ユニット間で処理能力を分担することも含む。分散コンピューティングは、ネットワーク接続を利用して、クライアントが、企業全体の利益のために、集団的な力を発揮することを認める。この点に関して、様々なデバイスは、本発明の開示の様々な実施形態のいずれか１つまたは複数の態様を実行するために協力できる、アプリケーション、オブジェクト、またはリソースを有することができる。
【０１１３】
図３３は、例示的なネットワーク環境または分散コンピューティング環境の概略図を提供する。分散コンピューティング環境は、アプリケーション３３３０、３３３２、３３３４、３３３６、３３３８によって表されるように、プログラム、メソッド、データストア、プログラマブルロジックなどを含むことができる、コンピューティングオブジェクト３３１０、３３１２などおよびコンピューティングオブジェクトまたはコンピューティングデバイス３３２０、３３２２、３３２４、３３２６、３３２８などを含む。オブジェクト３３１０、３３１２などおよびコンピューティングオブジェクトまたはコンピューティングデバイス３３２０、３３２２、３３２４、３３２６、３３２８などが、ＰＤＡ、オーディオ／ビデオデバイス、モバイル電話、ＭＰ３プレーヤー、パーソナルコンピューター、ラップトップなど、異なるデバイスを含み得ることが理解できよう。
【０１１４】
オブジェクト３３１０、３３１２などおよびコンピューティングオブジェクトまたはコンピューティングデバイス３３２０、３３２２、３３２４、３３２６、３３２８などの各々は、通信ネットワーク３３４０を介して、直接的または間接的に、１つまたは複数の他のオブジェクト３３１０、３３１２などおよびコンピューティングオブジェクトまたはコンピューティングデバイス３３２０、３３２２、３３２４、３３２６、３３２８などと通信することができる。図３３では単一の要素として示されているが、ネットワーク３３４０は、図３３のシステムにサービスを提供する他のコンピューターオブジェクトおよびコンピューティングデバイスを含むことができ、ならびに／または図示されていない複数の相互接続ネットワークを表すことができる。オブジェクト３３１０、３３１２などまたは３３２０、３３２２、３３２４、３３２６、３３２８などの各々は、本発明の開示の様々な実施形態に従って提供される列ベースの符号化および問い合わせ処理との通信、列ベースの符号化および問い合わせ処理のための処理、または列ベースの符号化および問い合わせ処理の実施に適した、ＡＰＩ、または他のオブジェクト、ソフトウェア、ファームウェア、および／もしくはハードウェアを利用できる、アプリケーション３３３０、３３３２、３３３４、３３３６、３３３８などのアプリケーションも含むことができる。
【０１１５】
分散コンピューティング環境をサポートする、様々なシステム、コンポーネント、およびネットワーク構成が存在する。例えば、コンピューティングシステムは、有線システムまたは無線システムによって、ローカルネットワークまたは広域分散ネットワークによって、互いに接続することができる。現在、多くのネットワークは、広域分散コンピューティングのためのインフラストラクチャを提供し、多くの異なるネットワークを包含するインターネットに接続されるが、様々な実施形態で説明された列ベースの符号化および問い合わせ処理に付随して行われる例示的な通信のために、任意のネットワークインフラストラクチャを使用することができる。
【０１１６】
したがって、クライアント／サーバー、ピアツーピア、またはハイブリッドアーキテクチャなど、多くのネットワークトポロジおよびネットワークインフラストラクチャを利用することができる。「クライアント」は、それが関係しない別のクラスまたはグループのサービスを使用する、クラスまたはグループのメンバである。クライアントは、別のプログラムまたはプロセスによって提供されるサービスを要求するプロセス、すなわち、大雑把に言って、１組の命令またはタスクとすることができる。クライアントプロセスは、他のプログラムまたはサービス自体についてのいかなる作業詳細も「知る」必要なしに、要求したサービスを使用する。
【０１１７】
特にネットワークシステムのクライアント／サーバーアーキテクチャでは、クライアントは通常、例えばサーバーなどの別のコンピューターによって提供される共用ネットワークリソースにアクセスするコンピューターである。図３３の図では、非限定的な例として、コンピューター３３２０、３３２２、３３２４、３３２６、３３２８などは、クライアントと考えることができ、コンピューター３３１０、３３１２などは、サーバーと考えることができ、サーバー３３１０、３３１２などは、クライアントコンピューター３３２０、３３２２、３３２４、３３２６、３３２８などからのデータの受信、データの保存、データの処理、クライアントコンピューター３３２０、３３２２、３３２４、３３２６、３３２８などへのデータの送信などのデータサービスを提供するが、状況に応じて、任意のコンピューターをクライアント、サーバー、またはその両方と考えることができる。これらのコンピューティングデバイスのいずれかが、１つまたは複数の実施形態について本明細書で説明された列ベースの符号化および問い合わせ処理に関わることができるデータを処理し、データを符号化し、データを問い合わせ、またはサービスもしくはタスクを要求することができる。
【０１１８】
サーバーは一般に、インターネットまたはワイヤレスネットワークインフラストラクチャなどのリモートネットワークまたはローカルネットワークを介してアクセス可能な、リモートコンピューターシステムである。クライアントプロセスは、第１のコンピューターシステムにおいてアクティブとすることができ、サーバープロセスは、第２のコンピューターシステムにおいてアクティブとすることができ、通信媒体を介して互いに通信し、したがって、分散された機能を提供し、複数のクライアントがサーバーの情報収集機能を利用することを認める。列ベースの符号化および問い合わせ処理に従って利用されるどのソフトウェアオブジェクトも、スタンドアロンとして提供することができ、または複数のコンピューティングデバイスまたはコンピューティングオブジェクト間に分散させることができる。
【０１１９】
通信ネットワーク／バス３３４０がインターネットであるネットワーク環境では、例えば、サーバー３３１０、３３１２などは、ＨＴＴＰ（ハイパーテキスト転送プロトコル）など、多くの知られたプロトコルのいずれかを介して、クライアント３３２０、３３２２、３３２４、３３２６、３３２８などが通信するＷｅｂサーバーとすることができる。サーバー３３１０、３３１２などは、分散コンピューティング環境に特徴的なように、クライアント３３２０、３３２２、３３２４、３３２６、３３２８などとしても機能することができる。
【０１２０】
例示的なコンピューティングデバイス
言及したように、有利には、本明細書で説明された技法は、大量のデータを迅速に問い合わせることが望ましい任意のデバイスに適用することができる。したがって、ハンドヘルドデバイス、ポータブルデバイス、および他のコンピューティングデバイス、ならびにすべての種類のコンピューティングオブジェクトは、様々な実施形態に関連して、すなわち、デバイスが高速で効率的な結果を求めて大量のデータをスキャンまたは処理することを望むことがある場合に、使用されることが企図されていることを理解されたい。したがって、以下図３４において説明される以下の汎用リモートコンピューターは、コンピューティングデバイスの一例であるにすぎない。
【０１２１】
必ずしも必要ではないが、実施形態は、デバイスもしくはオブジェクトのためのサービスのデベロッパによって使用するために、オペレーティングシステムを介して部分的に実施することができ、および／または本明細書で説明された様々な実施形態の１つもしくは複数の機能的態様を実行するように動作するアプリケーションソフトウェア内に含むことができる。ソフトウェアは、クライアント、ワークステーション、サーバー、または他のデバイスなど、１つまたは複数のコンピューターによって実行される、プログラムモジュールなどの、コンピューター実行可能命令という一般的な文脈において説明することができる。コンピューターシステムは、データを伝達するために使用できる様々な機器構成およびプロトコルを有し、したがって、特定の機器構成またはプロトコルを限定と考えるべきではないことを当業者であれば理解されよう。
【０１２２】
したがって、図３４は、本明細書で説明された実施形態の１つまたは複数の態様を実施できる、適切なコンピューティングシステム環境３４００の一例を示しているが、上で明らかにされたように、コンピューティングシステム環境３４００は、適切なコンピューティング環境の一例にすぎず、使用または機能の範囲に関して、どのような限定を暗示することも意図していない。コンピューティング環境３４００は、例示的な動作環境３４００に示されるコンポーネントのいずれか１つまたは組合せに関して、何らかの依存性または要件を有すると解釈されるべきではない。
【０１２３】
図３４を参照すると、１つまたは複数の実施形態を実施するための例示的なリモートデバイスは、コンピューター３４１０の形態の汎用コンピューティングデバイスを含む。コンピューター３４１０のコンポーネントは、処理ユニット３４２０と、システムメモリ３４３０と、システムメモリを含む様々なシステムコンポーネントを処理ユニット３４２０に結合するシステムバス３４２２とを含むことができるが、それらに限定されない。
【０１２４】
コンピューター３４１０は一般に、様々なコンピューター可読媒体を含み、また、コンピューター３４１０によってアクセスできる任意の利用可能な媒体にすることができる。システムメモリ３４３０は、ＲＯＭ（リードオンリメモリ）および／またはＲＡＭ（ランダムアクセスメモリ）などの、揮発性および／または不揮発性メモリの形態のコンピューター記憶媒体を含むことができる。限定することなく、例を挙げると、メモリ３４３０は、オペレーティングシステム、アプリケーションプログラム、他のプログラムモジュール、およびプログラムデータを含むこともできる。
【０１２５】
ユーザは、入力デバイス３４４０を介して、コンピューター３４１０にコマンドおよび情報を入力することができる。モニタまたは他のタイプのディスプレイデバイスも、出力インターフェース３４５０などのインターフェースを介して、システムバス３４２２に接続される。モニタに加えて、コンピューターは、出力インターフェース３４５０を介して接続できる、スピーカおよびプリンタなどの他の周辺出力デバイスも含むことができる。
【０１２６】
コンピューター３４１０は、リモートコンピューター３４７０などの１つまたは複数の他のリモートコンピューターへの論理接続を使用して、ネットワーク環境または分散環境において動作することができる。リモートコンピューター３４７０は、パーソナルコンピューター、サーバー、ルーター、ネットワークＰＣ、ピアデバイスもしくは他の共通ネットワークノード、または他の任意のリモート媒体消費もしくは伝送デバイスとすることができ、コンピューター３４１０に関して上で説明された要素のいずれかまたはすべてを含むことができる。図３４に描かれた論理接続は、ＬＡＮ（ローカルエリアネットワーク）またはＷＡＮ（ワイドエリアネットワーク）などのネットワーク３４７２を含むが、他のネットワーク／バスも含むことができる。そのようなネットワーク環境は、家庭、オフィス、企業規模のコンピューターネットワーク、イントラネット、およびインターネットにおいて一般的である。
【０１２７】
上で言及したように、例示的な実施形態は、様々なコンピューティングデバイスおよびネットワークアーキテクチャとの関連で説明されたが、基礎をなす概念は、大規模データを圧縮すること、または大規模データに対する問い合わせを処理することが望ましい、任意のネットワークシステムおよび任意のコンピューティングデバイスまたはシステムに適用することができる。
【０１２８】
また、アプリケーションおよびサービスが効率的な符号化および問い合わせ技法を使用できるようにする、例えば、適切なＡＰＩ、ツールキット、ドライバコード、オペレーティングシステム、コントロール、スタンドアロンまたはダウンロード可能なソフトウェアオブジェクトなど、同一または類似の機能を実施するための複数の方法が存在する。したがって、本明細書の実施形態は、列ベースの符号化および／または問い合わせ処理を提供する、ソフトウェアオブジェクトまたはハードウェアオブジェクトの観点と同様に、ＡＰＩ（または他のソフトウェアオブジェクト）の観点からも企図されている。したがって、本明細書で説明された様々な実施形態は、すべてがハードウェアの、一部がハードウェアで一部がソフトウェアの、およびソフトウェアの態様を有することができる。
【０１２９】
「例示的（ｅｘｅｍｐｌａｒｙ）」という語は、本明細書では、例、事例、または例示として提示されたことを意味するために使用される。疑問を回避するために言うと、本明細書で開示された主題は、そのような例によって限定されない。加えて、「例示的」として本明細書で説明された態様または設計はいずれも、必ずしも他の態様または設計よりも好ましいまたは有利であると解釈されるべきではなく、当業者に知られた等価の例示的な構造および技法を排除することを意味していない。さらに、疑問を回避するために言うと、「含む（ｉｎｃｌｕｄｅｓ）」、「有する（ｈａｓ）」、「含む（ｃｏｎｔａｉｎｓ）」という用語および他の類似の語が詳細な説明または特許請求の範囲で使用される限りにおいて、そのような用語は、いかなる付加的な要素または他の要素も排除することなく、開かれた移行語としての「備える（ｃｏｍｐｒｉｓｉｎｇ）」という用語と同様に包含的であることが意図されている。
【０１３０】
言及したように、本明細書で説明された様々な技法は、ハードウェアもしくはソフトウェアに関連して、または適切な場合には両方の組合せに関連して実施することができる。本明細書で使用される場合、「コンポーネント」および「システム」などの用語も同様に、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、または実行中ソフトウェアなど、コンピューター関連エンティティを指すことが意図されている。例えば、コンポーネントは、プロセッサ上で動作中のプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行スレッド、プログラム、および／またはコンピューターとすることができるが、それらに限定されない。例を挙げると、コンピューター上で実行中のアプリケーションとコンピューターはともに、コンポーネントとすることができる。１つまたは複数のコンポーネントは、プロセスおよび／または実行スレッド内に存在することができ、コンポーネントは、１つのコンピューター上にローカルに配置すること、および／または複数のコンピューター間に分散させることができる。
【０１３１】
上記のシステムは、いくつかのコンポーネント間の対話に関して説明された。そのようなシステムおよびコンポーネントは、それらのコンポーネントもしくは指定されたサブコンポーネント、指定されたコンポーネントもしくはサブコンポーネントのいくつか、および／または付加的なコンポーネントを、上記のものの様々な置換および組合せによって含むことができることが理解できよう。サブコンポーネントは、親コンポーネント内に（階層的に）含まれたコンポーネントとしてではなく、他のコンポーネントに通信可能に結合されたコンポーネントとしても実施することができる。加えて、１つまたは複数のコンポーネントは、集約された機能を提供する１つのコンポーネントに組み合わせることができること、またはいくつかの別個のサブコンポーネントに分割することができること、また管理レイヤーなど、いずれか１つまたは複数の中間レイヤーは、統合された機能を提供するために、そのようなサブコンポーネントに通信可能に結合されるように提供することができることに留意されたい。本明細書で説明されたコンポーネントはいずれも、本明細書では具体的に説明されていないが、一般に当業者によって知られている、１つまたは複数の他のコンポーネントと相互に作用することもできる。
【０１３２】
上で説明された例示的なシステムに鑑みて、説明された主題に従って実施できる方法は、様々な図のフローチャートを参照してより良く理解することができる。説明を簡潔にする目的で、方法は一連のブロックとして示され、説明されているが、特許請求される主題は、ブロックの順序によって限定されず、いくつかのブロックは、本明細書で描写および説明されたのとは異なる順序で、ならびに／または他のブロックと同時に生じることができることを理解および認識されたい。フローチャートによって、非順次的な流れまたは分岐のある流れが示される場合、同一または類似の結果を達成する様々な他の分岐、流れの経路、ブロックの順序を実施できることが理解できよう。さらに、以下本明細書で説明される方法を実施するために、必ずしも示されたすべてのブロックが必要とされるわけではない。
【０１３３】
本明細書で説明された様々な実施形態に加えて、対応する実施形態と同一または等価の機能を実行するために、対応する実施形態から逸脱することなく、他の類似の実施形態を使用すること、または説明された実施形態に変更および追加を施すことができることを理解されたい。またさらに、複数の処理チップまたは複数のデバイスは、本明細書で説明された１つまたは複数の機能の実行を分担することができ、同様に、ストレージは、複数のデバイスにわたって実施することができる。したがって、本発明は、いずれか単一の実施形態に限定することなく、添付の特許請求の範囲に従った、広さ、主旨、および範囲をもつと解釈されるべきである。
【図１】
2012504824.tif 000010
【図２】
2012504824.tif 000011
【図３】
2012504824.tif 000012
【図４】
2012504824.tif 000013
【図５】
2012504824.tif 000014
【図６】
2012504824.tif 000015
【図７】
2012504824.tif 000016
【図８】
2012504824.tif 000017
【図９】
2012504824.tif 000018
【図１０】
2012504824.tif 000019
【図１１】
2012504824.tif 000020
【図１２】
2012504824.tif 000021
【図１３】
2012504824.tif 000022
【図１４】
2012504824.tif 000023
【図１５】
2012504824.tif 000024
【図１６】
2012504824.tif 000025
【図１７】
2012504824.tif 000026
【図１８】
2012504824.tif 000027
【図１９】
2012504824.tif 000028
【図２０】
2012504824.tif 000029
【図２１】
2012504824.tif 000030
【図２２】
2012504824.tif 000031
【図２３】
2012504824.tif 000032
【図２４】
2012504824.tif 000033
【図２５】
2012504824.tif 000034
【図２６】
2012504824.tif 000035
【図２７】
2012504824.tif 000036
【図２８】
2012504824.tif 000037
【図２９】
2012504824.tif 000038
【図３０】
2012504824.tif 000039
【図３１】
2012504824.tif 000040
【図３２】
2012504824.tif 000041
【図３３】
2012504824.tif 000042
【図３４】
2012504824.tif 000043
【国際調査報告】
2012504824.tif 000044
2012504824.tif 000045
2012504824.tif 000046