JP2011530234A - 大規模なデータストレージのための効率的な列ベースデータの符号化 - Google Patents

Abstract

主題開示は、列ベースデータの符号化に関し、これにおいて、圧縮されるべき生データが列により組織化され、次に、データサイズ削減の第１および第２の層として、列により組織化されるように、辞書符号化および／または値符号化がデータに適用され、列に対応する整数のシーケンスが作成される。次に、ハイブリッドでグリーディなランレングス符号化・ビットパッキング圧縮のアルゴリズムは、ビットセービングの分析に従って、データをさらにコンパクトにする。列ベース組織化を合わせたハイブリッドなデータ削減の技術のシナジーは、コンパクトなデータの表現に因るスキャニングおよびクエリの効率における利益と相まって、従来のシステムの何分の一かのコストで、かなり向上したデータ圧縮をもたらした。

Description

主題開示は概して、膨大な量のデータサイズを削減し、かつ、データを処理またはクエリするスピードを高めるための、効率的な列ベースデータの符号化に関する。

従来の圧縮に関する背景技術として、膨大な量のデータをデータベースに記憶させる時、例えば、サーバコンピュータが、長期間に渡るデータの大量のレコードまたはトランザクションを収集する時、他のコンピュータが、このデータまたはこのデータの目的のサブセットへのアクセスを要求することがある。このような場合、該他のコンピュータは、１つまたは複数のクエリ演算子を介して、要求するデータにクエリを行うことができる。これに関して歴史的には、リレーショナルデータベースが、この目的のために発達して、そのような大規模なデータ収集に対して使用され、また、種々のクエリ言語が開発され、これによりデータベース管理ソフトウェアに命令して、クエリを行うクライアントに代わってリレーショナルデータベースまたは分散データベースの組からデータを検索させるようになった。

従来、リレーショナルデータベースは、行に従って組織化されるものであって、行はレコードに対応し、フィールドを有する。例えば、第１の行には、第１の行のレコードを定義する列に対応するフィールドの様々な情報（名前１、年齢１、住所１、性別１、等）が含まれ、第２の行には、第２の行のフィールドの様々な異なる情報（名前２、年齢２、住所２、性別２、等）が含まれる。しかし従来、クライアントによるローカルなクエリまたはローカルなビジネスインテリジェンスのための、莫大なデータ量に渡るクエリ、または、莫大なデータ量の検索は、リアルタイムまたはほぼリアルタイムの要求を満たすことができない程度のものに限られてきた。特に、クライアントが、サーバから最新のデータのローカルコピーを取り出したい場合、サーバからそのような大規模な量のデータを転送することは、限られたネットワーク帯域幅および限られたクライアントのキャッシュストレージを考えると、実用的ではなく、多くのアプリケーションに対して時代遅れなものとなった。

例えば、現在、２つの「ｇｒｏｕｐ ｂｙ」操作と４つの「ａｇｇｒｅｇａｔｅ」操作をサンプルクエリとして使用して、ほぼ１６０バイトのデータをそれぞれ持つ６億行のデータ（約１００ギガバイトのデータ）をスキャンおよび集計すると、最速の既知のリレーショナルデータベース管理システム（ＲＤＢＭＳ）は、業界標準のＴＰＣ−Ｈの測定基準による測定では、データを約３９．９秒で配信および処理することが可能である。これは、ほぼ２．５Ｇｂ／秒のビットレート、すなわち約１５００万行／秒での配信を表す。しかし、従来技術のシステムの今日の状態では、コストの観点からは、２００，０００ドル近い費用がかかり、ほとんどのユーザにとって、参入への高い障壁になっている。さらに、３９．９秒は、速いとは言えるが、最も厳しいリアルタイムのデマンドおよび要求は満たされてはおらず、また、多くの改善の余地が残されている。

さらなる背景技術として、アーキテクチャの一部としてリレーショナルデータベースを伴う異なるレコードとして異なる行を概念化することの利便性により、データセットのサイズを削減するための技術では、従って、リレーショナルデータベースをどのように組織化するかについての性質のため、さらに行に焦点が向けられてきた。言い換えれば、行情報には、レコードの全てのフィールドを一緒に１行に保持することにより、各レコードが維持され、集計データサイズを削減するための従来の技術では、符号化自体の一部として、フィールドが一緒に維持される。

ランレングス符号化（ＲＬＥ）は従来の形式のデータ圧縮であり、連続するデータ、すなわち、同じデータ値が多くの連続するデータ要素において現れるシーケンス、が、元の連続するデータではなく、単一のデータ値とカウントとして記憶される。実際には、エントリとして「ＥＥＥＥＥＥ」と記載する代わりに、「６Ｅ」というランレングスが、その多数のＥに対して定義される。ＲＬＥは、多くのそのような連続データ、例えば、アイコン、線画、およびアニメーション等の比較的シンプルなグラフィック画像、を含むデータに対しては有用である。しかし、データが、値ごと、またはピクセルごと等に一意的であったり、または、どの場所においてもほとんど一意的である傾向がある場合、ＲＬＥは、あまり効率的でないことが分かっている。従って、ＲＬＥは、単独では効率的なデータ削減には役に立たず、貴重な処理時間を浪費してもほとんどまたは全く利得が無いことがある。

データに適用される別のタイプの圧縮には辞書符号化があり、これは、フィールドデータ値を、得られるデータと一緒に使用される辞書を介したコンパクトにされた表現で、連続した整数等の減少させたビットセットにトークン化することにより動作し、コンパクトにされた表現から元のフィールドデータ値が取得される。

データに適用される別のタイプの圧縮には値符号化があり、これは、よりコンパクトな表現を可能にする何らかの変換をデータ全体に実行することにより、例えば、可逆的な数学関数をデータに適用して、データを表現するのに必要なビット数を減少させることにより、実数を整数に変換する。例えば、浮動小数値等の実数は、メモリ内で整数値よりもより多くの空間をとり、従って、浮動小数値を整数値に可逆的に変換することにより、ストレージのサイズを減少させ、そして、データを使用するプロセッサが、必要に応じて浮動小数値を得ることが可能である。

データに適用されるさらに別のタイプの圧縮には、ビットパッキングがあり、これは、データの別個の値の数をカウントし、または、異なる値が及ぶ範囲を判定し、そして、数または値のこの組を最適化関数により決定されるような最小ビット数で表す。例えば、所定の列の各フィールドが限られた範囲にしか及ばない可能性があると、各値を、例えば、このフィールドに対して最初に定義された１０ビットで表す代わりに、６ビットのみがその値を表すのに必要であるということになるかもしれない。ビットパッキングでは、データのより効率的な６ビットの表現に従って値が再記憶される。

これらの従来の圧縮技術の各々は、リレーショナルデータベースの行組織化された情報に、例えば、ｒｏｗｓｅｔ演算子を介して、それぞれ無関係に適用され、その上、これらの技術の各々は、データベースから、最新のデータを求めてリアルタイムの要求を有するであろう消費側のクライアントに、素早く、膨大な量のデータを配信することを満たすという問題が適切に対処されていないという点において、不都合を有する。主に、従来の方法論では、記憶するデータサイズを削減して、所定のディスクのサイズまたはストレージ制限に対して、記憶可能なデータの量を最大化することに焦点が向けられてきた。

しかし、これらの技術それ自体でも、実際は、データ集約型の復号、または問い合わせに応えるために伝送されなければならない巨大なサイズの圧縮ストレージ構造の為、データのスキャンまたはクエリに従ったデータ全体を処理する時間を長くさせてしまう。例えば、多くの従来の圧縮技術において、データの圧縮に長く時間がかかるほど、サイズについて達成されるセービング（節減）が大きくなる。しかし、一方で、そのような従来の圧縮スキームを用いたデータの圧縮に長く時間がかかるほど、結局、解凍および処理に長く時間がかかる。従って、従来のシステムでは、データを圧縮するだけでなく、データをより早くクエリ、検索、スキャンする方法でデータを圧縮するデータ符号化技術を、提供することはできない。

加えて、ネットワーク伝送帯域幅における制限により、圧縮データがクライアントによってどのくらい速く受信され得るかが、本質的に制限され、莫大な量のデータを求める要求に対しての障壁となる。従って、データサイズの削減とクエリ処理のスピードを同時に向上させる解決策を提供することが望ましい。大量のデータのためのクエリベースのシステムにおいて高度に効率的な圧縮および処理を可能にする、改善されたデータ符号化技術を提供することがさらに望ましい。

今日のリレーショナルデータベースおよび対応する圧縮技術の欠陥についての上記の記載では、単に従来のシステムのいくつかの問題の概要を提供することを意図しており、網羅することを意図していない。従来のシステムの他の問題、および本明細書に記載される種々の非制限的実施形態の対応する利益は、以下の記載を精査することによりさらに明らかになるであろう。

本明細書において、簡素化された概要が提供され、より詳細な説明および添付の図面に続く例示の非制限的実施形態の種々の態様の、基本的または一般的な理解を可能にする助けとなる。しかし、この概要は広範囲または網羅的な概観として意図されない。その代わりに、この概要の唯一の目的は、いくつかの例示の非制限的実施形態に関するいくつかの概念を、後に続く種々の実施形態のより詳細な記載の前置きとして、簡素化された形式で表すことである。

列ベースデータの符号化の実施形態が記載される。種々の非限定的実施形態において、圧縮されるべき生データが列により組織化され、次に、データサイズ削減の第１および第２の層として、列により組織化されるように、辞書符号化および／または値符号化がデータに適用され、列に対応する整数のシーケンスが作成される。次に、圧縮の追加の層として、ハイブリッドランレングス符号化・ビットパッキングのアルゴリズムは、データをさらにコンパクトにすることが可能である。一実施形態において、ハイブリッドランレングス符号化・ビットパッキングでは、最大限の圧縮によるセービングが達成される列のランレングス符号化に対して有利に働く、所定のデータセットに対する反復圧縮分析に従って操作が行われる。この圧縮分析に従って、セービングが比較的重要でない場所では、例えば、ランレングス符号化が適用されなかった列の残りのデータセットの値が、お互いに比較的一意的である時は、ランレングス符号化は、使用されない。その代わり、そのような状況ではビットパッキングが使用される。

