JP4623318B2

JP4623318B2 - 追記型データベース管理システム、不要領域修復処理方法及び不要領域修復プログラム

Info

Publication number: JP4623318B2
Application number: JP2007013849A
Authority: JP
Inventors: 輝聖川畠
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2007-01-24
Filing date: 2007-01-24
Publication date: 2011-02-02
Anticipated expiration: 2027-01-24
Also published as: JP2008181297A

Description

本発明は、追記型データベース管理システム、不要領域修復処理方法及び不要領域修復プログラムに関し、特に、データベースの更新に伴うテーブルの不要領域の修復を効率よく行う追記型データベース管理システム、不要領域修復処理方法及び不要領域修復プログラムに関する。

従来、データベースを管理するデータベース管理システムでは、トランザクションの同時実効性制御を考慮する必要があった。

このトランザクションとは、データベースにおいてデータを処理する為の一連の処理手続きのことを言う。

具体的には、コンピュータを用いてデータを処理する際、ハードウェアやソフトウェアの障害などが発生しても、全体に破綻をきたさないように、データの処理を確実に行うための論理ユニットのことを指す。

ここで、従来の追記型のストレージを持つデータベース管理システムでは、データベースの更新を行う際、更新前のデータと、更新後のデータとの両方を保持する多版式同時実行制御(Multi Version Concurrency Control)を用いている。

この追記型ストレージを用いた多版式同時実効制御では、問い合わせロックの獲得と、書き込みロックとの獲得が競合しないため、ロールバックやリカバリの実装が非常に単純になる。

しかしながら、この多版式同時実行制御は、削除や更新が発生するごとに古いデータが丸ごと不必要となり、古いデータが残存することにより、データを記憶する記憶領域を大きく消費していくという問題がある。

なお、追記型でない既存のデータベース管理システムであっても、削除や更新時にはデータを書き換えることにより不要領域が発生するので、追記型でない既存のデータベース管理システムの場合であっても追記型のデータベースより不要領域が大きくないものの、同様に不要領域が発生してしまう。

このような場合には、データベースのレコードを分割して格納することにより、不要領域の再利用を行うなどの機能が備わっているが、複数のブロックに１つのレコードを挿入する状態が発生し、挿入・更新に時間がかかってしまう場合がある。

なぜなら、データベースは、レコードの集合体であり、レコードは、1つのカードのようなものである。そのレコードには、フィールドと呼ばれる互いに関連する情報の断片を含んでいるため、１つのレコードに含まれる情報を、複数のブロックに分割することになるからである。

そこで、追記型のデータベース管理システムでは、定期的にデータベースの記録単位であるページごとに自動的に不要領域を詰め、利用可能な領域のページアドレスと利用可能領域サイズを記憶することによって、データを再利用するための処理が行われている。

また更に、不要領域が詰められたページにおいて、テーブルに対するデータ（以下、これをテーブルデータと言うことがある。）の更新件数の割合などによって、不要領域の修復処理（以下、これを不要領域修復処理という。）を自動的に行う方法なども行われている（非特許文献１参照）。

なお、ここで言うテーブルとは、データを記憶する為のオブジェクトであって、同じフィールドを共有しているレコードの集まりのことを言う。また、テーブルは、レコード(行)とフィールド(列)のオブジェクトによって管理されている。

しかしながら、このような従来技術では、不要領域の修復処理がテーブルにおける不要領域が発生した全てのページに対してスキャンが行われることにより、ディスクなどの処理負荷が高くなり、この不要領域修復処理は、ストレージ等を持つデータベースの記憶装置に、高い処理負荷を与えることとなり、他の処理に悪影響を与えるという問題があった。

また、この不要領域修復処理は、テーブルの更新行数（すなわち、レコード数）が、テーブル全体に対して一定の割合を超えた場合に不要領域の修復処理を行っていたので、不要領域の大きさとは何ら無関係に不要領域修復処理を行っていた。

従って、不要領域修復処理を行う際に、領域修復率が低い場合であっても不要領域修復処理を行っているという問題があった。

具体的には例えば、可変長のデータ定義がされた場合には、それぞれのテーブルデータのサイズが違うため、更新行数が不要領域サイズには必ずしも比例しない。そのため、全体としては不要領域が少なくても更新行数が多い場合には、不要領域修復処理が行われてしまう可能性があった。

また、ページの不要領域に偏りが生じている場合にも、領域の修復率が低いページに対してデータを詰める処理が発生し、非常に非効率になってしまうという問題があった。

そこで、このようなデータベース管理システムにおける不要領域のデータの取り扱いに関するものが、特許文献１乃至３に記載されている。
石井達夫著「PostgreSQL完全攻略ガイド改定第５版」技術評論社出版、２００６年４月１日、ｐｐ．４３７−４４６特開２０００−１３７６３９号公報特開２００１−０７５８３２号公報特開２００４−３０３３６８号公報

しかしながら、特許文献１及び３に記載されたものを、従来の追記型データベース管理システムに適用したとしても、不要領域が大量にデータベースに蓄積した状態であって空き容量を確保し直す場合には、不要領域修復処理が複雑となり、ストレージであるディスクに相当な負担がかかることによって処理能力が低下し、他の処理に悪影響を与えるという問題が依然としてあった。

本発明は、上記問題点に鑑みてなされたものであり、データの更新に伴う不要領域修復処理を効率良く行う追記型データベース管理システム、不要領域修復処理方法及び不要領域修復プログラムを提供することを目的とする。

本発明に係る追記型データベース管理システムは、データを記憶するデータベースを管理する追記型データベース管理システムにおいて、前記データを更新又は削除することにより前記データベース内に生じる不要領域を、当該データベースの記録単位であるページ毎に更新しながら管理する管理手段と、前記管理手段が前記ページ毎に管理する前記不要領域から当該不要領域のサイズを算出すると共に、当該不要領域のサイズと、前記データベース内における当該不要領域の位置とを、前記ページ毎に記憶する不要領域記憶手段と、前記ページに前記不要領域が発生した場合に、前記不要領域記憶手段に記憶された前記不要領域のサイズと、当該ページにおける前記不要領域の比率に基づいて、当該不要領域に属するデータを解放するか否かを判断する不要領域比率判断手段と、を備え、前記不要領域比率判断手段は、前記不要領域のサイズと、前記ページにおける前記不要領域の比率とに基づいて、予め設定された閾値を超えた場合には、当該ページの前記不要領域に属するデータを前記不要領域の位置から解放する不要領域解放処理手段を更に備えることを特徴とする。

