JPH0695936A - バッファ管理方法 - Google Patents

Abstract

(57)【要約】 【目的】 トランザクションに固有のデータアクセスタ
イプを予め、あるいは、実行時に検出してバッファ置換
の優先度を決定して、優先度に基づくバッファの割当て
と置換を行うようにした優先度付きバッファ管理方法を
提供すること。 【構成】 インデックスを用いて表中の目的とする行を
検索あるいは更新するオンライントランザクションと、
表内の各行を逐次的に読み出して条件判定を行うこと
で、対象とする行を探索し検索あるいは更新するバッチ
トランザクションとを混在させて実行する際に、オンラ
イントランザクションとバッチトランザクションに固有
のアクセス特性を検出し、該検出したアクセス特性に基
づいてバッファリング時の優先度を決定することを特徴
とするバッファ管理方法。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ディスク装置等の２次
記憶装置に格納された関係データベースの表およびイン
デックス等を、高速かつ小容量の半導体メモリ等の１次
記憶装置にバッファリングして処理するデータ処理装置
におけるバッファ管理方法に関し、特に、トランザクシ
ョンのアクセス特性および該アクセス特性とトランザク
ションの実行優先度あるいは表やインデックス等のデー
タ属性の違いに基づいてバッファ管理の優先度を決定す
るようにした優先度付きバッファ管理方法に関する。

【０００２】

【従来の技術】データベースは、金融システム，チケッ
ト予約システム，在庫管理システム，人事管理システム
等、多くのビジネスアプリケーションで利用され、大規
模なデータベースシステムが実現されている。これらの
システムの大部分は、オンライントランザクションが更
新したデータベースに対して、バッチトランザクション
が統計処理を行い、販売戦略を作成するような使用方法
になっている。ここで、一般に、オンライントランザク
ションは、インデックスを活用して表(テーブル)の特定
の行(タプル)を検索・更新するのに対して、バッチトラ
ンザクションは、表全体のフルスキャンやジョイン等を
必要とし、処理時間が長大化する傾向にある。このた
め、従来のデータベース管理システム(ＤＢＭＳ)では、
オンライントランザクションとバッチトランザクション
を走行させる時間帯を分ける使い方(例えば、昼間はオ
ンライン、夜間はバッチ)をしていた。金融システムを
例にとると、個々の個人口座の預金残高は、預金・引出
し操作に伴ってオンラインで更新されなければならない
し、支店毎の総預金残高の変動は、日単位で集計されな
ければならない。

【０００３】上述の前者はオンライントランザクション
の典型例、後者はバッチトランザクションの典型例であ
り、従来は、オンラインが終了した夜間に、バッチを処
理していた。しかし、24時間サービスを提供する大規模
なネットワーク管理や、世界規模での取引を行うシステ
ムでは、１日24時間サービスを停止できないため、上述
の如き時間帯を分けた使い方が困難となり、統計処理等
を行うバッチトランザクションを、オンライントランザ
クションと並行して実行することが要求される。上述の
データベース管理システムが処理の対象とする表および
該表から生成したインデックスは、極めて大量のデータ
の集合であり、かつ、高い信頼性をもって永続的に格納
する必要があることから、磁気ディスク装置等の２次記
憶装置に格納される。また、磁気ディスク装置はアクセ
ス速度が遅いことから、一般に、データベース処理装置
では、磁気ディスク装置等に格納されたデータベースの
一部を、高速アクセスが可能な半導体記憶装置等の１次
記憶装置にバッファリングして処理している。