列ベース組織化を合わせたハイブリッドなデータ削減の技術のシナジーは、列ベースのコンパクトな表現に因るスキャンおよびクエリの効率における利得と相まって、従来のシステムの何分の一かのコストで、例えば、最速の既知の従来のシステムのコストの１／１０より少ないコストで、４００倍という率の速さの、かなり向上したデータ圧縮をもたらした。

これらおよび他の実施形態が、より詳細に以下に記載される。

種々の非限定的実施形態が、添付の図面を参照してさらに記載される。

列ベースの符号化技術および符号化されたデータ全体に渡るクエリのインメモリのクライアント側の処理を例示する概略的なブロック図である。 列ベースの符号化技術を採用する符号化装置の例示の非限定的な実装を例示するブロック図である。 列ベースの符号化を大規模なデータに適用するための例示の非限定的な処理を例示するフロー図である。 レコードがそのそれぞれのフィールドに分割され、同じタイプのフィールドがシリアル化されベクトルが形成される、生データの列ベースの表現を例示する図である。 レコードデータのカラム化を例示する非限定的ブロック図である。 クエリに関連して受け取られる列データのインメモリのクライアント側の処理の作業を、複数のコアの間で分けて、列組織全体に渡る大量の行を処理する負荷を共有させることができることを例示する図である。 辞書符号化の概念を例示する非限定的ブロック図である。 値符号化の概念を例示する非限定的ブロック図である。 ハイブリッドな圧縮技術の一態様に適用されるビットパッキングの概念を例示する非限定的ブロック図である。 ハイブリッドな圧縮技術の別の態様に適用されるランレングス符号化の概念を例示する非限定的ブロック図である。 列ベースの符号化技術を採用する符号化装置の例示の非限定的な実装を例示するブロック図である。 一実装に従って列ベースの符号化を大規模なデータに適用するための例示の非限定的な処理を例示するフロー図である。 代替の圧縮技術を適用するための閾値セービングのアルゴリズムを選択的に適用することを含んで、グリーディ（貪欲）なランレングス符号化圧縮のアルゴリズムを実行する方法を例示する図である。 代替の圧縮技術を適用するための閾値セービングのアルゴリズムを選択的に適用することが含んで、グリーディなランレングス符号化圧縮のアルゴリズムを実行する方法を例示する図である。 グリーディなランレングス符号化圧縮のアルゴリズムをさらに例示するブロック図である。 ハイブリッドランレングス符号化・ビットパッキング圧縮のアルゴリズムを例示するブロック図である。 トータルビットセービング分析に基づく異なるタイプの圧縮を適応的に提供する、ハイブリッドな圧縮技術の適用を例示するフロー図である。 主題開示の種々の実施形態に従って、データの全体のサイズを削減する、列ベースの符号化のサンプルの性能を例示するブロック図である。 純粋領域と非純粋領域の間での遷移に関して、列ベース符号化データに適用することが可能なバケット化処理を例示する図である。 一実施形態に従って、列のバケット化に関する非純粋のレベルを例示する図である。 クエリ／スキャン演算子を、現在のクエリ／スキャンに関する列に存在する異なるタイプのバケットに対応するサブ演算子に分割する効率的な分割を例示する図である。 得られる純粋バケットがデータの行の５０％超を表す場所における、列ベース符号化の指数を例示する図である。 標準化された様式でデータ全体に渡ってクエリを指定するためのクエリ言語の例示の非限定的なクエリのビルディングブロックを例示する図である。 ネットワークを介して利用可能な大規模なデータ全体に渡る、消費側のクライアントデバイスにより要求されるサンプルクエリの代表的な処理を例示する図である。 様々な実施形態に従う、列に従ってデータを符号化する処理を例示するフロー図である。 １つまたは複数の実施形態に従う、整数のシーケンスをビットパッキングする処理を例示するフロー図である。 データの列ベース表現全体に渡ってクエリを行う処理を例示するフロー図である。 本明細書に記載される種々の実施形態が実装される、例示の非限定的なネットワーク化環境を表すブロック図である。 本明細書に記載される種々の実施形態の１つまたは複数の態様を実装可能な、例示の非限定的なコンピュータシステムまたは動作環境を表すブロック図である。

背景技術において検討したように、とりわけ、従来のシステムは、非常に大量のデータをサーバまたは「クラウド」内の他のデータストアからメモリに極めて速く読み込むという問題を、現在の圧縮技術についての制限、ネットワーク上の伝送帯域幅についての制限、およびローカルキャッシュメモリについての制限の為、適切に処理しない。例えば、１秒当たり１．５テラバイト相当のデータを読み込むことは、主要な高価な従来の解決法でもそのスピードの何分の一か（〜２．５Ｇｂ／秒）で動作する今日においては、非常な偉業であり桁違いのコストがかかる。

従って、種々の非限定的実施形態において、列指向の符号化技術が大量のデータに適用されて、データをコンパクトにし、同時にそのデータを組織化して、その後のデータ全体に渡るスキャン／検索／クエリの操作を大幅により効率的なものにする。以下に続くロードマップとしては、種々の実施形態の概要について最初に記載し、次に、例示の非限定的な選択的実装について、補足的なコンテキストおよび理解のためにより詳細に検討される。まず、大量のデータをパッキングするための列ベースの符号化技術について記載し、ハイブリッドな圧縮技術を介するランレングス符号化およびビットパッキングのパフォーマンス利益を適応的にトレードオフする例示の実施形態が含まれる。

例示の非限定的な一実施形態において、各列に対して１つ、生データを値のシーケンスの組にカラム化した後（例えば、列のデータのフィールドをシリアル化することであり、例えば、全ての姓を１つのシーケンスに、または、全ての注文書番号を別のシーケンスにするなど）、データは「整数化」されて、各列にする整数のシーケンスが形成され、シーケンスは、辞書符号化、値符号化、または辞書符号化および値符号化の両方に従って、どちらかの順番で均一に表される。この整数化の段階により、均一に表される列ベクトルが得られ、これ自体で大幅なセービングが、特に、テキスト文字列等の、長いフィールドがデータに記録される場所で、達成される。次に、全ての列を検査しながら、圧縮の段階ではランレングス符号化が列のランに繰り返し適用され、これにより列ベクトルの組全体に渡る全体のサイズの削減の量が最も高くなる。

以上のように、パッキング技術は、列ベースであり、優れた圧縮を提供するだけでなく、コンパクトにされた整数の列ベクトルが一旦クライアント側に配信されると、圧縮技術自体がデータを素早く処理する際の助けとなる。

種々の非限定的実施形態において、図１に示すように、列ベースエンコーダ／コンプレッサ１１０が提供され、大規模なデータストレージ１００をコンパクトにし、かつ、その後のデータ全体に渡るスキャン／検索／クエリの操作を大幅により効率的なものにする。データ処理ゾーンＣ内のデータ消費側のデバイス１２０によるクエリに応答して、コンプレッサ１１０が、クエリに関係する圧縮された列を、データ伝送ゾーンＢの伝送ネットワーク１１５を介して伝送する。データはインメモリストレージ１３０に配信され、従って、該当する列の解凍はデータ処理ゾーンＣ内のデコーダ・クエリプロセッサ１４０により高速で処理可能である。これに関して、バケット移動（ｂｕｃｋｅｔ ｗａｌｋｉｎｇ）が、効率的な処理で追加の層に対してなされるクエリに関連して、解凍された列により表される行に適用される。行との類似点が、バケット移動中に有効利用されて、繰り返しの動作が一緒に実行されるようにする。以下にさらに詳述するように、この技術が、標準のまたは１９６ＧｂのＲＡＭを有する汎用のサーバを用いて、大量のウェブトラフィックデータまたはトランザクションデータ等の実在のサンプルデータに適用されると、サーバのデータのクエリ／スキャンは、１秒当たりおよそ１．５テラバイトのデータの速さで達成され、これは従来のシステムの能力を桁はずれに上回り、ハードウェアのコストを大幅に減少させるものである。

圧縮可能な特定のデータタイプが任意の特定のデータタイプに限られるものではなく、かつ、莫大な量のデータの大規模なスキャンに依存する多数のシナリオが、同様に制限されるものではない一方、これらの技術を、リアルタイムのビジネス人工知能応用においてビジネスのデータまたはレコードに適用することの商業的重要性は、疑う余地が無い。リアルタイムの報告およびトレンド同定が、圧縮技術により達成されるクエリ処理のスピードにおける法外な利得により、全く新しい段階に入る。
＜列ベースデータの符号化＞
概要において触れたように、列指向の符号化および圧縮は、種々の実施形態において大量のデータに適用されて、データをコンパクトにし、同時に組織化して、その後のデータ全体に渡るスキャン／検索／クエリの操作を大幅により効率的なものにすることが可能である。種々の実施形態において、符号化および圧縮を開始するにあたって、生データは、最初に、データのカラム化されたストリームとして再組織化される。

エンコーダの一実施形態が、概して図２に示されるが、２００にて生データがストレージから受け取られ、または読み込まれ、その時点で２１０にて符号化装置および／または符号化ソフトウェア２５０がデータを列として組織化する。２２０にて、列ストリームが均一のベクトル表現に変換される。例えば、整数符号化を、名前または住所等の地図的な個人の項目に適用して整数にすることが可能である。そのような整数符号化技術は、辞書符号化技術とすることができ、データを２倍から１０倍削減することが可能である。加えて、または代替えとして、値符号化は、１倍から２倍のサイズ削減をさらに提供することが可能である。これにより、２２０にて各列は整数のベクトルとされる。そのような性能向上は、コンパクト化されているデータから敏感に影響を受け、従って、そのようなサイズ削減の範囲は、単に非制限的な予測として与えられ、異なる工程での相対的性能についての一般的な概念を与えるものである。