また本発明に係る追記型データベース管理システムは、前記不要領域解放処理手段が、前記ページの前記不要領域に属するデータの実行ログであるトランザクション識別子と、システムの実行ログとして一番古く関わった最古トランザクションとを比較して、当該不要領域に属するデータが削除可能なタプルデータか否かを判断するタプルデータ有効性判断手段と、前記タプルデータ有効性判断手段により、前記トランザクション識別子が前記最古トランザクション識別子より古い場合には、前記不要領域に属するデータは、前記削除可能なタプルデータと判断されると共に、当該削除可能なタプルデータに対し削除予約を行うタプルデータ削除予約手段と、前記タプルデータ削除予約手段により、前記削除可能なタプルデータがある場合には、当該削除可能なタプルデータに割り当てられたインデックスデータの有無を判断するインデックスデータ判断手段と、前記インデックス判断手段により、前記削除可能なタプルデータに割り当てられた前記インデックスデータが有った場合には、当該インデックスデータを削除するインデックスデータ削除手段と、を備え、前記インデックス判断手段は、前記インデックスデータ削除手段によって前記インデックスデータが無くなった場合又は前記インデックスデータが前記削除可能なタプルデータに無かった場合には、当該削除可能なタプルデータを解放して空き領域を確保するようにしても良い。

また本発明に係る追記型データベース管理システムは、前記管理手段が前記ページを更新することにより、前記データベースに記憶された前記データを更新する場合であって、更新により前記データベースに新たに追記するタプルデータのレコードを、追記タプルデータ長として算出するタプル長算出手段、を更に備え、前記タプル長算出手段によって前記追記タプルデータ長が算出されることにより、確保された前記空き領域に、当該追記タプルデータ長の前記タプルデータのレコードを挿入可能な場合には、当該空き領域に挿入すると共に、挿入された当該タプルデータの前記ページを更新し、算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの最終ページに当該タプルデータ長の前記タプルデータを挿入できる場合には、当該最終ページに挿入し、算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの前記最終ページに前記タプルデータ長の前記タプルデータを挿入できない場合には、前記データベースに新規ページを確保して、当該タプルデータ長の前記タプルデータを追記するようにしても良い。

また本発明に係る追記型データベース管理システムは、前記管理手段が、前記データベース内に生じる前記不要領域を、前記データのテーブル毎に合計しながら管理するテーブル合計管理手段と、前記テーブル合計管理手段が、当該テーブル毎の前記不要領域のサイズを更新しながら記憶するテーブル不要領域記憶手段と、を更に備え、前記テーブル合計管理手段は、前記テーブル毎の前記不要領域のサイズと、前記テーブルにおける前記不要領域の比率とに基づいて、前記不要領域解放処理手段を開始する開始閾値、又は前記不要領域解放処理手段を終了する終了閾値の少なくとも一方を備えると共に、前記開始閾値又は前記終了閾値によって前記不要領域解放処理手段を制御するようにしても良い。

また本発明に係る追記型データベース管理システムは、前記不要領域比率判断手段が、前記ページに前記不要領域が発生した場合であって、前記予め設定された閾値を超えた場合には、前記不要領域解放処理手段を実施するための予約を行う不要領域解放処理予約手段を更に備え、前記不要領域解放処理予約手段は、前記データベースの処理負荷に基づいて、前記不要領域解放処理手段を制御するようにしても良い。

本発明によれば、データベース内に発生する不要領域をデータベースの記録単位であるページ毎に管理すると共に、発生した不要領域のサイズと、ページにおける不要領域の比率とに基づいて、予め設定された閾値を超えた場合には、閾値を超えたそのページに対して不要領域解放処理を行うことができる。従って、不要領域のサイズが、閾値を超えたページに限定して不要領域修復処理を行うことができるので、かくして、データの更新に伴う不要領域修復処理を効率良く行う追記型データベース管理システム、不要領域修復処理方法及び不要領域修復プログラムを実現できる。

次に、本発明の実施の形態の構成について図面を参照して詳細に説明する。
（第１の実施の形態）
（１）第１の実施の形態による追記型データベース管理システム
（１−１）追記型データベース管理システムの構成
図１を参照すると、第１の実施の形態による追記型データベース管理システムは、データベースクライアント１と、データベースクライアント１が接続されるデータベース管理システム２と、データベースを記憶する記憶装置３とを備えている。

データベース管理システム２は、クエリ管理部２１と、トランザクション管理部２２と、ストレージ管理部２３とを備えている。

クエリ管理部２１は、クエリ解析部２１１と、実行計画作成部２１２とを備えている。

クエリ解析部２１１は、データベースクライアントから渡されたクエリを解析し、その結果を実行計画作成部２１２に渡す。

実行計画作成部２１２は、トランザクション管理部２２やストレージ管理部２３での実行計画を作成する。

トランザクション管理部２２は、トランザクション制御管理部２２１を備えている。

トランザクション制御管理部２２１は、後述するトランザクションの有効状態をストレージ管理部２３のタプル管理部２３３が有するタプルデータ、及びトランザクション情報記憶部３３のコミット状態情報から、タプルが有効な状態か無効な状態かの判定を行う。

ここでタプルとは、いくつかの値を１つにまとめて、あたかも１つの値のように扱う機能のことであり、表における行に相当する。また、タプルデータとは、タプルの機能によって割り当てられるデータのことを言う。

ストレージ管理部２３は、インデックス管理部２３１と、ページ管理部２３２（本発明における管理手段に該当する。）と、タプル管理部２３３（本発明における管理手段に該当する。）と、空き容量管理部２３４（本発明における不要領域比率判断手段に該当する。）と、統計情報管理部２３５とを備えている。

インデックス管理部２３１は、後述するタプルイメージをタプル管理部２３３より受け取り、インデックスデータの作成・削除などを行う。また、インデックス管理部２３１は、作成したインデックスデータを、後述するインデックスデータ記憶部３１へ入出力を行い管理する。