【０００４】図３は、バッファ管理機構を備えた、従来
のＤＢＭＳの構成例を示すものである。図中、１はオン
ライントランザクション、２はバッチトランザクショ
ン、３はデータベースの表やインデックス等を格納する
磁気ディスク装置、３１はデータベース管理システム
(ＤＢＭＳ)を示している。ここでは、ＤＢＭＳ３１は、
上述のオンライントランザクション１とバッチトランザ
クション２を矛盾なく実行するための実行制御部３２
と、磁気ディスク装置３に格納された表やインデックス
等のデータをバッファリングするバッファサブシステム
３３から構成されている。更に、バッファサブシステム
３３は、磁気ディスク３に格納されたデータを一時的に
保持するための半導体記憶装置３６と、該半導体記憶装
置３６が現在保持しているデータを管理するためのバッ
ファ管理表３５と、バッファの割当ておよび置換を制御
するバッファ制御部３４から構成されている。ＤＢＭＳ
３１に入力されたトランザクション１あるいは２は、実
行制御部３２が処理内容を解読して実行プランを作成
し、実行プランに従ってバッファサブシステム３３に必
要なデータの読み出しを要求する。また、データの更新
を伴うトランザクションであれば、読み出したデータを
更新し、あるいは、新規のデータの追加格納をバッファ
サブシステム３３に対して要求する。

【０００５】バッファサブシステム３３は、要求された
データが既に半導体記憶装置３６にバッファリングされ
ていればそのデータを、また、バッファリングされてい
なければ磁気ディスク装置３から半導体記憶装置３６の
空き領域に、要求されたデータを読み込んでそのデータ
を、実行制御部３２に返却する。その際、半導体記憶装
置３６に空き領域が存在しなければ、半導体記憶装置３
６にバッファリングされているいずれかのデータを追い
出して、空き領域を作成し、バッファを起換しなければ
ならない。従って、バッファ管理の課題は、ヒット率が
高いバッファの割当てと置換を実現することである。デ
ータベース処理装置における従来のバッファ管理方法
が、Ｗ.Ｅffelsberg and Ｔ.Ｈearder著"Ｐrinciples o
f Ｄatabase Ｂuffer Ｍanagement"，ＡＣＭ Ｔrans．o
n Ｄatabase Ｓystems，Ｖol.9,Ｎo.4，pp.560-595，Ｄ
ec．1984で整理されている。

【０００６】上記文献では、バッファの置換アルゴリズ
ムとして、ＦＩＦＯ(Ｆirst Ｉn Ｆirst Ｏut)，ＬＲＵ
(Ｌeast Ｒecentry Ｕsed)，ＬＦＵ(Ｌeast Ｆrequentl
y Ｕsed)等があることが示されている。これら従来の置
換アルゴリズムは、過去のアクセス経緯から、次にアク
セスされるであろうデータをできるだけ高い確率でバッ
ファに保持するように置換する方法で、バッファ管理部
内で得られる情報、例えば、アクセスの順序や頻度、デ
ータ属性を用いて制御していた。このため、バッファ管
理を独立したサブシステムとして構成できる特徴を持つ
が、オンライントランザクション１とバッチトランザク
ション２を混在実行する場合には、以下の如き問題が生
ずる。 (１)バッチ処理でスキャンが完了したページは、その後
使用される可能性が低いにもかかわらず、ＬＲＵでは、
バッファ内に高い確率で存在してしまうこと。 (２)バッチで生成される中間結果は、頻繁に利用される
データではないので、ＦＩＦＯ，ＬＦＵアルゴリズムで
は、早い段階でバッファから追い出されてしまうこと。

【０００７】

【発明が解決しようとする課題】上述の問題に対して
は、バッファ管理に優先度を導入する手法が、Ｍ.Ｊ.Ｃ
arey，Ｒ.Ｊauhari and Ｍ.Ｌivny著"Ｐriority in Ｄ
ＢＭＳ Ｒesource Ｓcheduling"，15th Ｉnt'l Ｃonf．
on Ｖery Ｖarge Ｄata Ｂases，Ａmsterdam，1989に示
されている。ここでは、リアルタイムデータベース処理
を対象として、トランザクションに与えられた実行優先
度をバッファ管理の優先度として継承する方法が示され
ている。バッファ管理部は、アクセス要求があったデー
タを、優先度毎にＬＲＵリストに登録して管理し、低い
優先度を先に追い出すようにバッファの置き換えを制御
することで、高い優先度で実行するトランザクションが
使用するデータが不用意に追い出されないようにしてい
る。しかしながら、オンライントランザクションとバッ
チトランザクション等の異なる種類のトランザクション
を混在して実行する際に、従来のバッファ管理方法を適
用したのでは、複数のオンラインユーザのためにバッフ
ァが細分化されて分割損が生ずるという問題や、バッチ
トランザクションに大量のバッファが割当てられてオン
ラインの性能が低下するという問題が生ずる。