次に、２３０にて、符号化された均一な列ベクトルがさらにコンパクト化される。一実施形態において、ランレングス符号化技術を適用して、全ての列に渡って最も頻出する値すなわちある値の出現を判定し、その場合、その値のランレングスが定義され、かつ、処理は、ランレングス符号化による利得が限界になるポイントまで、例えば、整数値が列内で少なくとも６４回の出現を繰り返すまで、繰り返される。

別の実施形態において、ランレングス符号化を適用することによるビットセービングが検査され、繰り返す処理の各工程において、ランレングスの並べ替えおよび定義の適用を介して最大限のビットセービングを達成する列が列の中ら選択される。言い換えれば、列をできるだけ少ないビットで表すことが目的であるため、各工程において、ビットセービングは、最大のセービングを提供する列において最大化される。これに関して、ランレングス符号化は、例えば、それ自体で１００倍以上という、著しい圧縮向上を提供することが可能である。

別の実施形態において、２３０にて、ビットパッキングとランレングス符号化を組み合わせて採用するハイブリッドな圧縮技術が適用される。圧縮分析を適用して、２つの技術による潜在的なセービングを検査し、例えば、ランレングス符号化では正味のビットセービングが不十分であると思われる場所には、列ベクトルの残りの値に対してビットパッキングを適用する。従って、ランレングスセービングが、１つまたは複数の基準に従って最低であると判定されると、アルゴリズムは、列の残りの比較的一意的な値に対してビットパッキングに切替える。例えば、列内に表される値が比較的一意的になる場所には（一意的でない値または繰り返す値が既にランレングス符号化されている場所）、ランレングス符号化の代わりに、ビットパッキングをそれらの値に適用することができる。２４０にて、上述の技術に従って符号化および圧縮されるような列の値に対応する圧縮列のシーケンスの組が出力される。

図３は、上記の方法論を、生データ３００の入力で開始されるフロー図に従って概して記載する。３１０にて、上述したように、従来のシステムのようなレコードの各フィールドを一緒に保持することとは対照的に、データが、生データ３００の列に従って認識される。例えば、図４に示すように、各列は、シーケンスＣ４０１、Ｃ４０２、Ｃ４０３、Ｃ４０４、Ｃ４０５、Ｃ４０６等の独立したシーケンスを形成する。小売りのトランザクションデータがデータである場所では、例えば、列Ｃ４０１が製品の価格の文字列であり、列Ｃ４０２が仕入れの日付を表し、列Ｃ４０３が店舗立地を表す、などとすることができる。列ベースの組織は、コンピュータシステムにより収集されるほとんどの実在のデータが、表される値の観点からはそれほど多様ではないということを考慮すると、データ型において特有の類似性を保持する。３２０にて、列ベースデータは１つまたは複数の変換を施されて、均一に表される列ベースデータのシーケンスが形成される。一実施形態において、ステップ３２０では、辞書符号化および／または値符号化を介して、各列を削減しての整数のシーケンスのデータにする。

３３０にて、列ベースシーケンスは、ランレングス符号化処理および選択的にビットパッキングで、圧縮される。一実施形態において、ランレングス符号化処理は、全ての列の、列の列データ値のシーケンスを並べ替え、これにより最も高い圧縮によるセービングが達成される。従って、ランレングス符号化により最高の削減が達成される列は、並べ替えられて、ランレングス符号化により置き換えられている共有の値をグループ化し、次に、ランレングスが並べ替えられたグループに対して定義される。一実施形態において、ランレングス符号化のアルゴリズムが列全体に渡って繰り返し適用され、各列を各工程で検査して、最高の圧縮によるセービングを達成するであろう列を判定する。

ランレングス符号化を適用することによる利得が、１つまたは複数の基準に従うと限界または最小となり、例えば、ビットセービングが不十分であったり、削減が閾値より低くなると、その適用による利得が相応して低下する。その結果、アルゴリズムを停止させることが可能であり、または、各列におけるランレングス符号化により符号化されない残りの値に対してビットパッキングを適用して、それらの値のストレージの必要性をさらに減少させることができる。ハイブリッドランレングス符号化およびビットパッキングの技術は、組み合わせて、列のシーケンス、特に、シーケンス内に表される値の数が有限または制限される列のシーケンス、を強力に削減することが可能である。

例えば、「性別」のフィールドが、男および女という２つのフィールドの値のみを持つ。ランレングス符号化では、そのようなフィールドは、データが、上述のように生データの列ベース表現に従って符号化される限り、非常にシンプルに表すことができる。これは、背景技術において記載した行に注目する従来の技術が、実際には各レコードのフィールドを一緒に保持することにより、列データの共通点を断ち切るからである。「２１」等の年齢の値の隣にある「男」は、単なる「男」または「女」という値の隣にある「男」という値と同じようには、圧縮されない。従って、データの列ベースの組織化は、効率的な圧縮を可能にし、かつ、処理の結果は、別個の、均一に表されコンパクト化される、データの列ベースシーケンスの組３４０となる。

図５は、実際のデータに基づくカラム化処理の例を与える。図５の例には、４つのデータレコード５００、５０１、５０２および５０３があるが、これは例示の簡素化のためのものであり、本発明は数テラバイトのデータに適用可能である。一般的に言えば、トランザクションデータは、コンピュータシステムにより記録される時、レコードごとに記録され、かつ、一般的にはレコードを受け取る時の時間順で記録される。従って、データは実際には行を持ち、行は各レコードに対応する。

図５において、レコード５００は、値「Ｊｏｎ」５１１を持つ名前フィールド５１０、値「５５５−１２１２」５２１を持つ電話番号フィールド５２０、値「ｊｏｎ＠ｇｏ」５３１を持つ電子メールフィールド５３０、値「２ １ｓｔ Ｓｔ」５４１を持つ住所フィールド５４０、および、値「Ｗａｓｈ」５５１を持つ州フィールド５５０、を有する。

レコード５０１は、値「Ａｍｙ」５１２を持つ名前フィールド５１０、値「１２３−４５６７」５２２を持つ電話番号フィールド５２０、値「Ａｍｙ＠ｗｏ」５３２を持つ電子メールフィールド５３０、値「１ ２ｎｄ Ｐｌ」５４２を持つ住所フィールド５４０、および、値「Ｍｏｎｔ」５５２を持つ州フィールド５５０、を有する。

レコード５０２は、値「Ｊｉｍｍｙ」５１３を持つ名前フィールド５１０、値「７６５−４３２１」５２３を持つ電話番号フィールド５２０、値「Ｊｉｍ＠ｓｏ」５３３を持つ電子メールフィールド５３０、値「９ Ｆｌｙ Ｒｄ」５４３を持つ住所フィールド５４０、および、値「Ｏｒｅｇ」５５３を持つ州フィールド５５０、を有する。

レコード５０３は、値「Ｋｉｍ」５１４を持つ名前フィールド５１０、値「９８７−６５４３」５２４を持つ電話番号フィールド５２０、値「Ｋｉｍ＠ｔｏ」５３４を持つ電子メールフィールド５３０、値「９１ Ｙ Ｓｔ」５４４を持つ住所フィールド５４０、および、値「Ｍｉｓｓ」５５４を持つ州フィールド５５０、を有する。

行表現５６０が再組織化列表現５７０にカラム化される時、それぞれ５個のフィールドを有する４つのレコードを有する代わりに、５つの列がフィールドに対応して形成される。

従って、列１は、値「Ｊｏｎ」５１１、続いて値「Ａｍｙ」５１２、続いて値「Ｊｉｍｍｙ」５１３、続いて値「Ｋｉｍ」５１４、を持つ名前フィールド５１０に対応する。同様に列２は、値「５５５−１２１２」５２１、続いて値「１２３−４５６７」５２２、続いて値「７６５−４３２１」５２３、続いて値「９８７−６５４３」５２４、を持つ電話番号フィールド５２０に対応する。列３は、値「ｊｏｎ＠ｇｏ」５３１、続いて値「Ａｍｙ＠ｗｏ」５３２、続いて値「Ｊｉｍ＠ｓｏ」５３３、続いて値「Ｋｉｍ＠ｔｏ」５３４、を持つ電子メールフィールド５３０に対応する。更には、列４は、値「２ １ｓｔ Ｓｔ」５４１、続いて値「１ ２ｎｄ Ｐｌ」５４２、続いて値「９ Ｆｌｙ Ｒｄ」５４３、続いて値「９１ Ｙ Ｓｔ」５４４、を持つ住所フィールド５４０に対応する。そして、列５は、値「Ｗａｓｈ」５５１、続いて値「Ｍｏｎｔ」５５２、続いて値「Ｏｒｅｇ」５５３、続いて値「Ｍｉｓｓ」５５４、を持つ州フィールド５５０に対応する。

一実施形態において、上述の技術に従って圧縮された列が、消費側のクライアントシステム上のメモリにロードされる時、データは各列Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６に渡って分割されて、セグメント６００、６０２、６０４、６０６等を形成する。これに関して、各セグメントは数億以上の行を含むことができるため、例えば、クエリに従って、並列化によりデータの処理またはスキャンのスピードを向上させる。各セグメントの結果が集計されて結果の完全な組が形成され、一方、各セグメントが別個に処理される。

図７は、本明細書に記載される実施形態により採用されるような、辞書符号化の非限定的な例を例示するブロック図である。都市名の典型的な列７００には、値「Ｓｅａｔｔｌｅ」、「Ｌｏｓ Ａｎｇｅｌｅｓ」、「Ｒｅｄｍｏｎｄ」等を含むことができ、そのような値はそれ自体が何度も繰り返される。辞書符号化では、符号化された列７１０には、それぞれの別個の値に対するシンボル、例えば、値ごとの一意的な整数、が含まれる。従って、テキスト「Ｓｅａｔｔｌｅ」が何度も表される代わりに、整数「１」が記憶され、よりコンパクトである。より頻繁に繰り返される値は、最もコンパクトな表現（最小ビット、ビットにおける最小変更、等）にマッピングで列挙可能である。値「Ｓｅａｔｔｌｅ」は、辞書７２０の一部としてさらに符号化に含まれるが、「Ｓｅａｔｔｌｅ」は何度もではなく、一度表されれば良い。符号化される列７１０のストレージセービングは、辞書７２０に関わる余分に必要なストレージを大きく上回る。