ページ管理部２３２は、タプル管理部２３３から後述するタプルイメージを受け取ると共にページの作成を行い、そのページのデータ（以下、これをページデータと言う。）をテーブルデータとして、後述するテーブルデータ記憶部３２へ入出力する。また、ページ管理部２３２は、不要領域修復処理なども行う。

タプル管理部２３３は、クエリ管理部２１やトランザクション管理部２２から受け取った情報により、タプルイメージの生成やページ管理部２３２から受け取ったページデータからタプルデータの取得を行う。また、タプルの生成や抽出した情報から、後述するトランザクション情報のトランザクション情報記憶部３３へ入出力を行う。

ここで、タプルイメージとは、タプルデータとタプル機能とによって生成される、ページデータに相当するテーブルデータに対応するものである。

空き容量管理部２３４は、更新や削除によって生じた不要領域を含むページ情報と、不要領域のサイズ情報とを、後述するページ不要領域情報記憶部３５へ入出力を行う。

統計情報管理部２３５は、テーブルの定義や、テーブルデータサイズ、ページサイズ、ページ不要領域修復処理開始閾値、空き容量を持っているページアドレスとサイズ、最古トランザクション識別子などといったデータベースの全体情報を管理する。また、それらのデータベース統計情報記憶部３４への入出力を行う。

記憶装置３は、インデックスデータ記憶部３１と、テーブルデータ記憶部３２と、トランザクション情報記憶部３３と、データベース統計情報記憶部３４と、ページ不要領域情報記憶部３５（本発明における不要領域記憶手段に該当する。）とを備えている。

インデックスデータ記憶部３１は、テーブルにインデックスが作成されている場合のインデックスデータを記憶する。

テーブルデータ記憶部３２は、データベースのテーブルデータを、ページと呼ばれる単位で記憶する。

トランザクション情報記憶部３３は、各トランザクションを一意に示すためのトランザクション識別子（図示する場合、これをトランザクションＩＤと言うことがある。）によって、トランザクション別の状態情報を記憶する。

データベース統計情報記憶部３４は、データベース管理システムの実行中の全トランザクションにおいて、一番古いコミット済みトランザクション識別子（これを、最古トランザクション識別子という。）、テーブルの定義や、テーブルデータサイズ、ページサイズ、ページ不要領域修復処理開始閾値、空き容量を持っているページアドレスとサイズなどを記憶する。

ページ不要領域情報記憶部３５は、テーブルデータ記憶部３２に記憶されているテーブルデータに対して更新や削除が実行された際に発生したページ毎の不要領域合計サイズを記憶する。
（１−２）追記型データベース管理システムの不要領域修復処理
次に、図１のブロック図と、図２及び図３のフローチャートを参照して、第１の実施の形態による追記型データベース管理システムの不要領域修復処理について、詳細に説明する。

なお、第１の実施の形態では、対象となるデータベースの操作を多版式同時実行制御(Multi Version Concurrency Control)により、不要領域が発生した場合の不要領域の削除と、更新のクエリの動作のみに限って説明を行う。

まず、データベース管理システム２（図１）は、データベースクライアント１（図１）から、更新のクエリを受ける。

次に、クエリ管理部２１がクエリを受け取ると、クエリ解析部２１１が、そのクエリの解析を行う。

そして、実行計画作成部２１２が実行計画を作成し、その情報（すなわち作成された実行計画である。）を、ストレージ管理部２３へ送る（図２のステップＡ１）。

ストレージ管理部２３は、トランザクションの多版式同時実行制御を行うため、トランザクション管理部２２のトランザクション制御管理部２２１によって、トランザクション識別子（図２では、これをトランザクションＩＤと記載する。）を受け取る（図２のステップＡ２）。

ここで、先に受け取ったクエリが、更新であるか或いは削除であるかによって動作が変わる（図２のステップＡ３）。

もし先に受け取ったクエリが更新の場合には、タプル管理部２３３（図１）によってタプルイメージを作成し、ページ管理部２３２（図１）により、そのタプルイメージをテーブルデータとしてテーブルデータ記憶部３２に書込みを行う。

ここで、作成されたタプルイメージにインデックスが有る場合には、インデックス管理部２３１がインデックスデータ記憶部３１に、作成されたタプルイメージのインデックスの書込みを行う（図２のステップＡ４）。

これに対し、先に受け取ったクエリが削除であった場合、或いは更新データの書込みが終了した場合には、タプル管理部２３３によって作成されたタプルイメージに、削除フラグとトランザクション識別子を書き込み（図２のステップＡ５）、そのタプルイメージをテーブルデータとしてページ管理部２３２によってテーブルデータ記憶部３２に書き込む（図２のステップＡ６）。

これにより、現在のトランザクション識別子によって削除された状態になる。

また、空き容量管理部２３４は、ステップＡ５において、削除フラグを立てたタプルイメージのページアドレスとタプルイメージのサイズを記憶しておき、ステップＡ６において、削除されたページアドレスとタプルイメージのデータのサイズから、ページごとの合計不要領域サイズが記憶されているページ不要領域情報記憶部３５へ更新を行う。

タプル管理部２３３は、トランザクションが終了したことを記録するため、トランザクション情報記憶部３３に対して、トランザクション識別子にコミットされた情報を書き込む。また、タプル管理部２３３は、統計情報管理部２３５（図１）を介して、データベース統計情報記憶部３４に記憶していた最古トランザクション識別子の更新が行える場合には、更新情報を書き込む（図２のステップＡ７）。

その後、空き容量管理部２３４は、統計情報管理部２３５からページのサイズやページ不要領域修復処理開始閾値を取得し、ステップＡ４において更新を行ったページの不要領域サイズ比率が閾値を超えているか否か、ページ不要領域情報記憶部３５に記憶されている情報から、ページ毎に調査する（図２のステップＡ８〜Ａ９）。

ここで、更新済みのページであって（ステップＡ８）、その更新済みのページにおいてページ不要領域の比率を判断し（ステップＡ９）、閾値の比率を超えていれば、そのページに対して後述する不要領域解放処理を行う（図２のステップＢ）。