【０００８】また、バッチトランザクションを混在実行
することによってオンライントランザクションが頻繁に
アクセスするページがバッファから追い出されると、オ
ンライントランザクションは再読み込みを行う必要が生
ずるために演算量が増大し、かつ、ディスクアクセス待
ちが生ずるために応答性能が低下するという問題も生ず
る。一方、トランザクションに与えられた実行優先度を
バッファ管理の優先度として継承することで、バッファ
の入れ替え順序にトランザクションの優先度を反映する
従来法を、オンライントランザクションとバッチトラン
ザクションを混在実行する場合に適用すると、オンライ
ンとバッチの２段階の優先度しか存在しないので、十分
な優先度分けができないという問題や、更に、高い優先
度のトランザクションが使用を完了して近い将来には使
用いないことが明らかなデータであっても、バッファか
ら追い出されないという問題が生ずる。本発明は上記事
情に鑑みてなされたもので、その目的とするところは、
従来の技術における上述の如き諸問題を解消し、トラン
ザクションに固有のデータアクセスタイプを予め、ある
いは、実行時に検出してバッファ置換の優先度を決定し
て、優先度に基づくバッファの割当てと置換を行うよう
にした優先度付きバッファ管理方法を提供することにあ
る。

【０００９】

【課題を解決するための手段】本発明の上述の目的は、
データベースの表および該表から作成したインデックス
を格納する２次記憶手段と、該２次記憶手段より高速ア
クセスが可能な１次記憶手段と、複数のトランザクショ
ンを矛盾なく実行するための実行制御手段とを有し、前
記２次記憶手段に格納された表およびインデックスの一
部分を前記１次記憶手段にバッファリングして処理する
データベース処理装置におけるバッファ管理方法であっ
て、前記インデックスを用いて前記表中の目的とする行
を検索あるいは更新するオンライントランザクション
と、前記表内の各行を逐次的に読み出して条件判定を行
うことで、対象とする行を探索し検索あるいは更新する
バッチトランザクションとを混在させて実行する際に、
前記オンライントランザクションとバッチトランザクシ
ョンに固有のアクセス特性を検出し、該検出したアクセ
ス特性に基づいてバッファリング時の優先度を決定する
ことを特徴とするバッファ管理方法によって達成され
る。

【００１０】

【作用】本発明に係る優先度付きバッファ管理方法にお
いては、上記実行制御手段が、トランザクションの実行
プランを作成することから、バッファサブシステムに対
するデータアクセスの順序と、一旦、アクセスしたデー
タが近い将来にデータベース管理システム内で処理して
いる自トランザクションあるいは他のトランザクション
によって使用される可能性を容易に検出することができ
る。例えば、オンライントランザクションが使用したイ
ンデックスデータであれば、他のオンライントランザク
ションによって近い将来に使用される確率が高い。一
方、バッチトランザクションが条件検索でスキャンした
表データは、少なくとも、自トランザクションが使用す
ることはないし、他のトランザクションが使用する確率
も低いと言える。これに対して、バッチトランザクショ
ンが検索した結果を一時表としてバッファに格納する中
間結果データは、自トランザクション内の後続する処理
で必ず１回は使用されると言える。また、ジュイン等の
ために生成した中間結果も、近い将来に必ず再使用され
ることが保証できる。上述の如く、実行制御手段におい
て、各トランザクションのアクセス特性を検出すること
は極めて容易であり、簡単な回路でアクセス特性検出手
段を実現できる。そこで、このアクセス特性検出手段で
検出したアクセス特性に基づいてバッファ管理の優先度
を判定し、アクセス特性検出手段で近い将来高い確率で
使用されると判断したインデックスやある種の中間結果
には高い優先度を割当て、そうでない場合は低い優先度
を割当てて、バッファ管理を行う。すなわち、バッファ
リングされたデータを低い優先度のデータほど先に追い
出すようにバッファを制御することで、バッファの利用
効率を向上させることができる。

