データベース管理システム、同システムにおけるページ配置最適化方法及びデータベース管理プログラム
【課題】データ格納手段におけるページ再配置が、再配置の効果の大きいページについて、システムに最適となるように行えるようにする。
【解決手段】ミスヒットテーブル２６１の各行及び各列には、データベース１０内の全ページのうちの、例えばバッファミスヒットの頻度が高い上位一定数のページの各々が対応付けられる。ミスヒットテーブル更新部２６４はバッファミスヒット時に、ミスヒットテーブル２６１の、直前にバッファミスヒットしたページに対応する例えば行と、今回バッファミスヒットしたページに対応する例えば列とで決まる、当該テーブル２６１の配列要素の値をインクリメントする。ページ配置最適化部２７は、テーブル２６１内の各配列要素のうち、例えば閾値を超える配列要素の、行及び列にそれぞれ対応付けられたページのデータがデータベース１０内で連続するようにページを再配置する。
【解決手段】ミスヒットテーブル２６１の各行及び各列には、データベース１０内の全ページのうちの、例えばバッファミスヒットの頻度が高い上位一定数のページの各々が対応付けられる。ミスヒットテーブル更新部２６４はバッファミスヒット時に、ミスヒットテーブル２６１の、直前にバッファミスヒットしたページに対応する例えば行と、今回バッファミスヒットしたページに対応する例えば列とで決まる、当該テーブル２６１の配列要素の値をインクリメントする。ページ配置最適化部２７は、テーブル２６１内の各配列要素のうち、例えば閾値を超える配列要素の、行及び列にそれぞれ対応付けられたページのデータがデータベース１０内で連続するようにページを再配置する。
【発明の詳細な説明】
【技術分野】
【０００１】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムに係り、特にデータ格納手段に格納されたページデータをアクセスする際のアクセス効率を向上するのに好適な、データベース管理システム、同システムにおけるページ配置最適化方法及びデータベース管理プログラムに関する。
【背景技術】
【０００２】
一般に、データベース管理システム（ＤＢＭＳ：Data Base Management System）では、アプリケーションから与えられたデータと、データを高速に検索するために必要な索引等の情報とを、データ格納手段としてのディスク装置上に格納する。ディスク装置の記憶領域（ディスク領域）はページ（またはブロック）と呼ばれる固定長の領域に分割され、個々のページ（領域）に上記の情報が分割して格納される。
【０００３】
ＤＢＭＳ（データベース管理システム）は、ユーザからの要求に応じてアプリケーションから与えられた問い合わせ（クエリ）を処理する場合、ディスク装置に格納された情報のうちクエリの処理に必要な一連の情報を、当該ディスク装置から（例えばメモリ上に確保された）入出力バッファに読み込む。ＤＢＭＳは、入出力バッファ上でクエリの処理を行う。多くの場合、このディスクアクセスを伴う、入出力バッファへの情報の読み込みに要する時間の、クエリ処理時間に占める割合が大きい。
【０００４】
そこで、ディスク装置から入出力バッファへの情報読み込みの回数を減らす工夫、即ち目的の情報が当該バッファに存在する確率を高める工夫が、従来からなされている（例えば、特許文献１参照）。ここでは、ディスク装置の物理的な領域単位に統計情報が採取される。この統計情報は、対応する領域がアクセスされた際に入出力バッファ（キャッシュメモリ）に当該領域のデータが存在するキャッシュヒットまたは当該領域のデータが存在しないキャッシュミスとなった回数（キャッシュヒット／ミス回数）を含む。ディスク制御装置は、上位装置よりアクセス要求があり、且つアクセス対象データがキャッシュ内に存在しない場合には、上記統計情報をもとに、当該データをキャッシュにロードした場合にヒットの可能性があるかを判定する。そしてディスク制御装置は、ヒットの可能性がある場合に、アクセス対象データをキャッシュにロードする。
【特許文献１】特開平６−１１９２４４号公報（段落００１３，００２９及び００３０）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記した従来技術においては、アクセス頻度の高いページの情報が入出力バッファに存在する確率を高めることができるものの、アクセス頻度の高くないページの情報が入出力バッファに存在する確率を高めることは難しい。即ち、アクセス頻度の高くないページの情報、特にアクセス頻度が中程度のページについては、ディスク装置から入出力バッファへの情報読み込みの回数を減らすことは難しい。したがって、アクセス頻度の高くないページの情報に関しては、ディスクアクセスに要する時間がクエリの応答性能を決めることになる。
【０００６】
一般に、ディスク装置のアクセス性能は、ディスク上に連続に配置されたデータを順次読み出す場合と、ランダムに配置されたデータを読み出す場合とで大きく異なり、前者の方が後者より１桁以上応答性能が良い。このためクエリの処理に必要な一連の情報が、ディスク上の連続した領域、つまり連続したページに配置されるように工夫するならば、ディスクアクセスの効率を上げてクエリの応答性能を高速化することが可能となる。
【０００７】
そこで、情報の種別（ページ種別）によって、それぞれの情報がどのようにアクセスされるかを推定して、それぞれの情報を格納するページを決定することで、ディスクアクセスがシーケンシャルになるようにページの再配置を行うことが考えられる。例えば、データの全検索（フルスキャン）が発生する場合は、フルスキャンの対象となる一連のデータをその単位で連続になるように再配置するならば、ディスクアクセス効率を向上することが期待される。また、Ｂ木の索引を持っていてＢ木を使用した大小比較を行うような場合は、Ｂ木の葉ページを昇順または降順に連続になるように再配置するならば、ディスクアクセス効率を向上することが期待される。
【０００８】
しかし、情報の種別を手掛かりにしてページの再配置を行うだけでは、多種多様なクエリが様々なタイミングで発生する実際のシステムにおいては、必ずしもそれが最適な配置になるとは限らない。つまりクエリ処理のためのページのアクセス順は、アプリケーションが実行するクエリとその実行順序に大きく依存しており、事前にそれを予測するのが難しい。更にクエリによっては、上述のページ再配置では最適にならないケースもある。例えばＢ木を用いた検索を考えると、Ｂ木を用いた一致検索のクエリが多量に行われる場合は、Ｂ木のルートページから葉ページに向かった縦方向のアクセスになり、この縦方向のページ群のうち頻繁にアクセスされるページを連続または近傍に配置することが効果的になる。また、連続的に配置してもその部分はバッファ上に長期間存在していて、ディスクアクセスが殆ど発生しないケースもある。更に、どのページをどのように配置するのが効果的なのか、ページ再配置の優先順位を判別するのが困難である。
【０００９】
本発明は上記事情を考慮してなされたものでその目的は、データ格納手段におけるページ再配置が、当該データ格納手段を利用するシステムがどのようなものであっても、再配置の効果の大きいページについて、そのシステムに最適となるように行える、データベース管理システム、同システムにおけるページ配置最適化方法及びデータベース管理プログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明の１つの観点によれば、記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムが提供される。このデータベース管理システムは、外部からの要求を処理するクエリ処理手段と、上記データ格納手段に格納された一部のページデータを保持する入出力バッファと、このクエリ処理手段によって要求されたページデータが上記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを上記クエリ処理手段に返し、存在しなければバッファミスヒットとして上記要求されたページデータを上記データ格納手段から読み出して上記入出力バッファに配置すると共に当該ページデータを上記クエリ処理手段に返す入出力バッファ管理手段と、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、上記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が上記配列の各行及び各列に対応付けられたミスヒットテーブルと、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合、上記ミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、上記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、上記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが上記データ格納手段内で連続するようにページを再配置するページ配置最適化手段とを備える。
【００１１】
このような構成において、ミスヒットテーブル（論理的に２次元のカウンタの配列）には、ミスヒットテーブル更新手段のインクリメント操作により、バッファミスヒットしたページの順序関係を表す統計情報が採取される。ページ配置最適化手段は、この統計情報をもとに、即ちミスヒットテーブルの各配列要素の値をもとに、その配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータがデータ格納手段内で連続するように、ページを再配置する。
【００１２】
このように、上記の構成においては、連続してバッファミスヒットする頻度の高いページ順序に従ってページが再配置されることにより、バッファミスヒットが発生しても、データ格納手段内では、連続配置されたページデータへのシーケンシャルアクセスとして処理されて、アクセス効率を上げることができ、結果としてクエリの応答性能を向上することができる。しかも、ミスヒットテーブルに採取される統計情報は、データ格納手段の利用状況を動的に反映している。このため、データ格納手段を利用するシステムがどのようなものであっても、再配置の効果の大きいページについて、そのシステムに最適となるページ再配置を実現できる。また、ミスヒットテーブルに採取される統計情報から、ページ配置の最適化の効果に基く再配置の優先順位を判別することも可能である。
【００１３】
上記の構成は、データ格納手段に対するデータの追加削除が繰り返し多数行われるシステムや、障害回復の一方式であるシャドウページ方式を採用するデータベース管理システムなど、データ格納手段内の情報が断片化（フラグメント）しやすいケースで特に有効である。更に、データ格納手段が大規模化して、例えばディスク領域を多量に使用するようなシステムでは、ディスクのシーク時間が増加することで断片化のペナルティが大きくなるが、そのような場合に特に有効である。
【００１４】
また、上記の構成においては、通常のページ再配置による最適化がデータの種別のみを手掛かりにするのに比較して、データの種別だけでは判別できないような、システム固有の隠れたページアクセスの規則性を統計的に見出して手掛かりとするため、仮に既にデータの種別による最適化が行われた後であっても、更にシステム性能を向上するような最適化を行うことができる。よって、上記の構成におけるページ再配置の最適化は、ページ種別に基く最適化よりも効果が大きい。
【００１５】
また、上記の構成に、１次元のカウンタの配列から構成されるミスヒットカウンタアレイであって、上記データ格納手段内の各ページが上記配列のそれぞれの配列要素に対応付けられたミスヒットカウンタアレイと、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットしたページに対応する上記ミスヒットカウンタアレイの配列要素の値をインクリメントするミスヒットカウンタアレイ更新手段と、上記ミスヒットカウンタアレイの配列要素の値に基づいて、バッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページを、上記ミスヒットテーブルの各行及び列の要素として抽出するミスヒットテーブル要素抽出手段と、このミスヒットテーブル要素抽出手段によって抽出された各ページを上記ミスヒットテーブルを構成する配列の各行及び各列に対応付けるミスヒットテーブル構築手段とを追加すると良い。
【００１６】
このような構成においては、データ格納手段内の全ページの各々について、バッファミスヒットの頻度が、ミスヒットカウンタアレイ（１次元のカウンタの配列）に採取され、その採取結果をもとにバッファミスヒットの頻度の高いページが、ミスヒットテーブルの各行及び列の要素として抽出される。これにより、ミスヒットテーブルのサイズが巨大化するのを効果的に防ぐことができる。
【００１７】
また、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合に、当該バッファミスヒットに先行してミスヒットした最大Ｘ個（Ｘは２以上の整数）のページと、今回ミスヒットと判定されたページとの各々のページ対にそれぞれ対応する、上記ミスヒットテーブルの配列要素の値が、上記ミスヒットテーブル更新手段によってインクリメントされる構成としても良い。
【００１８】
このような構成においては、バッファミスヒットの順序にアクセスの明確な順序性を見出すことができるほどの統計的な規則性がなく、連続してバッファミスヒットとなるページ対のみに着目したのでは、ミスヒットテーブルの各配列要素の値が均一になってしまうような場合であっても、時間的に比較的ゆるやかなページアクセス順の因果関係があれば、それらの関係を見い出して、それらのページが互いに近くに配置される。これによりデータ格納手段がディスク装置を用いて実現されるシステムでは、ディスクのシーク時間を減らしてディスクアクセスの効率を向上し、結果としてクエリの応答性能を向上することができる。
【発明の効果】
【００１９】
本発明によれば、バッファミスヒットしたページの順序関係を表す統計情報を採取し、その統計情報をもとに、再配置の効果の大きいページについて、データ格納手段を利用するシステムに最適となるように、ページ再配置を行うことができるため、当該システムがどのようなものであっても、当該システムに適合した最適なページ再配置を実現できる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の一実施形態につき図面を参照して説明する。
図１は本発明の一実施形態に係るデータベース管理システムを備えた計算機システムの構成を示すブロック図である。同図において、データベース１０は、複数のファイルを格納するデータ格納手段であり、磁気ディスクドライブ等のディスク装置に置かれる。データベース１０の領域は、ページ（またはブロック）と呼ばれる固定長の領域に分割されて管理される。このページのサイズは、例えばユーザの操作によってシステム毎に設定可能であり、本実施形態では、２ＫＢ，４ＫＢ，８ＫＢ及び１６ＫＢの中から選択可能である。各ページには、例えばデータベース１０の領域内のオフセット位置が領域の開始位置に近い方から順に、シリアルのページ番号Ｐｉｄ（Ｐｉｄ＝１，２，…，ｎ）が割り当てられている。データベース１０内では、各ファイルのデータと、当該データを高速に検索するために必要な索引等の情報がページ単位に分割されて、個々のページに格納される。
【００２１】
データベース管理システム（ＤＢＭＳ）２０は、データベース１０を管理する。データベース管理システム２０は、ユーザインタフェース２１と、クエリ処理部２２と、入出力バッファ２３と、バッファ管理部２４と、１次統計採取部２５と、２次統計採取部２６と、ページ配置最適化部２７とから構成される。
【００２２】
ユーザインタフェース２１は、ユーザ（アプリケーション）とのインタフェースをなす。ユーザーインタフェース２１は、ユーザの入力操作に応じてアプリケーションから与えられるクエリ（query: 問い合わせ、例えば検索要求）の受け付け、及び当該クエリに対する応答の出力等を行う。クエリ処理部２２は、ユーザーインタフェース２１によって受け付けられたクエリを当該インタフェース２１から受け取ると、処理に必要な情報が格納されたページを順次バッファ管理部２４に要求し、ユーザ（アプリケーション）からのクエリを処理する。
【００２３】
入出力バッファ２３は、データベース１０に格納されている一部のページデータを保持するキャッシュである。入出力バッファ２３は計算機システムのメモリ（図示せぬ）上に配置される。バッファ管理部２４は、入出力バッファ２３を管理する。即ちバッファ管理部２４は、クエリ処理部２２から要求されるページデータが既に入出力バッファ２３上に存在すれば、当該入出力バッファ２３上の要求されたページデータを、要求に対する応答としてクエリ処理部２２に返す。バッファ管理部２４はまた、クエリ処理部２２から要求されるページデータが入出力バッファ２３上に存在しなければ、バッファミスヒットを判定する。この場合、バッファ管理部２４は、従来からよく知られているＬＲＵ（Least Recently Used）制御に基いて入出力バッファ２３上に空きページを確保する。そしてバッファ管理部２４は、要求されたページデータをデータベース１０から読み出して、入出力バッファ２３上に確保された空きページに配置すると共に、その配置されたページデータをクエリ処理部２２に返す。
【００２４】
１次統計採取部２５は、上述のバッファミスヒットしたページの統計情報（１次統計情報）を採取する。１次統計採取部２５は、ミスヒットカウンタアレイ２５１と、ミスヒットカウンタアレイ更新部２５２と、ミスヒットカウンタアレイ再構築部２５３とを含む。
【００２５】
ミスヒットカウンタアレイ２５１は、複数のカウンタ（例えばソフトウェアカウンタ）の１次元の配列から構成される。ミスヒットカウンタアレイ２５１は計算機システムの上記メモリ上に配置される。ミスヒットカウンタアレイ２５１中の各カウンタは、データベース１０内の全ページの各々（または一部の各ページ）と対応付けられており、対応するページのミスヒットの回数をカウントするのに用いられる。
【００２６】
ミスヒットカウンタアレイ更新部２５２は、バッファミスヒットしたページに対応する、ミスヒットカウンタアレイ２５１内のカウンタの値を１インクリメントする。ミスヒットカウンタアレイ再構築部２５３は、バッファミスヒットしたページの１回目の統計情報採取の後に、その採取結果に基づいて、バッファミスヒットの発生頻度の比較的高いページ（例えば、上位の一定数のページ）を、２回目の統計情報採取の候補として抽出する。ミスヒットカウンタアレイ再構築部２５３は、抽出された各ページのミスヒットの回数をカウント可能とするために、ミスヒットカウンタアレイ２５１を再構築する。
【００２７】
図２は再構築前のミスヒットカウンタアレイ２５１と再構築後のミスヒットカウンタアレイ２５１の一例を示す。本実施形態において、再構築前のミスヒットカウンタアレイ２５１は、データベース１０のページ数をｎとすると、図２（ａ）に示すように、全ページ分（ここでは、ｎページ分）のカウンタの１次元配列から構成される。このｎページ用のミスヒットカウンタアレイ２５１内の各カウンタは、それぞれデータベース１０内の各ページのページ番号Ｐｉｄと対応付けられている。図２（ａ）に示すミスヒットカウンタアレイ２５１内の各カウンタの長さをＬ１とする。一方、再構築後のミスヒットカウンタアレイ２５１は、データベース１０の全ページの中から２回目の統計情報採取の候補として抽出されたページの数をｍ（ｍ＜ｎ）とすると、図２（ｂ）に示すように、ｍページ分のカウンタの１次元配列から構成される。この図２（ｂ）に示す、ｍページ用のミスヒットカウンタアレイ２５１内の各カウンタの長さをＬ２（Ｌ２＞Ｌ１）とする。
【００２８】
２次統計採取部２６は、バッファミスヒットしたページのアクセス順序関係に関する統計情報（２次統計情報）を採取する。２次統計採取部２６は、ミスヒットテーブル２６１と、ミスヒットテーブル要素抽出部２６２と、ミスヒットテーブル構築部２６３と、ミスヒットテーブル更新部２６４とを含む。
【００２９】
ミスヒットテーブル２６１は、複数のカウンタ（例えばソフトウェアカウンタ）を計算機システムのメモリ上に論理的にＭ行×Ｍ列の２次元に配列することで構成される。ミスヒットテーブル２６１の各行ｉ及び列ｉ（ｉ＝１，２，…，Ｍ）の対には、ミスヒットテーブル要素抽出部２６２によって抽出されたＭ個のページの各々が、そのページ番号Ｐｉｄに対応付けて割り当てられる。図３は、このミスヒットテーブル２６１のデータ構造例を示す。図３では、作図の都合上、Ｍ＝７のミスヒットテーブル２６１が示されているが、実際にはＭは例えば１０，０００など、十分大きい値である。
【００３０】
ミスヒットテーブル要素抽出部２６２は、ミスヒットカウンタアレイ２５１の各カウンタによって示される、ページ毎のバッファミスヒットの回数（つまり頻度）をもとに、上位Ｍページ（ミスヒットの発生頻度の高い上位Ｍページ）を、ミスヒットテーブル２６１の各行及び列の要素として抽出する。
【００３１】
ミスヒットテーブル構築部２６３は、ミスヒットテーブル要素抽出部２６２によって抽出されたＭページのページ番号Ｐｉｄをもとに、ミスヒットテーブル２６１を構築する。ミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１と対応付けられているページの１つがバッファミスヒットし、その直後に別のページがバッファミスヒットした場合に、その連続してミスヒットした２つのページに対応するミスヒットテーブル２６１内の配列要素（フィールド）の値（カウンタ値）を１インクリメントする。
【００３２】
ページ配置最適化部２７は、バッファミスヒットが連続して発生する頻度の高い各ページ対がそれぞれデータベース１０上で連続するように再配置する。ページ配置最適化部２７は、ページ再配置候補抽出部２７１と、ページ入れ替え部２７２とを含む。
【００３３】
ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１の各フィールドの値をもとに、バッファミスヒットが連続して発生する頻度の高いページ対を頻度順に抽出する。ページ入れ替え部２７２は、ページ再配置候補抽出部２７１によって抽出された各ページ対がそれぞれデータベース１０上で連続するように、ページの内容の入れ替えを行う。
【００３４】
データベース管理システム２０内の入出力バッファ２３、ミスヒットカウンタアレイ２５１及びミスヒットテーブル２６１を除く各要素は、計算機システムにインストールされたデータベース管理のためのソフトウェアプログラム（データベース管理プログラム）を当該計算機システム（内のＣＰＵ）が読み取って実行することにより実現される。このプログラムは、コンピュータで読み取り可能な記憶媒体（フロッピー（登録商標）ディスクに代表される磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤに代表される光ディスク、フラッシュメモリに代表される半導体メモリ等）に予め格納して頒布可能である。また、このプログラムが、ネットワークを介してダウンロード（頒布）されても構わない。
【００３５】
次に、図１の計算機システム内のデータベース管理システム２０の動作について、データベース１０内のページの配置の最適化のための処理を例に説明する。
まず、このページの配置の最適化のための処理の概略手順について、図４のフローチャートを参照して説明する。まず、１次統計採取部２５は、１次統計情報採取処理（ステップＳ１）を実行する。この１次統計情報採取処理により、バッファミスヒットしたページの統計情報（１次統計情報）が採取される。その後、２次統計採取部２６に制御が移る。２次統計採取部２６は、２次統計情報採取処理（ステップＳ２）を実行する。この２次統計情報採取処理では、１次統計採取部２５によって採取された１次統計情報をもとに、バッファミスヒットの頻度の高い上位Ｍページが抽出される。そして抽出されたＭページの全てのページ対Ｐｉ，Ｐｊ（ｉ＝１，２，…，Ｍ，ｊ＝１，２，…，Ｍ）の組み合わせ毎に、ページＰｉがバッファミスヒットした直後にページＰｊがバッファミスヒットする回数を表す統計情報（２次統計情報）が採取される。その後、ページ配置最適化部２７に制御が移る。ページ配置最適化部２７は、２次統計採取部２６による２次統計情報採取結果をもとに、ページ配置最適化処理（ステップＳ３）を実行する。このページ配置最適化処理では、続けてバッファミスヒットを発生する頻度の高いページ対が、ページ再配置の候補として抽出され、その抽出された各ページ対がそれぞれデータベース１０上で連続するように、ページの内容が入れ替えられる。
【００３６】
次に、１次統計情報採取処理（ステップＳ１）の詳細な手順について、図５のフローチャートを参照して説明する。なお、１次統計情報採取処理の前には、ミスヒットカウンタアレイ２５１の各カウンタの値が０に初期化される。この初期化のタイミングは、例えばデータベース管理システム２０の起動時など、１次統計情報採取処理が開始されるまでの任意の時点で良い。また、初期化のタイミングが、外部からユーザインタフェース２１を介して与えられる構成であっても良い。
【００３７】
まず、１次統計採取部２５は、ミスヒットカウンタアレイ２５１を用いて、データベース１０内の全ページ（ここでは、ページ番号１（Ｐｉｄ＝１）乃至ｎ（Ｐｉｄ＝ｎ）のｎページ）を対象に、バッファミスヒットを発生したページの統計情報を採取する（ステップＳ１１）。このステップＳ１１において、１次統計採取部２５のミスヒットカウンタアレイ更新部２５２は、バッファ管理部２４でバッファミスヒットが判定される都度、ミスヒットしたページのページ番号Ｐｉｄに対応付けられた、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５１のカウンタを１インクリメントする。但し、インクリメント対象のカウンタの値が、カウント可能な最大値となっている場合には、当該カウンタの値は最大値に保持される。
【００３８】
ステップＳ１１が開始されてから、例えば一定期間が経過すると、ミスヒットカウンタアレイ再構築部２５３に制御が移る。ミスヒットカウンタアレイ再構築部２５３は、ミスヒットページ（のページ番号）を、対応するミスヒットカウンタアレイ２５１のカウンタの値の大きい順、つまりミスヒットの頻度の高い順（降順）にソートする（ステップＳ１２）。なお、ステップＳ１１が開始されてから発生したバッファミスヒットの総数が一定値を超えた場合に、ステップＳ１２が実行される構成としても良い。この他に、ミスヒットカウンタアレイ２５１内の任意のカウンタのカウント値がカウント可能な最大値となった場合に、ステップＳ１２が実行される構成としても良い。
【００３９】
次にミスヒットカウンタアレイ再構築部２５３は、ソート後のミスヒットページから、上位のｍ（ｍ＜ｎ）ページ（のページ番号）を、ミスヒットカウンタアレイ再構築後の統計情報の採取候補として抽出する（ステップＳ１３）。抽出されたｍページのページ番号はメモリ上に記録される。次に、ミスヒットカウンタアレイ再構築部２５３は、ミスヒットカウンタアレイ２５１を図２（ｂ）に示すｍページ用に再構築する（ステップＳ１４）。このとき、ミスヒットカウンタアレイ２５１内の各カウンタ（フィールド）は０に初期化される。すると、再びミスヒットカウンタアレイ更新部２５２に制御が移る。
【００４０】
ミスヒットカウンタアレイ更新部２５２は、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１を用いて、ミスヒットカウンタアレイ再構築部２５３によって決定されたｍページだけを対象に、バッファミスヒットを発生したページの統計情報を採取する（ステップＳ１５）。このステップＳ１５において、ミスヒットカウンタアレイ更新部２５２は、上記抽出されたｍページのうちのいずれかがバッファミスヒットした場合だけ、そのミスヒットしたページのページ番号Ｐｉｄに対応付けられた、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１のカウンタを１インクリメントする。ステップＳ１５は、例えば一定期間実行される。このステップＳ１５の実行が終了した時点の、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１の各カウンタの値が、目的の１次統計情報を表す。ここで、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１の各カウンタの長さＬ２は、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５１の各カウンタの長さＬ１より大きい。したがって、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１には、ミスヒットの頻度が比較的高い上位ｍページの精度の高い統計情報が、１次統計情報として採取されることになる。
【００４１】
ここで、１次統計採取部２５において、２ステップで統計情報を採取する理由について説明する。まず、データベース１０内の全ページ（ｎページ）についてバッファミスヒットの精度の高い統計情報を１ステップで採取するには、長さがＬ２（例えば４バイト）のｎ個のカウンタの配列をメモリ上に配置する必要があるものとする。本実施形態では、データベース１０のサイズ（つまりデータベース１０のページ数ｎ）が極めて大きく、カウンタ長をＬ２（４バイト）とすると、ｎ個のカウンタの配列をメモリ上に確保できないものとする。そこで本実施形態では、Ｌ２より短い、長さがＬ１（例えばＬ２の１／８の長さである４ビット）のｎ個のカウンタの配列を、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５としてメモリ上に用意することで、第１のステップで、データベース１０内の全ページ（ｎページ）についてバッファミスヒットの大まかな統計情報を比較的短時間で採取する（ステップＳ１１）。そして、この大まかな統計情報をもとにミスヒットの頻度の高い上位ｍページを抽出すると共に、長さＬ２（４バイト）のｍ個のカウンタの配列を、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５としてメモリ上に用意することで、第２のステップで、当該上位ｍページについてバッファミスヒットの精度の高い統計情報（１次統計情報）を、第１のステップに比べて十分時間をかけて採取する。
【００４２】
なお、データベース１０を複数の区画に分けて、各区画毎に順番に１次統計情報を採取することも可能である。この場合、長さＬ２のカウンタを１区画のページ数分だけ用意すれば良い。勿論、長さＬ２のｎ個のカウンタの配列をメモリ上に用意できるならば、データベース１０内の全ページ（ｎページ）について、１ステップで１次統計情報を採取できる。
【００４３】
さて、１次統計情報採取処理（ステップＳ１）で採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、そのページのバッファミスヒットの頻度順（頻度の降順）に水平軸方向に並べ、垂直軸方向に頻度を表すと、図６のようなグラフが得られる。このグラフ上で、バッファミスヒットの頻度が高い上位Ｍ個のページは、中程度のアクセス頻度を持ち、次の理由により再配置の最適化の効果が大きいページである。
【００４４】
（１）アクセス頻度の高いページはミスヒットしにくいため最適化の効果は小さい。
（２）アクセス頻度の低いページは、アクセスが発生した場合にはミスヒットする確率が高いものの、アクセス自体が希にしか発生しないためにミスヒットの頻度が低く、最適化の効果は小さい。
（３）アクセス頻度が中程度のページはミスヒットの頻度が高く、したがって最適化の効果が大きい。
【００４５】
そこで、最適化の効果が大きいミスヒットの頻度の高いページを、どの順に配置すれば最適化できるかを決定するのに必要な、２次統計情報採取処理（ステップＳ２）の詳細な手順について、図７のフローチャートを参照して説明する。
【００４６】
まず、１次統計採取部２５の１次統計情報採取処理（ステップＳ１）により、ｍビット用のミスヒットカウンタアレイ２５１内に１次統計情報が採取されると、２次統計採取部２６内のミスヒットテーブル要素抽出部２６２に制御が移る。ミスヒットテーブル要素抽出部２６２は、ｍビット用のミスヒットカウンタアレイ２５１内に採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、カウンタの値の大きい順、即ちバッファミスヒットの頻度順（頻度の降順）にソートする（ステップＳ２１）。
【００４７】
次にミスヒットテーブル要素抽出部２６２は、ステップＳ２１でのソート結果をもとに、バッファミスヒットの頻度の高い上位Ｍ個（Ｍ＜ｍ）のページを、ミスヒットページのアクセス順序関係の統計情報（つまり２次統計情報）の採取候補として抽出する（ステップＳ２２）。なお、Ｍを一定値とせずに、一定のミスヒット発生頻度を超えるページ（ページ数をＭとする）を、２次統計情報の採取候補として抽出するようにしても良い。
【００４８】
ミスヒットテーブル構築部２６３は、ミスヒットテーブル要素抽出部２６２によって抽出されたＭ個のページのページ番号Ｐｉｄをもとに、ミスヒットテーブル２６１を構築する（ステップＳ２３）。即ちミスヒットテーブル構築部２６３は、抽出されたＭ個のページのページ番号Ｐｉｄに対応付けられた行要素及び列要素を持つ、論理的にＭ行×Ｍ列の２次元のカウンタ配列から構成されるミスヒットテーブル２６１をメモリ上に構築する。但し、行ｉ及び列ｉ（ｉ＝１，２，…，Ｍ）で指定される配列要素位置（ｉ，ｉ）のカウンタ（ミスヒットテーブル２６１内フィールド）は不要である。このとき、ミスヒットテーブル２６１内の各カウンタ（フィールド）は０に初期化される。なお、Ｍが一定値で、且つメモリの容量に余裕がある場合には、データベース管理システム２０の起動時にミスヒットテーブル２６１が構築されても構わない。
【００４９】
ミスヒットテーブル構築部２６３によってミスヒットテーブル２６１が構築されると、ミスヒットテーブル更新部２６４に制御が移る。すると、ミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１を更新するミスヒットテーブル更新処理（ステップＳ２４）を例えば一定期間実行する。即ち、ミスヒットテーブル更新部２６４は、一定期間の間に、ミスヒットテーブル２６１と対応付けられているページの１つ（ページ番号をＰｉｄｐとする）がバッファミスヒットし、その直後に別のページ（ページ番号をＰｉｄｃとする）がバッファミスヒットする毎に、ミスヒットテーブル２６１内の、（Ｐｉｄｐと対応付けられた行，Ｐｉｄｃと対応付けられた列）で指定される配列要素（フィールド）の値（カウンタ値）を１インクリメントする。
【００５０】
次に、上記ミスヒットテーブル更新処理（ステップＳ２４）の詳細な手順について、図８のフローチャートを参照して説明する。
ミスヒットテーブル更新部２６４は、クエリ処理部２２からバッファ管理部２４に要求されたページデータについて、バッファ管理部２４でバッファヒットまたはバッファミスヒットのいずれが判定されたかを監視する（ステップＳ３１）。もし、バッファミスヒットである場合、ミスヒットテーブル更新部２６４は、バッファミスヒットしたページは、ミスヒットテーブル２６１の配列要素に対応付けられているかを判定する（ステップＳ３２）。このステップＳ３２の判定がＹＥＳの場合、ミスヒットテーブル更新部２６４は、前回のバッファミスヒットの該当ページは、ミスヒットテーブル２６１の配列要素に対応付けられているかを判定する（ステップＳ３３）。
【００５１】
ステップＳ３３の判定がＹＥＳの場合、つまりミスヒットテーブル２６１の配列要素に対応付けられている２つのページがバッファミスヒットした場合、ミスヒットテーブル更新部２６４はステップＳ３４に進む。これに対し、ステップＳ３１乃至Ｓ３３のいずれかの判定がＮＯの場合、つまりミスヒットテーブル２６１の配列要素に対応付けられている２つのページの少なくとも一方はバッファミスヒットしていない場合、ミスヒットテーブル更新部２６４はステップＳ３１に戻る。
【００５２】
ステップＳ３４において、ミスヒットテーブル更新部２６４は、前回バッファミスヒットしたページのページ番号をＰｉｄｐとして設定すると共に、今回バッファミスヒットしたページのページ番号をＰｉｄｃとして設定する。そしてミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１内の、（Ｐｉｄｐ，Ｐｉｄｃ）で指定されるフィールドの値を１インクリメントする（ステップＳ３５）。このように本実施形態では、ページ番号がＰｉｄｐ，Ｐｉｄｃの両ページが、ミスヒット頻度の高い上記Ｍ個のページに含まれていて、且つページ番号がＰｉｄｐのページがバッファミスヒットした直後に、ページ番号がＰｉｄｃのページがバッファミスヒットした場合に、ミスヒットテーブル２６１が更新される。具体的には、ミスヒットテーブル２６１内の、Ｐｉｄｐに対応付けられている行位置と、Ｐｉｄｃに対応付けられている列位置とで指定されるフィールドの値が１インクリメントされる。
【００５３】
ミスヒットテーブル更新部２６４はステップＳ３５を実行すると、ミスヒットテーブル更新処理の開始時から一定期間が経過したかを判定する（ステップＳ３６）。もし、一定期間が経過していないならば、ミスヒットテーブル更新部２６４はステップＳ３１に戻る。これに対し、一定期間が経過しているならば、ミスヒットテーブル更新部２６４はミスヒットテーブル更新処理を終了する。この結果、バッファミスヒットが連続して発生したページの順序と回数が、バッファミスヒットしたページのアクセス順序関係に関する統計情報（２次統計情報）として、ミスヒットテーブル２６１に記録される。これにより、２次統計採取部２６による２次統計情報採取処理（ステップＳ２）が終了する。
【００５４】
なお、メモリに余裕がある場合には、ミスヒットテーブル２６１を、データベース１０の全ページに対応付けるようにしても構わない。この場合、１次統計採取部２５と、ミスヒットテーブル要素抽出部２６２と、ミスヒットテーブル構築部２６３とが不要となる。
【００５５】
さて、２次統計採取部２６の２次統計情報採取処理（ステップＳ２）により、ミスヒットテーブル２６１内に２次統計情報が採取されると、ページ配置最適化部２７に制御が移る。以下、このページ配置最適化部２７によるページ配置最適化処理（ステップＳ３）の詳細な手順について、図９乃至図１１のフローチャートを参照して説明する。
【００５６】
まず、ページ配置最適化部２７のページ再配置候補抽出部２７１は、現在ミスヒットテーブル２６１上で最大の値を持つフィールドを探す（ステップＳ４１）。次にページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の最大の値が閾値より大きいかを判定する（ステップＳ４２）。
【００５７】
図１２は、ミスヒットテーブル２６１の一例を示す。通常、ミスヒットテーブル２６１の行及び列の数、つまりＭの値は例えば１０，０００程度である。しかし、図１２では、作図の都合で、Ｍ＝５の場合が示されている。ここでは、ミスヒットの発生頻度の高い上位Ｍ（＝５）個のページとして、Ｐ１０，Ｐ２０，Ｐ３０，Ｐ４０，Ｐ５０の各ページが抽出されているものとする。なお、以降の説明では、表現の簡略化のために、Ｐ１０，Ｐ２０，Ｐ３０，Ｐ４０，Ｐ５０がページではなくて、ページ番号またはページデータとして扱われることもある。図１２の例では、ミスヒットテーブル２６１上の最大の値は、ページＰ４０に対応する行位置と、ページＰ３０に対応する列位置とで指定されるフィールド、つまり（Ｐ４０，Ｐ３０）で指定されるフィールドの値で“９８”である。ここで、ステップＳ４２で用いられる閾値が“４０”であるものとする。この場合、“９８”は閾値より大きい。
【００５８】
ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の現在の最大の値が閾値より大きい場合（ステップＳ４２）、ミスヒットテーブル２６１上の該当するフィールドの行位置に対応するページ番号をＡに、当該フィールドの列位置に対応するページ番号をＢに、それぞれ設定する（ステップＳ４３）。ここでは、Ａ＝Ｐ４０，Ｂ＝Ｐ３０が設定される。次にページ再配置候補抽出部２７１は、ページ番号がＡ，Ｂの両ページ（つまり、Ｐ４０，Ｐ３０）をページ再配置の候補として抽出する（ステップＳ４４）。この抽出された、ページ番号がＡ，Ｂの両ページ、即ちページＰ４０及びＰ３０は、Ｐ４０→Ｐ３０の順にアクセスされた場合に、最も多くミスヒットしている。したがって、両ページＰ４０及びＰ３０のデータ（ページデータ）をデータベース１０（が置かれる例えば磁気ディスクドライブ）内で連続するように再配置すれば、シーケンシャルアクセスとなって、ミスヒットした場合にも高速アクセスが可能となる。
【００５９】
そこでページ再配置候補抽出部２７１は、抽出した両ページのページ番号Ａ，Ｂの対を、配置フラグと組にして、図１３に示すページ再配置リスト２７３に記録する（ステップＳ４５）。このページ再配置リスト２７３は、計算機システムのメモリ上に確保される。ここで、ページ番号Ａ，Ｂの対と組をなす配置フラグは、ページ番号がＡ，Ｂの両ページのデータが、データベース１０内で連続的に再配置されているか否かを示す。この配置フラグは、ページ再配置リスト２７３に記録される際には、ＯＦＦ状態（０）に初期設定される。
【００６０】
さて、Ｐ４０，Ｐ３０の対を再配置の候補として抽出することは、当該Ｐ４０及びＰ３０のデータが、ページ入れ替え部２７２によってデータベース１０内でＰ４０→Ｐ３０の順に連続的に再配置されることを表す。つまり、Ｐ４０（のページデータ）の直後にＰ３０（のページデータ）以外が配置されることはない。また、Ｐ３０（のページデータ）の直前にＰ４０（のページデータ）以外が配置されることもない。更に、Ｐ３０（のページデータ）の直後にＰ４０（のページデータ）が配置されることもない。
【００６１】
そこでページ再配置候補抽出部２７１は、ページ番号Ａ，Ｂの対と配置フラグ（ＯＦＦ）との組をページ再配置リスト２７３に記録すると（ステップＳ４５）、次のステップＳ４６乃至Ｓ４８を実行する。即ち、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、ページ番号Ａに対応する行（Ａ行）に属する全フィールドを０に初期化する（ステップＳ４６）。また、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、ページ番号Ｂに対応する列（Ｂ列）に属する全フィールドを０に初期化する（ステップＳ４７）。更に、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、Ｂ行Ａ列の位置、つまり（Ｂ，Ａ）の位置のフィールドを０に初期化する（ステップＳ４８）。これにより、ステップＳ４５において、Ｐ４０，Ｐ３０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録された上記の例では、ミスヒットテーブル２６１上の、Ｐ４０の行に属する全フィールドと、Ｐ３０の列に属する全フィールドと、（Ｐ３０，Ｐ４０）の位置のフィールドとが、いずれも０に初期化される。
【００６２】
ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を実行すると、上記ステップＳ４１から始まる処理を再び実行する。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ５０，Ｐ１０）の位置のフィールドの値で“５１”であり、閾値“４０”より大きい。この場合、ステップＳ４１乃至Ｓ４４を経て、Ｐ５０，Ｐ１０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録される（ステップＳ４５）。
【００６３】
その後、ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を経て、ステップＳ４１に戻る。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ３０，Ｐ２０）の位置のフィールドの値で“４１”であり、閾値“４０”より大きい。この場合、ステップＳ４１乃至Ｓ４４を経て、Ｐ３０，Ｐ２０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録される（ステップＳ４５）。その後、ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を経て、ステップＳ４１に戻る。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ４０，Ｐ１０）の位置のフィールドの値で“３８”である。このように、ミスヒットテーブル２６１上の現在の最大の値が閾値以下の場合（ステップＳ４２）、ページ再配置候補抽出部２７１からページ入れ替え部２７２に制御が渡される。図１３のページ再配置リスト２７３は、このときの状態を表している。つまり、ページ再配置リスト２７３には、（Ｐ４０，Ｐ３０），（Ｐ５０，Ｐ１０）及び（Ｐ３０，Ｐ２０）の３つのページ番号対が、連続してミスヒットする頻度の高いページの順序関係を表す情報で、且つ対応するページをその順番の並びとなるように再配置するならばページ配置の最適化の効果が高い情報として記録されている。なお、ミスヒットテーブル２６１上で値が大きい方から一定数のフィールドを抽出し、その一定数のフィールドの各々にそれぞれ対応するページ番号対のページを、ページ再配置の候補として抽出するようにしても良い。
【００６４】
さて、ページ入れ替え部２７２はページ再配置候補抽出部２７１から制御を渡されると、ページ再配置リスト２７３にページ番号対が存在するかを判定する（ステップＳ４９）。もし、ページ再配置リスト２７３にページ番号対が存在しないならば、ページ入れ替え部２７２はページ入れ替えを行わずに、処理を終了する。
【００６５】
これに対し、本実施形態のように、ページ再配置リスト２７３にページ番号対が存在するならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内のページ番号対の位置を示すポインタｋを初期値１に設定する（ステップＳ５０）。次にページ入れ替え部２７２は、ページ再配置リスト２７３上のｋ番目のページ番号対と配置フラグとの組を参照する（ステップＳ５１）。次にページ入れ替え部２７２は、この配置フラグがＯＮ状態にあるかを判定する（ステップＳ５２）。もし、本実施形態とは異なって、配置フラグがＯＮ状態にあるならば、ページ入れ替え部２７２は後述するステップＳ６０に進む。
【００６６】
一方、本実施形態のように、配置フラグがＯＮ状態にないならば、ページ入れ替え部２７２は、ｋ番目のページ番号対の示すページをＰｉ，Ｐｊとして設定する（ステップＳ５３）。そしてページ入れ替え部２７２は、ページＰｉの次のページＰｉｎとページＰｊとを入れ替える（ステップＳ５４）。更に詳細に述べるならば、ページ入れ替え部２７２はステップＳ５４において、ページＰｉの次のページＰｉｎのページデータとページＰｊのページデータとを入れ替える。この入れ替えにより、データベース１０内でのページＰｉ，Ｐｊのページ配置に関し、Ｐｉ→Ｐｊの順に連続する順序関係が実現できる。なお、ページＰｊの前のページＰｊｐとページＰｉとを入れ替えるようにしても、Ｐｉ→Ｐｊの順に連続する順序関係が実現できる。
【００６７】
さて、ｋ＝１の場合、ｋ番目のページ番号対の示すページは、Ｐ４０，Ｐ３０、つまりＰｉ＝Ｐ４０，Ｐｊ＝Ｐ３０である。このとき、データベース１０の状態が図１４（ａ）のようになっているものとすると、Ｐ４０の次のページはＰ４１である。この場合、図１４（ａ）に示すように、Ｐ４１とＰ３０との入れ替え１４１が行われる。これにより、データベース１０は図１４（ｂ）に示す状態に遷移する。この図１４（ｂ）から明らかなように、ｋ＝１番目のページ番号対の示すページＰ４０，Ｐ３０のページ配置に関し、Ｐ４０→Ｐ３０の順に連続する順序関係が実現できる。
【００６８】
ページ入れ替え部２７２は、ステップＳ５４を実行すると、ページ再配置リスト２７３内でｋ（＝１）番目のページ番号対に対応している配置フラグをＯＮする（ステップＳ５５）。次に、ページ入れ替え部２７２は、ページ再配置リスト２７３内にＰｉｎ（＝Ｐ４１）を要素とするページ番号対が存在するかを調べる（ステップＳ５６）。本実施形態のように、Ｐｉｎ（＝Ｐ４１）を要素とするページ番号対が存在しないならば、ページ入れ替え部２７２はステップＳ６０に進む。
【００６９】
これに対し、本実施形態とは異なって、Ｐｉｎを要素とするページ番号対が存在するならば、ページ入れ替え部２７２は、そのページ番号対の示す両ページがデータベース１０内で順序関係を保っているかを判定する（ステップＳ５７）。もし、Ｐｉｎを要素とするページ番号対の示す両ページが順序関係を保っていないならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内の対応する配置フラグを現在の状態に無関係にＯＦＦ状態にする（ステップＳ５８）。このような状態は、（１）Ｐｉｎを要素とするページ番号対の示す両ページの入れ替えが未だ実行されていない場合、または（２）一旦入れ替えが実行されて当該両ページの順序関係が保たれた状態で、ＰｉｎとＰｊとの入れ替えが行われた結果、この順序関係が保たれなくなった場合に生じる。これに対し、ＰｉｎとＰｊとの入れ替えが行われた結果、上記両ページが順序関係を保つようになったならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内の対応する配置フラグをＯＮ状態にする（ステップＳ５９）。ページ入れ替え部２７２は、ステップＳ５８またはステップＳ５９を実行すると、ステップＳ６０に進む。
【００７０】
ステップＳ６０において、ページ入れ替え部２７２は、ページ再配置リスト２７３内の全ての配置フラグがＯＮ状態にあるかを判定する。もし、ＯＦＦ状態の配置フラグが１つでもあるならば、ページ入れ替え部２７２は、ｋ番目のページ番号対がページ再配置リスト２７３の最後のページ番号対であるかを判定する（ステップＳ６１）。もし、最後のページ番号対でないならば、ページ入れ替え部２７２はｋを１インクリメントして（ステップＳ６２）、ステップＳ５１に戻る。これに対し、最後のページ番号対であるならば、ページ入れ替え部２７２はステップＳ５０に戻って、ｋを初期値１に設定する。
【００７１】
本実施形態では、ｋが１から２にインクリメントされ、ｋ＝２番目のページ番号対と配置フラグとの組が参照される（ステップＳ５１）。ｋ＝２番目のページ番号対の示すページは、Ｐ５０，Ｐ１０である。この場合、図１４（ｂ）に示すように、Ｐ５０の次のＰ５１とＰ１０との入れ替え１４２が行われる（ステップＳ５４）。これにより、データベース１０は図１４（ｃｂ）に示す状態に遷移する。この図１４（ｃ）から明らかなように、ｋ＝２番目のページ番号対の示すページＰ５０，Ｐ１０のページ配置に関し、Ｐ５０→Ｐ１０の順に連続する順序関係が実現できる。そこで、ページ再配置リスト２７３内でｋ＝２番目のページ番号対に対応している配置フラグがＯＮされる（ステップＳ５５）。
【００７２】
同様にして、ｋが２から３にインクリメントされ、ｋ＝３番目のページ番号対と配置フラグとの組が参照される（ステップＳ５１）。ｋ＝３番目のページ番号対の示すページは、Ｐ３０，Ｐ２０である。この場合、図１４（ｃ）に示すように、Ｐ３０（つまりＰ４１と入れ替えられたＰ３０）の次のＰ４２とＰ２０との入れ替え１４３が行われる。これにより、データベース１０は図１４（ｄ）に示す状態に遷移する。この図１４（ｄ）から明らかなように、ｋ＝３番目のページ番号対の示すページＰ３０，Ｐ２０のページ配置に関し、Ｐ３０→Ｐ２０の順に連続する順序関係が実現できる。この状態では、既に再配置されたＰ４０→Ｐ３０及びＰ５０→Ｐ１０の順序関係も維持されている。ここで、Ｐ４０及びＰ３０が続けてミスヒットする頻度、Ｐ５０及びＰ１０が続けてミスヒットする頻度、そしてＰ３０及びＰ２０が続けてミスヒットする頻度は閾値より高い。したがって、図１４（ｄ）に示されているように、Ｐ４０→Ｐ３０、Ｐ５０→Ｐ１０及びＰ３０→Ｐ２０の順の並びに再配置されたことで、たとえ続けてミスヒットしたとしても、Ｐ４０→Ｐ３０、Ｐ５０→Ｐ１０及びＰ３０→Ｐ２０のように、それぞれシーケンシャルにアクセスされることから、高速アクセスが可能となる。
【００７３】
次に、上記ステップＳ１乃至Ｓ３の適用例を簡単に説明する。まず、ステップＳ１を、ある１日の業務中に行って、１次統計情報をミスヒットカウンタアレイ２５１に採取する。次に、翌日の業務開始までの間に、例えば翌日の業務開始直前にステップＳ２を開始して、ミスヒットカウンタアレイ２５１に採取された１次統計情報の示すページ毎のミスヒットの頻度を集計し、ミスヒット頻度が高い上位１万個（Ｍ＝１０，０００）のページを抽出する。しかる後に業務を開始し、この１万個のページに対して残りのステップＳ２を継続することで、２次統計情報をミスヒットテーブル２６１に採取する。次に、翌々日の業務開始までの間にステップＳ３を実行する。これにより、ミスヒットテーブル２６１に採取された２次統計情報の示す、１万個のページにおける順序を考慮した全てのページ対の組み合わせ毎の、連続してミスヒットする頻度を集計し、連続してミスヒットする頻度が閾値より高い全てのページ対について、データベース１０内でその順序関係を実現するような再配置が行われる。ここで、閾値には、ミスヒットテーブル２６１中の、値が０でないフィールドの平均値を用いると良い。
【００７４】
［変形例］
次に、上記実施形態の変形例について説明する。
上記実施形態では、Ｐｉｄｐ（の示すページ）がミスヒットした直後にＰｉｄｃ（の示すページ）がミスヒットした場合だけ、ミスヒットテーブル２６１内の（Ｐｉｄｐ，Ｐｉｄｃ）の位置のフィールドの値がインクリメントされる。しかし、Ｐｉｄｐ（の示すページ）がミスヒットした後の、Ｘ回のミスヒットのうちにＰｉｄｃ（の示すページ）のミスヒットが含まれている場合に、ミスヒットテーブル２６１内の（Ｐｉｄｐ，Ｐｉｄｃ）の位置のフィールドの値がインクリメントされる構成としても良い。
【００７５】
そこで、上記実施形態の変形例では、図１５に示すようなＸ段のＦＩＦＯ（First IN First Out）２６５が、２次統計採取部２６内に用意される。このＦＩＦＯ２６５は、最近ミスヒットした最大Ｘ個のページのページ番号をミスヒット順に保持するためのミスヒットページ履歴バッファである。この変形例では、ミスヒットテーブル更新部２６４は、ミスヒットが発生した場合に、ＦＩＦＯ２６５を参照し、当該ＦＩＦＯ２６５に保持されている最大Ｘ個のページ番号と今回ミスヒットとなったページのページ番号との各々のページ対にそれぞれ対応する、ミスヒットテーブル２６１内のフィールドの値をインクリメントする。そして、ミスヒットテーブル更新部２６４は、今回ミスヒットが発生したページのページ番号をＦＩＦＯ２６５に保持する。これにより、その時点で最も以前に保持されたページ番号がＦＩＦＯ２６５から棄てられる。
【００７６】
上記変形例において、ミスヒットテーブル２６１に採取された２次統計情報に基づく、ページ配置最適化部２７によるページ配置最適化処理自体は、上記実施形態と同様に行われる。但し、このミスヒットテーブル２６１に採取された２次統計情報に基づくページの入れ替えにより、時間的に近いタイミングでミスヒットを発生するページ群がデータベース１０内のある領域に集中配置（ニアアロケーション）される。これにより、ディスク装置のシーク時間を減らしてディスクアクセス効率を向上することができる。
【００７７】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【００７８】
【図１】発明の一実施形態に係るデータベース管理システムを備えた計算機システムの構成を示すブロック図。
【図２】同実施形態で適用される、再構築前のミスヒットカウンタアレイ２５１と再構築後のミスヒットカウンタアレイ２５１の一例を示す図。
【図３】図１中のミスヒットテーブル２６１のデータ構造例を示す図。
【図４】同実施形態におけるページ配置の最適化のための処理の概要手順を示すフローチャート。
【図５】図４中の１次統計情報採取処理（ステップＳ１）の詳細な手順を示すフローチャート。
【図６】採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、そのページのバッファミスヒットの頻度順に水平軸方向に並べて、垂直軸方向に頻度を表したグラフの一例を示す図。
【図７】図４中の２次統計情報採取処理（ステップＳ２）の詳細な手順を示すフローチャート。
【図８】図７中のミスヒットテーブル更新処理（ステップＳ２４）の詳細な手順を示すフローチャート。
【図９】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの一部を示す図。
【図１０】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの他の一部を示す図。
【図１１】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの残りを示す図。
【図１２】２次統計情報が採取されたミスヒットテーブル２６１の一例を示す図。
【図１３】ページ再配置リスト２７３の一例を示す図。
【図１４】ページ配置最適化処理におけるデータベース１０の状態の変化を示す図。
【図１５】上記実施形態の変形例で適用されるＦＩＦＯ（ミスヒットページ履歴バッファ）２６５の一例を示す図。
【符号の説明】
【００７９】
１０…データベース（データ格納手段）、２０…データベース管理システム、２１ユーザインタフェース、２２…クエリ処理部、２３…入出力バッファ、２４…バッファ管理部、２５…１次統計採取部、２６…２次統計採取部、２７…ページ配置最適化部、２５１…ミスヒットカウンタアレイ、２５２…ミスヒットカウンタアレイ更新部、２５３…ミスヒットカウンタアレイ再構築部、２６１…ミスヒットテーブル、２６２…ミスヒットテーブル要素抽出部、２６３…ミスヒットテーブル構築部、２６４…ミスヒットテーブル更新部、２６５…ＦＩＦＯ、２７１…ページ再配置候補抽出部、２７２…ページ入れ替え部、２７３…ページ再配置リスト。
【技術分野】
【０００１】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムに係り、特にデータ格納手段に格納されたページデータをアクセスする際のアクセス効率を向上するのに好適な、データベース管理システム、同システムにおけるページ配置最適化方法及びデータベース管理プログラムに関する。
【背景技術】
【０００２】
一般に、データベース管理システム（ＤＢＭＳ：Data Base Management System）では、アプリケーションから与えられたデータと、データを高速に検索するために必要な索引等の情報とを、データ格納手段としてのディスク装置上に格納する。ディスク装置の記憶領域（ディスク領域）はページ（またはブロック）と呼ばれる固定長の領域に分割され、個々のページ（領域）に上記の情報が分割して格納される。
【０００３】
ＤＢＭＳ（データベース管理システム）は、ユーザからの要求に応じてアプリケーションから与えられた問い合わせ（クエリ）を処理する場合、ディスク装置に格納された情報のうちクエリの処理に必要な一連の情報を、当該ディスク装置から（例えばメモリ上に確保された）入出力バッファに読み込む。ＤＢＭＳは、入出力バッファ上でクエリの処理を行う。多くの場合、このディスクアクセスを伴う、入出力バッファへの情報の読み込みに要する時間の、クエリ処理時間に占める割合が大きい。
【０００４】
そこで、ディスク装置から入出力バッファへの情報読み込みの回数を減らす工夫、即ち目的の情報が当該バッファに存在する確率を高める工夫が、従来からなされている（例えば、特許文献１参照）。ここでは、ディスク装置の物理的な領域単位に統計情報が採取される。この統計情報は、対応する領域がアクセスされた際に入出力バッファ（キャッシュメモリ）に当該領域のデータが存在するキャッシュヒットまたは当該領域のデータが存在しないキャッシュミスとなった回数（キャッシュヒット／ミス回数）を含む。ディスク制御装置は、上位装置よりアクセス要求があり、且つアクセス対象データがキャッシュ内に存在しない場合には、上記統計情報をもとに、当該データをキャッシュにロードした場合にヒットの可能性があるかを判定する。そしてディスク制御装置は、ヒットの可能性がある場合に、アクセス対象データをキャッシュにロードする。
【特許文献１】特開平６−１１９２４４号公報（段落００１３，００２９及び００３０）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記した従来技術においては、アクセス頻度の高いページの情報が入出力バッファに存在する確率を高めることができるものの、アクセス頻度の高くないページの情報が入出力バッファに存在する確率を高めることは難しい。即ち、アクセス頻度の高くないページの情報、特にアクセス頻度が中程度のページについては、ディスク装置から入出力バッファへの情報読み込みの回数を減らすことは難しい。したがって、アクセス頻度の高くないページの情報に関しては、ディスクアクセスに要する時間がクエリの応答性能を決めることになる。
【０００６】
一般に、ディスク装置のアクセス性能は、ディスク上に連続に配置されたデータを順次読み出す場合と、ランダムに配置されたデータを読み出す場合とで大きく異なり、前者の方が後者より１桁以上応答性能が良い。このためクエリの処理に必要な一連の情報が、ディスク上の連続した領域、つまり連続したページに配置されるように工夫するならば、ディスクアクセスの効率を上げてクエリの応答性能を高速化することが可能となる。
【０００７】
そこで、情報の種別（ページ種別）によって、それぞれの情報がどのようにアクセスされるかを推定して、それぞれの情報を格納するページを決定することで、ディスクアクセスがシーケンシャルになるようにページの再配置を行うことが考えられる。例えば、データの全検索（フルスキャン）が発生する場合は、フルスキャンの対象となる一連のデータをその単位で連続になるように再配置するならば、ディスクアクセス効率を向上することが期待される。また、Ｂ木の索引を持っていてＢ木を使用した大小比較を行うような場合は、Ｂ木の葉ページを昇順または降順に連続になるように再配置するならば、ディスクアクセス効率を向上することが期待される。
【０００８】
しかし、情報の種別を手掛かりにしてページの再配置を行うだけでは、多種多様なクエリが様々なタイミングで発生する実際のシステムにおいては、必ずしもそれが最適な配置になるとは限らない。つまりクエリ処理のためのページのアクセス順は、アプリケーションが実行するクエリとその実行順序に大きく依存しており、事前にそれを予測するのが難しい。更にクエリによっては、上述のページ再配置では最適にならないケースもある。例えばＢ木を用いた検索を考えると、Ｂ木を用いた一致検索のクエリが多量に行われる場合は、Ｂ木のルートページから葉ページに向かった縦方向のアクセスになり、この縦方向のページ群のうち頻繁にアクセスされるページを連続または近傍に配置することが効果的になる。また、連続的に配置してもその部分はバッファ上に長期間存在していて、ディスクアクセスが殆ど発生しないケースもある。更に、どのページをどのように配置するのが効果的なのか、ページ再配置の優先順位を判別するのが困難である。
【０００９】
本発明は上記事情を考慮してなされたものでその目的は、データ格納手段におけるページ再配置が、当該データ格納手段を利用するシステムがどのようなものであっても、再配置の効果の大きいページについて、そのシステムに最適となるように行える、データベース管理システム、同システムにおけるページ配置最適化方法及びデータベース管理プログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明の１つの観点によれば、記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムが提供される。このデータベース管理システムは、外部からの要求を処理するクエリ処理手段と、上記データ格納手段に格納された一部のページデータを保持する入出力バッファと、このクエリ処理手段によって要求されたページデータが上記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを上記クエリ処理手段に返し、存在しなければバッファミスヒットとして上記要求されたページデータを上記データ格納手段から読み出して上記入出力バッファに配置すると共に当該ページデータを上記クエリ処理手段に返す入出力バッファ管理手段と、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、上記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が上記配列の各行及び各列に対応付けられたミスヒットテーブルと、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合、上記ミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、上記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、上記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが上記データ格納手段内で連続するようにページを再配置するページ配置最適化手段とを備える。
【００１１】
このような構成において、ミスヒットテーブル（論理的に２次元のカウンタの配列）には、ミスヒットテーブル更新手段のインクリメント操作により、バッファミスヒットしたページの順序関係を表す統計情報が採取される。ページ配置最適化手段は、この統計情報をもとに、即ちミスヒットテーブルの各配列要素の値をもとに、その配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータがデータ格納手段内で連続するように、ページを再配置する。
【００１２】
このように、上記の構成においては、連続してバッファミスヒットする頻度の高いページ順序に従ってページが再配置されることにより、バッファミスヒットが発生しても、データ格納手段内では、連続配置されたページデータへのシーケンシャルアクセスとして処理されて、アクセス効率を上げることができ、結果としてクエリの応答性能を向上することができる。しかも、ミスヒットテーブルに採取される統計情報は、データ格納手段の利用状況を動的に反映している。このため、データ格納手段を利用するシステムがどのようなものであっても、再配置の効果の大きいページについて、そのシステムに最適となるページ再配置を実現できる。また、ミスヒットテーブルに採取される統計情報から、ページ配置の最適化の効果に基く再配置の優先順位を判別することも可能である。
【００１３】
上記の構成は、データ格納手段に対するデータの追加削除が繰り返し多数行われるシステムや、障害回復の一方式であるシャドウページ方式を採用するデータベース管理システムなど、データ格納手段内の情報が断片化（フラグメント）しやすいケースで特に有効である。更に、データ格納手段が大規模化して、例えばディスク領域を多量に使用するようなシステムでは、ディスクのシーク時間が増加することで断片化のペナルティが大きくなるが、そのような場合に特に有効である。
【００１４】
また、上記の構成においては、通常のページ再配置による最適化がデータの種別のみを手掛かりにするのに比較して、データの種別だけでは判別できないような、システム固有の隠れたページアクセスの規則性を統計的に見出して手掛かりとするため、仮に既にデータの種別による最適化が行われた後であっても、更にシステム性能を向上するような最適化を行うことができる。よって、上記の構成におけるページ再配置の最適化は、ページ種別に基く最適化よりも効果が大きい。
【００１５】
また、上記の構成に、１次元のカウンタの配列から構成されるミスヒットカウンタアレイであって、上記データ格納手段内の各ページが上記配列のそれぞれの配列要素に対応付けられたミスヒットカウンタアレイと、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットしたページに対応する上記ミスヒットカウンタアレイの配列要素の値をインクリメントするミスヒットカウンタアレイ更新手段と、上記ミスヒットカウンタアレイの配列要素の値に基づいて、バッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページを、上記ミスヒットテーブルの各行及び列の要素として抽出するミスヒットテーブル要素抽出手段と、このミスヒットテーブル要素抽出手段によって抽出された各ページを上記ミスヒットテーブルを構成する配列の各行及び各列に対応付けるミスヒットテーブル構築手段とを追加すると良い。
【００１６】
このような構成においては、データ格納手段内の全ページの各々について、バッファミスヒットの頻度が、ミスヒットカウンタアレイ（１次元のカウンタの配列）に採取され、その採取結果をもとにバッファミスヒットの頻度の高いページが、ミスヒットテーブルの各行及び列の要素として抽出される。これにより、ミスヒットテーブルのサイズが巨大化するのを効果的に防ぐことができる。
【００１７】
また、上記入出力バッファ管理手段によってバッファミスヒットが判定された場合に、当該バッファミスヒットに先行してミスヒットした最大Ｘ個（Ｘは２以上の整数）のページと、今回ミスヒットと判定されたページとの各々のページ対にそれぞれ対応する、上記ミスヒットテーブルの配列要素の値が、上記ミスヒットテーブル更新手段によってインクリメントされる構成としても良い。
【００１８】
このような構成においては、バッファミスヒットの順序にアクセスの明確な順序性を見出すことができるほどの統計的な規則性がなく、連続してバッファミスヒットとなるページ対のみに着目したのでは、ミスヒットテーブルの各配列要素の値が均一になってしまうような場合であっても、時間的に比較的ゆるやかなページアクセス順の因果関係があれば、それらの関係を見い出して、それらのページが互いに近くに配置される。これによりデータ格納手段がディスク装置を用いて実現されるシステムでは、ディスクのシーク時間を減らしてディスクアクセスの効率を向上し、結果としてクエリの応答性能を向上することができる。
【発明の効果】
【００１９】
本発明によれば、バッファミスヒットしたページの順序関係を表す統計情報を採取し、その統計情報をもとに、再配置の効果の大きいページについて、データ格納手段を利用するシステムに最適となるように、ページ再配置を行うことができるため、当該システムがどのようなものであっても、当該システムに適合した最適なページ再配置を実現できる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の一実施形態につき図面を参照して説明する。
図１は本発明の一実施形態に係るデータベース管理システムを備えた計算機システムの構成を示すブロック図である。同図において、データベース１０は、複数のファイルを格納するデータ格納手段であり、磁気ディスクドライブ等のディスク装置に置かれる。データベース１０の領域は、ページ（またはブロック）と呼ばれる固定長の領域に分割されて管理される。このページのサイズは、例えばユーザの操作によってシステム毎に設定可能であり、本実施形態では、２ＫＢ，４ＫＢ，８ＫＢ及び１６ＫＢの中から選択可能である。各ページには、例えばデータベース１０の領域内のオフセット位置が領域の開始位置に近い方から順に、シリアルのページ番号Ｐｉｄ（Ｐｉｄ＝１，２，…，ｎ）が割り当てられている。データベース１０内では、各ファイルのデータと、当該データを高速に検索するために必要な索引等の情報がページ単位に分割されて、個々のページに格納される。
【００２１】
データベース管理システム（ＤＢＭＳ）２０は、データベース１０を管理する。データベース管理システム２０は、ユーザインタフェース２１と、クエリ処理部２２と、入出力バッファ２３と、バッファ管理部２４と、１次統計採取部２５と、２次統計採取部２６と、ページ配置最適化部２７とから構成される。
【００２２】
ユーザインタフェース２１は、ユーザ（アプリケーション）とのインタフェースをなす。ユーザーインタフェース２１は、ユーザの入力操作に応じてアプリケーションから与えられるクエリ（query: 問い合わせ、例えば検索要求）の受け付け、及び当該クエリに対する応答の出力等を行う。クエリ処理部２２は、ユーザーインタフェース２１によって受け付けられたクエリを当該インタフェース２１から受け取ると、処理に必要な情報が格納されたページを順次バッファ管理部２４に要求し、ユーザ（アプリケーション）からのクエリを処理する。
【００２３】
入出力バッファ２３は、データベース１０に格納されている一部のページデータを保持するキャッシュである。入出力バッファ２３は計算機システムのメモリ（図示せぬ）上に配置される。バッファ管理部２４は、入出力バッファ２３を管理する。即ちバッファ管理部２４は、クエリ処理部２２から要求されるページデータが既に入出力バッファ２３上に存在すれば、当該入出力バッファ２３上の要求されたページデータを、要求に対する応答としてクエリ処理部２２に返す。バッファ管理部２４はまた、クエリ処理部２２から要求されるページデータが入出力バッファ２３上に存在しなければ、バッファミスヒットを判定する。この場合、バッファ管理部２４は、従来からよく知られているＬＲＵ（Least Recently Used）制御に基いて入出力バッファ２３上に空きページを確保する。そしてバッファ管理部２４は、要求されたページデータをデータベース１０から読み出して、入出力バッファ２３上に確保された空きページに配置すると共に、その配置されたページデータをクエリ処理部２２に返す。
【００２４】
１次統計採取部２５は、上述のバッファミスヒットしたページの統計情報（１次統計情報）を採取する。１次統計採取部２５は、ミスヒットカウンタアレイ２５１と、ミスヒットカウンタアレイ更新部２５２と、ミスヒットカウンタアレイ再構築部２５３とを含む。
【００２５】
ミスヒットカウンタアレイ２５１は、複数のカウンタ（例えばソフトウェアカウンタ）の１次元の配列から構成される。ミスヒットカウンタアレイ２５１は計算機システムの上記メモリ上に配置される。ミスヒットカウンタアレイ２５１中の各カウンタは、データベース１０内の全ページの各々（または一部の各ページ）と対応付けられており、対応するページのミスヒットの回数をカウントするのに用いられる。
【００２６】
ミスヒットカウンタアレイ更新部２５２は、バッファミスヒットしたページに対応する、ミスヒットカウンタアレイ２５１内のカウンタの値を１インクリメントする。ミスヒットカウンタアレイ再構築部２５３は、バッファミスヒットしたページの１回目の統計情報採取の後に、その採取結果に基づいて、バッファミスヒットの発生頻度の比較的高いページ（例えば、上位の一定数のページ）を、２回目の統計情報採取の候補として抽出する。ミスヒットカウンタアレイ再構築部２５３は、抽出された各ページのミスヒットの回数をカウント可能とするために、ミスヒットカウンタアレイ２５１を再構築する。
【００２７】
図２は再構築前のミスヒットカウンタアレイ２５１と再構築後のミスヒットカウンタアレイ２５１の一例を示す。本実施形態において、再構築前のミスヒットカウンタアレイ２５１は、データベース１０のページ数をｎとすると、図２（ａ）に示すように、全ページ分（ここでは、ｎページ分）のカウンタの１次元配列から構成される。このｎページ用のミスヒットカウンタアレイ２５１内の各カウンタは、それぞれデータベース１０内の各ページのページ番号Ｐｉｄと対応付けられている。図２（ａ）に示すミスヒットカウンタアレイ２５１内の各カウンタの長さをＬ１とする。一方、再構築後のミスヒットカウンタアレイ２５１は、データベース１０の全ページの中から２回目の統計情報採取の候補として抽出されたページの数をｍ（ｍ＜ｎ）とすると、図２（ｂ）に示すように、ｍページ分のカウンタの１次元配列から構成される。この図２（ｂ）に示す、ｍページ用のミスヒットカウンタアレイ２５１内の各カウンタの長さをＬ２（Ｌ２＞Ｌ１）とする。
【００２８】
２次統計採取部２６は、バッファミスヒットしたページのアクセス順序関係に関する統計情報（２次統計情報）を採取する。２次統計採取部２６は、ミスヒットテーブル２６１と、ミスヒットテーブル要素抽出部２６２と、ミスヒットテーブル構築部２６３と、ミスヒットテーブル更新部２６４とを含む。
【００２９】
ミスヒットテーブル２６１は、複数のカウンタ（例えばソフトウェアカウンタ）を計算機システムのメモリ上に論理的にＭ行×Ｍ列の２次元に配列することで構成される。ミスヒットテーブル２６１の各行ｉ及び列ｉ（ｉ＝１，２，…，Ｍ）の対には、ミスヒットテーブル要素抽出部２６２によって抽出されたＭ個のページの各々が、そのページ番号Ｐｉｄに対応付けて割り当てられる。図３は、このミスヒットテーブル２６１のデータ構造例を示す。図３では、作図の都合上、Ｍ＝７のミスヒットテーブル２６１が示されているが、実際にはＭは例えば１０，０００など、十分大きい値である。
【００３０】
ミスヒットテーブル要素抽出部２６２は、ミスヒットカウンタアレイ２５１の各カウンタによって示される、ページ毎のバッファミスヒットの回数（つまり頻度）をもとに、上位Ｍページ（ミスヒットの発生頻度の高い上位Ｍページ）を、ミスヒットテーブル２６１の各行及び列の要素として抽出する。
【００３１】
ミスヒットテーブル構築部２６３は、ミスヒットテーブル要素抽出部２６２によって抽出されたＭページのページ番号Ｐｉｄをもとに、ミスヒットテーブル２６１を構築する。ミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１と対応付けられているページの１つがバッファミスヒットし、その直後に別のページがバッファミスヒットした場合に、その連続してミスヒットした２つのページに対応するミスヒットテーブル２６１内の配列要素（フィールド）の値（カウンタ値）を１インクリメントする。
【００３２】
ページ配置最適化部２７は、バッファミスヒットが連続して発生する頻度の高い各ページ対がそれぞれデータベース１０上で連続するように再配置する。ページ配置最適化部２７は、ページ再配置候補抽出部２７１と、ページ入れ替え部２７２とを含む。
【００３３】
ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１の各フィールドの値をもとに、バッファミスヒットが連続して発生する頻度の高いページ対を頻度順に抽出する。ページ入れ替え部２７２は、ページ再配置候補抽出部２７１によって抽出された各ページ対がそれぞれデータベース１０上で連続するように、ページの内容の入れ替えを行う。
【００３４】
データベース管理システム２０内の入出力バッファ２３、ミスヒットカウンタアレイ２５１及びミスヒットテーブル２６１を除く各要素は、計算機システムにインストールされたデータベース管理のためのソフトウェアプログラム（データベース管理プログラム）を当該計算機システム（内のＣＰＵ）が読み取って実行することにより実現される。このプログラムは、コンピュータで読み取り可能な記憶媒体（フロッピー（登録商標）ディスクに代表される磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤに代表される光ディスク、フラッシュメモリに代表される半導体メモリ等）に予め格納して頒布可能である。また、このプログラムが、ネットワークを介してダウンロード（頒布）されても構わない。
【００３５】
次に、図１の計算機システム内のデータベース管理システム２０の動作について、データベース１０内のページの配置の最適化のための処理を例に説明する。
まず、このページの配置の最適化のための処理の概略手順について、図４のフローチャートを参照して説明する。まず、１次統計採取部２５は、１次統計情報採取処理（ステップＳ１）を実行する。この１次統計情報採取処理により、バッファミスヒットしたページの統計情報（１次統計情報）が採取される。その後、２次統計採取部２６に制御が移る。２次統計採取部２６は、２次統計情報採取処理（ステップＳ２）を実行する。この２次統計情報採取処理では、１次統計採取部２５によって採取された１次統計情報をもとに、バッファミスヒットの頻度の高い上位Ｍページが抽出される。そして抽出されたＭページの全てのページ対Ｐｉ，Ｐｊ（ｉ＝１，２，…，Ｍ，ｊ＝１，２，…，Ｍ）の組み合わせ毎に、ページＰｉがバッファミスヒットした直後にページＰｊがバッファミスヒットする回数を表す統計情報（２次統計情報）が採取される。その後、ページ配置最適化部２７に制御が移る。ページ配置最適化部２７は、２次統計採取部２６による２次統計情報採取結果をもとに、ページ配置最適化処理（ステップＳ３）を実行する。このページ配置最適化処理では、続けてバッファミスヒットを発生する頻度の高いページ対が、ページ再配置の候補として抽出され、その抽出された各ページ対がそれぞれデータベース１０上で連続するように、ページの内容が入れ替えられる。
【００３６】
次に、１次統計情報採取処理（ステップＳ１）の詳細な手順について、図５のフローチャートを参照して説明する。なお、１次統計情報採取処理の前には、ミスヒットカウンタアレイ２５１の各カウンタの値が０に初期化される。この初期化のタイミングは、例えばデータベース管理システム２０の起動時など、１次統計情報採取処理が開始されるまでの任意の時点で良い。また、初期化のタイミングが、外部からユーザインタフェース２１を介して与えられる構成であっても良い。
【００３７】
まず、１次統計採取部２５は、ミスヒットカウンタアレイ２５１を用いて、データベース１０内の全ページ（ここでは、ページ番号１（Ｐｉｄ＝１）乃至ｎ（Ｐｉｄ＝ｎ）のｎページ）を対象に、バッファミスヒットを発生したページの統計情報を採取する（ステップＳ１１）。このステップＳ１１において、１次統計採取部２５のミスヒットカウンタアレイ更新部２５２は、バッファ管理部２４でバッファミスヒットが判定される都度、ミスヒットしたページのページ番号Ｐｉｄに対応付けられた、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５１のカウンタを１インクリメントする。但し、インクリメント対象のカウンタの値が、カウント可能な最大値となっている場合には、当該カウンタの値は最大値に保持される。
【００３８】
ステップＳ１１が開始されてから、例えば一定期間が経過すると、ミスヒットカウンタアレイ再構築部２５３に制御が移る。ミスヒットカウンタアレイ再構築部２５３は、ミスヒットページ（のページ番号）を、対応するミスヒットカウンタアレイ２５１のカウンタの値の大きい順、つまりミスヒットの頻度の高い順（降順）にソートする（ステップＳ１２）。なお、ステップＳ１１が開始されてから発生したバッファミスヒットの総数が一定値を超えた場合に、ステップＳ１２が実行される構成としても良い。この他に、ミスヒットカウンタアレイ２５１内の任意のカウンタのカウント値がカウント可能な最大値となった場合に、ステップＳ１２が実行される構成としても良い。
【００３９】
次にミスヒットカウンタアレイ再構築部２５３は、ソート後のミスヒットページから、上位のｍ（ｍ＜ｎ）ページ（のページ番号）を、ミスヒットカウンタアレイ再構築後の統計情報の採取候補として抽出する（ステップＳ１３）。抽出されたｍページのページ番号はメモリ上に記録される。次に、ミスヒットカウンタアレイ再構築部２５３は、ミスヒットカウンタアレイ２５１を図２（ｂ）に示すｍページ用に再構築する（ステップＳ１４）。このとき、ミスヒットカウンタアレイ２５１内の各カウンタ（フィールド）は０に初期化される。すると、再びミスヒットカウンタアレイ更新部２５２に制御が移る。
【００４０】
ミスヒットカウンタアレイ更新部２５２は、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１を用いて、ミスヒットカウンタアレイ再構築部２５３によって決定されたｍページだけを対象に、バッファミスヒットを発生したページの統計情報を採取する（ステップＳ１５）。このステップＳ１５において、ミスヒットカウンタアレイ更新部２５２は、上記抽出されたｍページのうちのいずれかがバッファミスヒットした場合だけ、そのミスヒットしたページのページ番号Ｐｉｄに対応付けられた、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１のカウンタを１インクリメントする。ステップＳ１５は、例えば一定期間実行される。このステップＳ１５の実行が終了した時点の、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１の各カウンタの値が、目的の１次統計情報を表す。ここで、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１の各カウンタの長さＬ２は、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５１の各カウンタの長さＬ１より大きい。したがって、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５１には、ミスヒットの頻度が比較的高い上位ｍページの精度の高い統計情報が、１次統計情報として採取されることになる。
【００４１】
ここで、１次統計採取部２５において、２ステップで統計情報を採取する理由について説明する。まず、データベース１０内の全ページ（ｎページ）についてバッファミスヒットの精度の高い統計情報を１ステップで採取するには、長さがＬ２（例えば４バイト）のｎ個のカウンタの配列をメモリ上に配置する必要があるものとする。本実施形態では、データベース１０のサイズ（つまりデータベース１０のページ数ｎ）が極めて大きく、カウンタ長をＬ２（４バイト）とすると、ｎ個のカウンタの配列をメモリ上に確保できないものとする。そこで本実施形態では、Ｌ２より短い、長さがＬ１（例えばＬ２の１／８の長さである４ビット）のｎ個のカウンタの配列を、図２（ａ）に示すｎページ用のミスヒットカウンタアレイ２５としてメモリ上に用意することで、第１のステップで、データベース１０内の全ページ（ｎページ）についてバッファミスヒットの大まかな統計情報を比較的短時間で採取する（ステップＳ１１）。そして、この大まかな統計情報をもとにミスヒットの頻度の高い上位ｍページを抽出すると共に、長さＬ２（４バイト）のｍ個のカウンタの配列を、図２（ｂ）に示すｍページ用のミスヒットカウンタアレイ２５としてメモリ上に用意することで、第２のステップで、当該上位ｍページについてバッファミスヒットの精度の高い統計情報（１次統計情報）を、第１のステップに比べて十分時間をかけて採取する。
【００４２】
なお、データベース１０を複数の区画に分けて、各区画毎に順番に１次統計情報を採取することも可能である。この場合、長さＬ２のカウンタを１区画のページ数分だけ用意すれば良い。勿論、長さＬ２のｎ個のカウンタの配列をメモリ上に用意できるならば、データベース１０内の全ページ（ｎページ）について、１ステップで１次統計情報を採取できる。
【００４３】
さて、１次統計情報採取処理（ステップＳ１）で採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、そのページのバッファミスヒットの頻度順（頻度の降順）に水平軸方向に並べ、垂直軸方向に頻度を表すと、図６のようなグラフが得られる。このグラフ上で、バッファミスヒットの頻度が高い上位Ｍ個のページは、中程度のアクセス頻度を持ち、次の理由により再配置の最適化の効果が大きいページである。
【００４４】
（１）アクセス頻度の高いページはミスヒットしにくいため最適化の効果は小さい。
（２）アクセス頻度の低いページは、アクセスが発生した場合にはミスヒットする確率が高いものの、アクセス自体が希にしか発生しないためにミスヒットの頻度が低く、最適化の効果は小さい。
（３）アクセス頻度が中程度のページはミスヒットの頻度が高く、したがって最適化の効果が大きい。
【００４５】
そこで、最適化の効果が大きいミスヒットの頻度の高いページを、どの順に配置すれば最適化できるかを決定するのに必要な、２次統計情報採取処理（ステップＳ２）の詳細な手順について、図７のフローチャートを参照して説明する。
【００４６】
まず、１次統計採取部２５の１次統計情報採取処理（ステップＳ１）により、ｍビット用のミスヒットカウンタアレイ２５１内に１次統計情報が採取されると、２次統計採取部２６内のミスヒットテーブル要素抽出部２６２に制御が移る。ミスヒットテーブル要素抽出部２６２は、ｍビット用のミスヒットカウンタアレイ２５１内に採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、カウンタの値の大きい順、即ちバッファミスヒットの頻度順（頻度の降順）にソートする（ステップＳ２１）。
【００４７】
次にミスヒットテーブル要素抽出部２６２は、ステップＳ２１でのソート結果をもとに、バッファミスヒットの頻度の高い上位Ｍ個（Ｍ＜ｍ）のページを、ミスヒットページのアクセス順序関係の統計情報（つまり２次統計情報）の採取候補として抽出する（ステップＳ２２）。なお、Ｍを一定値とせずに、一定のミスヒット発生頻度を超えるページ（ページ数をＭとする）を、２次統計情報の採取候補として抽出するようにしても良い。
【００４８】
ミスヒットテーブル構築部２６３は、ミスヒットテーブル要素抽出部２６２によって抽出されたＭ個のページのページ番号Ｐｉｄをもとに、ミスヒットテーブル２６１を構築する（ステップＳ２３）。即ちミスヒットテーブル構築部２６３は、抽出されたＭ個のページのページ番号Ｐｉｄに対応付けられた行要素及び列要素を持つ、論理的にＭ行×Ｍ列の２次元のカウンタ配列から構成されるミスヒットテーブル２６１をメモリ上に構築する。但し、行ｉ及び列ｉ（ｉ＝１，２，…，Ｍ）で指定される配列要素位置（ｉ，ｉ）のカウンタ（ミスヒットテーブル２６１内フィールド）は不要である。このとき、ミスヒットテーブル２６１内の各カウンタ（フィールド）は０に初期化される。なお、Ｍが一定値で、且つメモリの容量に余裕がある場合には、データベース管理システム２０の起動時にミスヒットテーブル２６１が構築されても構わない。
【００４９】
ミスヒットテーブル構築部２６３によってミスヒットテーブル２６１が構築されると、ミスヒットテーブル更新部２６４に制御が移る。すると、ミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１を更新するミスヒットテーブル更新処理（ステップＳ２４）を例えば一定期間実行する。即ち、ミスヒットテーブル更新部２６４は、一定期間の間に、ミスヒットテーブル２６１と対応付けられているページの１つ（ページ番号をＰｉｄｐとする）がバッファミスヒットし、その直後に別のページ（ページ番号をＰｉｄｃとする）がバッファミスヒットする毎に、ミスヒットテーブル２６１内の、（Ｐｉｄｐと対応付けられた行，Ｐｉｄｃと対応付けられた列）で指定される配列要素（フィールド）の値（カウンタ値）を１インクリメントする。
【００５０】
次に、上記ミスヒットテーブル更新処理（ステップＳ２４）の詳細な手順について、図８のフローチャートを参照して説明する。
ミスヒットテーブル更新部２６４は、クエリ処理部２２からバッファ管理部２４に要求されたページデータについて、バッファ管理部２４でバッファヒットまたはバッファミスヒットのいずれが判定されたかを監視する（ステップＳ３１）。もし、バッファミスヒットである場合、ミスヒットテーブル更新部２６４は、バッファミスヒットしたページは、ミスヒットテーブル２６１の配列要素に対応付けられているかを判定する（ステップＳ３２）。このステップＳ３２の判定がＹＥＳの場合、ミスヒットテーブル更新部２６４は、前回のバッファミスヒットの該当ページは、ミスヒットテーブル２６１の配列要素に対応付けられているかを判定する（ステップＳ３３）。
【００５１】
ステップＳ３３の判定がＹＥＳの場合、つまりミスヒットテーブル２６１の配列要素に対応付けられている２つのページがバッファミスヒットした場合、ミスヒットテーブル更新部２６４はステップＳ３４に進む。これに対し、ステップＳ３１乃至Ｓ３３のいずれかの判定がＮＯの場合、つまりミスヒットテーブル２６１の配列要素に対応付けられている２つのページの少なくとも一方はバッファミスヒットしていない場合、ミスヒットテーブル更新部２６４はステップＳ３１に戻る。
【００５２】
ステップＳ３４において、ミスヒットテーブル更新部２６４は、前回バッファミスヒットしたページのページ番号をＰｉｄｐとして設定すると共に、今回バッファミスヒットしたページのページ番号をＰｉｄｃとして設定する。そしてミスヒットテーブル更新部２６４は、ミスヒットテーブル２６１内の、（Ｐｉｄｐ，Ｐｉｄｃ）で指定されるフィールドの値を１インクリメントする（ステップＳ３５）。このように本実施形態では、ページ番号がＰｉｄｐ，Ｐｉｄｃの両ページが、ミスヒット頻度の高い上記Ｍ個のページに含まれていて、且つページ番号がＰｉｄｐのページがバッファミスヒットした直後に、ページ番号がＰｉｄｃのページがバッファミスヒットした場合に、ミスヒットテーブル２６１が更新される。具体的には、ミスヒットテーブル２６１内の、Ｐｉｄｐに対応付けられている行位置と、Ｐｉｄｃに対応付けられている列位置とで指定されるフィールドの値が１インクリメントされる。
【００５３】
ミスヒットテーブル更新部２６４はステップＳ３５を実行すると、ミスヒットテーブル更新処理の開始時から一定期間が経過したかを判定する（ステップＳ３６）。もし、一定期間が経過していないならば、ミスヒットテーブル更新部２６４はステップＳ３１に戻る。これに対し、一定期間が経過しているならば、ミスヒットテーブル更新部２６４はミスヒットテーブル更新処理を終了する。この結果、バッファミスヒットが連続して発生したページの順序と回数が、バッファミスヒットしたページのアクセス順序関係に関する統計情報（２次統計情報）として、ミスヒットテーブル２６１に記録される。これにより、２次統計採取部２６による２次統計情報採取処理（ステップＳ２）が終了する。
【００５４】
なお、メモリに余裕がある場合には、ミスヒットテーブル２６１を、データベース１０の全ページに対応付けるようにしても構わない。この場合、１次統計採取部２５と、ミスヒットテーブル要素抽出部２６２と、ミスヒットテーブル構築部２６３とが不要となる。
【００５５】
さて、２次統計採取部２６の２次統計情報採取処理（ステップＳ２）により、ミスヒットテーブル２６１内に２次統計情報が採取されると、ページ配置最適化部２７に制御が移る。以下、このページ配置最適化部２７によるページ配置最適化処理（ステップＳ３）の詳細な手順について、図９乃至図１１のフローチャートを参照して説明する。
【００５６】
まず、ページ配置最適化部２７のページ再配置候補抽出部２７１は、現在ミスヒットテーブル２６１上で最大の値を持つフィールドを探す（ステップＳ４１）。次にページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の最大の値が閾値より大きいかを判定する（ステップＳ４２）。
【００５７】
図１２は、ミスヒットテーブル２６１の一例を示す。通常、ミスヒットテーブル２６１の行及び列の数、つまりＭの値は例えば１０，０００程度である。しかし、図１２では、作図の都合で、Ｍ＝５の場合が示されている。ここでは、ミスヒットの発生頻度の高い上位Ｍ（＝５）個のページとして、Ｐ１０，Ｐ２０，Ｐ３０，Ｐ４０，Ｐ５０の各ページが抽出されているものとする。なお、以降の説明では、表現の簡略化のために、Ｐ１０，Ｐ２０，Ｐ３０，Ｐ４０，Ｐ５０がページではなくて、ページ番号またはページデータとして扱われることもある。図１２の例では、ミスヒットテーブル２６１上の最大の値は、ページＰ４０に対応する行位置と、ページＰ３０に対応する列位置とで指定されるフィールド、つまり（Ｐ４０，Ｐ３０）で指定されるフィールドの値で“９８”である。ここで、ステップＳ４２で用いられる閾値が“４０”であるものとする。この場合、“９８”は閾値より大きい。
【００５８】
ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の現在の最大の値が閾値より大きい場合（ステップＳ４２）、ミスヒットテーブル２６１上の該当するフィールドの行位置に対応するページ番号をＡに、当該フィールドの列位置に対応するページ番号をＢに、それぞれ設定する（ステップＳ４３）。ここでは、Ａ＝Ｐ４０，Ｂ＝Ｐ３０が設定される。次にページ再配置候補抽出部２７１は、ページ番号がＡ，Ｂの両ページ（つまり、Ｐ４０，Ｐ３０）をページ再配置の候補として抽出する（ステップＳ４４）。この抽出された、ページ番号がＡ，Ｂの両ページ、即ちページＰ４０及びＰ３０は、Ｐ４０→Ｐ３０の順にアクセスされた場合に、最も多くミスヒットしている。したがって、両ページＰ４０及びＰ３０のデータ（ページデータ）をデータベース１０（が置かれる例えば磁気ディスクドライブ）内で連続するように再配置すれば、シーケンシャルアクセスとなって、ミスヒットした場合にも高速アクセスが可能となる。
【００５９】
そこでページ再配置候補抽出部２７１は、抽出した両ページのページ番号Ａ，Ｂの対を、配置フラグと組にして、図１３に示すページ再配置リスト２７３に記録する（ステップＳ４５）。このページ再配置リスト２７３は、計算機システムのメモリ上に確保される。ここで、ページ番号Ａ，Ｂの対と組をなす配置フラグは、ページ番号がＡ，Ｂの両ページのデータが、データベース１０内で連続的に再配置されているか否かを示す。この配置フラグは、ページ再配置リスト２７３に記録される際には、ＯＦＦ状態（０）に初期設定される。
【００６０】
さて、Ｐ４０，Ｐ３０の対を再配置の候補として抽出することは、当該Ｐ４０及びＰ３０のデータが、ページ入れ替え部２７２によってデータベース１０内でＰ４０→Ｐ３０の順に連続的に再配置されることを表す。つまり、Ｐ４０（のページデータ）の直後にＰ３０（のページデータ）以外が配置されることはない。また、Ｐ３０（のページデータ）の直前にＰ４０（のページデータ）以外が配置されることもない。更に、Ｐ３０（のページデータ）の直後にＰ４０（のページデータ）が配置されることもない。
【００６１】
そこでページ再配置候補抽出部２７１は、ページ番号Ａ，Ｂの対と配置フラグ（ＯＦＦ）との組をページ再配置リスト２７３に記録すると（ステップＳ４５）、次のステップＳ４６乃至Ｓ４８を実行する。即ち、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、ページ番号Ａに対応する行（Ａ行）に属する全フィールドを０に初期化する（ステップＳ４６）。また、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、ページ番号Ｂに対応する列（Ｂ列）に属する全フィールドを０に初期化する（ステップＳ４７）。更に、ページ再配置候補抽出部２７１は、ミスヒットテーブル２６１上の、Ｂ行Ａ列の位置、つまり（Ｂ，Ａ）の位置のフィールドを０に初期化する（ステップＳ４８）。これにより、ステップＳ４５において、Ｐ４０，Ｐ３０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録された上記の例では、ミスヒットテーブル２６１上の、Ｐ４０の行に属する全フィールドと、Ｐ３０の列に属する全フィールドと、（Ｐ３０，Ｐ４０）の位置のフィールドとが、いずれも０に初期化される。
【００６２】
ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を実行すると、上記ステップＳ４１から始まる処理を再び実行する。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ５０，Ｐ１０）の位置のフィールドの値で“５１”であり、閾値“４０”より大きい。この場合、ステップＳ４１乃至Ｓ４４を経て、Ｐ５０，Ｐ１０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録される（ステップＳ４５）。
【００６３】
その後、ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を経て、ステップＳ４１に戻る。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ３０，Ｐ２０）の位置のフィールドの値で“４１”であり、閾値“４０”より大きい。この場合、ステップＳ４１乃至Ｓ４４を経て、Ｐ３０，Ｐ２０のページ番号がページ番号Ａ，Ｂの対としてページ再配置リスト２７３に記録される（ステップＳ４５）。その後、ページ再配置候補抽出部２７１は、ステップＳ４６乃至Ｓ４８を経て、ステップＳ４１に戻る。この時点において、ミスヒットテーブル２６１上で最大の値は、（Ｐ４０，Ｐ１０）の位置のフィールドの値で“３８”である。このように、ミスヒットテーブル２６１上の現在の最大の値が閾値以下の場合（ステップＳ４２）、ページ再配置候補抽出部２７１からページ入れ替え部２７２に制御が渡される。図１３のページ再配置リスト２７３は、このときの状態を表している。つまり、ページ再配置リスト２７３には、（Ｐ４０，Ｐ３０），（Ｐ５０，Ｐ１０）及び（Ｐ３０，Ｐ２０）の３つのページ番号対が、連続してミスヒットする頻度の高いページの順序関係を表す情報で、且つ対応するページをその順番の並びとなるように再配置するならばページ配置の最適化の効果が高い情報として記録されている。なお、ミスヒットテーブル２６１上で値が大きい方から一定数のフィールドを抽出し、その一定数のフィールドの各々にそれぞれ対応するページ番号対のページを、ページ再配置の候補として抽出するようにしても良い。
【００６４】
さて、ページ入れ替え部２７２はページ再配置候補抽出部２７１から制御を渡されると、ページ再配置リスト２７３にページ番号対が存在するかを判定する（ステップＳ４９）。もし、ページ再配置リスト２７３にページ番号対が存在しないならば、ページ入れ替え部２７２はページ入れ替えを行わずに、処理を終了する。
【００６５】
これに対し、本実施形態のように、ページ再配置リスト２７３にページ番号対が存在するならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内のページ番号対の位置を示すポインタｋを初期値１に設定する（ステップＳ５０）。次にページ入れ替え部２７２は、ページ再配置リスト２７３上のｋ番目のページ番号対と配置フラグとの組を参照する（ステップＳ５１）。次にページ入れ替え部２７２は、この配置フラグがＯＮ状態にあるかを判定する（ステップＳ５２）。もし、本実施形態とは異なって、配置フラグがＯＮ状態にあるならば、ページ入れ替え部２７２は後述するステップＳ６０に進む。
【００６６】
一方、本実施形態のように、配置フラグがＯＮ状態にないならば、ページ入れ替え部２７２は、ｋ番目のページ番号対の示すページをＰｉ，Ｐｊとして設定する（ステップＳ５３）。そしてページ入れ替え部２７２は、ページＰｉの次のページＰｉｎとページＰｊとを入れ替える（ステップＳ５４）。更に詳細に述べるならば、ページ入れ替え部２７２はステップＳ５４において、ページＰｉの次のページＰｉｎのページデータとページＰｊのページデータとを入れ替える。この入れ替えにより、データベース１０内でのページＰｉ，Ｐｊのページ配置に関し、Ｐｉ→Ｐｊの順に連続する順序関係が実現できる。なお、ページＰｊの前のページＰｊｐとページＰｉとを入れ替えるようにしても、Ｐｉ→Ｐｊの順に連続する順序関係が実現できる。
【００６７】
さて、ｋ＝１の場合、ｋ番目のページ番号対の示すページは、Ｐ４０，Ｐ３０、つまりＰｉ＝Ｐ４０，Ｐｊ＝Ｐ３０である。このとき、データベース１０の状態が図１４（ａ）のようになっているものとすると、Ｐ４０の次のページはＰ４１である。この場合、図１４（ａ）に示すように、Ｐ４１とＰ３０との入れ替え１４１が行われる。これにより、データベース１０は図１４（ｂ）に示す状態に遷移する。この図１４（ｂ）から明らかなように、ｋ＝１番目のページ番号対の示すページＰ４０，Ｐ３０のページ配置に関し、Ｐ４０→Ｐ３０の順に連続する順序関係が実現できる。
【００６８】
ページ入れ替え部２７２は、ステップＳ５４を実行すると、ページ再配置リスト２７３内でｋ（＝１）番目のページ番号対に対応している配置フラグをＯＮする（ステップＳ５５）。次に、ページ入れ替え部２７２は、ページ再配置リスト２７３内にＰｉｎ（＝Ｐ４１）を要素とするページ番号対が存在するかを調べる（ステップＳ５６）。本実施形態のように、Ｐｉｎ（＝Ｐ４１）を要素とするページ番号対が存在しないならば、ページ入れ替え部２７２はステップＳ６０に進む。
【００６９】
これに対し、本実施形態とは異なって、Ｐｉｎを要素とするページ番号対が存在するならば、ページ入れ替え部２７２は、そのページ番号対の示す両ページがデータベース１０内で順序関係を保っているかを判定する（ステップＳ５７）。もし、Ｐｉｎを要素とするページ番号対の示す両ページが順序関係を保っていないならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内の対応する配置フラグを現在の状態に無関係にＯＦＦ状態にする（ステップＳ５８）。このような状態は、（１）Ｐｉｎを要素とするページ番号対の示す両ページの入れ替えが未だ実行されていない場合、または（２）一旦入れ替えが実行されて当該両ページの順序関係が保たれた状態で、ＰｉｎとＰｊとの入れ替えが行われた結果、この順序関係が保たれなくなった場合に生じる。これに対し、ＰｉｎとＰｊとの入れ替えが行われた結果、上記両ページが順序関係を保つようになったならば、ページ入れ替え部２７２は、ページ再配置リスト２７３内の対応する配置フラグをＯＮ状態にする（ステップＳ５９）。ページ入れ替え部２７２は、ステップＳ５８またはステップＳ５９を実行すると、ステップＳ６０に進む。
【００７０】
ステップＳ６０において、ページ入れ替え部２７２は、ページ再配置リスト２７３内の全ての配置フラグがＯＮ状態にあるかを判定する。もし、ＯＦＦ状態の配置フラグが１つでもあるならば、ページ入れ替え部２７２は、ｋ番目のページ番号対がページ再配置リスト２７３の最後のページ番号対であるかを判定する（ステップＳ６１）。もし、最後のページ番号対でないならば、ページ入れ替え部２７２はｋを１インクリメントして（ステップＳ６２）、ステップＳ５１に戻る。これに対し、最後のページ番号対であるならば、ページ入れ替え部２７２はステップＳ５０に戻って、ｋを初期値１に設定する。
【００７１】
本実施形態では、ｋが１から２にインクリメントされ、ｋ＝２番目のページ番号対と配置フラグとの組が参照される（ステップＳ５１）。ｋ＝２番目のページ番号対の示すページは、Ｐ５０，Ｐ１０である。この場合、図１４（ｂ）に示すように、Ｐ５０の次のＰ５１とＰ１０との入れ替え１４２が行われる（ステップＳ５４）。これにより、データベース１０は図１４（ｃｂ）に示す状態に遷移する。この図１４（ｃ）から明らかなように、ｋ＝２番目のページ番号対の示すページＰ５０，Ｐ１０のページ配置に関し、Ｐ５０→Ｐ１０の順に連続する順序関係が実現できる。そこで、ページ再配置リスト２７３内でｋ＝２番目のページ番号対に対応している配置フラグがＯＮされる（ステップＳ５５）。
【００７２】
同様にして、ｋが２から３にインクリメントされ、ｋ＝３番目のページ番号対と配置フラグとの組が参照される（ステップＳ５１）。ｋ＝３番目のページ番号対の示すページは、Ｐ３０，Ｐ２０である。この場合、図１４（ｃ）に示すように、Ｐ３０（つまりＰ４１と入れ替えられたＰ３０）の次のＰ４２とＰ２０との入れ替え１４３が行われる。これにより、データベース１０は図１４（ｄ）に示す状態に遷移する。この図１４（ｄ）から明らかなように、ｋ＝３番目のページ番号対の示すページＰ３０，Ｐ２０のページ配置に関し、Ｐ３０→Ｐ２０の順に連続する順序関係が実現できる。この状態では、既に再配置されたＰ４０→Ｐ３０及びＰ５０→Ｐ１０の順序関係も維持されている。ここで、Ｐ４０及びＰ３０が続けてミスヒットする頻度、Ｐ５０及びＰ１０が続けてミスヒットする頻度、そしてＰ３０及びＰ２０が続けてミスヒットする頻度は閾値より高い。したがって、図１４（ｄ）に示されているように、Ｐ４０→Ｐ３０、Ｐ５０→Ｐ１０及びＰ３０→Ｐ２０の順の並びに再配置されたことで、たとえ続けてミスヒットしたとしても、Ｐ４０→Ｐ３０、Ｐ５０→Ｐ１０及びＰ３０→Ｐ２０のように、それぞれシーケンシャルにアクセスされることから、高速アクセスが可能となる。
【００７３】
次に、上記ステップＳ１乃至Ｓ３の適用例を簡単に説明する。まず、ステップＳ１を、ある１日の業務中に行って、１次統計情報をミスヒットカウンタアレイ２５１に採取する。次に、翌日の業務開始までの間に、例えば翌日の業務開始直前にステップＳ２を開始して、ミスヒットカウンタアレイ２５１に採取された１次統計情報の示すページ毎のミスヒットの頻度を集計し、ミスヒット頻度が高い上位１万個（Ｍ＝１０，０００）のページを抽出する。しかる後に業務を開始し、この１万個のページに対して残りのステップＳ２を継続することで、２次統計情報をミスヒットテーブル２６１に採取する。次に、翌々日の業務開始までの間にステップＳ３を実行する。これにより、ミスヒットテーブル２６１に採取された２次統計情報の示す、１万個のページにおける順序を考慮した全てのページ対の組み合わせ毎の、連続してミスヒットする頻度を集計し、連続してミスヒットする頻度が閾値より高い全てのページ対について、データベース１０内でその順序関係を実現するような再配置が行われる。ここで、閾値には、ミスヒットテーブル２６１中の、値が０でないフィールドの平均値を用いると良い。
【００７４】
［変形例］
次に、上記実施形態の変形例について説明する。
上記実施形態では、Ｐｉｄｐ（の示すページ）がミスヒットした直後にＰｉｄｃ（の示すページ）がミスヒットした場合だけ、ミスヒットテーブル２６１内の（Ｐｉｄｐ，Ｐｉｄｃ）の位置のフィールドの値がインクリメントされる。しかし、Ｐｉｄｐ（の示すページ）がミスヒットした後の、Ｘ回のミスヒットのうちにＰｉｄｃ（の示すページ）のミスヒットが含まれている場合に、ミスヒットテーブル２６１内の（Ｐｉｄｐ，Ｐｉｄｃ）の位置のフィールドの値がインクリメントされる構成としても良い。
【００７５】
そこで、上記実施形態の変形例では、図１５に示すようなＸ段のＦＩＦＯ（First IN First Out）２６５が、２次統計採取部２６内に用意される。このＦＩＦＯ２６５は、最近ミスヒットした最大Ｘ個のページのページ番号をミスヒット順に保持するためのミスヒットページ履歴バッファである。この変形例では、ミスヒットテーブル更新部２６４は、ミスヒットが発生した場合に、ＦＩＦＯ２６５を参照し、当該ＦＩＦＯ２６５に保持されている最大Ｘ個のページ番号と今回ミスヒットとなったページのページ番号との各々のページ対にそれぞれ対応する、ミスヒットテーブル２６１内のフィールドの値をインクリメントする。そして、ミスヒットテーブル更新部２６４は、今回ミスヒットが発生したページのページ番号をＦＩＦＯ２６５に保持する。これにより、その時点で最も以前に保持されたページ番号がＦＩＦＯ２６５から棄てられる。
【００７６】
上記変形例において、ミスヒットテーブル２６１に採取された２次統計情報に基づく、ページ配置最適化部２７によるページ配置最適化処理自体は、上記実施形態と同様に行われる。但し、このミスヒットテーブル２６１に採取された２次統計情報に基づくページの入れ替えにより、時間的に近いタイミングでミスヒットを発生するページ群がデータベース１０内のある領域に集中配置（ニアアロケーション）される。これにより、ディスク装置のシーク時間を減らしてディスクアクセス効率を向上することができる。
【００７７】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【００７８】
【図１】発明の一実施形態に係るデータベース管理システムを備えた計算機システムの構成を示すブロック図。
【図２】同実施形態で適用される、再構築前のミスヒットカウンタアレイ２５１と再構築後のミスヒットカウンタアレイ２５１の一例を示す図。
【図３】図１中のミスヒットテーブル２６１のデータ構造例を示す図。
【図４】同実施形態におけるページ配置の最適化のための処理の概要手順を示すフローチャート。
【図５】図４中の１次統計情報採取処理（ステップＳ１）の詳細な手順を示すフローチャート。
【図６】採取された１次統計情報をもとに、ｍ個のページのページ番号Ｐｉｄを、そのページのバッファミスヒットの頻度順に水平軸方向に並べて、垂直軸方向に頻度を表したグラフの一例を示す図。
【図７】図４中の２次統計情報採取処理（ステップＳ２）の詳細な手順を示すフローチャート。
【図８】図７中のミスヒットテーブル更新処理（ステップＳ２４）の詳細な手順を示すフローチャート。
【図９】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの一部を示す図。
【図１０】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの他の一部を示す図。
【図１１】図４中のページ配置最適化処理（ステップＳ３）の詳細な手順を示すフローチャートの残りを示す図。
【図１２】２次統計情報が採取されたミスヒットテーブル２６１の一例を示す図。
【図１３】ページ再配置リスト２７３の一例を示す図。
【図１４】ページ配置最適化処理におけるデータベース１０の状態の変化を示す図。
【図１５】上記実施形態の変形例で適用されるＦＩＦＯ（ミスヒットページ履歴バッファ）２６５の一例を示す図。
【符号の説明】
【００７９】
１０…データベース（データ格納手段）、２０…データベース管理システム、２１ユーザインタフェース、２２…クエリ処理部、２３…入出力バッファ、２４…バッファ管理部、２５…１次統計採取部、２６…２次統計採取部、２７…ページ配置最適化部、２５１…ミスヒットカウンタアレイ、２５２…ミスヒットカウンタアレイ更新部、２５３…ミスヒットカウンタアレイ再構築部、２６１…ミスヒットテーブル、２６２…ミスヒットテーブル要素抽出部、２６３…ミスヒットテーブル構築部、２６４…ミスヒットテーブル更新部、２６５…ＦＩＦＯ、２７１…ページ再配置候補抽出部、２７２…ページ入れ替え部、２７３…ページ再配置リスト。
【特許請求の範囲】
【請求項１】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムにおいて、
外部からの要求を処理するクエリ処理手段と、
前記データ格納手段に格納された一部のページデータを保持する入出力バッファと、
前記クエリ処理手段によって要求されたページデータが前記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段と、
行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルと、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、前記ミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するページ配置最適化手段と
を具備することを特徴とするデータベース管理システム。
【請求項２】
前記ページ配置最適化手段は、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページ対をページ再配置候補として抽出するページ再配置候補抽出手段と、
前記ページ再配置候補抽出手段によって抽出されたページ対毎に、アクセス順が前側のページの次のページとアクセス順が後側のページ、またはアクセス順が後側のページに先行するページとアクセス順が前側のページのデータを入れ替えるページ入れ替え手段と
を含むことを特徴とする請求項１記載のデータベース管理システム。
【請求項３】
１次元のカウンタの配列から構成されるミスヒットカウンタアレイであって、前記データ格納手段内の各ページが前記配列のそれぞれの配列要素に対応付けられたミスヒットカウンタアレイと、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットしたページに対応する前記ミスヒットカウンタアレイの配列要素の値をインクリメントするミスヒットカウンタアレイ更新手段と、
前記ミスヒットカウンタアレイの配列要素の値に基づいて、バッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページを、前記ミスヒットテーブルの各行及び列の要素として抽出するミスヒットテーブル要素抽出手段と、
前記ミスヒットテーブル要素抽出手段によって抽出された各ページを前記ミスヒットテーブルを構成する前記配列の各行及び各列に対応付けるミスヒットテーブル構築手段と
を更に具備することを特徴とする請求項１記載のデータベース管理システム。
【請求項４】
前記ミスヒットテーブル更新手段は、前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットに先行してミスヒットした最大Ｘ個（Ｘは２以上の整数）のページと、今回ミスヒットと判定されたページとの各々のページ対にそれぞれ対応する、前記ミスヒットテーブルの配列要素の値をインクリメントすることを特徴とする請求項１記載のデータベース管理システム。
【請求項５】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムであって、外部からの要求を処理するクエリ処理手段と、前記データ格納手段に格納された一部のページデータを保持する入出力バッファと、前記クエリ処理手段によって要求されたページデータが前記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段とを含むデータベース管理システムにおけるページ配置最適化方法において、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするステップと、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するステップと
を具備することを特徴とするページ配置最適化方法。
【請求項６】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するためのデータベース管理プログラムであって、
計算機を、
外部からの要求を処理するクエリ処理手段と、
前記クエリ処理手段によって要求されたページデータが入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段と、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するページ配置最適化手段と
して機能させるためのデータベース管理プログラム。
【請求項１】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムにおいて、
外部からの要求を処理するクエリ処理手段と、
前記データ格納手段に格納された一部のページデータを保持する入出力バッファと、
前記クエリ処理手段によって要求されたページデータが前記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段と、
行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルと、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、前記ミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するページ配置最適化手段と
を具備することを特徴とするデータベース管理システム。
【請求項２】
前記ページ配置最適化手段は、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページ対をページ再配置候補として抽出するページ再配置候補抽出手段と、
前記ページ再配置候補抽出手段によって抽出されたページ対毎に、アクセス順が前側のページの次のページとアクセス順が後側のページ、またはアクセス順が後側のページに先行するページとアクセス順が前側のページのデータを入れ替えるページ入れ替え手段と
を含むことを特徴とする請求項１記載のデータベース管理システム。
【請求項３】
１次元のカウンタの配列から構成されるミスヒットカウンタアレイであって、前記データ格納手段内の各ページが前記配列のそれぞれの配列要素に対応付けられたミスヒットカウンタアレイと、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットしたページに対応する前記ミスヒットカウンタアレイの配列要素の値をインクリメントするミスヒットカウンタアレイ更新手段と、
前記ミスヒットカウンタアレイの配列要素の値に基づいて、バッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページを、前記ミスヒットテーブルの各行及び列の要素として抽出するミスヒットテーブル要素抽出手段と、
前記ミスヒットテーブル要素抽出手段によって抽出された各ページを前記ミスヒットテーブルを構成する前記配列の各行及び各列に対応付けるミスヒットテーブル構築手段と
を更に具備することを特徴とする請求項１記載のデータベース管理システム。
【請求項４】
前記ミスヒットテーブル更新手段は、前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、当該バッファミスヒットに先行してミスヒットした最大Ｘ個（Ｘは２以上の整数）のページと、今回ミスヒットと判定されたページとの各々のページ対にそれぞれ対応する、前記ミスヒットテーブルの配列要素の値をインクリメントすることを特徴とする請求項１記載のデータベース管理システム。
【請求項５】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するデータベース管理システムであって、外部からの要求を処理するクエリ処理手段と、前記データ格納手段に格納された一部のページデータを保持する入出力バッファと、前記クエリ処理手段によって要求されたページデータが前記入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段とを含むデータベース管理システムにおけるページ配置最適化方法において、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするステップと、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するステップと
を具備することを特徴とするページ配置最適化方法。
【請求項６】
記憶領域が固定長のページに区切って使用されるデータ格納手段を管理するためのデータベース管理プログラムであって、
計算機を、
外部からの要求を処理するクエリ処理手段と、
前記クエリ処理手段によって要求されたページデータが入出力バッファ上に存在するかを判定し、存在すれば当該入出力バッファ上のページデータを前記クエリ処理手段に返し、存在しなければバッファミスヒットとして前記要求されたページデータを前記データ格納手段から読み出して前記入出力バッファに配置すると共に当該ページデータを前記クエリ処理手段に返す入出力バッファ管理手段と、
前記入出力バッファ管理手段によってバッファミスヒットが判定された場合、行数と列数とが同数の論理的に２次元のカウンタの配列から構成されるミスヒットテーブルであって、前記データ格納手段内の全ページのうちの少なくともバッファミスヒットの頻度が一定レベルより高いページ、またはバッファミスヒットの頻度が高い上位一定数のページの各々が前記配列の各行及び各列に対応付けられたミスヒットテーブルの、直前にバッファミスヒットしたページに対応する行または列と、今回バッファミスヒットしたページに対応する列または行とで決まる、前記ミスヒットテーブルの配列要素の値をインクリメントするミスヒットテーブル更新手段と、
前記ミスヒットテーブルの各配列要素のうち、閾値を超える配列要素または値が大きい上位一定数の配列要素の、行及び列にそれぞれ対応付けられたページのデータが前記データ格納手段内で連続するようにページを再配置するページ配置最適化手段と
して機能させるためのデータベース管理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００６−１０６８９５（Ｐ２００６−１０６８９５Ａ）
【公開日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【出願番号】特願２００４−２８９２７９（Ｐ２００４−２８９２７９）
【出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【出願日】平成１６年９月３０日（２００４．９．３０）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]