そして、ステップＢによる不要領域解放処理が終了したか、或いはステップＡ９で閾値の比率を超えていなければ、この次のページの処理を行うためにステップＡ８に戻る。

このように、全ての更新されたページに対して、ページ不要領域の比率の確認が終了した時点で、当初に受け取ったクエリの処理は終了とする。
（１−３）追記型データベース管理システムの不要領域解放処理（ステップＢ）
次に、不要領域解放処理（図２のステップＢ）について、図３のフローチャートを用いて説明する。

まず、ページ管理部２３２（図１）とタプル管理部２３３（図１）は、テーブルデータ記憶部３２（図１）から獲得した不要領域解放を行うページに対して、タプル領域を一番目から検査していく（図３のステップＢ１）。

ここで、ページ内に未検査のタプルが有る場合は、データベース統計情報記憶部３４を通じて最古トランザクション識別子を参照する。

そして、トランザクション制御管理部２２１は、タプルのトランザクション識別子と最古トランザクション識別子とを比較して、タプルのトランザクション識別子が最古トランザクション識別子よりも古いと判定されれば、削除可能となる（図３のステップＢ２）。

また、削除可能な場合には、ストレージ管理部２３が、タプルの位置情報を削除予約リストに格納する（図３のステップＢ３）。

このように、図３のステップＢ１からステップＢ３を繰り返し、ページに格納されている全てのタプルについて検査を行う。

全てのタプルについて検査が終了すると、図３のステップＢ３で確認された削除予約リストに、タプル削除情報が格納されているかを確認する（図３のステップＢ４）。

ここで、削除予約リストに削除対象タプルが存在する場合には、テーブルのインデックスの有無を検査する（図３のステップＢ５）。

そして、削除対象タプルにインデックスが存在する場合には、インデックス管理部２３１が、ページに含まれる削除対象タプルのインデックス情報（すなわち、インデックスデータに相当する。）を削除する（図３のステップＢ６）。

これにより、インデックス情報がなかった場合、又は全てのインデックス情報の削除が完了した場合には、ページ管理部２３２がページの空き領域を確保する（図３のステップＢ７）。

空き容量管理部２３４は、統計情報管理部２３５を介して、データベース統計情報記憶部３４に確保した空き領域とページ番号を記憶し、空き領域と領域情報を更新する（図３のステップＢ８）。

ここで、空き領域の確保（図３のステップＢ７）について、具体例として図４において説明を行うことにする。

図４を参照すると、空き領域の解放前ページ４には、ページ管理情報４１と、タプルデータ４２とが含まれている。

また、タプルデータ４２には、有効タプルデータ４２１と、４２４とを有すると共に、削除可能タプルデータ４２２と、４２３と及び４２５が存在している。

ページ管理情報４１には、タプルデータ４２１から４２５の有効性情報が格納されている。そして、解放前ページ４から空き領域の確保を行ったものが空き領域解放後ページ５となる。

ページ管理部２３２は、有効タプルデータ４２１、４２４を順に後ろから揃えると共に、ページ管理情報４１に削除可能として管理されている、削除可能タプルデータ４２２と、４２３及び４２５のタプルデータを無効化し、ページ管理情報５１に書き換える。

つまり、有効タプルデータ４２１のデータが有効タプルデータ５２１と、有効タプルデータ４２４のデータが有効タプルデータ５２２と、等しいデータになっている。

これにより有効なタプルデータのみが残り、空き領域を適切に確保することができる。
（１−４）追記型データベース管理システムの確保領域追記処理
次に、この確保した空き領域を利用した確保領域追記処理について、図５に示すフローチャートによって説明を行う。

データベースであるテーブルデータ記憶部３２にテーブルデータの挿入及び更新により、データ追記が発生したら、ストレージ管理部２３が追記対象のタプルデータを、ひとつずつ操作していく（図５のステップＣ１）。

まず、タプル管理部２３３は、追記対象であるタプルデータのタプル長を算出する（図５のステップＣ２）。

そして、そのタプル長が、再利用領域で格納できるページが存在するか否か、空き容量管理部２３４によって確認する（図５のステップＣ３）。

ここで、もし再利用可能なページが存在した場合には、ページ管理部２３２がテーブルデータ記憶部３２の対象ページに追記対象のタプルデータを挿入する（図５のステップＣ４）。

その後、空き容量管理部２３４が再利用領域情報へ利用したページのサイズ情報を更新する（図５のステップＣ５）。

これに対し、再利用領域に格納できるページが存在しない場合には、ページ管理部２３２が最終ページに追記対象のタプルデータの挿入ができるか否か、確認を行う（図５のステップＣ６）。

もし、その追記対象のタプルデータが挿入できる場合には、最終ページにその追記対象のタプルデータの挿入を行う（図５のステップＣ７）。

一方、最終ページにおいて、追記対象のタプルデータを挿入できない場合には、新しいページを確保して、その追記対象のタプルデータの挿入を行う（図５のステップＣ８）。

以上のステップＣ１からステップＣ８を繰り返し、全てのタプルデータの挿入が終われば、終了となる。
（１−５）追記型データベース管理システムの効果
本実施の形態では、空き容量管理部２３４が、更新や削除によって発生した不要領域を、ページ不要領域情報記憶部３５に、ページごとに記憶するように構成されているので、テーブルデータの更新や削除によって、ページごとの不要領域を管理し、記憶する。

これにより、ページごとの自動的な不要領域修復と再利用を効率的に実施することができる。また、運用状況により、ページ不要領域修復処理開始閾値を小さくすることにより、不要容量を発生させにくくさせることができ、或いは、ページ不要領域修復処理開始閾値を大きくすることにより、不要領域解放処理を効率の高いページに限定することもできる。

このように、本実施の形態によれば、不要領域となったサイズをデータベースの記録単位であるページごとに管理していることにより、不要領域修復を行う対象のページを、不要領域の比率が予め設定された閾値以上のページに限定して行うことができるので、効率の良い不要領域修復処理ができることにある。