【００１１】

【実施例】以下、本発明の実施例を図面に基づいて詳細
に説明する。図１は、本発明の一実施例に係るデータベ
ース管理システム(ＤＢＭＳ)の構成図である。図中の記
号１〜３は、図３に示したと同じ構成要素を示してお
り、また、１１はＤＢＭＳを示している。ＤＢＭＳ１１
は、前述のオンライントランザクション１とバッチトラ
ンザクション２を矛盾なく実行するための実行制御部１
２と、磁気ディスク装置３に格納された表やインデック
ス等のデータをバッファリングするためのバッファサブ
システム１４とから構成されている。実行制御部１２
は、ＤＢＭＳ１１に入力されたトランザクションの処理
内容を解読して実行プランを作成し、該実行プランに従
ってバッファサブシステム１４に必要なデータの読み出
しを要求すると同時に、アクセス特性判定部１３におい
て、バッファサブシステム１４に要求するデータのアク
セス順序および再利用の可能性に基づいてアクセスの優
先度を判定する。

【００１２】バッファサブシステム１４は、磁気ディス
ク装置３に格納されたデータを一時的に保持する半導体
記憶装置１８と、該半導体記憶装置１８が現在保持して
いるデータを管理するバッファ管理表１６と、該データ
の属性を判定するデータ属性判定部１７と、該データ属
性判定部１７で得られたデータ属性に基づく優先度と上
述のアクセス特性判定部１３で得られたアクセス特性に
基づく優先度とから、バッファ管理の優先度を決定し、
該優先度に基づいてバッファの割当ておよび入れ替えを
行う優先度制御部１５から構成されている。図２は、図
１に示した実施例におけるバッファ管理の手順を説明す
る動作フロー図である。以下、両図に基づいて、実施例
の動作を説明する。 ステップ21：ＤＢＭＳ１１に入力されたオンライントラ
ンザクション１およびバッチトランザクション２の処理
内容を、実行制御部１２において解読し、実行プランを
作成する。 ステップ22：作成した実行プランに従って、バッファサ
ブシステム１４に必要なデータの読み出しを要求する。
また、データを更新する場合には、更新の対象とするデ
ータの読み出し、あるいは、新規データの追加格納をバ
ッファサブシステムに要求する。

【００１３】ステップ23：バッファサブシステム１４
は、要求されたデータが既に半導体記憶装置１８にバッ
ファリングされているか否かを判定する。バッファリン
グされていれば、該データを使用して後述するデータベ
ース処理を行う。バッファリングされていない場合に
は、次のデータ読み込み操作に移る。 ステップ24：半導体記憶装置１８上に実現したバッファ
に、未使用領域が存在するか否かを判定する。未使用領
域が存在すれば、ステップ26のデータ読み込み操作を行
い、未使用領域が存在しなければ、次のバッファ入れ替
え操作に移る。 ステップ25：バッファがすべて使用され、余裕がない場
合には、バッファリングしているデータのいずれかを追
い出して空き領域を作成する。このとき、バッファ管理
表１６を参照して、最も優先度が低く、しかも、最も最
近使用されていないデータを追い出す。従って、バッフ
ァ管理表１６には、バッファしている各データに対して
少なくとも優先度と使用された順序を判定するための情
報を登録しておく。このためのバッファ管理表１６は、
各優先度毎にＬＲＵリストを構成することで容易に実現
することができる。