図８は、本明細書に記載される実施形態により採用されるような、値符号化の非限定的な例を例示するブロック図である。列８００は、売上高を表し、浮動小数のストレージに関わる、小数を含む典型的なドルとセントの表現を含む。ストレージをよりコンパクトにするため、値符号化で符号化された列８１０では、浮動小数値の代わりに、より少ないビット数で記憶できる整数で値を表すために、それに１０の倍数、例えば、１０^２を掛ける。変換は、値を表す整数の数の削減にも同様に適用することができる。例えば、値が、ある列では、２，０００，０００、１８５，０００，０００等のように一貫して百万台で終わる場合、全て１０^６で除算して、値を削減して２、１８５等のよりコンパクトな表現にすることができる。

図９は、本明細書に記載される実施形態により採用されるような、ビットパッキングの非限定的な例を例示するブロック図である。列９００は、辞書符号化および／または値符号化により整数化されたような注文量を表すが、値の表現には一行あたり３２ビットが予約されている。ビットパッキングでは、セグメント内の値に対して最小ビット数を使用することが努力される。本例では１０ビット／行を使用して、５９０、１１０、６８０および３２０の値を表すことができ、ビットパッキングが適用された第１の層に対して大幅なセービングが表され、列９１０が形成される。

ビットパッキングはまた、共通の１０（または他の数字）の累乗を削除して、第２のパッキング化列９２０を形成することが可能である。従って、例におけるように値が０で終わる場合、注文量を表すために使用される３ビット／行が必要ではなく、ストレージ構造を７ビット／行に減らすことができることを意味する。辞書符号化と同様に、１０の何乗を使用するのかなどの、データを列９００に復元するのに必要なメタデータによる任意のストレージの増加を、ビットセービングは大幅に上回る。

第３のパッキング化列９３０を形成するためのビットパッキングの別の層としては、６８などの値を表すのに７ビット／行を要することは認識されるであろうが、最小の値は１１であるため、範囲は１１だけずらすことができ（各値から１１を減じる）、従って、最高の数は６８−１１＝５７となり、これは６ビット／行で表すことが可能であるが、値の可能性が２^６＝６４であるためである。図９は、層をパッキングする特定の順番を表すが、層に対して異なる順番で実行することが可能であり、または、層のパッキングは、他の既知のビットパッキング技術で選択的に削除または補足することが可能である。

図１０は、本明細書に記載される実施形態により採用されるような、ランレングス符号化の非限定的な例を例示するブロック図である。例示するように、注文の型を表す列１０００等の列は、値が繰り返されているためランレングス符号化で効率的に符号化することが可能である。列の値のランテーブル１０１０は、注文の型を注文の型のランレングスにマッピングする。テーブル１０１０のメタデータの表現にわずかなばらつきは許容されるが、基本的な考え方は、ランレングス符号化ではランレングス「１００」に対して５０倍の圧縮が与えられることが可能であるということであり、これは、ビットパッキングが一般に同じデータセットに対して提供できる利得に勝る。

図１１は、本明細書に提供される実施形態の概略的なブロック図であり、図７から１０の技術が統合符号化・圧縮スキームの種々の実施形態に組み合わせられている。生データ１１００は、列組織１１１０に従って列ストリームとして組織化される。辞書符号化１１２０および／または値符号化１１３０が、上述のようにそれぞれのサイズ削減を提供する。そして、ハイブリッドＲＬＥ・ビットパッキングの段階において、圧縮分析１１４０が、ランレングス符号化１１５０またはビットパッキング１１６０を適用するかどうかを判定する時に、列全体に渡って潜在的なビットセービングを検査する。

図１１は、図１２のフロー図でさらに詳しく説明される。１２００にて、生データが特有の行表現に従って受け取られる。１２１０にて、データは列として再組織化される。１２２０にて、辞書符号化および／または値符号化が適用されて、１回目のデータの削減がなされる。１２３０にて、ハイブリッドＲＬＥ・ビットパッキング技術が、上述のように、適用される。１２４０にて、データの圧縮および符号化された列ベースシーケンスが記憶される。そして、クライアントがデータの圧縮符号化された列ベースシーケンスの全てまたはサブセットに対してクエリを行う時、１２５０にて、影響をうける列が要求クライアントに伝送される。

図１３は、ハイブリッドな圧縮技術の圧縮分析を実行する例示の方法のブロック図である。例えば、ヒストグラム１３１０は、値の出現の頻度、または個々のランレングスの出現の頻度を表す、列１３００から計算される。選択的に、閾値１３１２を設定し、ランレングスの利得が最小である、少ない回数の値の再出現には、ランレングス符号化が適用されないようにすることができる。あるいは、または加えて、ビットセービングヒストグラム１３２０は、値の出現の頻度だけでなく、ハイブリッド圧縮モデルの圧縮技術のどれか１つを適用することにより達成されるトータルビットセービングを表す。加えて、閾値１３２２を、再度、選択的に適用して、技術を適用してもランレングス符号化の利得が十分ではない場所に線引きすることができる。その代わりに、ビットパッキングを列のそのような値に適用することができる。

加えて、選択的に、列１３００のランレングス符号化を適用する前に、列１３００を並べ替えて、最も類似する値の全てを、並べ替えられた列１３３０としてグループ化することができる。本例において、これは、ランレングス符号化のためにＡを一緒にグループ化すること、および、ビットパッキングのためにＢを残すことを意味するが、頻度でもトータルビットセービングでも、２つのＢという値のランレングス符号化が正当であるとはされないからである。これに関して、並べ替えを他の列に適用して、レコードデータを標準的な工程で保持すること、または、列特有のメタデータを介してランレングス符号化の並べ替えをどのように元に戻すのかを記憶させることができる。

図１４は、圧縮分析が同様の列１４００に適用される、同様の例を例示するが、ここでは、ランレングスの置き換えによるビットセービングが変更されて、今度は、ハイブリッドな圧縮分析に従うと、２つのＢという値では正味のビットセービングがより高くなるため、１０個のＡという値の前でも、２つのＢという値にランレングス符号化を実行することが正当であるとされる。この点において、上に盛られる料理が変化する異なる１０枚の皿の中から選ぶ大食漢に良く似て、ランレングス符号化の適用は、各工程において全ての列に渡ってサイズの削減における最高の利得を繰り返し求めるという点で「グリーディ」である。図１３と同様に、頻度のヒストグラム１４１０および／またはビットセービングヒストグラム１４２０のデータ構造は、上述のようにランレングス符号化を適用すべきか、またはビットパッキングをすべきかについて判定させるように構築することができる。また、選択的閾値１４１２および１４２２は、ＲＬＥまたはビットパッキングを続行するかどうかを判定する時に使用することができる。並べ替えられた列１４３０は、ランレングス符号化の補助となり、より長いランレングスを定義して、より大きなランレングスセービングを達成させることが可能である。

図１５は、ランレングス符号化の「グリーディ」な態様を例示し、ここでは、各工程で最高のビットセービングが達成される場所が列全体に渡って検査され、選択的に、列を列１５３０、１５３２等に並べ替えてランレングスセービングを最大にすることができる。ある時点では、値が比較的一意的であるために、ランレングスセービングが比較的重要でない場合があり、その時点でランレングス符号化は停止される。

ハイブリッドな実施形態において、ビットパッキングが残りの値の範囲に適用され、これが図１６に例示される。これに関して、ハイブリッドな圧縮技術を適用すると、並べ替えられた列１６００には、ＲＬＥ部１６１０およびビットパッキング部１６２０が含まれ、これらは一般にそれぞれ、繰り返す値および比較的一意的な値に対応する。同様に、並べ替えられた列１６０２には、ＲＬＥ部１６１２およびＢＰ部１６２２が含まれる。

図１７に示す一実施形態において、ハイブリッドなアルゴリズムにより、１７００にて、ビットパッキングによるビットセービングと、ランレングス符号化によるビットセービングが計算され、次に、１７１０にて、ビットパッキングによるビットセービングと、ランレングスによるビットセービングが比較され、または、１７２０にて、検査されて、ビットセービングを最大にする圧縮技術が判定される。

上述の符号化および圧縮の技術の例示の性能では十分な利得が例示され、これは実在のデータサンプル１８０１、１８０２、１８０３、１８０４、１８０５、１８０６、１８０６、１８０７および１８０８に対して達成可能であり、９倍から９９．７倍程度の範囲の性能の向上があるが、これは、他の要因の中でも、特定の大規模なデータサンプル内において繰り返す値の相対量に依存する。

図１９は、種々の実施形態において本明細書に記載される、カラム化、符号化および圧縮の処理の最終結果を示すブロック図である。これに関して、各列Ｃｌ、Ｃ２、Ｃ３、．．．、ＣＮには、ランレングス符号化が適用された同種の繰り返す値を有する領域と、図面において「他の」または「他」と記される、列内に異種の値のグループを表す他の領域と、が含まれる。凡例で示すように、ランレングスにより定義される同種の繰り返す値を持つ領域は、純粋領域１９２０であり、多様な値を持つ領域は非純粋領域１９１０である。この点において、視線を列に沿って「下げる」と、本明細書で検討される圧縮技術の特有の利得として、データについての新しい見解が浮かび上がる。

全ての列に渡って、非純粋領域１９１０と純粋領域１９２０との間の、または逆の、最初の遷移の時点において、バケットは、第１の行から遷移時点の行までの行として定義される。これに関して、バケット１９００は、点線で示されるような各遷移時点ごとに列を下って定義される。バケット１９００は、遷移の間にある行により定義される。

図２０は、特定の行に渡る純粋領域と非純粋領域の数に基づきバケットに対して定義される用語体系を示す。純粋バケット２０００は、非純粋領域を持たない。シングル非純粋バケット２０１０は、バケットの行に渡って非純粋領域を１つ持つ。ダブル非純粋バケット２０１０は、バケットの行に渡って非純粋領域を２つ持つ。トリプル非純粋は３つ持つ等々である。