更に、本実施の形態によれば、不要領域解放処理を不要領域が発生した全てのページに対して行わず、削除や更新により不要領域が発生する毎に、その際、不要領域の比率の閾値を超えたページにのみ不要領域修復処理を行うことができるので、不要領域修復処理を分散化させることができる。
（第２の実施の形態）
（２）第２の実施の形態による追記型データベース管理システム
（２−１）追記型データベース管理システムの構成
次に、第２の実施の形態による追記型データベース管理システムについて説明する。

図６を参照すると、第２の実施の形態による追記型データベース管理システムでは、第１の実施の形態における構成に加え、更に記憶装置６が、テーブル不要領域情報記憶部６１を備えている。

テーブル不要領域情報記憶部６１には、ページ不要領域情報記憶部３５で記憶されている不要領域サイズのテーブル毎の合計が、記録されている。

また、データベース統計情報記憶部３４には、テーブル不要領域修復処理開始閾値と、テーブル不要領域修復終了閾値とが保存されている。

但し、ここでは、具体例として、テーブル不要領域修復処理開始閾値が、テーブル不要領域修復処理終了閾値よりも大きい値であるものとする。
（２−２）追記型データベース管理システムの不要領域修復処理
次に、第２の実施の形態における不要領域修復処理について、図６及び図７のフローチャートを参照しながら、詳細に説明する。

図７のフローチャートにおいて、ステップＡ１からＡ６及びステップＡ７、またステップＢで示される第２の実施の形態におけるクエリ解析部２１１、実行計画作成部２１２、トランザクション制御管理部２２１、インデックス管理部２３１、ページ管理部２３２、タプル管理部２３３、空き容量管理部２３４及び統計情報管理部２３５の動作は、第１の実施の形態で示した動作と同一であるため、説明は省略する。

第１の実施の形態では、空き容量管理部２３４が管理していたものは、ページ毎の不要領域のサイズのみであった。

これに対し、第２の実施の形態では、ステップＡ６においてページサイズ情報の更新の後、空き容量管理部２３４が、テーブルにおける合計不要領域サイズを、テーブル不要領域情報記憶部６１に更新する。

すなわち、空き容量管理部２３４は、参照しているテーブルのページ不要領域情報記憶部３５で保存している不要領域サイズの総和と等しい値を更新する（図７のステップＤ１）。

そして、図７のステップＡ７におけるトランザクションのコミットログを書込み後、空き容量管理部２３４は、統計情報管理部２３５からテーブルのサイズやテーブル不要領域修復処理開始閾値を取得すると共に、テーブル不要領域情報記憶部６１から合計テーブル不要容量サイズを取得する。そして、空き容量管理部２３４は、テーブルの不要領域比率（以下、テーブル不要領域比率と言う。）がテーブル不要領域修復処理開始閾値を超えていないか確認する（図７のステップＤ２）。

ここで、テーブル不要領域比率が、テーブル不要領域修復処理開始閾値を超えている場合には、ページ不要領域情報記憶部３５から一番大きい不要領域サイズを持っているページを調査し、そのページに対して不要領域解放処理（ステップＢ）を行う。

そして、不要領域解放処理（ステップＢ）を行った後、ステップＤ３へ戻り、先のテーブル不要領域比率が、データベース統計情報記憶部３４に記憶されているテーブル不要領域修復終了閾値より小さいか否かを判断し、小さければ終了となる。

ここで、具体的に検討すると、例えば、テーブル不要領域修復処理開始閾値が３０％であるとし、テーブル不要領域修復処理終了閾値が１０％であるとする。

もし、例えば、ステップＤ２において、あるテーブル不要領域比率が３２％であった場合には、図７のステップＤ３へ進むと共に、テーブル不要領域修復処理終了閾値が１０％であるので、ステップＤ４へ進む。また、ステップＤ４では、一番大きい不要領域サイズを持つページを調査し、不要比率の高いページを検索した後にステップＢへ移り、不要領域解放処理を実施する。

この場合、例えば、一番大きい不要領域サイズを持つページに対して不要領域解放処理（ステップＢ）を行ったことにより、３２％であったテーブル不要領域比率が、ステップＤ３において、テーブル不要領域修復処理終了閾値である１０％より小さくなった場合に、終了となる。

これに対し、ステップＤ３において、テーブル不要領域比率が、テーブル不要領域修復終了閾値である１０％よりもまだ大きい場合には、次に大きい不要領域サイズを持っているページを調査し（図７のステップＤ４）、そのページに対して不要領域解放処理（ステップＢ）を行う。

そして、不要領域解放処理（ステップＢ）が終了するとステップＤ３に戻り、テーブル不要領域の比率を判断し、テーブル不要領域修復終了閾値（上述の例では、１０％）を満たすまで不要領域解放処理（ステップＢ）を繰り返す。

なお、第２の実施の形態では、図７に示したステップＤ２及びＤ３の処理に特徴を有しており、確保した空き領域を利用したデータの確保領域追記処理については、第１の実施の形態の場合（１−４）と同一であるため、説明は省略する。

また或いは、ステップＤ２とステップＤ３の間に、ステップＤ４とステップＢを設け、テーブル不要領域修復処理開始閾値（例えば、３０％）を満たしていない場合に、もっとも大きい不要領域サイズを有するページを調査し（ステップＤ４）、そのページに対して不要領域解放処理（ステップＢ）を行い、テーブル不要領域修復処理終了閾値（例えば、１０％）を満たすような処理を追加しても良い。
（２−３）追記型データベースシステムの効果
第２の実施の形態では、テーブル不要領域修復処理開始閾値と、テーブル不要領域修復終了閾値とを設けることにより、テーブル全体での不要容量の比率によって不要容量修復のタイミングを自動的に計ることができる。

また、第１の実施の形態と同様に、空き容量管理部２３４が、ページ不要領域情報記憶部３５に更新や削除によって発生した不要容量を、ページごとに記憶するように構成されているので、効率性の高いページから不要容量修復を行うことができる。

また、運用状況により、第１の実施の形態で示したように、テーブル不要領域修復処理開始閾値を小さくすることによって、不要容量を発生させにくくさせることができると共に、テーブル不要領域修復処理終了閾値の大きくすることによって、不要容量修復の負荷をできるだけ小さくすることもできる。
（３）第３の実施の形態による追記型データベース管理システム
（３−１）追記型データベース管理システムの構成
第３の実施の形態における構成は、第１の実の形態の場合と同様であり、図１と同一であるが、ページ管理部２３２がオペレーティングシステムを通じてディスクの負荷や処理状況などを監視する点と、不要領域修復の開始条件となるディスク負荷閾値を有する点で異なる。
（３−２）追記型データベースシステムの不要領域修復処理
次に、第３の実施の形態における不要領域修復処理について、図８及び図９のフローチャートを参照しながら、詳細に説明する。