【００１４】ステップ26：以上の操作によって、バッフ
ァ上には空き領域が存在するので、要求されたデータを
読み込む。同時に、読み込んだデータを識別するための
情報をバッファ管理表１６に登録する ステップ27：ここでは、バッファ管理の優先度を決定す
るステップ28の操作で使用する独立した優先度の値を求
める。 ステップ27-1：実行制御部１２はバッファリングされた
データのデータ属性を使用して、実行プランに基づく処
理を行う。その際、アクセス特性判定部１３において、
アクセス特性に基づく優先度を判定する。このとき、作
用の項に示した如く、オンライントランザクションとバ
ッチトランザクションはデータアクセスの順序や偏り等
のアクセス特性に応じて、一旦アクセスしたデータが再
利用される確率が明らかに異なることから、優先度を付
与することができる。 ステップ27-2：トランザクションに付与された優先度を
バッファ管理で使用する優先度に変換する。トランザク
ションを発行するユーザは、個々のトランザクションの
実行に際して、それぞれ、実行の優先度として期待する
値を設定するので、ユーザ間のばらつきを除き、実行優
先度を統一して割当てる操作を行う。すなわち、通常、
ＤＢＭＳを共用する複数のユーザ間には、ユーザ毎に操
作できる権限が制限されていたり、トランザクションを
発行する際の優先度が与えられている。ＤＢＭＳを維持
管理をしている管理者には多くの権限と高い実行優先度
が与えられており、初心者ユーザには、限られた権限と
低い実行優先度が与えられている。ここでは、このユー
ザ毎に与えられた実行優先度を、トランザクションの実
行に反映する役割を持つ。

【００１５】ステップ27-3：一方、バッファリングした
データ属性に基づいて、バッファ管理の優先度を決定す
る。一般に、(インデックスの容量)＜(表の容量)である
ことから、インデックスに高い優先度を付与することが
できる。更に、データベースの格納状況を管理するスキ
ーマ情報をバッファリングする場合や、構造を持つイン
デックスを細分化して個々のデータ項目に対して優先度
を割当てることもできる。優先度を付与する基本原則と
して、容量が小さく、多くのトランザクションから頻繁
にアクセスされるデータ属性ほど高い優先度を与えると
すると、バッファのヒット率を向上することができる。 ステップ28：上記ステップ27-1，27-2，27-3で決定した
アクセス特性に基づく優先度，トランザクションの実行
優先度に基づく優先度と、データ属性に基づく優先度を
統合してバッファ管理の優先度を決定する。当該データ
が既にバッファリングされている場合は、バッファ管理
表１６に所定の値が設定されているので、この設定され
ている値と上で求めた３種類の優先度とで新しい優先度
を決定して、バッファ管理表１６の優先度値を更新す
る。前述のステップ25のバッファ追い出しは、このバッ
ファ管理表１６に登録された優先度の値を使用して制御
する。

【００１６】なお、優先度を如何に統合するかによっ
て、ＤＢＭＳの性書が決定される。例えば、データ属性
に基づく優先度を重視するシステムは、従来法に示した
データ属性別管理法に類似したバッファ管理となる。一
般的には、トランザクションの実行優先度pＴ1,pＴ2,・・
・・、データ属性による優先度pＤ1,pＤ2,・・・・、アクセス
特性による優先度pＡ1,pＡ2,・・・・が与えられたとき、こ
れらの組み合わせが(pＴ1,pＤ1,pＡ1)＞(pＴ1,pＤ1,pＡ
2)＞・・・・＞(pＴ1,pＤ2,pＡ1)＞(pＴ1,pＤ2,pＡ2)＞・・・・
＞(pＴ2,pＤ1,pＡ1)＞(pＴ2,pＤ1,pＡ2)＞・・・・となるよ
うに、トランザクションの実行優先度を重視した統合が
考えられる。 ステップ29：以上のステップ22から28の操作を、トラン
ザクション処理が終了するまで繰り返す。

【００１７】上記実施例によれば、データアクセス特性
に基づいてバッファ管理の優先度を決定することによ
り、バッチトランザクションを実行することによってオ
ンライントランザクションが必要とするデータが不用意
に追い出されてしまうことを防止し、また、バッチトラ
ンザクションが生成する中間結果をデータベースのバッ
ファサブシステムを用いて保持することが可能になる。
これにより、例えば、指定された条件でデータベースを
検索して結果を１件ずつ返却するバッチトランザクショ
ンを、検索するプロセスと結果を返却するプロセスで処
理する場合に、２つのプロセス間で受け渡す検索結果を
バッファサブシステムを用いて保持することができるた
め、結果受け渡し専用に新たなバッファ機構を設ける必
要がなくなる利点がある。また、大量の中間結果を保持
しなければならない結合処理においても、バッファサブ
システムを用いてバケット毎にバッファリングの優先度
を制御できるために、少ないバッファ容量であっても、
有効に利用することができる。