従って、例示のデータロード処理中、データは符号化され、圧縮され、後の効率的なクエリに適切な表現で記憶されて、圧縮技術には、セグメント内でのデータ分散を予期して、ビットパッキングよりもＲＬＥ圧縮を頻繁に使用しようとするものが使用される。これに関して、ＲＬＥは、圧縮とクエリの両方に以下の利点を提供する。（Ａ）ＲＬＥは典型的には、必要とするストレージがビットパッキングより極めて少ない、（Ｂ）ＲＬＥには、「Ｇｒｏｕｐ Ｂｙ」、「Ｆｉｌｔｅｒｉｎｇ（フィルタリング）」および／または「Ａｇｇｒｅｇａｔｉｏｎ（集計）」のようなクエリビルディングブロック操作を実行しながら、データの範囲に渡って効率的に「速く進ませる」能力があり、そのような操作は、列として組織化されたデータに対する効率的な操作になるように、数学的に削減される。

種々の非限定的な実施形態において、１つの列セグメントを、同一セグメント内の別の列をソートする前の時点でソートする代わりに、圧縮アルゴリズムにより、行のデータがその配信に基づきクラスタ化され、このことがセグメント内でのＲＬＥの使用を増加させる。本明細書において使用される場合、用語「バケット」は、行のクラスタを説明するために使用され、誤解を避けるために、用語「パーティション」とは異なるものとみなされるべきであり、明確に定義されたオンライン分析処理（ＯＬＡＰ）およびＲＤＢＭＳのコンセプトである。

上記で検討した技術は、データ分散が偏っていること、かつ、大量のデータにおいては均一な分散はほとんど存在しないことが認識されているため、効果的である。圧縮の専門用語では、「算術符号化」がこのことを活用し、頻繁に使用される文字をより少ないビットで表し、あまり頻繁に使用されない文字をより多くのビットで表すことにより、全体としてより少ないビットを使用することを目的としている。

ビットパッキングでは、固定のサイズのデータ表現が、より速いランダムなアクセスのために利用される。しかし、本明細書に記載される圧縮技術には、ＲＬＥを使用する能力もあり、これにより、より頻度の高い値に対してより少ないビットを使用する方法が提供される。例えば、元のテーブル（簡単に例示するため、１つの列Ｃｏｌ１が含まれる）が以下の通りである場合、

圧縮後、Ｃｏｌ１は以下のようになり、ランレングス符号化が適用される第１の部分と、ビットパッキングが適用される第２の部分に分けられる。

上記から分かるように、最も共通する値である１００の出現がＲＬＥ内に折り畳まれ、あまり頻繁に現れない値が、固定の幅のビットパッキングされたストレージにまだ記憶されている。

これに関して、データパッキングの上述の実施形態には、２つの別個のフェーズが含まれる：（１）バケット化を判定するためのデータ分析、および（２）バケット化されたレイアウトに従うセグメントデータの再組織化、である。これらはそれぞれ、以下で例示してさらに詳細に記載される。

バケット化を判定するためのデータ分析について、目的はＲＬＥのセグメント内のデータをできるだけ多くカバーすることである。そのため、この処理は、「より厚い」列、すなわち、クエリ時により頻繁に使用されるであろう列ではなく、大きな濃度を有する列、に有利に働くように偏っている。利用ごとの最適化も適用される。

別の簡素な例として、例示の目的で、以下の小さなテーブルを使用する。実際には、そのような小さいテーブルは、一般的には上述の圧縮の範囲には含まれないが、それは、そのようなテーブルの圧縮による利得にはそれほど価値が無いためである。また、そのような小さなテーブルが、一般的には含まれないのは、圧縮が、符号化が実行された後に生じ、一実施形態においては、値そのものではなくデータ識別（ＩＤ）と共に連動するからである。従って行番号の列が例示のために追加される。

列全体に渡って、バケット化処理が、セグメントデータにおいて最も大きな空間をとる１つの値を発見することにより開始される。図１３および１４に関連して上記で触れたように、これは、各列の１つのヒストグラムの統計値を使用して行われ、例えば、以下の通りである。

この値が一度選択されると、セグメント内の行は論理的に記録され、この値の全ての出現が連続して生じるようにされ、ＲＬＥのランの長さが最大化される。

一実施形態において、同一の行に属する全ての値は、各列セグメントにおいて同一のインデックスで存在し、例えば、ｃｏｌ１［３］およびｃｏｌ２［３］は両方とも第３の行に属する。これを確実にすることにより、同一の行内の値への効率的なランダムなアクセスが提供され、マッピングテーブルを介したそれぞれのアクセスに間接的であることによるコストがかからない。従って、グリーディなＲＬＥアルゴリズム、またはハイブリッドＲＬＥ・ビットパッキングアルゴリズムの適用についての現在記載している実施形態において、１つの列に値を並び替える際、これは他の列セグメント内の値が同様に並び替えられることを意味する。

上記の例において、ここでは２つのバケット、｛１，２，４，６，７｝および｛３，５｝が存在する。以上のように、本明細書において適用されるＲＬＥは、グリーディなアルゴリズムであり、これは、アルゴリズムが、各段階において大域的最適性を発見するという望みを持って、局所最適性を選択するという問題解決のメタヒューリスティックに従うということを意味する。最大のバケットを発見するという第１のフェーズの後、次のフェーズは、次に最大のバケットを選択し、そのバケット内で処理を繰り返すことである。

今度は、３つのバケット｛２，７｝、｛１，４，６｝、｛３，５｝があり、行がそれに従って再組織化される。最大のバケットは、２番目のものであるが、そこには繰り返す値は無い。１番目のバケットは、全ての列がＲＬＥのランを有し、残りの値が一意的であり、さらなるＲＬＥの利得がＣｏｌ１内には無いということが分かる。｛３，５｝バケットを考慮に入れると、別の値１２３１が存在し、これをＲＬＥに変換することが可能である。興味深いことに、１２３１は、前のバケットにも現れており、そのバケットを並べ替えて、１２３１を一番下にして、次のバケットの先頭と統合させるようにすることが可能である。次の工程は以下のようになる。

上記の例において、ここでは４つのバケット｛２，７｝、｛６，４｝、｛１｝、｛３，５｝が存在する。さらにデータを削減することはできないため、処理は、セグメントデータの再組織化という次のフェーズに進む。

例示では最上部で行を同様に並べ替えたが、性能上の理由で、バケットの判定は、各列セグメント内のデータを並べ替えるという動作から、純粋に統計に基づくことが可能である。各列セグメント内のデータを並べ替える動作では、ジョブスケジューラを使用して利用可能なコアに基づき並列化することが可能である。

以上のように、上述の技術を、小さなデータセット使用することは実用的ではない。顧客のデータセットでは、上述の技術は度々数万の工程を経るが、これには時間がかかり得る。アルゴリズムのグリーディな性質のため、空間のセービングの大半は、最初の数工程で生じる。最初の数千の工程において、セービングされるであろうほとんどの空間が、既にセービングされている。しかし、圧縮データのスキャン側では分かるように、パッキングされた列におけるＲＬＥの存在により、クエリ時の大幅なパフォーマンスブーストが与えられ、わずかな圧縮の利得でさえもクエリ時の恩恵を受ける。

１つのセグメントは一度に処理されるため、複数のコアを使用して、データソースからセグメントへのデータの読み込みにかかる時間を、前のセグメントの圧縮にかかる時間に重複させることができる。従来の技術では、リレーショナルデータベースから１０万行／秒のレートで読み込むと、８００万行のセグメントには８０秒かかり、これは、そのような作業で利用可能なかなりの時間量である。選択的に、一実施形態において、前のセグメントのパッキングは、次のセグメントのデータが利用可能になると停止させることができる。

＜列ベースデータの符号化の処理＞
以上のように、列ベースの符号化の種々の実施形態に従ってデータを組織化する方法は、それ自体が、データを消費する側において効率的なスキャンに適しており、そこでは、処理を、メモリ内の選択された数の列に対して非常に速く実行させることが可能である。上述のデータパッキングおよび圧縮の技術は、行の符号化時における圧縮のフェーズを更新し、一方で、スキャニングには、インテリジェント符号化を利用するクエリオプイティマイザ・プロセッサが含まれる。

スキャンまたはクエリの機構を使用して、ビジネスインテリジェンス（ＢＩ）のクエリに効率的に結果を戻すことが可能であり、また、スキャンまたはクエリの機構は、上述のデータパッキングおよび圧縮の技術により作られるクラスタ化されたレイアウトのために設計され、かつ、拡大するＲＬＥの使用に対して最適化され、例えば、クエリ処理の間に、クエリに使用される有意な数の列がＲＬＥを使用して圧縮されることが期待される。加えて、高速のスキャン処理により、列ストアへの行型のクエリプロセッサの代わりに、列指向のクエリエンジンが導入される。そのため、ビットパックデータ（ＲＬＥデータに対して）を含むバケットでも、データ局所性による性能の利得は、かなりものとなり得る。

上述のデータパッキングおよび圧縮の技術ならびに効率的なスキャニングを導入することに加えて、以下のことを、高度に効率的な様式でサポートすることができる。すなわち、クエリでの「ＯＲ」スライス、および、関係が指定されている複数のテーブル間での「Ｊｏｉｎ」である。

上記で示唆したように、スキャニングの機構では、セグメントがセグメント全体に渡るバケットを含み、かつ、図１９に示すように「純粋」なＲＬＥのランまたは「非純粋」な他のビットパックストレージ内の列の値を含むこととされる。

一実施形態において、スキャニングは、セグメントにかけられ、キーは一度に１つのバケットに働く。バケット内では、スキャニング処理が、クエリ指定に応じて、列指向の処理を段階的に実行する。第１のフェーズは、どの列領域が純粋で、どの領域が非純粋であるかについて統計値を集めることである。次に、フィルタ処理が行われ、Ｇｒｏｕｐ Ｂｙ操作、プロキシ列の処理、と続く。次に、集計処理が別のフェーズとして行われる。