図８のフローチャートにおいて、ステップＡ１からＡ８及びＡ９で示される第３の実施の形態におけるクエリ解析部２１１、実行計画作成部２１２、トランザクション制御管理部２２１、インデックス管理部２３１、ページ管理部２３２、タプル管理部２３３、空き容量管理部２３４及び統計情報管理部２３５の動作は、第１の実施の形態で示した動作と同一であるため、説明は省略する。

第１の実施の形態では、不要領域サイズ比率が閾値を超えていた場合、その比較の後にステップＢによる不要領域解放処理によって不要領域の修復を行っていた。

これに対し、第３の実施の形態では、ステップＡ９において不要領域比率の調査後に、不要領域サイズ閾値を超えていた場合には、そのページに対する不要領域修復の予約を、対象ページ位置と共にページ管理部２３２が覚えておく（図８のステップＥ１）。

次に、図９のフローチャートを参照すると、また、ページ管理部２３２は、一定時間ごとや指定された時間帯に不要領域修復の予約が登録されているかどうかを確認する。（図９のステップＦ１）。

ここで、不要領域修復の予約が登録されている場合には、ページ管理部２３２は、オペレーティングシステムを通じてディスクの負荷や処理状況を調べる（図９のステップＦ２）。

そして、一定時間の間、ディスク負荷が、ディスク負荷閾値を超えた場合には、ディスク負荷が、ディスク負荷閾値を下回り続けるまで待機する（図９のステップＦ３）。

このように、ディスク負荷が下がるまで待機することにより（図９のステップＦ３）、ディスク負荷がディスク負荷閾値を下回り続けた場合、或いはステップＦ２においてディスク負荷が低い場合には、不要領域解放処理を行う（図９のステップＢ）。

ステップＢの不要領域解放処理が終了すると、ステップＦ１に戻り、不要領域修復の予約が無くなるまで一連の流れを続け、不要領域解放処理の予約が無くなれば、第３の実施の形態における不要領域修復処理は、終了となる。

なお、不要領域解放処理や、確保した空き領域を利用した確保領域追記処理については、第１の実施の形態のものと同一であるため、説明は省略する。
（３−３）追記型データベースの効果
本実施の形態では、不要領域修復の実施タイミングについて、ディスク負荷が低いときに自動的に行うことが出来る。

これにより、第1の実施の形態で示したように、ページ単位で不要領域修復のために領域修復対象範囲を少なくしている上、更にディスク負荷が低いときに不要領域を修復させることから、データベースの他の操作や同計算機上で動いている他のアプリケーションへの影響を最小限にとどめることが出来る。

また、事前にデータベースやその他アプリケーションの影響範囲が低い時間帯が分かっている場合には、この不要領域修復の実行時期を予め指定しておくことにより、不要領域修復の影響をさらに限定的にすることも出来る。

本発明における第１の実施の形態による追加型データベース管理システムの構成を示すブロック図である。本発明における第１の実施の形態による不要領域修復処理を表すフローチャートである。本発明における第１の実施の形態による不要領域解放処理を表すフローチャートである。本発明における第１の実施の形態による空き領域の確保を具体例で示した図である。本発明における第１の実施の形態による確保領域追記処理を表すフローチャートである。本発明における第２の実施の形態による追加型データベース管理システムの構成を示すブロック図である。本発明における第２の実施の形態による不要領域修復処理を表すフローチャートである。本発明における第３の実施の形態による不要領域修復処理を表すフローチャートである。本発明における第３の実施の形態による不要領域解放処理を解放処理予約の有無によって実行するフローチャートである。

符号の説明

１データベースクライアント
２データベース管理システム
３、６記憶装置
４解放前ページ
５解放後ページ
２１クエリ管理部
２２トランザクション管理部
２３ストレージ管理部
３１インデックスデータ記憶部
３２テーブルデータ記憶部
３３トランザクション情報記憶部
３４データベース統計情報記憶部
３５ページ不要領域情報記憶部
４１、５１ページ管理情報
４２タプルデータ
６１テーブル不要領域情報記憶部
２１１クエリ解析部
２１２実行計画作成部
２２１トランザクション制御管理部
２３１インデックス管理部
２３２ページ管理部
２３３タプル管理部
２３４空き容量管理部
２３５統計情報管理部
４２１、４２３、４２４有効タプルデータ
４２２、４２５削除可能タプルデータ
５２１、５２２有効タプルデータ

Claims

