(57)【要約】計算システムにおいてデータの格納および検索を実現する方法および機構が開示される。データ圧縮は、データベースブロック内で重複する値を減少または消去することにより格納データに対して実行される。重複データ値をデータ格納単位に書込むのでなく、ディスク上のデータは、シンボル表に格納された各々の重複データ値のコピーを参照するように構成される。さらに、データベース問合せ言語文の性能を向上させる方法および機構が開示される。データブロック内のデータ重複を記述する情報が維持される。一実施例において、データブロック内のデータに対してのデータベース問合せ言語文が受取られたときに、データ重複情報は、データブロック内のデータに対する述語評価の回数を少なくするために用いられる。別の実施例においては、データ重複情報は、データベース問合せ言語文によりアクセスされるデータの量を少なくするために用いられる。
2005531051.tif 000002
【特許請求の範囲】
【請求項１】
データを圧縮されたフォーマットで格納する方法であって、
ディスク上にある１つ以上のデータベースブロックにデータを格納する要求を受取るステップと、
冗長データ項目の存在を判断するために前記データを分析するステップと、
前記冗長データ項目を格納するためのシンボル構造を作成するステップと、
前記データに対応してディスク上のデータ構造をフォーマット付けするステップと、
前記ディスク上のデータ構造を、前記シンボル構造に格納された前記冗長データ項目への参照に関連付けるステップとを含み、前記ディスク上のデータ構造は、前記冗長データ項目のコピーを明示的に含まない、方法。
【請求項２】
前記シンボル構造に格納された前記冗長データ項目を参照するためにリンクまたはポインタが用いられる、請求項１に記載の方法。
【請求項３】
前記データは、１つ以上の行を有するリレーショナルデータを含む、請求項１に記載の方法。
【請求項４】
各々の行はインラインに処理される、請求項３に記載の方法。
【請求項５】
一群の行がオフラインで処理される、請求項３に記載の方法。
【請求項６】
前記データは、冗長データ項目がある可能性が増加するように再編成される、請求項１に記載の方法。
【請求項７】
前記データの濃度が再編成において考慮される、請求項６に記載の方法。
【請求項８】
前記シンボル構造は、前記シンボル構造内の他のエントリを再帰的に参照するエントリを含む、請求項１に記載の方法。
【請求項９】
前記エントリは、前記シンボル構造内の多数の他のエントリを参照する、請求項８に記載の方法。
【請求項１０】
前記エントリは、格納された前記冗長データ項目と、前記シンボル構造内の他のエントリを再帰的に参照するエントリとの両方を含む、請求項８に記載の方法。
【請求項１１】
前記シンボル構造内の他のエントリを再帰的に参照するエントリに関連付けられた第２のディスク上のデータ構造を含む、請求項８に記載の方法。
【請求項１２】
さらに、前記シンボル構造内の他のエントリを再帰的に参照する前記エントリへの参照に、前記ディスク上のデータ構造内の多数のフィールドがひとまとめで関連付けられる、第２のディスク上のデータ構造を含む、請求項８に記載の方法。
【請求項１３】
データの列は再順序付けされる、請求項１２に記載の方法。
【請求項１４】
前記データの列は、前記ディスク上のデータ構造内の前記多数のフィールドについて繰返す並びがある可能性が増加するように再順序付けされる、請求項１３に記載の方法。
【請求項１５】
列の再順序付けは前記データベースブロックのレベルで実行される、請求項１２に記載の方法。
【請求項１６】
後端のＮＵＬＬ値が前記ディスク上のデータ構造内に含まれない、請求項１３に記載の方法。
【請求項１７】
前記データベースブロックは圧縮が適用されているかどうかを標示するメタデータを含む、請求項１に記載の方法。
【請求項１８】
前記メタデータは単一のビットを含む、請求項１７に記載の方法。
【請求項１９】
前記データベースブロックは、列が再順序付けされているかどうかを標示するメタデータを含む、請求項１に記載の方法。
【請求項２０】
圧縮されたフォーマットで格納されたデータを検索する方法であって、
ディスク上にある１つ以上のデータベースブロックからデータを検索する要求を受取るステップと、
アクセスされるべき前記１つ以上のデータブロックを判断するために前記要求を分析するステップと、
圧縮が適用されているかどうかを判断するために前記１つ以上のデータベースブロックを分析するステップと、
前記データに対応するディスク上のデータ構造を検索するステップと、
前記ディスク上のデータ構造により参照される冗長データ項目について、前記冗長データ項目をシンボル構造から検索するステップとを含む、方法。
【請求項２１】
前記シンボル構造に格納された前記冗長データ項目を参照するためにリンクまたはポインタが用いられる、請求項２０に記載の方法。
【請求項２２】
前記データは、１つ以上の行を有するリレーショナルデータを含む、請求項２０に記載の方法。
【請求項２３】
前記シンボル構造は、前記シンボル構造内の他のエントリを再帰的に参照するエントリを含む、請求項２０に記載の方法。
【請求項２４】
前記エントリは、前記シンボル構造内の多数の他のエントリを参照する、請求項２３に記載の方法。
【請求項２５】
前記エントリは、格納された前記冗長データ項目と、前記シンボル構造内の他のエントリを再帰的に参照するエントリとの両方を含む、請求項２３に記載の方法。
【請求項２６】
前記シンボル構造内の他のエントリを再帰的に参照するエントリに関連付けられた第２のディスク上のデータ構造を検索するステップを含む、請求項２３に記載の方法。
【請求項２７】
さらに、前記シンボル構造内の他のエントリを再帰的に参照する前記エントリへの参照に、前記ディスク上のデータ構造内の多数のフィールドがひとまとめで関連付けられる、第２のディスク上のデータ構造を検索するステップを含む、請求項２３に記載の方法。
【請求項２８】
以前に除去された後端のＮＵＬＬ値が再構築される、請求項２０に記載の方法。
【請求項２９】
データを格納する方法であって、
データを格納する要求を受取るステップを含み、前記データは複数の列を含み、前記方法はさらに、
後端のＮＵＬＬ値がある可能性が増加するように前記複数の列を再順序付けするステップと、
前記データの格納バージョンを作成するステップとを含み、前記データの前記格納バージョンは前記後端のＮＵＬＬ値を含まない、方法。
【請求項３０】
前記データの前記格納バージョンがディスクに書込まれる、請求項２９に記載の方法。
【請求項３１】
さらに、前記後端のＮＵＬＬ値が前記格納バージョンに含まれていないことを標示するメタデータを作成する動作を含む、請求項２９に記載の方法。
【請求項３２】
データベースブロックにデータを格納するための構造であって、
冗長データ項目をディスクに格納するためのシンボル構造と、
ディスク上にあり、前記シンボル構造内の前記冗長データ項目への参照を含む、ディスク上のデータ構造とを含む、構造。
【請求項３３】
前記シンボル構造に格納された前記冗長データ項目を参照するためにリンクまたはポインタが用いられる、請求項３２に記載の構造。
【請求項３４】
前記データは、１つ以上の行を有するリレーショナルデータを含む、請求項３２に記載の構造。
【請求項３５】
前記シンボル構造は、前記シンボル構造内の他のエントリを再帰的に参照するエントリを含む、請求項３２に記載の構造。
【請求項３６】
前記エントリは、前記シンボル構造内の多数の他のエントリを参照する、請求項３５に記載の構造。
【請求項３７】
前記エントリは、格納された前記冗長データ項目と、前記シンボル構造内の他のエントリを再帰的に参照するエントリとの両方を含む、請求項３５に記載の構造。
【請求項３８】
前記シンボル構造内の他のエントリを再帰的に参照するエントリに関連付けられた第２のディスク上のデータ構造を含む、請求項３５に記載の構造。
【請求項３９】
さらに、前記シンボル構造内の他のエントリを再帰的に参照する前記エントリへの参照に、前記ディスク上のデータ構造内の多数のフィールドがひとまとめで関連付けられる、第２のディスク上のデータ構造を含む、請求項３５に記載の構造。
【請求項４０】
データの列が再順序付けされる、請求項３２に記載の構造。
【請求項４１】
前記データの列は、前記ディスク上のデータ構造内の前記多数のフィールドについて繰返す並びがある可能性が増加するように再順序付けされる、請求項４０に記載の構造。
【請求項４２】
後端のＮＵＬＬ値が前記ディスク上のデータ構造に含まれない、請求項３２に記載の構造。
【請求項４３】
前記データベースブロックは、圧縮が適用されているかどうかを標示するメタデータを含む、請求項３２に記載の構造。
【請求項４４】
前記メタデータは単一のビットを含む、請求項４３に記載の構造。
【請求項４５】
前記データベースブロックは、列が再順序付けされているかどうかを標示するメタデータを含む、請求項３２に記載の構造。
【請求項４６】
データベース問合せ言語文の性能を向上させる方法であって、
データブロック内のデータ重複を記述する情報を維持するステップと、
前記データブロック内のデータに対してのデータベース問合せ言語文を受取るステップとを含み、前記データベース問合せ言語文は少なくとも１つの述語を含み、前記方法はさらに、
前記データ重複情報を用いて前記データブロック内のデータに対する述語評価の回数を減少させるステップを含む、方法。
【請求項４７】
データブロック内のデータ重複を記述する情報を維持する前記ステップは、
前記データブロック内の１つ以上の重複データ値を識別するステップと、
前記１つ以上の重複データ値の各々についての出現数を算出するステップと、
前記１つ以上の重複データ値の各々と、対応する、前記重複データ値の出現数とを、シンボル構造のエントリに格納するステップとを含む、請求項４６に記載の方法。
【請求項４８】
データブロック内のデータ重複を記述する情報を維持する前記ステップはさらに、
前記データブロックから、前記１つ以上の重複データ値のうちの少なくとも１つについて１以上の出現を消去するステップと、
前記データブロックのうち消去された出現に対応する部分を、適当なシンボル構造エントリを参照するように構成するステップとを含む、請求項４７に記載の方法。
【請求項４９】
前記適当なシンボル構造エントリを参照するためにリンクまたはポインタが用いられる、請求項４８に記載の方法。
【請求項５０】
データブロック内のデータ重複を記述する情報を維持する前記ステップはさらに、前記重複データ値の出現が追加または削除されたときに前記１つ以上の重複データ値のうちの１つについての出現値を更新するステップを含む、請求項４７に記載の方法。
【請求項５１】
データブロック内のデータ重複を記述する情報を維持する前記ステップはさらに、シンボル構造エントリ内の前記重複データ値の出現数が０であるときに前記シンボル構造エントリを除去するステップを含む、請求項５０に記載の方法。
【請求項５２】
前記データブロック内のデータに対する述語評価の回数を減少させる前記ステップは、前記データブロック内の重複データ値に対して前記少なくとも１つの述語を多くとも１回評価するステップを含む、請求項４６に記載の方法。
【請求項５３】
前記データブロック内のデータに対する述語評価の回数を減少させる前記ステップは、
データ値に対して前記少なくとも１つの述語を評価する前に前記データブロック内の前記データ値の重複に対して前記少なくとも１つの述語が以前に評価されているかどうかを判断するステップと、
前記データ値の重複に対して前記少なくとも１つの述語が以前に評価されていたときに前記データ値の前記重複に対する前記少なくとも１つの述語についての以前の評価の結果を利用するステップと、
前記データ値の重複に対して前記少なくとも１つの述語が以前に評価されていなかったときに前記データ値に対して前記少なくとも１つの述語を評価するステップとを含む、請求項４６に記載の方法。
【請求項５４】
データ値の重複に対して前記少なくとも１つの述語が以前に評価されているかどうかを
判断する前記ステップは、前記データ値がコンテキストに現れるかどうかを検証するステップを含み、前記コンテキストは、前記少なくとも１つの述語が以前に評価された前記データブロック内の各々のデータ値と、対応する、前記以前の述語評価の結果とを格納する、請求項５３に記載の方法。
【請求項５５】
さらに、前記データ重複情報を用いて、前記データベース問合せ言語文によりアクセスされるデータの量を減少させるステップを含む、請求項４６に記載の方法。
【請求項５６】
前記データベース問合せ言語文によりアクセスされるデータの量を減少させる前記ステップは、
前記少なくとも１つの述語が真であると評価されることになる、前記データブロック内のデータ値の総数を算出するステップと、
カウンタを前記総数に等しくセットするステップと、
前記少なくとも１つの述語が真であると評価された、前記データブロック内のデータ値にアクセスされたときに、前記カウンタを減少させるステップと、
前記カウンタが０に等しくなるまで前記データブロック内のデータ値にアクセスするステップとを含む、請求項５５に記載の方法。
【請求項５７】
前記問合せによりアクセスされるデータの量を減少させる前記ステップは、前記データブロック内のデータ値にアクセスする代わりに前記データ重複情報を更新するステップを含む、請求項５５に記載の方法。
【請求項５８】
前記データ重複情報は前記データブロックに維持される、請求項４６に記載の方法。
【請求項５９】
コンピュータ読取可能媒体を含むコンピュータプログラム製品であって、前記コンピュータ読取可能媒体には、プロセッサにより実行されるとデータを圧縮されたフォーマットで格納するプロセスを前記プロセッサに実行させる命令シーケンスが格納され、前記プロセスは請求項１から請求項１９のいずれかに記載の動作を含む、コンピュータプログラム製品。
【請求項６０】
コンピュータ読取可能媒体を含むコンピュータプログラム製品であって、前記コンピュータ読取可能媒体には、プロセッサにより実行されると、圧縮されたフォーマットで格納されたデータを検索するプロセスを前記プロセッサに実行させる命令シーケンスが格納され、前記プロセスは請求項２０から請求項２８のいずれかに記載の動作を含む、コンピュータプログラム製品。
【請求項６１】
コンピュータ読取可能媒体を含むコンピュータプログラム製品であって、前記コンピュータ読取可能媒体には、プロセッサにより実行されると、データを格納するプロセスを前記プロセッサに実行させる命令シーケンスが格納され、前記プロセスは請求項２９から請求項３１のいずれかに記載の動作を含む、コンピュータプログラム製品。
【請求項６２】
コンピュータ読取可能媒体を含むコンピュータプログラム製品であって、前記コンピュータ読取可能媒体には、プロセッサにより実行されると、データベース問合せ言語文の性能を向上させるプロセスを前記プロセッサに実行させる命令シーケンスが格納され、前記プロセスは請求項４６から請求項５８のいずれかに記載の動作を含む、コンピュータプログラム製品。
【請求項６３】
請求項１から請求項１９のいずれかに記載の動作を実行するための手段を含む、データを圧縮されたフォーマットで格納するためのシステム。
【請求項６４】
請求項２０から請求項２８のいずれかに記載の動作を実行するための手段を含む、圧縮されたフォーマットで格納されたデータを検索するためのシステム。
【請求項６５】
請求項２９から請求項３１のいずれかに記載の動作を実行するための手段を含む、データを格納するためのシステム。
【請求項６６】
請求項４６から請求項５８のいずれかに記載の動作を実行するための手段を含む、データベース問合せ言語文の性能を向上させるためのシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
背景および概要
この発明はデータベース管理システムの分野に関する。より特定的には、この発明は、コンピュータシステムにおいてデータを格納および検索する方法および機構、ならびにデータベース問合せ言語文の性能を向上させる方法および機構に向けられている。
【背景技術】
【０００２】
現代の多くの企業および組織でより大量の情報にアクセスする必要性が高まるのに伴い、データベースおよびコンピュータシステムに格納する必要があるデータの量は増加している。大量の情報を格納するための経費の大部分は、データ格納システムの購入および維持にかかるコストに関するものである。この経費に鑑み、所与の量のデータを格納するのに必要な空間の量を減少させるための手法がいくつか提案されている。
【０００３】
多くの現代のコンピュータシステムにおいてデータの格納コストを減少させるために用いられる技術としてデータの圧縮がある。圧縮を実現させるための一般的な手法として、データをファイルの粒度で圧縮することが挙げられる。たとえば、Ｕｎｉｘ（登録商標）ベースのｇｚｉｐまたはＤＯＳベースのｚｉｐといった伝統的な圧縮手法においては、１つのファイル全体がこのファイルのよりコンパクトなバージョンへと圧縮される。しかしこの種の手法においては、１つのファイル全体が圧縮される場合、このファイルの一部を使用可能とするには、実際にはこのファイルのうち僅かな部分しかユーザが必要としていない場合ですらそのすべてまたは大部分を復元しなければならないという問題がある。これは特にデータベースシステムでのファイル圧縮において存在する問題である。データベースシステムにおいては、単一のデータベースファイルに大量のデータベースレコードが入っていることがあるが、どの時点においても個々のレコードのうち必要となるのは僅かな部分に過ぎないと考えられ得る。したがって、この圧縮または復元の粒度は、システムにおいてデータが使用およびアクセスを望まれる粒度に現実的に一致しないおそれがある。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、他の粒度で圧縮されると、その結果として格納での非効率性が生じるおそれがある。たとえば、「一度に１ページ（page-at-a-time）」圧縮手法のいくつかにおいては、異なるサイズの圧縮ページが物理ページ上に非効率的にマッピングされる場合がある。これに加え、伝統的な圧縮技術の多くにおいては、データサイズが圧縮後に増加することはないという保証すらない。
【０００５】
しかも、データの圧縮および復元という行為そのものが過剰な量のオーバーヘッドを消費するおそれがある。一般的に、このオーバーヘッドは、使用される特定の圧縮アルゴリズムや圧縮または復元されるデータの量に関係する。データベースシステムで情報を格納、検索または更新しようとするときにこのオーバーヘッドはかなりの待ち時間の一因となる場合がある。たとえば、いくつかの圧縮技術においては、圧縮されるデータとは別個の圧縮情報が格納される。したがって、単一の読出アクセスでもデータベース内の多数の場所にアクセスしなければならない場合があり、コストのかかる復元動作を実行しなければならない場合がある。
【０００６】
上述の待ち時間に関する諸問題や、圧縮の利得が必ずしも確実ではないという事情を考
慮すると、データベースまたはその他の種類の計算システムにおいて、圧縮における空間上の利益は必ずしもそれにかかる時間に見合うものではない。したがって、使用されるディスク空間の減少という効果をもたらすだけでなく、圧縮されたデータに対するデータベース問合せ言語文の性能に悪影響のない圧縮技術が必要とされている。
【課題を解決するための手段】
【０００７】
この発明は、圧縮されたフォーマットでデータを格納および検索する方法および機構を提供する。一実施例において、データ圧縮は、格納されたデータに対し、データブロックまたはその他の格納単位における重複したデータ値を減少または消去することによって実行される。別の実施例においては、データブロック内のデータ重複を記述する情報が維持される。この発明はさらに、データベース問合せ言語文の性能を向上させる方法および機構を提供する。一実施例において、維持されるデータ重複情報は、述語評価の回数を減少させるために維持および使用される。別の実施例では、データ重複情報は、データベース問合せ言語文によりアクセスされるデータの量を減少させるために使用される。
【０００８】
この発明の局面、目的および利点に関するより一層の詳細を、以下の詳細な説明、図面および特許請求の範囲において記載する。以上の一般的な記載および以下の詳細な記載はともに例示的かつ説明的なものであり、この発明の範囲について限定的であることを意図したものではない。
【発明を実施するための最良の形態】
【０００９】
添付の図面は、この発明のより一層の理解が可能となるよう含めたものであり、以下の詳細な説明とともにこの発明の原理を説明するためのものである。
【００１０】
詳細な説明
データ格納システムにおいてデータを格納および検索する方法が開示される。データをファイルレベルまたはその他の粒度で圧縮するといった、格納の非効率性および／またはデータベース問合せ言語文の実行時間の増加をもたらしかねない手法に代わって、データブロックまたはその他の格納単位において重複した値を減少または消去することによってデータ圧縮を達成する。さらに、データベース問合せ言語文の性能を向上させる方法が開示される。以前は、データブロック内で重複したデータはブロックのアクセスのたびに再計算される必要があったが、このデータ重複を記述する情報を維持することにより、このデータ重複情報を用いてデータベース問合せ言語文の性能を向上させることができる。
【００１１】
データベース問合せ言語文は、しばしば、データベース内のデータおよび構造を作成、探索、アクセス、検索、変更、編成、維持、操作、定義、制御、追加、および／または削除するために使用される。一般に普及しているデータベース問合せ言語の中では、構造化問合せ言語（ＳＱＬ）として知られるものがある。以下においては、限定としてではなく単に説明のため、具体的にＳＱＬに関するデータベース文を参照して説明を行なう。
【００１２】
この文書全体において用いられる「ディスク」または「ディスクシステム」という用語はデータ格納システムを指すものである。ここに開示される発明の概念はディスクを用いたシステム以外の種類の格納システムにも適用可能である。加えて、以下においてはデータベースにおけるリレーショナルデータの格納および検索に関して説明を行なうが、この発明は計算システムにおける他の種類および粒度のデータの管理にも適用可能であり、したがってリレーショナルデータの圧縮には限定されないことに注目されたい。
【００１３】
この発明の一実施例に従うと、特定のデータ格納単位内に格納されるべき１組のデータ内で重複した値の識別がなされる。これら重複データ値すべてをデータ格納単位に書込む代わりに、各々の重複データ値の１コピーを格納するためのシンボル表が作成される。重
複データ値についての各々の出現は、このシンボル表内の対応する重複データ値を参照するように構成される。
【００１４】
ここでの例示において、データ格納単位はデータブロックまたはディスクページとして示される。しかし、その他のデータ格納単位を採用することも可能である。一実施例においてデータブロックは自己完結型であり、たとえば或るデータブロック内で未圧縮のデータを再び作成するのに必要な情報は当該ブロック内で入手可能である。
【００１５】
図１は、ディスク１１２にあるブロック１１４に格納されるべきデータベース表１００を示す。表１００における各々の行は４列の情報を含み、これらの列は＜注文番号＞列１２０、＜顧客名＞列１２２、＜品目＞列１２４、および＜価格＞列１２６を含む。表１００には３行のデータを示す。行１０２ａにおいて、＜注文番号＞列１２０には値「１２５１」、＜顧客名＞列１２２には値「ジョー」、＜品目＞列１２４には値「本」、そして＜価格＞列１２６には値「１０」がある。行１０４ａにおいて、＜注文番号＞列１２０には値「１２５２」、＜顧客名＞列１２２には値「トム」、＜品目＞列１２４には値「本」、そして＜価格＞列１２６には値「１０」がある。行１０６ａにおいては、＜注文番号＞列１２０には値「１２５３」、＜顧客名＞列１２２には値「ジョー」、＜品目＞列１２４には値「テープ」、そして＜価格＞列１２６には値「２０」がある。
【００１６】
＜顧客名＞列１２２において、行１０２ａおよび１０６ａの両方で値「ジョー」が繰返されていることが注目される。また、＜品目＞列１２４においては行１０２ａおよび１０４ａで値「本」が繰返されている。＜価格＞列１２６においては行１０２ａおよび１０４ａで値「１０」が繰返されている。
【００１７】
各々の重複データ値を格納するためのシンボル表１１０が作成される。具体的に、重複値「ジョー」はシンボル表エントリ１３０に格納され、重複値「１０」はシンボル表エントリ１３２に格納され、そして重複値「本」はシンボル表エントリ１３４に格納される。
【００１８】
表１００の各行のデータがディスク１１２のブロック１１４に格納される際、繰返されるデータ値は再びディスクには書込まれず、各々の行のうち対応する部分は、ポインタまたはリンク構造を用いるなどして、正しいデータ値が入っているシンボル表１１０内の適当なシンボル表エントリを参照するように構成される。
【００１９】
説明のため、表１００の行１０２ａについて考察する。行１０２ａは、「１２５１」、「ジョー」、「本」および「１０」という列の値を含む。シンボル表１１０は、「ジョー」、「本」および「１０」という値についてのエントリを含むことが注目される。これらの値は表１００において行１０２ａに現われる重複データ値である。
【００２０】
行１０２ａがディスクに書込まれる際、一意である値「１２５１」のみが個別にディスクに書込まれる。これをディスク上の行構造１０２ｂにおいて示す。これは表１００における行１０２ａに対応するものである。ディスク上の行構造１０２ｂは、行１０２ａにおける＜注文番号＞列１２０に対応する第１の部分１４２を含み、これは一意のデータ値「１２５１」を含む。
【００２１】
重複するデータ値については、シンボル表１１０内の適当なエントリを指し示すためのポインタまたはリンクをディスク上の行構造の適当な部分に挿入することができる。ディスク上の行構造１０２ｂは、行１０２ａにおける＜顧客名＞列１２２に対応する部分１４４を含む。部分１４４は、行１０２ａの＜顧客名＞列１２２における重複データ値「ジョー」と一致するシンボル表エントリ１３０に対するポインタ１３６を含むように構成される。ディスク上の行構造１０２ｂはさらに、行１０２ａにおける＜品目＞列１２４に対応
する部分１４６を含む。部分１４６は、行１０２ａの＜品目＞列１２４における重複データ値「本」と一致するシンボル表エントリ１３４に対するポインタ１３８を含むように構成される。ディスク上の行構造１０２ｂはさらに、行１０２ａにおける＜価格＞列１２６に対応する部分１４８を含む。部分１４８は、行１０２ａの＜価格＞列１２６における重複データ値「１０」と一致するシンボル表エントリ１３２に対するポインタ１４０を含むように構成される。
【００２２】
表１００の行１０４ａおよび行１０６ａの各々は、ディスク１１２のブロック１１４に格納されるときに上記と同様に表現される。すなわち、表１００の行１０４ａはディスク上の行構造１０４ｂとしてディスクに書込まれる。行１０４ａの一意のデータ値、すなわち「１２５２」および「トム」はディスク上の行構造１０４ｂに個別に書込まれる。行１０４ａはまた、列１２４および列１２６に重複する行の値「本」および「１０」をそれぞれ含む。ディスク上の行構造１０４ｂのうち行１０４ａにおける列１２４に対応する部分１５０は、重複データ値「本」と一致するシンボル表１１０内のエントリ１３４に対するポインタ１５４を含むように構成される。ディスク上の行構造１０４ｂのうち行１０４ａにおける列１２６に対応する部分１５２は、重複データ値「１０」と一致するシンボル表１１０内のエントリ１３２に対するポインタ１５６を含むように構成される。
【００２３】
表１００の行１０６ａはディスク上の行構造１０６ｂとしてディスクに書込まれる。行１０６ａにおいて、一意のデータ値は「１２５３」、「テープ」および「２０」であり、これらは個別にディスク上の行構造１０６ｂに書込まれる。行１０６ａはさらに列１２２内に重複する行の値「ジョー」を含む。ディスク上の行構造１０６ｂのうち行１０６ａにおける列１２２に対応する部分１６０は、重複データ値「ジョー」と一致するシンボル表１１０内のエントリ１３０に対するポインタ１６２を含むように構成される。
【００２４】
図２は、データをディスクに格納するプロセスの一実施例のフローチャートを示す。２０２にて、データをディスクに格納する要求が受取られる。一実施例では、データが圧縮されるかどうかはユーザまたはシステムによって任意に選択されることである。圧縮が選択される場合、２０４にてデータが分析され、所与のデータブロック内に格納されるべきデータの各部分について繰返されるデータ値が識別される。識別されたデータ重複に基づき、重複データ値のいくつかまたはすべてを含むシンボル表が作成される（２０６）。その後、データブロック内における各々のディスク上の行構造が作成される。このディスク上の行構造は、重複データ値のいくつかまたはすべてを除外するようにフォーマット付けされる（２０８）。具体的には、重複データ値に関連したディスク上の行構造は、該当するデータ値を格納するシンボル表内の適当なエントリを参照するように構成される。
【００２５】
上記の圧縮手法がオフラインで実行される場合、行の分析およびフォーマット付けはバッチモードで実行され、このためデータベースブロックの内容全体がディスクへの書込前に予め編成される。オフラインで処理することにより、所与のデータブロックに適合する行の数を精度よく判断することが可能である。これに代えて、上記の圧縮手法をオンラインで実行することも可能であり、この場合、ディスク上の行構造は各々が個別に処理されてからディスクに書込まれる。いずれの場合においても、ブロックのメタデータは、ブロック内のデータまたはブロック内のデータの一部が圧縮されたかどうかを標示するように構成される。一実施例においては、ブロックのヘッダが、ブロックまたはブロック内データが圧縮されるかどうかを標示するデータ構造を含む。一実施例では、ブロック内データが圧縮されるかどうかを標示するには単一のビットで十分である。
【００２６】
別の実施例においては、データがデータブロックにロードされる際にデータを圧縮するのに代えて、圧縮されていないデータブロックを圧縮されたデータへと変換する。図９に示すように、データブロックが分析されて重複データ値が識別される（９００２）。識別
されたデータ重複に基づき、重複データ値のいくつかまたはすべてを含むシンボル表が作成される（９００４）。このシンボル表内のデータ値の重複のいくつかまたはすべてをデータブロックから除去または削除する（９００６）。次に、該当するデータ値を格納するシンボル表内の適当なエントリを参照するようにデータブロック内のディスク上の行構造が構成される（９００８）。
【００２７】
単一のブロック内でデータが繰返される可能性が低い場合、予想される圧縮比もまた低いことが見込まれる。このような繰返しがある可能性がもっと高い場合には予想される圧縮比は高くなる。したがって、このような繰返しがある可能性が高くなるように行を再編成する場合がある。これを単一の列の表について行なう方法として、表の行を列の値で順序付けるというものがある。これは、構造化問合せ言語（ＳＱＬ）においては、order by句で“CREATE TABLE AS SELECT”文を実行することによって達成され得る。この種の技術はまた、１本の列の濃度が低く他の列の濃度が高い表にも適用可能であり、この場合は低い濃度の列で表の行同士を順序付ける。
【００２８】
低い濃度の列が多数ある表の場合、より良好な圧縮比を達成するための調整は、まず最も低い濃度の列を決定することにより実行可能である。列の濃度は“SELECT COUNT(DISTINCT(c))from T；”文を実行することで決定され得る。最も低い濃度の列が一旦決定されると（これが列Ｃ１であると仮定する）、選ばれた列の固定値についての他の列の濃度が決定される。これはＣ１以外のすべての列ｃＫにつき“SELECT SUM(count(*)*COUNT(DISTINCT(cK)))from T group by C1;”文を実行することで測ることができる。列Ｃ２がこのような測度のうち最も低いものを有すると仮定する。すると、最初の２列が固定されるときに最も低い濃度の列が決定される。これはＣ１およびＣ２以外のすべての列ｃＫにつき“SELECT SUM(count(*)*COUNT(DISTINCT(cK)))from T group by C1, C2;”文を実行することで測ることができる。このプロセスを続けることで、いくつかの列並びＣ１，Ｃ２，…，Ｃｎを決定することになる。この並びは、create table compress文のORDERED BY句で列の並びとして使用され得る。
【００２９】
図３は、ディスクからデータを検索するプロセスの一実施例のフローチャートを示す。３０２にて、ディスクからデータを検索する要求が受取られる。３０４にて、求められている特定のブロックまたは行が識別される。動作３０４を実行するには従来のどのような索引付けまたは探索の技術を採用してもよい。３０６にて、該当するデータベースブロックが圧縮フォーマットで格納されているかどうかについての判断がなされる。一実施例ではこの判断を行なうためにブロックヘッダにアクセスがなされる。ブロックが圧縮されていなければ、要求されている行の情報が直ちにディスクから検索されて（３１０）要求側エンティティに返される（３１２）。ブロックが圧縮されていれば、要求されている行についての該当するディスク上の行構造にアクセスがなされてシンボル表から重複データ値が検索される（３０８）。これに加え、ディスク上の行構造から、個別に格納されたデータ値もまた検索される（３１０）。３１２にて、要求されたデータの完全な組が要求側エンティティに返される。
【００３０】
シンボル表においては再帰的シンボルエントリを用いる場合がある。再帰的シンボルエントリとは、シンボル表におけるエントリであって、それ自体が１つ以上の他のシンボル表エントリを参照するものである。図４は、再帰的シンボルエントリを用い、データブロックをフォーマット付けして図１の表１００を格納できるようにする過程を示す。図１のシンボル表１１０と同様、再帰的シンボル表４１０は、「ジョー」というデータ値を格納するエントリ４３０と、「１０」というデータ値を格納するエントリ４３２と、「本」というデータ値を格納するエントリ４３４とを含む。
【００３１】
図１のシンボル表１１０とは異なり再帰的シンボル表４１０は、シンボル表４１０内の
他のエントリを参照する再帰的シンボル表エントリ４８０を含む。具体的には、再帰的シンボル表エントリ４８０は、エントリ４３４内のデータ値「本」へのリンク４８６に関連付けられた第１の部分４８２と、エントリ４３２内のデータ値「１０」へのリンク４８８に関連付けられた第２の部分４８４とを含む。第１の部分４８２と第２の部分４８４とを組合わせることで、エントリ４８０は、参照される連続したデータ値の両方を含むエントリ、すなわちデータ値「１０」の直前にデータ値「本」があるエントリを論理的に作成する。
【００３２】
このように多数のエントリを組合わせる利点の１つは、これらの組合せに一致し得る、ブロック内に格納された行についての列の値の並びがあるということである。シンボル表内の個別のデータ値とディスク上の行構造との間にリンクまたはポインタ構造を多数設けるのに代えて、単一のリンクまたはポインタ構造を用いて、多数の他のエントリへ再帰的にリンクする組合せエントリを指し示すことができる。
【００３３】
図１の表１００を参照して、行１０２ａおよび行１０４ａの両方における列１２４および列１２６は連続したデータ値「本」および「１０」を提示する。図１では、ディスク上の行構造１０２ｂ（行１０２ａに対応）は、データ値「本」へのリンク１３８と、これとは別個の、データ値「１０」へのリンク１４０とを含む。同様に、ディスク上の行構造１０４ｂ（行１０４ａに対応）は、データ値「本」へのリンク１５４と、これとは別個の、データ値「１０」へのリンク１５６とを含む。すなわち、これらディスク上の行構造からシンボル表１１０内のエントリへ合計４つのリンクがあることになる。
【００３４】
図４の再帰的手法においては、ディスク上の行構造４０２ｂ（行１０２ａに対応）は、再帰的シンボル表エントリ４８０により表わされる連続する組合わせられたデータ値「本」および「１０」に対する単一のリンク４７２を含む。これにより、ディスク上の行構造４０２ｂ内の両方の部分４４６，４４８（行１０２ａの列１２４，１２６に対応）の値を単一のリンクまたはポインタ構造で表わすことが可能となる。同様に、ディスク上の行構造４０４ｂ（行１０４ａに対応）は、再帰的シンボル表エントリ４８０によって表わされる連続する組合わせられたデータ値「本」および「１０」に対する単一のリンク４７６を含む。これによってやはり、ディスク上の行構造４０４ｂの部分４５０，４５２の両方（行１０４ａの列１２４，１２６に対応）の値を単一のリンクまたはポインタ構造により表現することが可能となる。最終的な結果として、図４の手法においては、ディスク上の行構造とシンボル表との間で必要とされるリンクまたはポインタは、図１の手法で必要とされるよりも少なくなる。
【００３５】
図４に示したリンクまたはポインタの数を減少させる手法は、シンボル表４１０内で非再帰的組合せエントリでもまた採用可能である。具体的には、部分４８２がエントリ４３４への再帰的リンク４８６に関連付けられるのでなくてデータ値「本」を明示的に格納するようにエントリ４８０が構成され得る。エントリ４８０の部分４８４もまた、エントリ４３２への再帰的リンク４８８に関連付けられるのでなくてデータ値「１０」を明示的に格納するように構成され得る。この手法によっても、ディスク上の行構造とシンボル表４１０との間のリンクの数を減少させることは可能であるが、その代償としてシンボル表４１０内の重複データ値を明示的に格納するのに必要なディスク空間の量が増加する可能性がある。また、シンボル表４１０内のエントリは、再帰的リンクと明示的に格納されたデータ値とをさまざまに組合せたものを含んでもよい。図４の例は再帰的シンボルエントリ４８０となるように組合わせられた２つのデータ値のみを示しているが、この発明の概念を拡張させて、組合わせられたシンボル表エントリ内に任意の数のデータ値を含めることが可能である。
【００３６】
一実施例では、圧縮比を向上させるために列の再順序付けがなされる場合がある。上の
段落で述べたように、所与のブロックに格納された行について連続した繰返しの列の値がある場合、シンボル表とディスク上の行構造との間のリンクの数は、シンボル表内で組合わせのエントリへのリンクを作成することによって減少され得る。そこで、列の再順序付けを行なうことで列の値の重複の並びの数を増加させることができる。一実施例において、列の再順序付けはデータブロックの粒度レベルで行なわれる。これに代えてその他の粒度で、たとえば多数のブロックにわたって列の再順序付けを行なってもよい。
【００３７】
説明のため、図５に示すデータベース表６００について考察する。表６００は３行のデータを含み、各々の行には＜注文番号＞列、＜価格＞列、＜品目＞列、および＜数量＞列がある。行６０２ａには以下のように並んだデータ値がある。「１２５４」、「５」、「本」および「２」。行６０４ａには以下のように並んだデータ値がある。「１２５５」、「１０」、「テープ」および「３」。行６０６ａには以下のように並んだデータ値がある。「１２５６」、「１０」、「映画」および「３」。
【００３８】
列が再順序付けされていない最初の状況について考察する。データ値「１０」および「３」がこれらの行で重複していることが注目される。したがって、この表がディスク６８０に書込まれるとき、データ値「１０」を有する第１のエントリ６５２と、データ値「３」を有する第２のエントリ６５４とがあるシンボル表６５０が作成され得る。行６０２ａ，６０４ａ，６０６ａがディスクに書込まれる際、これら重複したデータ値に関連付けられた、これらの行についてのディスク上の行構造の各々は、シンボル表６５０内の適当なエントリを参照するように構成される。すなわち、行６０４ａに対応するディスク上の行構造６０４ｂは、データ値「１０」についてのシンボル表６５０内のエントリ６５２へのリンク６４０に関連付けられた部分６４１（＜価格＞列にあるデータ値に対応）を有する。ディスク上の行構造６０４ｂはまた、データ値「３」についてのシンボル表６５０内のエントリ６５４へのリンク６４２に関連付けられた部分６４３（＜数量＞列にあるデータ値に対応）を有する。行６０６ａに対応するディスク上の行構造６０６ｂは、データ値「１０」についてのシンボル表６５０内のエントリ６５２へのリンク６４６に関連付けられた部分６４５（＜価格＞列にあるデータ値に対応）を有する。ディスク上の行構造６０６ｂはさらに、データ値「３」についてのシンボル表６５０内のエントリ６５４へのリンク６４４に関連付けられた部分６４７（＜数量＞列にあるデータ値に対応）を有する。行６０２ａは重複データ値を含んでいないので、その関連付けられたディスク上の行構造６０２ｂは各々の列の値を明示的に格納し、シンボル表への参照は含まない。
【００３９】
表６００に対して列の再順序付けが実行される場合について考察する。列の再順序付けは、表内の行についての繰返す列の値の並びがある可能性を増加させるために実行される。この例においては、表６００内の＜品目＞列と＜数量＞列とで順序を入れ換えることにより、＜価格＞列と＜数量＞列との間に繰返す値の並びがもたらされることを見て取ることができる。この列の再順序付けの結果を図５で表６２０として示す。具体的には、行６２４ａおよび行６２６ａの両方は、＜価格＞および＜数量＞の列について同じ並びのデータ値「１０」および「３」を有している。したがって、シンボル表６６０がディスク６８２に作成されるとき、表６２０に示す行６２４ａおよび行６２６ａについての並びでのデータ値「１０」および「３」を直接的または間接的に含む組合せエントリ６６６を挿入することができる。組合せエントリ６６６がこれら値を間接的に含む場合、エントリ６６６は、エントリ６６２を再帰的に参照する第１の部分６６８と、エントリ６６４を再帰的に参照する第２の部分６７０とを含む。
【００４０】
行６２４ａがディスクに書込まれるとき、そのディスク上の行構造６２４ｂは、値「１０」よび「３」の並びについての組合せエントリ６６６への単一のリンク６３２に関連付けられる。これは、列を再順序付けせずに同じ行についてのディスク上の行構造６０４ｂによって取られる手法とは対照的なものであり、後者においては同じ２つのデータ値を参
照するために２つのリンク６４０，６４２を使用している。同様に、行６２６ａがディスクに書込まれるとき、そのディスク上の行構造６２６ｂは値「１０」および「３」の並びについての単一のリンク６３６に関連付けられる。これもまた、列を再順序付けせずに同じ行についてのディスク上の行構造６０６ｂによって取られる手法とは対照的なものであり、後者においては同じ２つのデータ値を参照するのに２つのリンク６４６，６４４を使用している。
【００４１】
図６は、列の再順序付けを利用してデータをディスクに格納するプロセスの一実施例のフローチャートを示す。６０２にて、データをディスクに格納する要求が受取られる。圧縮がオンにされていれば、６０４にて当該データが分析され、所与のデータブロック内に格納されるべきデータの各部分について繰返しのデータ値が識別される。このデータ分析は、繰返しのデータ値の並びがある可能性を増加させるために実行され得る、可能な列の再順序付けの組合せの分析も含む。列の再順序付けを通じて有利に獲得され得る列の並びが存在するかどうかについて判断がなされる（６０６）。もし存在すれば、適当な列が再順序付けされる（６０８）。識別されたデータ重複に基づいて、重複データ値のいくつかまたはすべてを含むようにシンボル表が作成される（６１０）。そして、重複データ値を除外するようにデータベースブロック内の各々のディスク上の行構造が作成およびフォーマット付けされ（６１２）、それからディスクに書込まれる（６１４）。具体的には、重複データ値に関連付けられた各々のディスク上の行構造は、該当するデータ値を格納したシンボル表内の適当なエントリへのリンクを含むかまたはこれを参照するように構成される。ブロックのメタデータは、ブロック内のデータまたはブロック内のデータの一部が圧縮されたかどうかを標示するように構成される。これに加え、ブロックのメタデータは、格納されたデータに対して列の再順序付けが実行されたかどうか、そしてそれがどのようになされたかを標示するように構成される。一実施例において、ブロックのヘッダは、ブロックまたはブロック内のデータが圧縮および／または再順序付けされたかどうかを標示するデータ構造を含む。データがブロックから検索されるとき、ヘッダ情報にアクセスすることによって、このデータを再順序付けし復元することでその元の形に戻すことが可能となる。
【００４２】
ここで適用され得る最適化の方策としては、格納された行のディスク上のバージョンから後端のＮＵＬＬ値を除去するというものがある。データベース表内の行は、行の終わりにある１本以上の列にＮＵＬＬ値を含む場合がある。これら行がディスクに書込まれるとき、これらＮＵＬＬ値についてはディスクに空間を割当てたり書込んだりしないことにより追加の圧縮を達成することができる。空間を割当てたり書き込んだりする代わりに、特定のデータベース行のディスク上のバージョンが行の終わりの列に１つ以上の格納値を含まない場合、これら列値はＮＵＬＬ値であると仮定されると認識するように格納システムが構成される。
【００４３】
説明のため、図７の表７００について考察する。表７００はディスク７２０にあるブロック７２２に格納されるものである。行７０２ａおよび行７０６ａはともに行の最後の列にＮＵＬＬ値を有することが注目される。これらの行がディスク７２０に書込まれるとき、これらの行についてのディスク上の行構造は後端のＮＵＬＬ値を除外するように構成される。行７０２ａに対応するディスク上の行構造７０２ｂは、「要望」列における後端のＮＵＬＬ値に割当てられる空間を含んではおらず、行７０２ａで先行して現われる「１２６０」、「トム」および「１０」の値について割当てられた空間のみを含む。また、行７０６ａに対応するディスク上の行構造７０６ｂは、後端のＮＵＬＬ値に割当てられる空間を含んではおらず、行７０６ａで先行して現われる「１２６２」、「ハリー」および「３０」の値について割当てられた空間のみを含む。
【００４４】
場合によっては、ディスクに格納されるべき行に後端のＮＵＬＬ値が現われる可能性が
増加するように列の再順序付けを行なう。１組のデータについての列の値を分析し、各々の列にあるＮＵＬＬ値の数に基づいて列同士を並び替える。列を再順序付けすることで、ＮＵＬＬ値の数がより多い列を行の終わりへ順序付け、ＮＵＬＬ値の数がより小さい列を行の初めに近くなるように順序付ける。こうしてＮＵＬＬ値の数が最も多い列を表の終わりへ再順序付けすることができる。ＮＵＬＬ値の数が次に多い列は表における最後から２列目に再順序付けでき、これら動作の連続を、列の効果的な順序付けが達成されるまで続行することができる。
【００４５】
列の再順序付けが実行されない場合に生じ得る非効率性を明らかにするために図８の表８００を参照する。表８００は、ディスクに書込まれるべき１組の行８０２ａ，８０４ａ，８０６ａを含む。各々の行は１つ以上のＮＵＬＬ値を含む。行８０２ａ，８０６ａは＜方式＞列および＜要望＞列にＮＵＬＬ値を含む。行８０４ａは＜方式＞列にＮＵＬＬ値を含む。これら行におけるＮＵＬＬ値はいずれも後端のＮＵＬＬではないため、これら行がディスクに書込まれるとき、対応する各々のディスク上の行構造においてＮＵＬＬ値のため空間が浪費されるおそれがある。
【００４６】
図示するように、行８０２ａに対応するディスク上の行構造８０２ｂは、行８０２ａについての＜方式＞および＜要望＞の列における値に対応するＮＵＬＬ値に割当てられた２つの空間８１０，８１２を含む。行８０４ａに対応するディスク上の行構造８０４ｂは、行８０４ａの＜方式＞列における値に対応するＮＵＬＬ値に割当てられた空間８１４を含む。行８０６ａに対応するディスク上の行構造８０６ｂは、行８０６ａにおける＜方式＞および＜要望＞の列における値に対応するＮＵＬＬ値に割当てられた２つの空間８１６，８１８を含む。
【００４７】
表８００をディスクに格納する圧縮の効率性を増大させるように列の再順序付けを行なうことができる。最初のステップでは、列を並び替えて、ＮＵＬＬ値の数がより多い特定の列を識別する。この例では、表８００内の＜方式＞列においてＮＵＬＬ値の数が最も多い（ＮＵＬＬ値は各々の行にある）ことを見て取ることができる。ＮＵＬＬ値の数が次に多いのは＜要望＞列においてである（行８０２ａ，８０６ａにＮＵＬＬ値がある）。その他の列はＮＵＬＬ値を含んでいない。
【００４８】
列を再順序付けすることにより、ＮＵＬＬ値の数がより多い列をより行の終わり近くに置く。この処置を表８００に対して行なった結果を表９００に示す。具体的には、列を再順序付けすることにより、ＮＵＬＬ値の数が最も多い＜方式＞列を行の終わりに置く。ＮＵＬＬ値の数が次に多い＜要望＞列は列の並びの最後から２番目に置かれる。その他の列はいずれもＮＵＬＬ値を含んでいないため再順序付けされない。
【００４９】
このような再順序付けにより表内の後端のＮＵＬＬ値の数が最大限になっている。ここで、表８００において行８０２ａおよび行８０６ａにそれぞれ対応する行９０２ａおよび行９０６ａはともに２つの後端のＮＵＬＬ値を含んでいる。行８０２ａおよび行８０６ａは後端のＮＵＬＬ値を含んでいなかった。表９００において、表８００の行８０４ａに対応する行９０４ａは１つの後端のＮＵＬＬ値を含んでいる。行８０４ａは後端のＮＵＬＬ値を含んでいなかった。
【００５０】
表９００内の行９０２ａ，９０４ａ，９０６ａがディスクに書込まれるとき、後端のＮＵＬＬ値を各々の行のディスク上のバージョンから除去することができる。これにより、表９００の行９０２ａに対応するディスク上の行構造９０２ｂにおいては、＜要望＞および＜方式＞の列についてのＮＵＬＬ値は除外される。ディスク上の行構造９０２ｂは、それぞれ＜注文番号＞、＜顧客名＞および＜価格＞の列についてのデータ値「１２７０」、「トム」および「５」を格納するための３つのフィールドのみを含む。これとは対照的に
、列の再順序付けをする前のその等価物であるディスク上の行構造８０２ｂは、それぞれ＜注文番号＞、＜顧客名＞、＜方式＞、＜要望＞および＜価格＞の列についてのデータ値「１２７０」、「トム」、「ＮＵＬＬ」、「ＮＵＬＬ」および「５」を格納するための５つのフィールドを含む。
【００５１】
表９００の行９０４ａに対応するディスク上の行構造９０４ｂにおいては、＜方式＞列についてのＮＵＬＬ値が除外される。ディスク上の行構造９０４ｂは、それぞれ＜注文番号＞、＜顧客名＞、＜価格＞および＜要望＞列についてのデータ値「１２７０」、「ディック」、「１０」および「地上輸送」を格納するための４つのフィールドのみを含む。これとは対照的に、列の再順序付けをする前のその等価物であるディスク上の行構造８０４ｂは、それぞれ＜注文番号＞、＜顧客名＞、＜方式＞、＜要望＞および＜価格＞の列についてデータ値「１２７０」、「ディック」、「ＮＵＬＬ」、「地上輸送」および「１０」を格納するための５つのフィールドを含む。
【００５２】
ディスク上の行構造９０２ｂと同様に、表９００の行９０６ａに対応するディスク上の行構造９０６ｂにおいては、＜要望＞および＜方式＞の列についてのＮＵＬＬ値が除外される。ディスク上の行構造９０６ｂは、＜注文番号＞、＜顧客名＞および＜価格＞の列についてのデータ値を格納するための３つのフィールドのみを含む。これとは対照的に、列の再順序付けをする前のその等価物であるディスク上の行構造８０６ｂは、＜注文番号＞、＜顧客名＞、＜方式＞、＜要望＞および＜価格＞の列についてのデータ値を格納するための５つのフィールドを含む。
【００５３】
図１０にて、データベース問合せ言語文の性能を向上させる方法を説明する。１００２にて、データブロック内のデータ重複を記述する情報が維持される。上述のように、データ重複情報を維持するためには、シンボル表を用いるなどいくつかの方策がある。データ重複情報を維持するためにデータブロック内のデータを圧縮する必要はない。１００４にて、データブロック内のデータに対し、少なくとも１つの述語を伴うデータベース問合せ言語文が受取られる。上記データ重複情報を用いて述語評価の回数を減少させる（１００６）。述語評価の回数を減少させることでデータベース問合せ言語文の性能が向上する。
【００５４】
図１１にはデータ重複情報を維持する１つの方策が示される。１つ以上の重複データ値が識別され（１１０２）、各々の重複データ値の出現数が算出される（１１０４）。各々の重複データ値およびその対応する出現数がシンボル構造のエントリに格納される（１１０６）。上記重複データ値のうち少なくとも１つについての１以上の出現がデータブロックから消去または除去される（１１０８）。消去された出現に対応するデータブロックの部分は、適当なシンボル構造エントリを参照するように構成される（１１１０）。適当なシンボル構造エントリを参照するにはリンクまたはポインタを使用することができる。
【００５５】
図１２にデータ重複情報を維持する一例を示す。ディスク１２０２におけるデータブロック１２０４には４つのディスク上の行構造１２０６〜１２１２が入っている。各々のディスク上の行構造は表（図示せず）内の１行に対応する。データブロック１２０４において２つの重複データ値「ＨＲ」および「ＬＡ」が識別され、各々の重複データ値の出現数とともにシンボル構造１２１４に格納される。この実施例においては、シンボル構造１２１４は行構造１２０６〜１２１２とともにデータブロック１２０４に格納される。データ値「ＨＲ」は２回出現する。すなわち行構造１２０６の部分１２１６にて一回、そして、行構造１２０８の部分１２２０にてもう一回である。データ値「ＬＡ」は３回出現する。すなわち行構造１２０６の部分１２１８にて一回、行構造１２１０の部分１２２２にてもう一回、さらに行構造１２１２の部分１２２４にてもう一回である。図１２に示すように、データブロック１２０４内の重複データ値は消去され、部分１２１６〜１２２４は、シンボル構造１２１４内の適当なエントリを参照するように構成される。
【００５６】
図１３は、データ重複情報を維持する別の方策を示す。１３０２にて、１つ以上の重複データ値が識別される。各々の重複データ値の出現数が算出される（１３０４）。各々の重複データ値およびその対応する出現数がシンボル構造のエントリに格納される（１３０６）。上記重複データ値のうち１つについての出現が追加または削除されたときに、上記重複データ値の出現数が更新される（１３０８）。シンボル構造エントリ内の重複データ値の出現数が０になればシンボル構造エントリは除去される（１３１０）。
【００５７】
図１４においては、ディスク１４０２におけるデータブロック１４０４内のデータ重複についての情報がシンボル構造１４０６内で維持される。この例においては、ディスク上の行構造１４１６の部分１４１８がデータ値「ＬＡ」からデータ値「ＳＦ」へ更新されるものとする。これに伴い、重複データ値「ＬＡ」に対応するシンボル構造１４０６内のエントリ１４２０を更新することにより、データブロック１４０４からデータ値「ＬＡ」が削除されたことを反映させる。
【００５８】
図１５には、データベース問合せ言語文の性能を向上させる方法の一実施例が示される。１５０２にて、データ重複についての情報が維持される。データベース問合せ言語文が受取られる（１５０４）。このデータベース問合せ言語文は少なくとも１つの述語を含む。この述語は重複データ値に対して多くとも一回評価される（１５０６）。
【００５９】
図１６は、データベース問合せ言語文の性能を向上させる別の方法のプロセスフローを示す。この実施例では、データ重複情報が維持される（１６０２）。少なくとも１つの述語を伴うデータベース問合せ言語文が受取られ（１６０４）、それからデータ値へのアクセスがなされる（１６０６）。このデータ値に対して上記少なくとも１つの述語を評価する前に、上記述語が上記データ値の重複に対して以前に評価されたかどうかについての判断がなされる（１６０８）。上記述語が上記データ値の重複に対して以前に評価されていなければ、上記述語が上記データ値に対して評価される（１６１０）。上記述語が上記データ値の重複に対して以前に評価されていれば、同じデータ値に対して述語を評価する代わりにこの以前の述語評価の結果を用いる（１６１２）。
【００６０】
図１７には、データベース問合せ言語文の性能をどのように向上させるかについての一例が示される。表１７０４内のデータに対してデータベース問合せ言語文１７０２が受取られる。データベース問合せ言語文１７０２は、表１７０４内で述語１７０６を満足させるレコードすべてを探す。すなわち、データベース問合せ言語文１７０２は、表１７０４内で列１７０８にデータ値「ＬＡ」を有するレコードすべてを探す。まず行１７１０にアクセスがなされる。これより以前には述語評価がないため、述語１７０６が行１７１０内のデータ値１７１８に対して評価される。この述語評価の結果がコンテキスト１７２６に格納される。述語評価の結果が真であるため、行１７１０は返される。
【００６１】
次に行１７１２にアクセスがなされる。行１７１２内のデータ値１７２０に対して述語１７０６を評価する前に、データ値１７２０の重複に対して述語１７０６が以前に評価されたかどうかについての判断がなされる。一実施例においては、コンテキスト１７２６を調べることで、データ値１７２０の重複であるデータ値「ＤＣ」について以前の述語評価の結果があるかどうかを判断する。述語１７０６が以前に評価されたデータ値は「ＬＡ」のみであるため、述語１７０６はデータ値１７２０に対して評価される。述語評価の結果はコンテキスト１７２６に格納される。述語評価の結果が偽であるため、行１７１２は返されない。
【００６２】
次に行１７１４にアクセスがなされる。行１７１４内のデータ値１７２２に対して述語１７０６を評価する前に、データ値１７２２の重複に対して述語１７０６が以前に評価さ
れたかどうかについての判断がなされる。コンテキスト１７２６は、データ値１７２２の重複であるデータ値「ＬＡ」についての以前の述語評価の結果を含んでいるため、データ値１７２２に対しては述語１７０６は評価されず、コンテキスト１７２６内の以前の述語評価の結果が用いられる。以前の述語評価の結果は真であったため、行１７１４は返される。行１７１６にも同様にアクセスされてその処理がなされる。このように、述語１７０６は４つのデータ値でなく２つのデータ値に対して評価されただけなので、データベース問合せ言語文の性能は向上している。
【００６３】
図１８には、この発明の一実施例に従うデータベース問合せ言語文の性能を向上させる方法が示される。データブロック内のデータ重複についての情報が維持される（１８０２）。１８０４にて、少なくとも１つの述語を伴うデータベース問合せ言語文が受取られる。上記データ重複情報を用いて、述語評価の回数（１８０６）と、データベース問合せ言語文によりアクセスされるデータの量（１８０８）とを減少させる。
【００６４】
図１９は、データベース問合せ言語文によりアクセスされるデータの量を減少させる１つの方法を示す。１９０２においては、データ値であって、それに対して述語が真であると評価されるものの総数が算出される。次に、１９０４にて、この算出された合計と等しくなるようにカウンタをセットする。或るデータ値にアクセスがなされ（１９０６）、上記述語が上記データ値に対して評価される（１９０８）。この述語評価の結果が偽であれば、プロセスは戻って１９０６で別のデータ値にアクセスがなされる。上記述語評価の結果が真であれば、カウンタは１だけ減少される（１９１０）。１９１２にて、カウンタが現在０に等しいかどうかについて判断がなされる。カウンタが０と等しくなければ、プロセスは１９０６へ戻って別のデータ値にアクセスがなされる。カウンタが０と等しければプロセスは終了する。
【００６５】
図２０では、データベース問合せ言語文の性能向上を目的としてデータ重複情報をどのように使用するのかについての一例を示す。図２０において、表２００４内のデータに対してのデータベース問合せ言語文２００２が受取られる。表２００４はデータブロック２０６に格納されている。データベース問合せ言語文２００２は、表２００４の行のうち＜営業所＞列２０１６内にデータ値「ＬＡ」を含む行すべてを探して返す。表２００４は１０の行および４の列、すなわち＜ＩＤ＞列２０１０、＜名前＞列２０１２、＜部門＞列２０１４、および＜営業所＞列２０１６を含む。＜ＩＤ＞列２０１０にも＜名前＞列２０１２にも重複データ値はない。＜部門＞列２０１４および＜営業所＞列２０１６の各々は３つの重複データ値を有する。
【００６６】
図２０の実施例では、データ重複情報がシンボル表２００８に格納される。シンボル表２００８は、表２００４における各々の重複データ値のコピーと、対応する、重複データ値の出現数とを含む。シンボル表２００８内の各々のエントリはまた、データブロック２００６においてシンボル表エントリを参照するために用いられ得るエントリ番号を含む。図２０に示すように、データブロック２００６内の重複データ値の各々の出現は、対応するシンボル表エントリへのポインタまたはリンクでなく対応するシンボル表エントリ番号と入れ替えられている。
【００６７】
データベース問合せ言語文２００２を評価するために、表２００４内の行２０１８ａに対応する、データブロック２００６内の行構造２０１８ｂにアクセスがなされる。行構造２０１８ｂのうちで、行２０１８ａの列２０１６に対応する部分２０２０は、シンボル表２００８内のエントリ番号♯３を参照するので、シンボル表２００８から重複データ値「ＬＡ」が検索され、これがデータベース問合せ言語文２００２の述語に対して評価される。述語評価の結果はコンテキスト２０２４に格納される。次にカウンタ２０２６を「３」にセットする。この数は表２００４内の重複データ値「ＬＡ」の出現数と等しいものであ
る。「ＬＡ」は、当該述語が真であると評価されることになる唯一のデータ値だからである。次に、表２００４の行２０１８ａが返され、カウンタ２０２６が１だけ減少される。カウンタ２０２６が０になると、当該データベース問合せ言語文を満足させるであろう行の最大数が返されたのであるから、データブロック２００６の一連の行アクセスは終了することができる。
【００６８】
次に、表２００４内の行２０２８ａに対応する、データブロック２００６内の行構造２０２８ｂにアクセスがなされる。行構造２０２８ｂのうち、行２０２８ａの列２０１６に対応する部分２０３０は、シンボル表２００８内のエントリ番号♯４を参照する。シンボル表２００８から重複データ値「ＤＣ」が検索されてデータベース問合せ言語文２００２内の述語に対して評価される前に、まずコンテキスト２０２４を調べて、エントリ番号♯４について以前の述語評価の結果があるかどうかを判断する。コンテキスト２０２４はエントリ番号♯４についての以前の述語評価の結果を含んでいないため、シンボル表２００８から重複データ値「ＤＣ」が検索され、これがデータベース問合せ言語文２００２の述語に対して評価される。次に、この述語評価の結果がコンテキスト２０２４に格納される。述語評価の結果は偽であるため、行２０２８ａは返されず、カウンタ２０２６は減少させられない。
【００６９】
表２００４内の行２０３２ａに対応する、データブロック２００６内の行構造２０３２ｂにアクセスがなされる。行構造２０３２ｂのうち、行２０３２ａの列２０１６に対応する部分２０３４は、シンボル表２００８内のエントリ番号♯３を参照する。コンテキスト２０２４は既にエントリ番号♯３についての以前の述語評価の結果を含んでいるので、この述語は再び評価される必要はない。エントリ番号♯３についての以前の述語評価の結果が真であるため、行２０３２ａは返されてカウンタ２０２６が１だけ減少される。
【００７０】
表２０２４内の行２０３６ａに対応する、データブロック２００６内の行構造２０３６ｂへのアクセスは、行構造２０３２ｂの場合とほぼ同じ方法で行なわれる。行構造２０３２ｂの部分２０３４と同様に、行構造２０３６ｂのうち行２０３６ａの列２０１６に対応する部分２０３８はシンボル表２００８内のエントリ番号♯３を参照する。コンテキスト２０２４は既にエントリ番号♯３についての以前の述語評価の結果を含んでいるため、この述語は再び評価される必要はない。エントリ番号♯３についての以前の述語評価の結果が真であるため、行２０３６ａは返されてカウンタ２０２６がやはり１だけ減少される。そして、データベース問合せ言語文２００２を満足させるであろう行すべてが返されたため、データブロック２００６の一連の行アクセスは終了する。
【００７１】
図２０に示す例においては、述語評価の回数が４から２に減じられただけでなく、データ重複情報を有する結果として、アクセスされる行の数もまた１０から４に減じられた。このように、データブロック内のデータ重複についての情報を維持することにより、データベース問合せ言語文の性能を大幅に向上させることができる。
【００７２】
図２０ではただ１つの一意のデータ値がデータベース問合せ言語文２００２の述語を満足させ得るため、述語が真であると評価されるデータブロック内のデータ値の総数は、シンボル表２００８を参照するだけで算出される。一方、２つ以上の一意のデータ値が述語を満足させ得るデータベース問合せ言語文の場合、述語が真であると評価されるデータブロック内のデータ値の総数は、当該述語を満足させるデータブロック内の各々の一意のデータ値の出現数を合計することで算出される。たとえば、３つの異なる一意のデータ値すなわちＸ，Ｙ，Ｚが述語を満足させることができ、Ｘがデータブロック内で５回、Ｙがデータブロック内で８回、そしてＺがデータブロック内で３回出現する場合、データブロック内で当該述語が真であると評価されるデータ値の総数は５＋８＋３＝１６に等しくなる。したがって、図２０のカウンタ２０２６は１６にセットされ、満足させるデータ値が返
されるたびに減少させられる。このように、データベース問合せ言語文を満足させるためにアクセスされるデータの量を大幅に減少させることができる。
【００７３】
図２１は、データベース問合せ言語文の性能を向上させる別の方法のプロセスフローを示す。データブロック内のデータ重複情報が維持される（２１０２）。２１０４にて、少なくとも１つの述語を伴うデータベース問合せ言語文が受取られる。上記データ重複情報を用いて述語評価の回数を減少させる（２１０６）。これに加え、データベース問合せ言語文を満足させるためにデータ値にアクセスする代わりにデータ重複情報が更新される（２１０８）。
【００７４】
図２２において、データブロック内のデータ値にアクセスする代わりに、データベース問合せ言語文を満足させるためにデータ重複情報をどのように更新するのかについての一例が示される。表２２０４に対してのデータベース問合せ言語文２２０２が受取られる。表２２０４はディスク２２０８のデータブロック２２０６に格納されている。データベース問合せ言語文２２０２は、表２２０４の＜営業所＞列２２１０内のデータ値「ＬＡ」を「ＳＦ」に変更しようとするものである。図１２を参照して既に説明したように、シンボル構造２２１２にはデータ重複についての情報が既に維持されているため、データベース問合せ言語文２２０２を満足させるには、シンボル構造２２１２内のエントリ２２１４のみを「ＬＡ」から「ＳＦ」へ更新すればよい。このように、データ重複情報が利用可能であるときにデータベース問合せ言語文の性能を大幅に向上させることが可能である。
【００７５】
システムアーキテクチャの概観
図２３は、データベース問合せ言語文の性能を向上させる方法が実現され得るコンピュータシステム２３００を例示するブロック図である。コンピュータシステム２３００は、バス２３０２またはその他情報を通信するための通信機構と、バス２３０２に結合され情報を処理するプロセッサ２３０４とを備える。コンピュータシステム２３００はさらに、ランダムアクセスメモリ（ＲＡＭ）またはその他の動的記憶装置などの主メモリ２３０６を備え、これはバス２３０２に結合されて、プロセッサ２３０４が実行する命令および情報を記憶する。主メモリ２３０６はまた、プロセッサ２３０４が実行する命令の実行の間に一時的な変数またはその他の中間情報を蓄積するためにも用いられ得る。コンピュータシステム２３００はさらに、バス２３０２に結合されてプロセッサ２３０４のための静的情報および命令を記憶する読出専用メモリ（ＲＯＭ）２３０８またはその他の静的記憶装置を備える。さらに、バス２３０２に結合されて情報および命令を記憶するための磁気ディスクまたは光ディスクなどの記憶装置２３１０が設けられる。
【００７６】
コンピュータシステム２３００はバス２３０２を介して、情報をコンピュータユーザに対して表示するための陰極線管（ＣＲＴ）などの表示装置２３１２に結合され得る。英数字式キーおよびその他のキーを含む入力装置２３１４がバス２３０２に結合されて情報およびコマンド選択をプロセッサ２３０４に通信する。別の種類のユーザ入力装置として、マウス、トラックボールまたはカーソルキーなどのカーソル操作装置２３１６があり、これにより方向情報およびコマンド選択をプロセッサ２３０４に通信し、ディスプレイ２３１２におけるカーソルの動きを制御する。一般的に、この入力装置は、第１の軸（たとえばｘ軸）および第２の軸（たとえばｙ軸）の２軸による２自由度を有し、これにより入力装置は或る平面上の位置を指定することができる。
【００７７】
一実施例において、コンピュータシステム２３００はデータベース問合せ言語文の性能を向上させるために使用される。一実施例に従うと、主メモリ２３０６に入っている１つ以上の命令からなる１つ以上のシーケンスをプロセッサ２３０４が実行するのに応じて上記のような使用がコンピュータシステム２３００でなされる。上記命令は別のコンピュータ読取可能媒体、たとえば記憶装置２３１０から主メモリ２３０６に読込まれ得る。主メ
モリ２３０６に入っている命令シーケンスが実行されるのに伴い、プロセッサ２３０４においてここに記載された各プロセスステップが実行される。主メモリ２３０６に入っている命令シーケンスの実行には、多重処理構成に設けた１つ以上のプロセッサを採用してもよい。実施例によっては、ソフトウェアによる命令に代えて、またはこれと組合せて、ハードウェア回路を用いる場合もある。したがってこの発明の各実施例は、ハードウェア回路およびソフトウェアのいかなる特定の組合せにも限定されない。
【００７８】
ここで用いる「コンピュータ読取可能媒体」という用語は、命令をプロセッサ２３０４が実行できるようここに供給することに関与するあらゆる媒体を指す。このような媒体は多くの形態を取ることができ、これには不揮発性媒体、揮発性媒体および伝送媒体が含まれるがこれに限定されない。不揮発性媒体にはたとえば、記憶装置２３１０といった光ディスクまたは磁気ディスクが含まれる。揮発性媒体には主メモリ２３０６といったダイナミックメモリが含まれる。伝送媒体には、同軸ケーブル、銅線および光ファイバが含まれ、これにはバス２３０２を含むワイヤが含まれる。伝送媒体はまた音波または光波の形態を取る場合もあり、これには電波通信および赤外線データ通信の際に生成されるものなどがある。
【００７９】
コンピュータ読取可能媒体の一般的な形態には、たとえば、フロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、またはその他任意の磁気媒体、ＣＤ−ＲＯＭ、その他任意の光媒体、パンチカード、紙テープ、その他任意の孔パターンによる物理的媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、その他任意のメモリチップまたはカートリッジ、後に述べる搬送波、またはその他コンピュータが読出可能な任意の媒体が含まれる。
【００８０】
１つ以上の命令からなる１つ以上のシーケンスをプロセッサ２３０４が実行できるようここへ伝達することにはさまざまな形態のコンピュータ読取可能媒体が関与し得る。たとえば、命令はまず遠隔のコンピュータの磁気ディスクに収められ得る。この遠隔のコンピュータは命令を自分のダイナミックメモリにロードし、モデムを用いて電話回線経由で上記命令を送信し得る。コンピュータシステム２３００に対してローカルなモデムが上記電話回線上のデータを受信し、赤外線送信機を用いてこのデータを赤外線信号に変換し得る。
【００８１】
赤外線信号で搬送されたデータは、バス２３０２に結合された赤外線検出器が受信して、このデータをバス２３０２に出力し得る。バス２３０２はデータを主メモリ２３０６へと伝達し、ここからプロセッサ２３０４は命令を検索して実行する。任意には、主メモリ２３０６が受取った命令をプロセッサ２３０４による実行前または実行後に記憶装置２３１０に記憶させてもよい。
【００８２】
コンピュータシステム２３００はさらに、バス２３０２に結合された通信インターフェイス２３１８を含む。通信インターフェイス２３１８は、ローカルネットワーク２３２２に接続されたネットワークリンク２３２０に対する２方向データ通信結合を行なうものである。たとえば通信インターフェイス２３１８として統合デジタル通信サービス網（ＩＳＤＮ）カードまたはモデムを用いることができ、これにより対応する種類の電話回線に対するデータ通信接続を行なう。もう１つの例として、通信インターフェイス２３１８にローカルエリアネットワーク（ＬＡＮ）カードを用いて対応するＬＡＮに対するデータ通信接続を行なってもよい。無線リンクもまた実現可能である。このような実現例のいずれにおいても、通信インターフェイス２３１８は、さまざまな種類の情報を表わすデジタルデータの流れを搬送する電気信号、電磁信号または光信号を送受信する。
【００８３】
一般的に、ネットワークリンク２３２０は、１つ以上のネットワーク経由で他のデータ
装置に対するデータ通信を可能にする。たとえばネットワークリンク２３２０はローカルネットワーク２３２２経由で、ホストコンピュータ２３２４や、またはインターネットサービスプロバイダ（ＩＳＰ）２３２６の稼動するデータ装置に対する接続を行なうことができる。そしてＩＳＰ２３２６は、現在一般に「インターネット」と称される全世界規模パケットデータ通信網２３２８を通じてデータ通信サービスを提供する。ローカルネットワーク２３２２およびインターネット２３２８ではともに、デジタルデータの流れを搬送する電気信号、電磁信号または光信号を使用する。このようにさまざまなネットワークを経由する信号や、デジタルデータをコンピュータシステム２３００に入出力するように搬送するネットワークリンク２３２０上および通信インターフェイス２３１８経由の信号は、情報を運ぶ搬送波の形態の例である。
【００８４】
コンピュータシステム２３００は、ネットワーク、ネットワークリンク２３２０および通信インターフェイス２３１８を通じてメッセージを送信し、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバ２３３０は或るアプリケーションプログラムについての要求されたコードを、インターネット２３２８、ＩＳＰ２３２６、ローカルネットワーク２３２２そして通信インターフェイス２３１８経由で送信することがあり得る。この発明に従うと、このようにダウンロードされたアプリケーションの１つによって、多数のデータ格納装置を含む格納システムにおけるデータの管理、格納および検索が可能となる。受信されたコードは、受信されるとプロセッサ２３０４により実行され、かつ／または記憶装置２３１０もしくはその他の不揮発性記憶装置内で、後で実行されるように蓄積され得る。このようにコンピュータシステム２３００は搬送波の形でアプリケーションコードを取得し得る。
【００８５】
説明のための実施例
以下において、この発明の一実施例を実現したものについて詳細に説明する。この実施例においては、さまざまなデータ圧縮スキームが可能なブロックデータフォーマットが採用される。このデータブロックフォーマットは、既存のシステムのための既存のブロックフォーマットの拡張として適用され得る。このデータブロックフォーマットは行の各部分がどのようにデータブロックに格納されるかを規定する。ブロックヘッダは、特定のブロックにおいて以下の特徴のうちいずれかまたはそのすべてが使用されるかどうかを標示するフィールドを含む。
【００８６】
・ブロックレベルの圧縮
・ブロックレベルの列の再順序付け
・行内におけるラン長さのＮＵＬＬ圧縮。
【００８７】
［列の再順序付け］
列の再順序付けの標識がセットされる場合、ブロックはブロックレベルの列の再順序付けを用いる。Ｎ列の各々は１組の行部分を有しているため、列の数をブロックレベルにて置換すれば列を再順序付けできる。ブロックが列の再順序付けを用いる場合、ブロックのヘッダの直後に２つの配列を格納することができる。第１の配列は先行の列の長さを格納する（ub2 Lens［fixed_width_column_count］）。この実施例におけるブロック内の第１のfixed_width_column_count>=0列は、当該ブロック内の固定長の列である。この実施例において、fixed_width_column_countの値は０であり得る。第２の配列は当該ブロックについての列の数の置換を格納する（ub1 Perms［block-level_column_count］）。
【００８８】
列の再順序付けは少なくとも２つの利点を有する。第１には、列の再順序付けによって適当な列同士をひとまとめにすることでより高い圧縮が可能となる。第２に、列の再順序付けによって、固定長の列を可変長の列の前に動かすことによりＮ番目の列のアクセスが向上される。第１の組の列がブロック内で固定長を有する場合、これら長さは各々の行に
でなくブロック内に一回だけ格納され得る。これら長さは長さ配列に格納され得る。このような配列は、空間の計算の際にはブロックヘッダの一部として考えられ得る。
【００８９】
列の再順序付けについてのもう１つの利点としては、或る列がブロック内のすべての行部分においてＮＵＬＬである場合、ＮＵＬＬ列にはデータがないためこれをすべての行部分から効果的に「圧縮して出す」ことができ、その長さが長さ配列に格納され得るということが挙げられる。行部分からブロックレベルの固定の列長さをブロックレベルの配列に動かすことで比較的低コストの圧縮を行なうことができるが、これは特に、データが高度に数値的である場合のように列の値が短い場合に効果的であろう。
【００９０】
一実施例において、列が再順序付けされる行同士は等しい列カウントを有するのがよく、対応する列同士も等しい長さを有するのがよい。しかし、所与のブロック内の行部分すべてがこの特性を有することはあらゆる実施例で必要なことではない。それは、この要件に違反する「挿入」および「更新」の演算はこの方法では非効率的となるおそれがあるからである。したがって、代替的な実施例においては、列が再順序付けされるブロックにおいて、再順序付けの要件を満足しない行部分が許容される。列が再順序付けされるブロックについては、上記行部分は再順序付けから除外される。一方、上記行部分は、当該ブロックが再順序付けされかつ圧縮される場合には圧縮から除外されない。このように、固定長の要件を部分的にのみ満足させる行が許容される。列が再順序付けされるブロック内の各々の行は、ブロックレベルの列長さ配列パラメータに追従する長さを有する行内の先行の列がいくつあるかを識別する指定されたフィールドに関連付けられる。一実施例において列の再順序付けは、順送りの行部分および削除された行部分には当てはまらない。列の再順序付けはまた、明示的に再順序付けから除外される行部分には当てはまらない。
【００９１】
新たなデータ層ヘッダの可変部分は、perms配列に格納される置換と、lens配列に格納される固定幅の列の長さとを含む。Ｍ固定長列を有するＮ列行のブロックの場合、可変部分はsizeof(ub1)×N＋sizeof(ub2)×Mバイトを取る。sizeof(ub1)×N＋sizeof(ub2)×M_3×Nと仮定すると、取られる空間（VARSPACE(M,N)と呼ぶ）は３×Ｎを超えることはない。固定幅の列の長さを行部分の中に格納しないことによって、１行当たり少なくともＭバイトを節約することができる。Ｋ列再順序付け行のブロックの場合、節約は少なくとも（Ｍ−１）×Ｋバイトであり得る（Ｍ−１であるのは、ub1の中に行部分当たりの固定長の列のカウントがあるからである）。一実施例においては、差引きなしの点はＫ＝５においてであり、追加の節約はＫ＞５で生じる。
【００９２】
一実施例において、列が再順序付けされたデータが未圧縮データよりも大きい空間を消費することがないようにプロセスを構成することが求められる。
【００９３】
上述のように、第１の配列lens(ub2 lens［fixed_width_column_count］)は、最初のｎ列につき、ブロックについての固定の列の長さを含む（ここでn=fixed_width_column_count）。列の長さを配列内の各々の要素に格納する代わりに、可能性のあるＮＵＬＬ値を回避するために交換不可能な総和を用いて列の長さにつきプレフィックス和を格納することができる。これは以下のように行なわれる。
【００９４】
【数１】
2005531051.tif 000003
【００９５】
たとえば、以下のような１０の固定幅の列の長さの並びについて考察する。
【００９６】
5,5,12,7,NULL,NULL,4,NULL,4,6
この場合、配列は以下の値を含むことになる。
【００９７】
5,10,22,29,32797,32797,33,32801,37,43
この配列からのＮ番目の列長さの抽出は以下のように行なわれる。まず、k<fixed_width_column_countの場合、lens［k］&0x8000をテストして列ｋがＮＵＬＬであるかどうかを調べる。もしＮＵＬＬでなければ、長さは
len←lens［k］-(lens［k-1］&0x7FFF),k>0
または
len←lens［0］, k=0
となる。ブロック内に固定幅の列が多数ある場合、配列はかなりの空間量を消費することがある。固定長の列の再順序付けを採用することには潜在的な利点があり、これはたとえばＮＵＬＬ列を終わりまで大域的に回転させてから後端のＮＵＬＬ値の打切りを行なうことでＮＵＬＬ列からなる長い並びを圧縮して出すことを目的とする。一般に、ブロック内に固定長の列が多くなればなるほど、いくつかの列が同じ列長さを有する可能性は高くなる。
【００９８】
［ブロックフォーマット］
行圧縮の標識がブロックヘッダにおいてセットされる場合、これはブロック内の行すべてまたはその一部が圧縮されていることを標示する。以下の説明のため、所与のブロックが列を再順序付けられ、ブロックの列０から(fixed_width_column_count-1)までが固定長により、残りの列が可変長によると仮定する。さらに、０から(fixed_width_column_count-1)までの列は、その長さが除去されblock-level array lensに格納されると仮定する。残りの列は、その長さが行自体の中に格納される。一実施例においては、以下のものがブロックについての行部分フォーマットとなるように定義される。
【００９９】
♯define SHORT_INDEX 200
♯define SHORT_LENGTH 250
♯define LONG_INDEX 251
♯define LONG_LENGTH SHORT_LENGTH
SHORT_INDEXの値はシンボル表への索引である。値L∈［SHORT_INDEX,SHORT_LENGTH)の場合、len←(L-KDRCS SHORT INDEX)はその場で格納される列（すなわち圧縮されていない列）の長さである。LONG_INDEXの値は、次の２バイトがシンボル表への索引値を含むことを標示する。LONG_LENGTHの値は、圧縮されていない列（長さバイトが最初）が続くことを標示する。行ヘッダ内の列カウントフィールドは、行内にある列の長さの最初のバイトのカウントを含む。
【０１００】
一実施例においては、シンボル表はデータ層の意味での行のある表［０］である。シンボル表内の行はフラグバイトまたはロックバイトを有していない。フラグバイトについて
、シンボル表エントリをロックすることは、たとえばデータブロックのロックを得ることで実現可能である。一実施例では、シンボル表に対する演算が不当に頻繁でなければシンボル表演算に同時並行の損失が生じる可能性がある。シンボル表の行のフラグバイトおよびロックバイトはub2として格納される参照カウントを含み得る。一実施例においては、シンボル表の行は、第１の長さのバイトの値を値域に分割するのに用いられる以下の定数を除き行部分フォーマットに類似する。
【０１０１】
♯define SYMTAB_SHORT_INDEX 200
♯define SYMTAB_SHORT_LENGTH 250
♯define SYMTAB_LONG_INDEX 251
♯define SYMTAB_LONG_LENGTH SYMTAB_SHORT_LENGTH
第１の長さのバイトの解釈は上述のブロックについての行部分と同じである。加えて、シンボル表には多数の列エントリが許容される。
【０１０２】
一実施例において、プレフィックスの固定長の列の圧縮は他の列の圧縮と異なる。このように異なるのは、長さがこれら列から除去されるからである。ストップバイトBiを用いて、プレフィックスの固定長の列を圧縮するために以下のことを実行することができる。行部分データの第１のバイトB0は、B0＜SHORT_INDEXであればこれはシンボル表への索引である。他では、（B0-SHORT_INDEX）は、これに続く、その場で格納される（すなわち圧縮されていない）固定長の列の数である。次のバイトB1は直接B0に続くか、または先行する（B0-SHORT_INDEX）列についてのデータにそれぞれ直接続く。この定義は、Bkに続く列がなお固定長である間は再帰的に続行する。
【０１０３】
［圧縮部］
一実施例において、圧縮には少なくとも２つの異なる手法が利用可能である。オンライン圧縮においては、圧縮されたブロックを増分的に形成する。オフライン圧縮では、まず十分な数の行をバッファの中にバッファリングし、それから実施可能な限り多くの行を圧縮ブロック内に置く。オンライン圧縮には、追加のバッファを維持したり追加のmemcopy演算を実行する必要がないという利点がある。しかし状況によっては、オンライン圧縮は圧縮品質に関してオフライン圧縮よりもはるかに劣る場合がある。たとえば、ブロックを増分的に形成すると、処理前に列の完全な前分析が妨げられる場合があり、これはブロックレベルの列の再順序付けを効率的に実行する能力に悪影響を及ぼすおそれがある。これらの制約を回避する試みとして、ブロックのうち大部分が既に形成された後にブロック再編成（再圧縮）を行なうと、過剰なほどのコストがかかるおそれがある。
【０１０４】
以下においては、バルク組をなす行を処理して１つ以上の完全なデータブロックをフォーマット付けするオフライン圧縮について説明を行なう。各々のデータ列は、ソース表のデータブロックにおけるなどバッファにおける自分のデータへのポインタとして記述され得る。
【０１０５】
この圧縮部の実施例の説明に際して以下の用語を用いる。
【０１０６】
−単一エントリ（SingleEntry：ＳＥ）とは、データへのポインタ、データ長さおよびいくつかの参照カウントを有する列の表現である。
【０１０７】
−行モデル（RowModel：ＲＭ）とは、ＳＥへのポインタの配列およびＳＥのカウント（列カウント）としての行の表現である。
【０１０８】
−行セットモデル（RowSetmodel：ＲＳＭ）とは、ＲＭへのポインタの配列および行カウントとしての行からなる組の表現である。
【０１０９】
［ＲＳＭの構築］
圧縮モジュールは、オフライン圧縮の場合に行をバッファリングする際、行からなる組についてのＲＳＭを構築する。行の列は各々がハッシュ表で調べられ、もしなければ当該列に新たなＳＥが割当てられ、他では既存のＳＥへのポインタが用いられる。細分化およびメモリ割当オーバーヘッドを減少させるために動的メモリマネージャを用いることができる。一実施例において、メモリマネージャは、単一のブロックの圧縮の間だけ持続するブロックごとの一時的な割当と、セグメント圧縮の期間だけ持続するセグメントごとの記憶とのためのものである。
【０１１０】
ＲＳＭはＳＥポインタの行列としての行からなる組を表わし、ここで等しい列は同じＳＥを指す。各々のＳＥは、単一の列シンボル表エントリになる候補である。ＲＳＭが一旦構築されれば、ＳＥ参照カウントに基づく単一の列エントリからなるシンボル表を生成させることができる。これにより、いくつかのデータ組については効率的な圧縮がもたらされるが、それは繰返されるＳＥが小さなバイト索引を通じてシンボル表に符号化されることになるからである。より高い圧縮を達成するには、列の並びに代えてシンボル表への索引を用い、そして多数列のシンボル表エントリを生成すればよい。
【０１１１】
多エントリ（MultiEntry：ＭＥ）とは、多数列のシンボル表のエントリの候補を表わすものである。これはその最初の列、列カウント、さらにいくつかのフィールドの（行、列）対を用いて記述される。この実施例においては、圧縮の行為は所与のＲＳＭについて有用なＭＥの組を識別する行為に関係する。
【０１１２】
ブロックレベルの列の再順序付けの計算を行なうにはいくつかのステップを取ることができる。第１のステップ（ステップ（Ａ））においては、経験的な規則を用いてブロックレベルの列の再順序付けを計算することができる。すなわち（列の濃度，列の長さの濃度）によって列を順序付ける。圧縮部はこの規則を用いてＲＳＭごとに１回ブロックレベルの列の再順序付けを決定する。一実施例において、以下の２列c1，c2はこの順序付けの規則により等しい、すなわちc1≡c2と考えられるか、またはこれに代えて列c1はc2よりもっと許容可能であると考えられ得る。
【０１１３】
1 1
1 2
1 1
1 2
1 1
1 2
1 1
1 2
1 1
1 2
1 1
2 2
ステップ（Ａ）が終了すると、辞書構築ステップを実行することができる（ステップ（Ｃ））。このステップはＲＳＭについて｛ＭＥ｝を識別することに関する。ＲＳＭは、ＳＥへのポインタからなるアルファベット全てにわたるテキストとして考えることができる。一実施例における８ｋのブロックについては、テキストの長さはおよそ５０００〜１００００シンボルの範囲内（２００〜４００行・２５列）であり、ブロック当たりの個々のシンボルの数はおよそ７００〜９００の範囲内である。したがって、｛ＭＥ｝を識別する問題は、通常の１バイトのアルファベット（２５６・３  ２［７００，９００］）よりも
約３倍のアルファベットサイズのアルファベット全てにわたる代理の圧縮の問題として考えられ得る。
【０１１４】
一実施例において、圧縮部はステップ（Ａ）とステップ（Ｃ）との間に追加のステップ（Ｂ）を用い、ここでは「プレフィックス検出」ステップと呼ぶことにする。このステップにおいては、圧縮されているデータ組の個々の特性、たとえば１組の行を含むデータ組の特性が捕獲される。上記データ組の個々の特性としては、これが１組の行であり、列がステップ（Ａ）にて列の濃度で順序付けられるというものがある。
【０１１５】
｛ri｝i=1nの行の組についてＮ次のデジタル圧縮探索木を構築することができる。この探索木はＮ行につき正しくＮ個の葉と、根ノードと、いくつかの枝ノードとを有する。この木は以下の木構築手順により記述され得る。
【０１１６】
・空（empty）の木は根ノードのみを含む。
【０１１７】
・第１の行r1を木に追加した後、木は根ノードと、１つの葉ノードと、上記根を上記葉につなぐ１つの辺とを含む。この辺はr1にあるすべてのシンボルによってラベル付けされる。
【０１１８】
・行r2を木に追加するときに１つの葉ノードを追加する。
【０１１９】
r2における第１のシンボルがr1における第１のシンボルと同じであれば、上記の古い辺を削除し、新たな枝ノードを木に追加し、根をこの新たな枝とつなぎ、新たな枝ノードを両方の葉とつなぐ。根から上記新たな枝ノードへの辺を、行r1およびr2の最も長い共通のプレフィックスでラベル付けする。これに対応して、新たな枝ノードを葉につなぐ辺を行r1およびr2のサフィックスでラベル付けする。
【０１２０】
r2における第１のシンボルがr1における第１のシンボルと同じでなければ、単に根から新たな葉への新たな辺を追加し、これをr2にあるすべてのシンボルでラベル付けする。木の構築はＲＳＭにおけるすべての行について再帰的に進行する。
【０１２１】
例として以下の４行が木に追加されると仮定する。
【０１２２】
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNO1QRSTUVWXYZ
1BCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTAAAAAA
木は根ノードから出て行く２つの辺を有し、そのうち１つはr3についての葉ノードと根とをつなぎ、r3にあるすべてのシンボルでラベル付けされる。もう１つの辺は枝ノードと根とをつなぎ、この辺はシンボル
ABCDEFGHIJKLMNO
でラベル付けされる。この枝ノードから出て行く２つの辺はそれぞれ
1QRSTUVWXYZ
および
PQRST
でラベル付けされる。第１の辺は行r2についての葉と上記枝をつなぎ、第２の辺は上記枝を別の枝とつなぐ。最後に、上記別の枝は、これをr1およびr4についての葉とつなぐ２つの辺を有し、これはそれぞれ
UVWXYZ
および
AAAAAA
でラベル付けされる。図２４はこの木の一例を示す。
【０１２３】
この木は３つの特性を有する。
【０１２４】
・各々の枝ノードは少なくとも２つの出て行く辺を有する。
【０１２５】
・この木は多くとも２・Ｎ個のノードおよび２・Ｎ個の辺を有する。
【０１２６】
・根から葉へ辺のラベルを連結させれば対応する葉の行のシンボルが得られる。
【０１２７】
・２つの行が共通のプレフィックスを共有する場合、根からその葉への経路は共通の辺を共有し、累積的な長さは最大の共通プレフィックス長さと等しい。
【０１２８】
・少なくとも２つの行により共有されるプレフィックスと枝ノードとの１対１の対応関係がある。
【０１２９】
木における各々の枝ノードが、このノードを根とするサブ木における葉ノードの数と、根からこのノードへの累積の辺の長さとでラベル付けされる場合、各々の枝ノードにつき、このノードで終わるプレフィックスをいくつの行が共有しているかがすぐにわかる。木が一旦構築されると、深いところを最初に木を単一回トラバースすることでラベル付けが可能であり、これは行の数ＮにおけるＯ（Ｎ）複雑性を有する。
【０１３０】
木が一旦構築されてラベル付けされると、プレフィックス検出が行なわれる。プレフィックス検出は単純な再帰的手順に基づく。２０の行がある以下の例について考察する。
【０１３１】
【数２】
2005531051.tif 000004
【０１３２】
この木は根ノードn0を有し、そこから１つの辺（n0，n1）が出て行き、これは
ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯＰ
でラベル付けされる。ノードn1は、そこから出て行く２つの辺（n1，n2）および（n1，n3）を有し、辺（n1，n2）は
a
でラベル付けされ、辺（n1，n3）は
b
でラベル付けされる。
【０１３３】
ノードn2およびn3は１０の葉ノードのカウントでラベル付けされ、その根からの距離は１７である。ノードn1は２０の葉ノードのカウントでラベル付けされ、根からの距離は１６である。
【０１３４】
この例では、｛ＭＥ｝の構築において以下の選択肢を提示することができる。
【０１３５】
【数３】
2005531051.tif 000005
【０１３６】
もう１度木をトラバースして｛ＭＥ｝を選択する助けとする。アルゴリズムは共通のステップを有する。各々のステップにおいて１つの枝ノードは現在のノードである。上記共通のステップは、以下の代案より選択したものからなる。
【０１３７】
代案１：現在のノードが適切なプレフィックスである追加のＭＥを作成しない。
【０１３８】
代案２：現在のノードが適切なプレフィックスである追加のＭＥを作成する。現在のノードで終わるプレフィックスをこれらＭＥに複製する。
【０１３９】
代案３：現在のノードが適切なプレフィックスである追加のＭＥを作成する。現在のノードで終わるプレフィックスを別個のＭＥに要因として除外し、追加のＭＥがこれを指すようにする。
【０１４０】
上述の２０行の例について以下のことが注目される。
【０１４１】
選択肢１は、現在のノードがn0であるときに代案１により与えられる。
【０１４２】
選択肢２は、現在のノードがn0であるときに代案２により与えられ、現在のノードがn1であるときに代案１により与えられる。
【０１４３】
選択肢３は、現在のノードがn0であるときに代案２により与えられ、現在のノードがn1であるときには代案２により与えられる。
【０１４４】
選択肢４は、現在のノードがn0であるときに代案２により与えられ、現在のノードがn1であるときには代案３により与えられる。
【０１４５】
このように、プレフィックス検出アルゴリズムは木をトラバースし、以下のことを考慮して現在の枝ノードにおいて上述の３つの代案の中から選択を行なう。
【０１４６】
・現在のノードにおけるラベル
・現在のノードのサブ木にある隣接するノードすべてにあるラベル
・新たなシンボル表エントリを作成するゼロでないコスト。
そしてプレフィックス検出アルゴリズムはサブ木に進む。この木のトラバースが葉ノードに達すると、それは対応する行のプレフィックスが圧縮するかどうか、および圧縮する場合にはどのＭＥによって圧縮するかについて「知る」。したがって、一手法においては、プレフィックス検出は所与のブロックにつき最適な組の｛ＭＥ｝からすべてのプレフィッ
クスＭＥを見つけ、最適な組が空であるかまたはプレフィックスＭＥを含まない場合にはＭＥを見つけない。
【０１４７】
一実施例において、圧縮部はまず標準のデータブロックおよびこれについてのＲＳＭを並列的にロードすることによって作動する。その後、圧縮部は新たな圧縮ブロックの作成を試みてＲＳＭを圧縮する。上記標準のブロックからの行が新たな圧縮ブロックに合わない（すなわち圧縮がない）場合、圧縮部は標準のブロックを書込んで次の組の行に進む。他では、上記標準のブロック内の自由空間を上記圧縮ブロック内の自由空間と比較することで圧縮利得の推定を行なう。圧縮の利得が全くまたはほとんどない場合、上記の標準ブロックが書込まれ、圧縮部は次の組の行に進む。一方、圧縮の利得が意味のあるものであれば、内挿を通じてブロックに合うであろう行の数を推定し、バッファリングモードに切換わる。バッファリングモードにて、データをブロックにロードせずにＲＳＭを構築する。行の推定数が一旦ＲＳＭにバッファリングされると、ＲＳＭの圧縮を再び試みる。３つの結果が考えられ得る。
【０１４８】
・ＲＳＭは単一の圧縮ブロックに合わない。
【０１４９】
・ＲＳＭは単一の圧縮ブロックに合い、自由空間の浪費は最小である。
【０１５０】
・ＲＳＭは単一の圧縮ブロックに合い、さらに多くの行をロードするための自由空間がなお存在する。
【０１５１】
第１の場合においては、［known2fit,known2notfit］インターバルを繰返し二分することにより、圧縮部が単一のブロックにロードしようとするＲＳＭ内の行の数を減少させ始め、ここで開始条件known2fit＝圧縮されていないブロック内の行の数であり、known2notfit＝推定されたが合わなかった行の数である。第２の場合、圧縮されたブロックを書込んで次の組の行に進む。第３の場合には、行の数につき新たな推定を行ないＲＳＭのバッファリングを続行する。
【０１５２】
個々のブロック圧縮はその各々が、ステップ（Ａ）、ステップ（Ｂ）を実行し、ＲＳＭの中に検出されたプレフィックスを代入し、結果として得られたＲＳＭをステップ（Ｃ）に与えることに関する。
【０１５３】
［復元部］
この発明によれば、極めて高速に、少ないオーバーヘッドで圧縮データを復元することが可能である。一実施例において、列の値／長さはブロック内で容易に入手可能である。したがって、復元プロセスで重要となるのは、これら値を位置決めするために、ブロックヘッダビットと、もし存在すれば固定列および列の置換配列と、行およびこの行が参照するシンボル表エントリの中の最初の長さバイトとを解釈することである。これら参照されるデータ値は、コストのかかる復元または再構築アルゴリズムを行なうことなしに返され得る。
【０１５４】
以上の明細書においては、この発明についてその特定の実施例を参照して説明した。しかしながら、この発明のより広い意味および範囲から逸脱することなく、さまざまな変形および変更が可能であることが明らかであろう。たとえば上述の各プロセスフローは、プロセス動作の特定の順序を参照して記載したものである。しかし、ここに記載したプロセスアクションの多くについての順序は、この発明の範囲および動作に影響を及ぼすことなく変更可能である。したがってこの明細書および図面は、限定的でなく例示的な意味で考えられるべきである。
【図面の簡単な説明】
【０１５５】
【図１】この発明の一実施例に従うデータ格納構造を示す図である。
【図２】データを格納するプロセスの一実施例のフローチャートである。
【図３】データを検索するプロセスの一実施例のフローチャートである。
【図４】この発明の一実施例に従うシンボル表内のエントリの再帰的参照について説明する図である。
【図５】この発明の一実施例に従う列の再順序付けおよびシンボル表内のエントリの再帰的参照について説明する図である。
【図６】データを格納するプロセスの代替的な実施例のフローチャートである。
【図７】この発明の一実施例に従う後端のＮＵＬＬ値の除去について説明する図である。
【図８】この発明の一実施例に従う列の再順序付けおよび後端のＮＵＬＬ値の除去について説明する図である。
【図９】この発明の一実施例に従う、未圧縮のデータブロックを圧縮データブロックに変換するプロセスを示す図である。
【図１０】この発明の一実施例に従う、データベース問合せ言語文の性能を向上させる方法のフローチャートである。
【図１１】この発明の一実施例に従う、データ重複情報を維持するプロセスを示す図である。
【図１２】この発明の一実施例に従うデータ重複情報の維持について説明する図である。
【図１３】この発明の別の実施例に従う、データ重複情報を維持する方法のフローチャートである。
【図１４】この発明の一実施例に従うデータ重複情報の更新について説明する図である。
【図１５】この発明の一実施例に従う、データベース問合せ言語文の性能を向上させる方法のプロセスフローである。
【図１６】データベース問合せ言語文の性能を向上させる別の方法のフローチャートである。
【図１７】この発明の一実施例に従う、データベース問合せ言語文の性能をどのように向上させるのかについての一例を説明する図である。
【図１８】この発明の別の実施例に従う、データベース問合せ言語文の性能を向上させる方法のプロセスフローである。
【図１９】この発明の一実施例に従う、データベース問合せ言語文によりアクセスされるデータの量を減少させるプロセスを示す図である。
【図２０】この発明の一実施例に従う、データベース問合せ言語文の性能向上を目的としてデータ重複情報をどのように使用するのかについての一例を示す図である。
【図２１】この発明のさらなる実施例に従う、データベース問合せ言語文の性能を向上させる方法のフローチャートである。
【図２２】この発明の一実施例に従う、データベース問合せ言語文を満足させるためにデータ重複情報をどのように使用するのかについての一例を示す図である。
【図２３】この発明の各実施例が実現され得るコンピュータシステムを示す図である。
【図２４】この発明の一実施例に従う探索木の一例を示す図である。
【図１】
2005531051.tif 000006
【図２】
2005531051.tif 000007
【図３】
2005531051.tif 000008
【図４】
2005531051.tif 000009
【図５】
2005531051.tif 000010
【図６】
2005531051.tif 000011
【図７】
2005531051.tif 000012
【図８】
2005531051.tif 000013
【図９】
2005531051.tif 000014
【図１０】
2005531051.tif 000015
【図１１】
2005531051.tif 000016
【図１２】
2005531051.tif 000017
【図１３】
2005531051.tif 000018
【図１４】
2005531051.tif 000019
【図１５】
2005531051.tif 000020
【図１６】
2005531051.tif 000021
【図１７】
2005531051.tif 000022
【図１８】
2005531051.tif 000023
【図１９】
2005531051.tif 000024
【図２０】
2005531051.tif 000025
【図２１】
2005531051.tif 000026
【図２２】
2005531051.tif 000027
【図２３】
2005531051.tif 000028
【図２４】
2005531051.tif 000029
【手続補正書】
【提出日】平成16年10月25日(2004.10.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを圧縮されたフォーマットで格納する方法であって、
ディスク（１１２）上にある１つ以上のデータベースブロックにデータを格納する要求を受取るステップを含み、前記データは１つ以上のデータ項目を含み、前記方法はさらに、
前記データの中に冗長データ項目の存在を判断するために前記データを分析するステップと、
前記データに対応してディスク上のデータ構造（１０２ｂ，１０４ｂ，１０６ｂ）をフォーマット付けするステップとを含む方法であって、前記方法はさらに、
前記冗長データ項目を格納するためのシンボル構造（１１０，４１０）を作成するステップと、
前記ディスク上のデータ構造（１０２ｂ，１０４ｂ，１０６ｂ）を、前記シンボル構造（１１０，４１０）に格納された前記冗長データ項目に関連付けるステップとを含むことを特徴とする、方法。
【請求項２】
前記シンボル構造（１１０，４１０）に格納された前記冗長データ項目を参照するためにリンクまたはポインタ（１３６，１３８，１４０，１５４，１５６，１６２）が用いられる、請求項１に記載の方法。
【請求項３】
前記データは、１つ以上の行（１０２ａ，１０４ａ，１０６ａ）を有するリレーショナルデータを含む、請求項１に記載の方法。
【請求項４】
各々の行（１０２ａ，１０４ａ，１０６ａ）はインラインに処理される、請求項３に記載の方法。
【請求項５】
一群の行（１０２ａ，１０４ａ，１０６ａ）はオフラインで処理される、請求項３に記載の方法。
【請求項６】
前記データは、冗長データ項目がある可能性が増加するように再編成される、請求項１に記載の方法。
【請求項７】
前記データの濃度は再編成において考慮される、請求項６に記載の方法。
【請求項８】
前記シンボル構造（４１０）は、前記シンボル構造（４１０）内の他のエントリ（４３２，４３４）を再帰的に参照するエントリ（４８０）を含む、請求項１に記載の方法。
【請求項９】
前記エントリ（４８０）は、前記シンボル構造（４１０）内の多数の他のエントリ（４３２，４３４）を参照する、請求項８に記載の方法。
【請求項１０】
前記エントリは、格納された前記冗長データ項目と、前記シンボル構造（４１０）内の他のエントリ（４３２，４３４）を再帰的に参照するエントリ（４８０）との両方を含む、請求項８に記載の方法。
【請求項１１】
前記シンボル構造（４１０）内の他のエントリ（４３２，４３４）を再帰的に参照するエントリ（４８０）に関連付けられた第２のディスク上のデータ構造を含む、請求項８に記載の方法。
【請求項１２】
さらに、前記シンボル構造（４１０）内の他のエントリ（４３２，４３４）を再帰的に参照する前記エントリ（４８０）への参照に、前記ディスク上のデータ構造内の多数のフィールドがひとまとめで関連付けられる、第２のディスク上のデータ構造を含む、請求項８に記載の方法。
【請求項１３】
データの列は再順序付けされる、請求項１２に記載の方法。
【請求項１４】
前記データの列は、前記ディスク上のデータ構造（１０２ｂ，１０４ｂ，１０６ｂ）内の前記多数のフィールドについて繰返す並びがある可能性が増加するように再順序付けされる、請求項１３に記載の方法。
【請求項１５】
列の再順序付けは前記データベースブロックのレベルで実行される、請求項１２に記載の方法。
【請求項１６】
後端のＮＵＬＬ値は前記ディスク上のデータ構造（１０２ｂ，１０４ｂ，１０６ｂ）内に含まれない、請求項１３に記載の方法。
【請求項１７】
前記データベースブロックは圧縮が適用されているかどうかを標示するメタデータを含む、請求項１に記載の方法。
【請求項１８】
前記メタデータは単一のビットを含む、請求項１７に記載の方法。
【請求項１９】
前記データベースブロックは、列が再順序付けされているかどうかを標示するメタデータを含む、請求項１に記載の方法。
【請求項２０】
コンピュータ読取可能媒体を含むコンピュータプログラム製品であって、前記コンピュータ読取可能媒体には、プロセッサにより実行されると、請求項１から請求項１９に記載の方法のいずれかを前記プロセッサに実行させる命令シーケンスが格納される、コンピュータプログラム製品。
【請求項２１】
請求項１から請求項１９に記載の方法のいずれかを実行するための手段を含む、データを圧縮されたフォーマットで格納するためのシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
上述の待ち時間に関する諸問題や、圧縮の利得が必ずしも確実ではないという事情を考慮すると、データベースまたはその他の種類の計算システムにおいて、圧縮における空間上の利益は必ずしもそれにかかる時間に見合うものではない。したがって、使用されるディスク空間の減少という効果をもたらすだけでなく、圧縮されたデータに対するデータベース問合せ言語文の性能に悪影響のない圧縮技術が必要とされている。
米国特許第６，００６，２３２号においては、サブ表ブロックを含む表であって、上記サブ表ブロックが、圧縮されたデータと、この圧縮されたデータに関連した共通の情報とを含むものが開示されている。
ゴールドスタイン  Ｊ．（Goldstein J.）他による「リレーションおよび索引の圧縮（Compressing relations and indexes）」においては、ページレベルの圧縮およびファイルレベルの圧縮を用いた圧縮アルゴリズムが開示されている。上記ページレベルの圧縮の際には、或る範囲内の値がビットで表わされる。上記ファイルレベルの圧縮の際には、ファイル内のオブジェクトがこのファイルの圧縮前に分割される。
欧州特許第００７９４６５号では、レコードの内容を格納する方法であって、データベースからデータ要素全ての要約リストを定めるステップと、上記要約リストを用いて索引表に上記データ要素を対応付けるステップとを含むものが開示されている。
【国際調査報告】
2005531051.tif 000030
2005531051.tif 000031
2005531051.tif 000032
2005531051.tif 000033
2005531051.tif 000034
2005531051.tif 000035
2005531051.tif 000036