上記で触れたように、本明細書に示されるスキャニングの実施形態では、従来のシステムのような行指向ではなく、列指向のクエリ処理が実装されることに留意すべきである。従って、これらのフェーズそれぞれに対して、実行される実際のコードは、（１）操作されている列がランレングス符号化されているか否か、（２）ビットパッキングに使用される圧縮のタイプ、（３）結果が薄いか濃いか、等に対して特定させることができる。Ａｇｇｒｅｇａｔｉｏｎ句については、追加的に（１）符号化のタイプ（ハッシュまたは値）、（２）集計関数（ｓｕｍ／ｍｉｎ／ｍａｘ／ｃｏｕｎｔ）等、が考慮される。

一般に、スキャニング処理は図２１の形式に従い、種々の標準のクエリ／スキャン操作２１００からのクエリの結果は全バケット行の関数である。クエリ／スキャン操作２１００は、実際には数学的に分割可能であり、フィルタ、Ｇｒｏｕｐ Ｂｙ、プロキシ列、および集計を、お互いに別々に段階的に処理することができる。

これに関して、処理工程のそれぞれについて、２１１０にて、演算子が、バケット移動処理に応じてバケットの異なる純粋度に従って処理される。その結果、全てのバケット行に対する一般化された高価なスキャンではなく、本明細書に記載される符号化および圧縮のアルゴリズムの働きによりもたらされた、異なるバケットに特化することで、その結果が、純粋バケット、シングル非純粋バケット、ダブル非純粋バケット等を処理した集約結果となる。

図２４は、バケットのサンプルの分散および圧縮アーキテクチャの力を示し、純粋バケットに実行される処理が、処理の計算を削減して操作が簡素になったことにより最も早く、続いて、２番目に速いシングル非純粋バケットが続き、追加の非純粋バケットが同様に続く。さらに、驚くほど大量のバケットが純粋であることが分かる。例えば、図２５に示すように、クエリに関連する６列について、各列が約９０％の純粋度を有する場合（値の約９０％の意味は、同様のデータによるランレングス符号化で表される）、約６０％のバケットが純粋であり、約１／３がシングル非純粋、約８％がダブル非純粋であり、残りはほんの１％である。純粋バケットの処理が一番速く、かつ、シングル非純粋バケットおよびダブル非純粋バケットの処理もかなり速いため、３個またはそれ以上の非純粋領域を有するバケットの「より複雑な」処理が、最小限度に維持される。

図２３は、サンプルクエリ２３００を示し、サンプルの「ｆｉｌｔｅｒ ｂｙ ｃｏｌｕｍｎ」クエリビルディングブロック２３０２、サンプルの「Ｇｒｏｕｐ ｂｙ Ｃｏｌｕｍｎ」クエリビルディングブロック２３０４、および、サンプルの「Ａｇｇｒｅｇａｔｅ ｂｙ Ｃｏｌｕｍｎ」クエリビルディングブロック２３０６等の、いくつかのサンプルの標準クエリビルディングブロックが示される。

図２４は、列選択性を介した帯域幅削減の追加の態様を例示するブロック図である。サンプルクエリ２４００を精査すると、全列２４２０のうちわずか６列２４１０のみが関係しており、従って、高度に効率的なクエリに対して６列のみがローカルＲＡＭにロードされれば良いことが分かる。

種々の実施形態が本明細書に記載された。図２５には、データ符号化の実施形態が例示され、２５００にて、データの異なるデータフィールドに対応する値の列ベースシーケンスの組に従って、データを組織化することが含まれる。次に、２５１０にて、値の列ベースシーケンスの組が、辞書符号化および／または値符号化等の少なくとも１つの符号化アルゴリズムに従って、値の列ベースの整数シーケンスの組に変換される。次に、２５２０にて、列ベースの整数のシーケンスの組が、列ベースの整数のシーケンスの組全体に渡って適用されるグリーディなランレングス符号化アルゴリズム、またはビットパッキングアルゴリズム、または、ランレングス符号化とビットパッキングの組み合わせ、を含む少なくとも１つの圧縮アルゴリズムに従って、圧縮される。

一実施形態において、整数のシーケンスを分析して、ランレングス符号化（ＲＬＥ）圧縮またはビットパッキング圧縮を適用するかどうかを判定するが、これには、ビットパッキング圧縮と比較したＲＬＥ圧縮のビットセービングを分析して、最大のビットセービングが達成される場所を判定することが含まれる。この処理には、ヒストグラムを生成して、最大のビットセービングが達成される場所の判定を支援することを含むことができる。

別の実施形態において、図２６に示すように、ビットパッキング技術には、２６００にて、列のデータを表す値の整数のシーケンスの一部を受け取ること、および、ビットパッキングによる潜在的な削減の３つの段階が含まれる。２６１０にて、データフィールドを表すのに必要なビット数に基づき、データを削減することができる。２６２０にて、整数のシーケンスの一部の値全体に渡って任意の共有される数値の累乗を削除することにより、データを削減することができる。２６３０にて、ある範囲に及ぶ整数のシーケンスの一部の値をオフセットすることにより、データを削減することもできる。

別の実施形態において、図２７のフロー図に示すように、クエリに応答して、２７００にて、データのサブセットを、そのデータの異なる列に対応する、値の整数の符号化・圧縮シーケンスとして検索する。次に、２７１０にて、処理バケットは、データのサブセットの値の整数の符号化・圧縮シーケンス内のいずれかで生じる圧縮タイプの変更に基づき、データのサブセット全体に及ぶものと定義される。次に、２７２０にて、クエリ操作は、効率的なクエリ処理のために、処理されている現在のバケットのタイプに基づき実行される。操作はメモリ内で実行され、マルチコアアーキテクチャで並列化することができる。

異なるバケットに含まれるものは、（１）純粋バケットを定義する、シーケンス全体に渡るバケット内の値の異なる部分が、ランレングス符号化圧縮に従って全て圧縮されている場所、（２）シングル非純粋バケットを定義する、ランレングス符号化に従って圧縮された１つの部分を除く全て、または、（３）ダブル非純粋バケットを定義する、ランレングス符号化に従って圧縮された２つの部分を除く全て、である。

改善されたスキャニングでは、様々な標準クエリおよびスキャン演算子を、特に最も純粋なバケットに対して、さらに効率的に実行することが可能にされる。例えば、論理ＯＲクエリのスライス操作、関係が指定されている複数のテーブル間でのクエリのｊｏｉｎ操作、ｆｉｌｔｅｒ操作、Ｇｒｏｕｐ Ｂｙ操作、プロキシ列操作、またはａｇｇｒｅｇａｔｉｏｎ操作は全て、バケット移動の技術が適用され、かつ、処理がバケットタイプに基づき実行される場合は、より効率的に実行することができる。

＜例示のネットワーク化分散環境＞
当業者は、理解するであろうが、本明細書に記載される列ベースの符号化およびクエリ処理の種々の実施形態は、任意のコンピュータまたは他のクライアントデバイスもしくはサーバデバイスに関連して実装可能であり、これらはコンピュータネットワークの一部として、または、分散コンピュータ環境において展開可能であり、かつ、任意の種類のデータストアに接続可能である。これに関して、本明細書に記載される種々の実施形態は、任意の数のメモリまたは記憶装置、ならびに、任意の数のアプリケーションおよび任意の数の記憶装置に渡って起こる処理を有する、任意のコンピュータシステムまたは環境において実装可能である。これには、ネットワーク環境または分散コンピュータ環境において展開される、サーバコンピュータおよびクライアントコンピュータを有し、リモートまたはローカルなストレージを持つ環境、が含まれるが、これに限定されない。

分散コンピューティングでは、コンピュータデバイスおよびコンピュータシステムにおける通信可能な交換により、コンピュータリソースおよびサービスが共有される。これらのリソースおよびサービスには、情報の交換、キャッシュストレージ、および、ファイル等のオブジェクトのディスクストレージ、が含まれる。これらのリソースおよびサービスにはまた、ロードバランシング、リソースの拡大、処理の特化等のための、複数の処理ユニットに渡る処理能力の共有が含まれる。分散コンピューティングでは、ネットワーク接続性を利用して、クライアントの能力を集結させてクライアントに利用させ、企業に利益を与えることができる。これに関して、様々なデバイスが、主題開示の種々の実施形態のいずれかの１つまたは複数の態様を実行すべく協働することができるアプリケーション、オブジェクト、またはリソースを有することができる。

図２８は、例示のネットワーク化または分散コンピュータ環境の概略ブロック図を提供する。分散コンピュータ環境には、コンピュータオブジェクト２８１０、２８１２、等、およびコンピュータオブジェクトまたはコンピュータデバイス２８２０、２８２２、２８２４、２８２６、２８２８等が含まれ、これには、アプリケーション２８３０、２８３２、２８３４、２８３６、２８３８により表されるような、プログラム、メソッド、データストア、プログラム可能論理等を含むことができる。オブジェクト２８１０、２８１２等およびコンピュータオブジェクトまたはコンピュータデバイス２８２０、２８２２、２８２４、２８２６、２８２８等は、ＰＤＡ、音声／映像デバイス、携帯電話、ＭＰ３プレイヤ、パーソナルコンピュータ、ラップトップ等の異なるデバイスを含むことができることは理解できるであろう。

各オブジェクト２８１０、２８１２等、およびコンピュータオブジェクトまたはコンピュータデバイス２８２０、２８２２、２８２４、２８２６、２８２８等は、１つまたは複数の他のオブジェクト２８１０、２８１２等、およびコンピュータオブジェクトまたはコンピュータデバイス２８２０、２８２２、２８２４、２８２６、２８２８等と、通信ネットワーク２８４０を介して、直接または間接的に通信することができる。図２８には１つの要素として例示されるが、ネットワーク２８４０は、図２８のシステムにサービスを提供する他のコンピュータオブジェクトおよびコンピュータデバイスを含むことができ、および／または、図示されない、複数の相互接続するネットワークを表すことができる。各オブジェクト２８１０、２８１２等、または２８２０、２８２２、２８２４、２８２６、２８２８等はまた、アプリケーション２８３０、２８３２、２８３４、２８３６、２８３８等の、ＡＰＩを使用することができるアプリケーション、または、主題開示の種々の実施形態に従って提供される列ベースの符号化およびクエリ処理の、通信、処理、または実装、に適切な他のオブジェクト、ソフトウェア、ファームウェアおよび／またはハードウェア、を含むこともできる。