データを記憶するデータベースを管理する追記型データベース管理システムにおいて、
前記データを更新又は削除することにより前記データベース内に生じる不要領域を、当該データベースの記録単位であるページ毎に更新しながら管理する管理手段と、
前記管理手段が前記ページ毎に管理する前記不要領域から当該不要領域のサイズを算出すると共に、当該不要領域のサイズと、前記データベース内における当該不要領域の位置とを、前記ページ毎に記憶する不要領域記憶手段と、
前記ページに前記不要領域が発生した場合に、前記不要領域記憶手段に記憶された前記不要領域のサイズと、当該ページにおける前記不要領域の比率に基づいて、当該不要領域に属するデータを解放するか否かを判断する不要領域比率判断手段と、を備え、
前記不要領域比率判断手段は、
前記不要領域のサイズと、前記ページにおける前記不要領域の比率とに基づいて、予め設定された閾値を超えた場合には、当該ページの前記不要領域に属するデータを前記不要領域の位置から解放する不要領域解放処理手段
を更に備えることを特徴とする追記型データベース管理システム。
前記不要領域解放処理手段は、
前記ページの前記不要領域に属するデータの実行ログであるトランザクション識別子と、システムの実行ログとして一番古く関わった最古トランザクションとを比較して、当該不要領域に属するデータが削除可能なタプルデータか否かを判断するタプルデータ有効性判断手段と、
前記タプルデータ有効性判断手段により、前記トランザクション識別子が前記最古トランザクション識別子より古い場合には、前記不要領域に属するデータは、前記削除可能なタプルデータと判断されると共に、当該削除可能なタプルデータに対し削除予約を行うタプルデータ削除予約手段と、
前記タプルデータ削除予約手段により、前記削除可能なタプルデータがある場合には、当該削除可能なタプルデータに割り当てられたインデックスデータの有無を判断するインデックスデータ判断手段と、
前記インデックス判断手段により、前記削除可能なタプルデータに割り当てられた前記インデックスデータが有った場合には、当該インデックスデータを削除するインデックスデータ削除手段と、を備え、
前記インデックス判断手段は、前記インデックスデータ削除手段によって前記インデックスデータが無くなった場合又は前記インデックスデータが前記削除可能なタプルデータに無かった場合には、当該削除可能なタプルデータを解放して空き領域を確保する
ことを特徴とする請求項１記載の追記型データベース管理システム。
前記管理手段が前記ページを更新することにより、前記データベースに記憶された前記データを更新する場合であって、
更新により前記データベースに新たに追記するタプルデータのレコードを、追記タプルデータ長として算出するタプル長算出手段、を更に備え、
前記タプル長算出手段によって前記追記タプルデータ長が算出されることにより、確保された前記空き領域に、当該追記タプルデータ長の前記タプルデータのレコードを挿入可能な場合には、当該空き領域に挿入すると共に、挿入された当該タプルデータの前記ページを更新し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの最終ページに当該タプルデータ長の前記タプルデータを挿入できる場合には、当該最終ページに挿入し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの前記最終ページに前記タプルデータ長の前記タプルデータを挿入できない場合には、前記データベースに新規ページを確保して、当該タプルデータ長の前記タプルデータを追記する
ことを特徴とする請求項２記載の追記型データベース管理システム。
前記管理手段が、前記データベース内に生じる前記不要領域を、前記データのテーブル毎に合計しながら管理するテーブル合計管理手段と、
前記テーブル合計管理手段が、当該テーブル毎の前記不要領域のサイズを更新しながら記憶するテーブル不要領域記憶手段と、を更に備え、
前記テーブル合計管理手段は、
前記テーブル毎の前記不要領域のサイズと、前記テーブルにおける前記不要領域の比率とに基づいて、前記不要領域解放処理手段を開始する開始閾値、又は前記不要領域解放処理手段を終了する終了閾値の少なくとも一方を備えると共に、
前記開始閾値又は前記終了閾値によって前記不要領域解放処理手段を制御する
ことを特徴とする請求項１記載の追記型データベース管理システム。
前記不要領域比率判断手段は、
前記ページに前記不要領域が発生した場合であって、前記予め設定された閾値を超えた場合には、前記不要領域解放処理手段を実施するための予約を行う不要領域解放処理予約手段を更に備え、
前記不要領域解放処理予約手段は、
前記データベースの処理負荷に基づいて、前記不要領域解放処理手段を制御する
ことを特徴とする請求項１記載の追記型データベース管理システム。
データを記憶するデータベースを管理する追記型データベース管理システムにおける不要領域修復処理方法であって、
前記データを更新又は削除することにより前記データベース内に生じる不要領域を、当該データベースの記録単位であるページ毎に更新しながら管理する管理ステップと、
前記管理ステップにおいて前記ページ毎に管理する前記不要領域から当該不要領域のサイズを算出すると共に、当該不要領域のサイズと、前記データベース内における当該不要領域の位置とを、前記ページ毎に記憶する不要領域記憶ステップと、
前記ページに前記不要領域が発生した場合に、前記不要領域記憶ステップに記憶された前記不要領域のサイズと、当該ページにおける前記不要領域の比率に基づいて、当該不要領域に属するデータを解放するか否かを判断する不要領域比率判断ステップと、を備え、
前記不要領域比率判断ステップは、
前記不要領域のサイズと、前記ページにおける前記不要領域の比率とに基づいて、予め設定された閾値を超えた場合には、当該ページの前記不要領域に属するデータを前記不要領域の位置から解放する不要領域解放処理ステップ
を更に備えることを特徴とする不要領域修復処理方法。
前記不要領域解放処理ステップは、
前記ページの前記不要領域に属するデータの実行ログであるトランザクション識別子と、システムの実行ログとして一番古く関わった最古トランザクションとを比較して、当該不要領域に属するデータが削除可能なタプルデータか否かを判断するタプルデータ有効性判断ステップと、
前記タプルデータ有効性判断ステップにより、前記トランザクション識別子が前記最古トランザクション識別子より古い場合には、前記不要領域に属するデータは、前記削除可能なタプルデータと判断されると共に、当該削除可能なタプルデータに対し削除予約を行うタプルデータ削除予約ステップと、
前記タプルデータ削除予約ステップにより、前記削除可能なタプルデータがある場合には、当該削除可能なタプルデータに割り当てられたインデックスデータの有無を判断するインデックスデータ判断ステップと、
前記インデックス判断ステップにより、前記削除可能なタプルデータに割り当てられた前記インデックスデータが有った場合には、当該インデックスデータを削除するインデックスデータ削除ステップと、を備え、
前記インデックス判断ステップは、前記インデックスデータ削除ステップによって前記インデックスデータが無くなった場合又は前記インデックスデータが前記削除可能なタプルデータに無かった場合には、当該削除可能なタプルデータを解放して空き領域を確保する
ことを特徴とする請求項６記載の不要領域修復処理方法。
前記管理ステップが前記ページを更新することにより、前記データベースに記憶された前記データを更新する場合であって、
更新により前記データベースに新たに追記するタプルデータのレコードを、追記タプルデータ長として算出するタプル長算出ステップ、を更に備え、
前記タプル長算出ステップによって前記追記タプルデータ長が算出されることにより、確保された前記空き領域に、当該追記タプルデータ長の前記タプルデータのレコードを挿入可能な場合には、当該空き領域に挿入すると共に、挿入された当該タプルデータの前記ページを更新し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの最終ページに当該タプルデータ長の前記タプルデータを挿入できる場合には、当該最終ページに挿入し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの前記最終ページに前記タプルデータ長の前記タプルデータを挿入できない場合には、前記データベースに新規ページを確保して、当該タプルデータ長の前記タプルデータを追記する
ことを特徴とする請求項７記載の不要領域修復処理方法。
前記管理ステップが、前記データベース内に生じる前記不要領域を、前記データのテーブル毎に合計しながら管理するテーブル合計管理ステップと、
前記テーブル合計管理ステップが、当該テーブル毎の前記不要領域のサイズを更新しながら記憶するテーブル不要領域記憶ステップと、を更に備え、
前記テーブル合計管理ステップは、
前記テーブル毎の前記不要領域のサイズと、前記テーブルにおける前記不要領域の比率とに基づいて、前記不要領域解放処理ステップを開始する開始閾値、又は前記不要領域解放処理ステップを終了する終了閾値の少なくとも一方を備えると共に、
前記開始閾値又は前記終了閾値によって前記不要領域解放処理ステップを制御する
ことを特徴とする請求項６記載の不要領域修復処理方法。
前記不要領域比率判断ステップは、
前記ページに前記不要領域が発生した場合であって、前記予め設定された閾値を超えた場合には、前記不要領域解放処理ステップを実施するための予約を行う不要領域解放処理予約ステップを更に備え、
前記不要領域解放処理予約ステップは、
前記データベースの処理負荷に基づいて、前記不要領域解放処理ステップを制御する
ことを特徴とする請求項６記載の不要領域修復処理方法。
データを記憶するデータベースを管理する追記型データベース管理システムにおける不要領域修復プログラムであって、
前記データを更新又は削除することにより前記データベース内に生じる不要領域を、当該データベースの記録単位であるページ毎に更新しながら管理する管理手順と、
前記管理手順が前記ページ毎に管理する前記不要領域から当該不要領域のサイズを算出すると共に、当該不要領域のサイズと、前記データベース内における当該不要領域の位置とを、前記ページ毎に記憶する不要領域記憶手順と、
前記ページに前記不要領域が発生した場合に、前記不要領域記憶手順に記憶された前記不要領域のサイズと、当該ページにおける前記不要領域の比率に基づいて、当該不要領域に属するデータを解放するか否かを判断する不要領域比率判断手順と、を備え、
前記不要領域比率判断手順は、
前記不要領域のサイズと、前記ページにおける前記不要領域の比率とに基づいて、予め設定された閾値を超えた場合には、当該ページの前記不要領域に属するデータを前記不要領域の位置から解放する不要領域解放処理手順を更に備え、
コンピュータに実行させることを特徴とする不要領域修復プログラム。
前記不要領域解放処理手順は、
前記ページの前記不要領域に属するデータの実行ログであるトランザクション識別子と、システムの実行ログとして一番古く関わった最古トランザクションとを比較して、当該不要領域に属するデータが削除可能なタプルデータか否かを判断するタプルデータ有効性判断手順と、
前記タプルデータ有効性判断手順により、前記トランザクション識別子が前記最古トランザクション識別子より古い場合には、前記不要領域に属するデータは、前記削除可能なタプルデータと判断されると共に、当該削除可能なタプルデータに対し削除予約を行うタプルデータ削除予約手順と、
前記タプルデータ削除予約手順により、前記削除可能なタプルデータがある場合には、当該削除可能なタプルデータに割り当てられたインデックスデータの有無を判断するインデックスデータ判断手順と、
前記インデックス判断手順により、前記削除可能なタプルデータに割り当てられた前記インデックスデータが有った場合には、当該インデックスデータを削除するインデックスデータ削除手順と、を備え、
前記インデックス判断手順は、前記インデックスデータ削除手順によって前記インデックスデータが無くなった場合又は前記インデックスデータが前記削除可能なタプルデータに無かった場合には、当該削除可能なタプルデータを解放して空き領域を確保する
ことをコンピュータに実行させることを特徴とする請求項１１記載の不要領域修復プログラム。
前記管理手順が前記ページを更新することにより、前記データベースに記憶された前記データを更新する場合であって、
更新により前記データベースに新たに追記するタプルデータのレコードを、追記タプルデータ長として算出するタプル長算出手順、を更に備え、
前記タプル長算出手順によって前記追記タプルデータ長が算出されることにより、確保された前記空き領域に、当該追記タプルデータ長の前記タプルデータのレコードを挿入可能な場合には、当該空き領域に挿入すると共に、挿入された当該タプルデータの前記ページを更新し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの最終ページに当該タプルデータ長の前記タプルデータを挿入できる場合には、当該最終ページに挿入し、
算出された前記タプルデータ長の前記タプルデータが前記空き領域に挿入できない場合であって、前記データベースの前記最終ページに前記タプルデータ長の前記タプルデータを挿入できない場合には、前記データベースに新規ページを確保して、当該タプルデータ長の前記タプルデータを追記する
ことをコンピュータに実行させることを特徴とする請求項１２記載の不要領域修復プログラム。
前記管理手順が、前記データベース内に生じる前記不要領域を、前記データのテーブル毎に合計しながら管理するテーブル合計管理手順と、
前記テーブル合計管理手順が、当該テーブル毎の前記不要領域のサイズを更新しながら記憶するテーブル不要領域記憶手順と、を更に備え、
前記テーブル合計管理手順は、
前記テーブル毎の前記不要領域のサイズと、前記テーブルにおける前記不要領域の比率とに基づいて、前記不要領域解放処理手順を開始する開始閾値、又は前記不要領域解放処理手順を終了する終了閾値の少なくとも一方を備えると共に、
前記開始閾値又は前記終了閾値によって前記不要領域解放処理手順を制御する
ことをコンピュータに実行させることを特徴とする請求項１１記載の不要領域修復プログラム。
前記不要領域比率判断手順は、
前記ページに前記不要領域が発生した場合であって、前記予め設定された閾値を超えた場合には、前記不要領域解放処理手順を実施するための予約を行う不要領域解放処理予約手順を更に備え、
前記不要領域解放処理予約手順は、
前記データベースの処理負荷に基づいて、前記不要領域解放処理手順を制御する
ことをコンピュータに実行させることを特徴とする請求項１１記載の不要領域修復プログラム。