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