分散コンピュータ環境を支援する、様々なシステム、コンポーネント、および、ネットワーク構成がある。例えば、コンピュータシステムは、ローカルネットワークまたは広く分散したネットワークで、有線または無線のシステムにより、一緒に接続することができる。現在、多くのネットワークがインターネットに連結され、インターネットにより、広く分散したコンピューティングにインフラストラクチャが提供され、かつ、多くの異なるネットワークが包含されるが、任意のネットワークインフラストラクチャを、種々の実施形態において記載されるような列ベースの符号化およびクエリ処理に付随する例示の通信に使用することが可能である。

従って、クライアント／サーバ、ピアツーピア、またはハイブリッドなアーキテクチャ等の、ネットワークトポロジとネットワークインフラストラクチャのホスト、を利用することが可能である。「クライアント」は、自身が関連しないクラスまたはグループのサービスを使用するクラスまたはグループの構成要素である。クライアントは、別のプログラムまたは処理により提供されるサービスを要求する、処理、すなわち、概略的には命令またはタスクの組とすることができる。クライアントの処理は、他のプログラムまたはサービスそのものについての任意の動作の詳細を「知る」必要なく、要求されたサービスを利用する。

クライアント／サーバアーキテクチャ、特に、ネットワーク化されたシステムにおいて、クライアントは、通常、別のコンピュータ、例えば、サーバ、により提供される、共有ネットワークリソースにアクセスするコンピュータである。図２８の例示では、非限定的な例として、コンピュータ２８２０、２８２２、２８２４、２８２６、２８２８等が、クライアントであると考えられ、コンピュータ２８１０、２８１２等が、サーバであると考えられ、サーバ２８１０、２８１２等は、クライアントコンピュータ２８２０、２８２２、２８２４、２８２６、２８２８等からのデータの受信、データの記憶、データの処理、クライアントコンピュータ２８２０、２８２２、２８２４、２８２６、２８２８等へのデータの伝送、等のデータサービスを提供するが、任意のコンピュータを、状況に応じて、クライアント、サーバ、または両方と見なすことができる。これらのコンピュータデバイスの任意のものが、データの処理、データの符号化、データのクエリ、または、１つまたは複数の実施形態に対して本明細書に記載されるような列ベースの符号化およびクエリ処理に関わるサービスまたはタスクの要求、を行っている。

サーバは、典型的には、インターネットまたは無線ネットワークインフラストラクチャ等のリモートまたはローカルのネットワークを介してアクセス可能な、リモートコンピュータシステムである。クライアントの処理は、第１のコンピュータシステムにおいてアクティブとすることができ、かつ、サーバの処理は、第２のコンピュータシステムにおいてアクティブとすることができ、クライアントとサーバは通信媒体を介してお互いに通信し、従って、分散された機能性が提供され、複数のクライアントがサーバの情報収集能力を利用することが可能にされる。列ベースの符号化およびクエリ処理に従って利用される任意のソフトウェアオブジェクトを、スタンドアロンで提供すること、または、複数のコンピュータデバイスまたはコンピュータオブジェクトに渡って分散させることができる。

通信ネットワーク／バス２８４０がインターネットであるネットワーク環境において、例えば、サーバ２８１０、２８１２等は、クライアント２８２０、２８２２、２８２４、２８２６、２８２８等が、ＨＴＴＰ（ｈｙｐｅｒｔｅｘｔ ｔｒａｎｓｆｅｒ ｐｒｏｔｏｃｏｌ）等の多くの既知のプロトコルのいずれかを介して通信する、ウェブサーバとすることができる。サーバ２８１０、２８１２等はまた、分散コンピュータ環境の特徴であるように、クライアント２８２０、２８２２、２８２４、２８２６、２８２８等として機能することもできる。
＜例示のコンピュータデバイス＞
以上のように、有利には、本明細書に記載される技術は、大量のデータを素早くクエリすることが望ましい任意のデバイスに適用することができる。従って、種々の実施形態に関連した使用に対して、すなわち、デバイスにより、速くかつ効率的な結果が得られるような膨大な量のデータのスキャンおよび処理が求められるどんな場合にでも、ハンドヘルド、携帯用、ならびに全ての種類の他のコンピュータデバイスおよびコンピュータオブジェクトが意図されることは理解すべきである。従って、以下で図２９に記載される以下の汎用のリモートコンピュータは、まさにコンピュータデバイスの一例である。

要求されていないが、実施形態は、デバイスまたはオブジェクトのサービスの開発者による使用のために、オペレーティングシステムを介して部分的に実装可能であり、および／または、本明細書に記載される種々の実施形態の１つまたは複数の機能的態様を実行するよう作動するアプリケーションソフトウェア内に含ませることができる。ソフトウェアは、プログラムモジュール等のコンピュータ実行可能命令の一般的コンテキストで記述することができ、クライアントワークステーション、サーバ、または他のデバイス等の１つまたは複数のコンピュータにより実行される。当業者は理解するであろうが、コンピュータシステムは、データを通信するために使用することができる様々な構成およびプロトコルを有し、従って、特定の構成またはプロトコルは、制限するものとしてみなされない。

従って、図２９は、本明細書に記載される実施形態の１つまたは態様を実装可能な、適切なコンピュータシステム環境２９００の例を例示し、上記において明らかにされたように、コンピュータシステム環境２９００は、適切なコンピュータ環境の単なる一例であり、使用または機能性の範囲について任意の制限を示唆することは意図されない。また、コンピュータ環境２９００は、例示の動作環境２９００に例示されるコンポーネントの任意の１つまたは組み合わせに関して、任意の依存性または要件を有するものとして解釈されるべきでもない。

図２９を参照すると、１つまたは複数の実施形態を実装するための例示のリモートデバイスには、コンピュータ２９１０の形式で汎用コンピュータデバイスが含まれる。コンピュータ２９１０のコンポーネントには、プロセシングユニット２９２０、システムメモリ２９３０、および、システムメモリを含む種々のシステムコンポーネントをプロセシングユニット２９２０に連結させるシステムバス２９２２、を含むことができるがこれに限定されない。

コンピュータ２９１０は典型的には、様々なコンピュータ可読媒体が含まれ、コンピュータ２９１０によりアクセス可能な任意の利用可能な媒体とすることができる。システムメモリ２９３０には、ＲＯＭ（ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ）および／またはＲＡＭ（ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）等の揮発性および／または不揮発性のメモリの形式で、コンピュータ記憶媒体を含むことができる。制限ではなく例として、メモリ２９３０にはまた、オペレーティングシステム、アプリケーションプログラム、他のプログラムモジュール、およびプログラムデータを含むことができる。

ユーザは、コマンドおよび情報を、入力デバイス２９４０を介してコンピュータ２９１０に入力することができる。モニタまたは他のタイプの表示デバイスもまた、出力インターフェース２９５０等のインターフェースを介してシステムバス２９２２に連結させることができる。モニタに加えて、コンピュータにはまた、スピーカおよびプリンタ等の他の周辺出力デバイスを含むこともでき、これらは出力インターフェース２９５０を介して接続させることができる。

コンピュータ２９１０は、リモートコンピュータ２９７０等の１つまたは複数の他のリモートコンピュータへの論理接続を使用して、ネットワーク化されたまたは分散環境において作動することができる。リモートコンピュータ２９７０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイスもしくは他の共通ネットワークノード、または任意の他のリモート媒体の消費デバイスもしくは伝送デバイス、とすることができ、かつ、コンピュータ２９１０に関して上記で記載した任意または全ての要素を含むことができる。図２９に示す論理接続には、ローカルエリアネットワーク（ＬＡＮ）またはワイドエリアネットワーク（ＷＡＮ）等のネットワーク２９７２が含まれるが、他のネットワーク／バスを含むこともできる。そのようなネットワーキング環境は、家庭、事務所、企業規模のコンピュータネットワーク、イントラネット、およびインターネットにおいては一般的なものである。

上記で触れたように、例示の実施形態が、種々のコンピュータデバイスおよびネットワークアーキテクチャと関連して記載されたが、根底にある概念は、大規模なデータを圧縮することまたは大規模なデータに渡ってクエリを処理することが望ましい、任意のネットワークシステム、および任意のコンピュータデバイスまたはシステムに適用することができる。

また、同一または同様の機能性を実装するための複数の方法があり、例えば、適切なＡＰＩ、ツールキット、ドライバコード、オペレーティングシステム、コントロール、スタンドアロンまたはダウンロード可能なソフトウェアオブジェクト等があり、これらは、アプリケーションおよびサービスが効率的な符号化およびクエリの技術を使用することを可能にする。従って、本明細書の実施形態は、ＡＰＩ（または他のソフトウェアオブジェクト）の観点から考えられ、また、列ベース符号化および／またはクエリ処理を提供するソフトウェアオブジェクトまたはハードウェアオブジェクトの観点からも同様に考えられる。従って、本明細書に記載される種々の実施形態は、全体的にハードウェアにおける態様、部分的にハードウェアかつ部分的にソフトウェアにおける態様、また同様にソフトウェアにおける態様、を有することができる。

「例示の」という単語は、本明細書において使用されて、例、事例、または例示としての役割を意味する。誤解を避けるために、本明細書に開示される主題は、そのような例によって制限されない。加えて、本明細書において「例示の」と記載される任意の態様または設計は、必ずしも他の態様または設計より好ましいまたは有利であるとは解釈されず、また、当業者に既知の同等の例示の構造および技術を排除することも意味されない。さらに、用語「含む」「有する」「含有する」および他の同様の単語が「発明を実施するための形態」または「請求の範囲」において使用される範囲で、誤解を避けるために、そのような用語が、任意の追加のまたは他の要素を排除せずに、公の遷移語としての用語「備える」と同様の様式で、包括的であることが意図される。