【００１８】なお、上記実施例は本発明の一例を示した
ものであり、本発明はこれに限定されるべきものではな
いことは言うまでもないことである。例えば、上記実施
例においては、データアクセス特性とデータ属性に基づ
いてバッファ管理の優先度を決定する方法を説明した
が、データアクセス特性だけを用いてバッファ管理の優
先度を決定することもできる。更に、トランザクション
自体に実行優先度を指定できる場合、例えば、オンライ
ントランザクションはバッチトランザクションに優先し
て処理を実行するように設定された場合にも、データア
クセス特性に基づく優先度とトランザクションに与えら
れた優先度を統合した優先度を用いてバッファ管理を行
うこともできる。上述の説明では、バッファ管理表の構
成については詳細に説明しなかったが、一例として示し
た優先度別のＬＲＵリスト以外にも、アクセス頻度に基
づくＬＦＵリスト等他の構成であっても、優先度とアク
セスの順序関係を保持できれば、バッファ管理表の構成
に依存せずに実現することができる。また、オンライン
トランザクションとバッチトランザクションの混在実行
以外の場合であっても、種類が異なるトランザクション
を混在させて実行する場合であり、かつ、各トランザク
ションのアクセス特性が予め、あるいは、実行時に判別
できる場合は、本発明に係るアクセス特性を用いた優先
度付きバッファ管理方法を適用できる。

【００１９】

【発明の効果】以上、詳細に説明した如く、本発明によ
れば、トランザクションに固有のデータアクセスタイプ
を予め、あるいは、実行時に検出してバッファ置換の優
先度を決定して、優先度に基づくバッファの割当てと置
換を行うようにした優先度付きバッファ管理方法を実現
できるという顕著な効果を奏するものである。

【００２０】

【図面の簡単な説明】

【図１】本発明の一実施例に係るデータベース管理シス
テムの構成図である。

【図２】図１に示した実施例における、バッファ管理の
手順を説明する動作フロー図である。

【図３】従来のバッファ管理を用いたデータベース管理
システムの構成図である。

【符号の説明】

１：オンライントランザクション、２：バッチトランザ
クション、３：磁気ディスク装置、１１：ＤＢＭＳ、１
２：実行制御部、１３：アクセス特性判定部、１４：バ
ッファサブシステム、１５：優先度制御部、１６：バッ
ファ管理表、１７：データ属性判定部、１８：半導体記
憶装置。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 データベースの表および該表から作成し
   たインデックスを格納する２次記憶手段と、該２次記憶
   手段より高速アクセスが可能な１次記憶手段と、複数の
   トランザクションを矛盾なく実行するための実行制御手
   段とを有し、前記２次記憶手段に格納された表およびイ
   ンデックスの一部分を前記１次記憶手段にバッファリン
   グして処理するデータベース処理装置におけるバッファ
   管理方法であって、前記インデックスを用いて前記表中
   の目的とする行を検索あるいは更新するオンライントラ
   ンザクションと、前記表内の各行を逐次的に読み出して
   条件判定を行うことで、対象とする行を探索し検索ある
   いは更新するバッチトランザクションとを混在させて実
   行する際に、前記オンライントランザクションとバッチ
   トランザクションに固有のアクセス特性を検出し、該検
   出したアクセス特性に基づいてバッファリング時の優先
   度を決定することを特徴とするバッファ管理方法。
2. 【請求項２】 前記混在させて実行するオンライントラ
   ンザクションとバッチトランザクションの各々に対して
   実行時の優先度を指定し、該指定された実行優先度と前
   記アクセス特性とに基づいてバッファリング時の優先度
   を決定することを特徴とする請求項１記載のバッファ管
   理方法。
3. 【請求項３】 前記二次記憶装置に格納された表および
   インデックスのデータ属性と前記アクセス特性とに基づ
   いてバッファリング時の優先度を決定することを特徴と
   する請求項１または２記載のバッファ管理方法。