以上のように、本明細書に記載される種々の技術は、ハードウェアまたはソフトウェアと関連して実装することができ、または、適切な場合には、その両方の組み合わせと関連して実装することができる。本明細書で使用される時、用語「コンポーネント」「システム」等は同様に、コンピュータ関連のエンティティ、あるいは、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェア、に言及していることが意図される。例えば、コンポーネントは、プロセッサ上で稼働中の処理、プロセッサ、オブジェクト、実行ファイル、実行のスレッド、プログラム、および／またはコンピュータとすることができるがこれに限定されない。例示として、コンピュータ上で実行中のアプリケーションとそのコンピュータの両方を、コンポーネントであるとすることができる。１つまたは複数のコンポーネントが、処理および／または実行のスレッド内に存在することができ、かつ、コンポーネントは、１つのコンピュータ上に配置、および／または、２つまたはそれ以上のコンピュータ間で分散されることが可能である。

前述のシステムは、いくつかのコンポーネント間の相互作用に関して記載された。理解されるであろうが、そのようなシステムおよびコンポーネントには、それらのコンポーネントまたは特定のサブコンポーネント、特定のコンポーネントまたはサブコンポーネントの内のいくつか、および／または、追加のコンポーネントを含むことができ、かつ、前述したものの種々の置き換えおよび組み合わせによる。サブコンポーネントはまた、親のコンポーネント（階層的な）内に含まれるのではなく、他のコンポーネントに通信可能に連結されるコンポーネントとして実装することもできる。加えて、１つまたは複数のコンポーネントが、集計機能を提供する単一のコンポーネントに組み合わされる、または、いくつかの別個のサブコンポーネントに分割されることもできること、また、任意の１つまたは複数の管理層等の中間層を提供して、統合された機能性を提供するためにそのようなサブコンポーネントと通信可能に連結させることができること、に留意すべきである。本明細書に記載される任意のコンポーネントはまた、本明細書に特には記載されないが、当業者には一般に既知である、１つまたは複数の他のコンポーネントと相互作用することができる。

上記に記載した例示のシステムを考慮して、記載される主題に従って実装される方法論は、種々の図面のフローチャートを参照することにより、より良く理解されるであろう。説明を簡単にする目的で、方法論が一連のブロックで示され記載されるが、請求される主題はブロックの順番により制限されず、いくつかのブロックが本明細書に示されかつ記載されるものとは異なる順番で、および／または他のブロックと同時に生じることがあることは、理解されるべきである。順次的でないまたは分岐したフローが、フローチャートを介して例示される場合、種々の他の分岐、フロー経路、およびブロックの順番が実装されて、それにより同一のまたは同様の結果が達成されるということが理解されるであろう。さらに、以下に記載される方法論の実装には、必ずしも例示される全てのブロックが必要とされるわけではない。

本明細書に記載される種々の実施形態に加えて、他の同様の実施形態を使用することが可能であり、または修正および追加が記載される実施形態に対してなされ、対応する実施形態から逸脱することなくそれと同一または同等の機能を実行することが可能であることは理解されるべきである。またさらに、複数の処理チップまたは複数のデバイスは、本明細書に記載される１つまたは複数の機能の性能を共有することが可能であり、かつ、同様に、ストレージが複数のデバイスに渡って達成され得る。従って、本発明は、任意の単一の実施形態に限定されるべきではなく、むしろ、添付の請求項に従う広さ、精神および範囲で解釈されるべきである。

Claims (20)

1. データを符号化する方法であって、
   データの異なるデータフィールドに対応する値の列ベースシーケンスの組に従って、前記データを組織化するステップ２１０と、
   少なくとも１つの符号化アルゴリズムに従って、前記値の列ベースシーケンスの組を、値の列ベースの整数シーケンスの組に変換するステップ２２０と、
   少なくとも１つの圧縮アルゴリズムに従って、前記列ベースの整数のシーケンスの組を圧縮するステップ２３０と
   を含むことを特徴とする方法。
2. 前記変換するステップ２２０が、データフィールドを整数値にマッピングする辞書符号化を介して、前記列ベースシーケンスの組を符号化するステップを含むことを特徴とする請求項１に記載の方法。
3. 前記変換するステップ２２０が、可逆的数学関数を前記データフィールドに適用してより少ないビットを使用して前記データフィールドを表す値符号化を介して、前記列ベースシーケンスの組を符号化するステップを含むことを特徴とする請求項２に記載の方法。
4. 前記圧縮するステップ２３０が、各符号化のステップにおいて最大のビットセービングが達成される場所に適用される、グリーディなランレングス符号化アルゴリズムで、圧縮するステップを含むことを特徴とする請求項１に記載の方法。
5. 前記圧縮するステップ２３０が、ヒストグラムを生成して前記最大のビットセービングが達成される場所の判定を支援するステップを含むことを特徴とする請求項４に記載の方法。
6. 前記圧縮するステップ２３０が、各圧縮のステップにおいてビットセービングを最大にしようと試みる少なくとも１つのグリーディな圧縮アルゴリズムに従って、前記列ベースの整数のシーケンスを圧縮するステップを含むことを特徴とする請求項１に記載の方法。
7. データを符号化する方法であって、
   データを値の整数のシーケンスに変換するステップ１２２０であって、各整数のシーケンスが前記データの異なる列の値を順次表す、ステップと、
   前記整数のシーケンスを分析して、ランレングス符号化（ＲＬＥ）圧縮またはビットパッキング圧縮を適用するかどうかを判定するステップ１７１０であって、ビットパッキング圧縮と比較したＲＬＥ圧縮のビットセービングを分析して最大のビットセービングが達成される場所を判定するステップが含まれる、ステップと
   を含むことを特徴とする方法。
8. 前記分析するステップに従って、前記最大のビットセービングが達成される場所で、データを圧縮するステップ１７２０をさらに含むことを特徴とする請求項７に記載の方法。
9. 前記分析するステップ１７１０および前記圧縮するステップ１７２０を繰り返し実行して、前記最大のビットセービングが達成される各ステップにおいて、圧縮を実行するステップをさらに含むことを特徴とする請求項８に記載の方法。
10. 前記分析するステップ１７１０が、前記整数のシーケンスの任意の部分のランレングス符号化圧縮から閾値セービングが得られるかどうか、を判定するステップを含むことを特徴とする請求項７に記載の方法。
11. 前記整数のシーケンスの任意の部分のランレングス符号化圧縮から前記閾値セービングが得られない場合、ビットパッキング圧縮１７２０を適用することを特徴とする請求項１０に記載の方法。
12. データを符号化する方法であって、
    データを値の整数のシーケンスに変換するステップ２５１０であって、各整数のシーケンスが前記データの異なるフィールドの値を順次表す、ステップと、
    前記整数のシーケンスを分析して、ランレングス符号化（ＲＬＥ）圧縮またはビットパッキング圧縮を適用するかどうかを判定するステップ２５２０であって、列全体に渡って定義されるグループに対するビットパッキング圧縮と比較したＲＬＥ圧縮のビットセービングを分析するステップが含まれ、分析するステップには、前記整数のシーケンスの値に対してヒストグラムを生成して最大のビットセービングを優先させるステップが含まれる、ステップと
    を含むことを特徴とする方法。
13. 受け取られた生データを、前記生データの異なるフィールドまたは列に対応するシリアル化された値の組として組織化して、データのカラム化されたシーケンスを形成するための、組織化コンポーネント１１１０と、
    辞書符号化または値符号化の少なくとも１つを実行して、前記データのカラム化されたシーケンスを整数のシーケンスとして均一に表す、データ符号化コンポーネント１１２０または１１３０と、
    どの整数シーケンスのどの部分に次に圧縮を実行するか、および、圧縮を、繰り返される値をランとして表すランレングス符号化（ＲＬＥ）で、または、一部分を表すために使用されるビット数を最小化することを試みるビットパッキングアルゴリズムで、実行するかどうかを判定し、前記整数のシーケンスに対して定義される各部分に、ビットパッキングに対するＲＬＥの性能測定基準を分析することを含む、圧縮コンポーネント１１４０と
    を含むことを特徴とするエンコーダ。
14. 前記圧縮コンポーネント１１４０は、ＲＬＥを実行する時に列を並べ替えることを特徴とする請求項１３に記載のエンコーダ。
15. 値符号化を実行する前記データ符号化コンポーネント１１３０は、各データフィールド内の繰り返される数字を除去することにより前記整数のシーケンスを削減すること、または、数学関数を介して浮動小数値を整数値に変換することにより前記整数のシーケンスを削減すること、の少なくとも一方を行うことを特徴とする請求項１３に記載のエンコーダ。
16. データを符号化する方法であって、
    データの列を表す値の整数のシーケンスの少なくとも一部を受け取るステップ２６００と、
    前記整数のシーケンスの前記少なくとも一部に使用する最小ビット数を判定することに基づき、各整数を表すのに使用するビット数を削減するステップ２６１０と、
    前記整数のシーケンスの前記少なくとも一部の値全体に渡って任意の共有される数値の累乗を削除するステップ２６２０と、
    ある範囲に及ぶ前記整数のシーケンスの前記少なくとも一部の値をオフセットするステップ２６３０であって、ビット数を削減するステップをさらに含む、ステップと
    を含むことを特徴とする方法。
17. ランレングス符号化の適用によるトータルビットセービングが、ビットパッキングの適用によるトータルビットセービングを超える場所に、代替えとしてランレングス符号化を実行するステップ１７１０をさらに含むことを特徴とする請求項１６に記載の方法。
18. ランレングス符号化の適用によるトータルビットセービングが、ビットパッキングの適用による閾値トータルビットセービングを超える場所に、代替えとしてランレングス符号化を実行するステップ１７１０をさらに含むことを特徴とする請求項１６に記載の方法。
19. 請求項１６の方法を実行するコンピュータ実行可能命令を含むコンピュータ可読媒体。
20. 請求項１６の方法を実行する手段を備える符号化装置。

Images