JPH0776935B2 - レコード格納方式 - Google Patents

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は２次記憶装置と複数のプロセッサを備えた並列
処理装置における上記２次記憶装置へのレコード格納方
式に関する。

（従来の技術） データベースを初めとする多くの情報処理システムで
は、一般的に種々の情報をレコードとして２次記憶装置
に格納することが行なわれる。しかして２次記憶装置は
そのデータ入出力を、或る一定長のデータを単位として
行なうように構成されている。この為、２次記憶装置に
種々の大きさのレコードをそれぞれ１つずつ個別に格納
することはできない。

そこで従来では、種々の大きさのレコードを２次記憶装
置に格納する場合、ページと称される或る一定長のレコ
ード領域を定義し、このページを単位として種々の大き
さの情報（レコード）を２次記憶装置に格納することが
行われている。

即ち、第５図に示すように、例えば２次記憶装置に格納
しようとする種々のレコードの中で最大の大きさを持つ
レコードが１ページに納まるように定められたページ
に、１つまたは複数のレコードをそのページ長を越えな
い範囲でまとめて格納するようにしている。この際、そ
のページの例えば先頭部に設定された管理領域には、そ
のページに格納されたレコードの数やそのページ数等の
情報が格納される。第５図に示す例ではそのページに
［ｎ］個のレコードが格納され、ページ数が［１］であ
ることを示す情報が格納される。

ところが２次記憶装置のデータ入出力特性等から、その
ページ長をレコードの最大長に合わせて設定するにも限
度がある。つまり２次記憶装置に対して設定されるペー
ジの大きさ（ページ長）には自ずと制約がある。この
為、往々にしてページ長を越えるレコードが出現するこ
とが否めない。

このような場合、従来一般的には、例えば第６図に示す
ように連続した複数のページを用い、ページ長より大き
いレコードをこれらの複数のページに連続的に分散させ
て格納することが行われる。この第６図に示す例ではｍ
個の連続したページを用いて１つのレコードをその１番
目のページから順に連続的に格納される。尚、この場合
には、１番目のページの先頭部に設定された管理領域に
［１］個のレコードが格納され、その使用ページ数が
［ｍ］であることを示す情報が格納される。

このようにして連続した複数ページに亘って１つのレコ
ードを格納した第６図に示すようなページが『非完結ペ
ージ』と称される。これに対して前述した第５図に示す
ように、１つのページに格納できる範囲内で１個以上の
レコードを詰め込んだページが『完結ページ』と称され
る。

ところで情報処理の技術分野では複数台のプロセッサを
備えた並列処理装置の開発が種々進められ、機能分散し
た並列処理により効率的に、且つ高速度にその情報処理
を実行することが行われている。データベース処理の技
術分野でもこの種の並列処理の導入が試みられ、種々の
方式が提案されている。

さてデータベース処理における最も基本的な処理は「２
次記憶装置に格納されている複数のレコードのうち、或
る検索条件を満たすレコードを選択的に取出す」と云う
処理である。

このような検索処理を複数のプロセッサを備え並列処理
装置にて実現する場合には、基本的には、例えば「各
プロセッサは他のプロセッサとの間で何等かの手段を用
いて同期をとり、２次記憶装置における処理対象の各ペ
ージについて、それを処理するプロセッサを決める。
その上で選択決定されたプロセッサでは、該当するペー
ジを２次記憶装置から当該プロセッサの主記憶装置に読
み出し、その中に詰められているレコードについて与え
られた検索条件を満たすかどうか調べる。」と云う処理
手続きが行われることになる。

このような処理手続きは、複数のプロセッサそれぞれ
に、例えば第７図に示すようなプログラムを実行させる
ことにより実現される。但し、第７図に示すプログラム
中のwait（Ｓ）とsignal（Ｓ）は、その間の処理を実行
するプロセッサが高々１つであることを保証する為の手
段である。即ち、このプログラムでは、例えば或るプロ
セッサＡがwait（Ｓ）を実行する時，仮にwait（Ｓ）か
らsignal（Ｓ）までの部分を実行している別のプロセッ
サＢがあれば、上記プロセッサＡはプロセッサＢがsign
al（Ｓ）を実行するまでwait（Ｓ）から先に進めないよ
うになっている。

尚、このような排他処理機能については下記の文献等に
詳しく紹介される。

『ブリンクハンセン著，田中穂積他訳“オペレーティン
グシステムの原理”近代科学社刊』 ところが通常の並列処理装置の場合、第７図に示すプロ
グラムのwait（Ｓ）からsignal（Ｓ）までの処理に要す
る時間は、２次記憶装置から主記憶装置に対して第Ｐペ
ージの読み出し［read（Ｐ）］に要する時間，および主
記憶装置に読出した第Ｐページに対する検索条件判定処
理に要する時間の［数百〜数万分の１］である。これ
故、上記プログラムのwait（Ｓ）からsignal（Ｓ）まで
の処理時間については、その間には高々１台のプロセッ
サでしか処理の実行できないとしても、さほど問題とな
ることはない。

然し乍ら、２次記憶装置から主記憶装置に対して読み出
されるページに前述した非完結ページが含まれている場
合、第７図に示すプログラムでは不具合が生じる。即
ち、ページの大きさを超えるレコードを格納した連続ペ
ージ（非完結ページ）の処理は１台のプロセッサで行な
う必要があるにも拘らず、第７図に示すプログラムでは
そのことが全く考慮されていない。この為、上記連続ペ
ージ（非完結ページ）に格納されたレコードがそのペー
ジ毎に異なるプロセッサの主記憶装置にそれぞれ読み出
されてしまう虞れがある。

そこでこのような非完結ページが含まれるレコードを２
次記憶装置から読み出す場合には、各プロセッサにおい
ては、例えば第８図に示すようなプログラムがそれぞれ
実行される。

このプログラムwait（Ｓ）とsignal（Ｓ）との間で、２
次記憶装置から主記憶装置への第Ｐページの読み出し
［read（Ｐ）］を行ない、その上で読出したページにつ
いて前述した管理領域に記述されている情報からその連
結ページ数を求め、読み出しページＰをその数（連結ペ
ージ数）だけ進めるように構成されている。そしてこの
処理が終了した後に前述したsignal（Ｓ）を実行するよ
うになっている。

従ってこのような対策を施した第８図に示すプログラム
では、wait（Ｓ）とsignal（Ｓ）との間の処理に要する
時間が、それ以外の処理に要する時間と略同程度になる
ことが否めない。その結果、プロセッサ台数を増やして
並列処理を実行するようにしても、その全体的な処理時
間をさほど短縮することができないという問題が生じ
る。

（発明が解決しようとする課題） このように従来のレコード格納方式は、基本的には１台
のプロセッサによる処理を念頭に開発されており、非完
結ページを含むコードを２次記憶装置に格納する場合、
その連結ページ数を当該ページの、例えば先頭部に設定
された管理領域に記録して管理するものとなっている。
しかしこのようにしてレコードを格納する方式では、そ
の連結ページ数を知る為には、そのページを２次記憶装
置から主記憶装置に一々読み出す必要がある。これ故、
並列処理を行うには前述した第８図に示すプログラムの
ように連結ページ数を調べて非完結ページのレコードを
連続的に読み出す必要があり、プロセッサの台数を増や
しても処理時間の短縮をさほど見込むことができないと
云う問題があった。つまり連結ページ数を調べる処理に
時間が掛かる為、並列処理の多重度が上がらないという
問題があった。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、非連結ページを含むレコードを
２次記憶装置から複数のプロセッサの主記憶装置に選択
的に読み出す際、各ページについての連結ページ数を調
べる為の処理を高速化し、複数のプロセッサを用いた並
列処理の多重度を高めて全体的な処理時間の短縮化を図
ることのできる実用性の高いレコード格納方式を提供す
ることにある。

［発明の構成］ （課題を解決するための手段） 本発明に係るレコード格納方式は、２次記憶装置とそれ
ぞれが主記憶装置を具備する複数のプロセッサとを備
え、上記２次記憶装置に一定長のページを単位として格
納された種々の大きさのレコードを前記プロセッサに選
択的に読み出して並列処理する並列処理装置のレコード
格納方式において、ページ長を越えない１つまたは複数
のレコードはそのページ長を越えない範囲でまとめて１
ページとし、ページ長を越えるレコードについては連続
する複数のページに分けて、当該レコードを前記２次記
憶装置中に格納するレコード格納手段と、このレコード
格納手段がレコードを格納する際、各ページについての
連結ページ数の情報を、前記２次記憶装置中の上記各ペ
ージの格納領域とは別に設定された格納領域に格納する
連結ページ数情報格納手段と、前記２次記憶装置に格納
されたレコードを前記複数のプロセッサがそれぞれ読み
出す際に各プロセッサは前記連結ページ数情報格納手段
によって格納された連結ページ数情報を排他的に当該各
プロセッサの主記憶装置に読み出す読み出し手段と、こ
の読み出し手段が読み出した連結ページ数情報を参照し
て当該プロセッサが読み出すページを決定する読み出し
ページ決定手段とを有することを特徴とするものであ
る。

（作 用） 本発明によれば、各ページについての連結ページ数の情
報が、当該ページの格納領域とは別の格納領域、例えば
２次記憶装置或いは他のプロセッサの主記憶装置に格納
されているので、一定長のページを単位として２次記憶
装置に格納された種々の大きさのレコードを複数のプロ
セッサの中の１つに選択的に読み出す際、上記連結ペー
ジ数情報を格納した別領域から連結ページ数情報を排他
的に当該プロセッサの主記憶装置に読み出し、この読み
出した連結ページ数情報を参照して当該プロセッサが読
み出すページ、例えばレコード単位の複数のページを決
定し読み出しを行う。これにより、従来のように各ペー
ジについての連結ページ数を調べるべく、その都度、当
該ページを２次記憶装置から主記憶装置に読み出す必要
がなくなる。

この結果、連結ページ数を調べる為の処理が非常に単純
化され、その処理速度を高速化することが可能となり、
全体的な処理時間の短縮化を図ることが可能となる。

（実施例） 以下、図面を参照して本発明の一実施例に係るレコード
格納方式について説明する。

この実施例方式は、２次記憶装置と複数のプロセッサと
を備え、上記２次記憶装置に一定長のページを単位とし
て格納された種々の大きさのレコードを前記複数のプロ
セッサの中の１つに選択的に読み出しながら複数のプロ
セッサにて並列処理するように構成された並列処理装置
に適用されるものである。

この実施例方式は、一定長のページを単位とし、ページ
長を超えない１つまたは複数のレコードをそのページ長
を超えない範囲でまとめて１ページに格納する（完結ペ
ージ）と共に、ページ長を超えるレコードについては連
続する複数のページに分けて格納する（非完結ページ）
に際し、例えば第１図にその概念を示すように、各ペー
ジ（完結ページａおよび非完結ページｂ）についての連
結ページ数ｃの情報を２次記憶装置中の別の領域に設定
されたファイルｄに格納するようにしたことを特徴とす
るものである。

尚、この第１図では第１ページ目が完結ページａ、第２
ページ目から第４ページ目までの連続する３ページが非
完結ページｂ、そして第５ページ目が完結ページａとな
っている。そしてこれらの各ページa,bの斜線部が、そ
のページにおける未使用領域をそれぞれ示している。し
かして各ページについての連結ページ数の情報を格納す
る別ファイルｄには、この例では前述した各ページに順
に対応して［1,3,0,0,1,〜］なる連結ページ数の情報が
それぞれ格納される。但し、連結ページ数の情報［０］
は、そのページが先のページに連結されていることを示
している。

しかしてこのようにして別ファイルｄに格納された連結
ページ数の情報を参照して各ページについての連結ペー
ジ数を調べ、各ページa,bのレコードを複数のプロセッ
サの中の１つに選択的に読み出して並列処理する為に
は、上記別ファイルｄの内容を各プロセッサの主記憶装
置上にそれぞれ読み出して各プロセッサが参照できるよ
うにする必要がある。つまり２次記憶装置からのページ
単位でのレコードの読み出しとは独立に、上記別ファイ
ルｄの内容を各プロセッサの主記憶装置にそれぞれ読み
出し、連結ページ数の情報を調べ得るようにすることが
必要となる。

第３図はこのような処理機能を含んで構成されたプログ
ラムの例を示すもので、各プロセッサはこのプログラム
をそれぞれ実行することで２次記憶装置から必要なペー
ジのレコードをそれぞれ読み出すことになる。

この第３図に示すプログラムについて説明すると、ここ
ではwait（Ｓ）とsignal（ｓ）との間でこれから処理し
ようとするページについての連結ページ数を調べる処理
が行われる。

尚、連結ページ数の情報を格納した別ファイルｄに該当
するページが既に主記憶装置上に読み出されている場合
には、それを参照するだけで良い。そうでない場合に
は、そのページに関する連結ページ数の情報を格納した
別ファイルｄに該当するページを主記憶装置上に読み出
す処理が行われる。

しかして通常の場合、レコードの記録単位をなすページ
の大きさは一般的には4096バイト程度に設定される。こ
れに対して各ページについての連結ページ数の値を格納
するのに必要な領域は、一般的には１ページ当り２バイ
ト程度で十分である。そしてページ単位での別ファイル
ｄからの連結ページ数の情報の読み出しが１回行われる
と、これによって2048ページ分の連結ページ数の情報が
求められることになる。そして読み出されたページに示
される範囲内での連結ページ数の情報を参照している限
りにおいては、新たに上記別ファイルｄからの連結ペー
ジ数の情報の読み出しは不要となる。

このようなことからこの実施例における第３図に示すプ
ログラムの場合には、wait（Ｓ）とsignal（ｓ）との間
で２次記憶装置から主記憶装置に対して連結ページ数の
情報を読み出す為の処理が行われる頻度は、確率論的に
2048回に１回の割合となり、その他の場合には既に読み
出されたファイルに示される連結ページ数の情報を用い
て読み出し対象とするページについての連結ページ数が
調べられることになる。

このことは従来の処理方式を示す第８図のプログラムで
は、wait（Ｓ）とsignal（ｓ）との間で２次記憶装置か
ら主記憶装置への読み出しを毎回必要としていたことに
比較してその読み出し処理の頻度を大幅に少なくし、そ
の処理性能の大幅な改善となることを意味する。そして
wait（Ｓ）とsignal（ｓ）との間での処理速度を高速化
し、全体的な処理時間の短縮化を図ることが可能とな
る。

尚、上述した実施例では各ページに関する連結ページ数
を別のファイルｄに格納するものとしているが、その他
の場所に格納するようにしても良い。

例えば本来のレコードを格納するファイルを第２図に例
示するようにツリー状とし、図中最右端のページｘに実
際のレコードを格納するようにする。そしてその１段左
のページｙに最右端の各ページｘについての２次記憶装
置中の格納場所と連結ページ数の情報をそれぞれ格納す
るようにしても良い。このようにした場合には、各ペー
ジについての連結ページ数を調べる際には、２次記憶装
置から主記憶装置に各ページｘについてデータを読み出
す必要がなく、上記ページｙに格納されているデータを
参照するだけで良いので、やはり大幅な性能改善が図る
ことが可能となる。

また別の例としては、連結ページ数の情報を、２次記憶
装置とは別個に複数のプロセッサの主記憶装置上にそれ
ぞれ格納しておくようにすることも可能である。即ち、
通常の連結ページ数の値を格納するのに必要な領域は２
バイト程度であり、元のページの大きさは前述したよう
に4096バイト程度である。従って連結ページ数の情報は
本来のファイルの大きさの［2048分の１］程度であり、
連結ページ数の情報を主記憶装置上に格納しても殆ど問
題はない。

尚、殆どのページが完結ページであり、極一部のページ
だけが非完結ページであるような場合には、個々のペー
ジ毎に連結ページ数を格納することに代えて、各ページ
が完結ページであるか否かの情報だけを元のページとは
別に保持するようにしても良い。このようにすれば、そ
の格納領域は非常に小さくすることが可能となる。また
このような場合には、例えば第４図に示すようなプログ
ラムを実行するようにすれば良い。このようなプログラ
ムによれば、wait（Ｓ）とsignal（Ｓ）との間の処理に
要する時間の平均値を従来の方式に比べてやはり大幅に
小さくすることができ、その処理性能を十分に高めるこ
とが可能となる。その他、本発明はその要旨を逸脱しな
い範囲で種々変形して実施することができる。

［発明の効果］ 以上説明したように本発明によれば、２次記憶装置と複
数のプロセッサを備えた並列処理装置において、各ペー
ジに対する連結ページ数の情報を、元のページとは別の
領域に格納してレコードの読み出しを制御するので、デ
ータベースで最も基本的な処理である「２次記憶装置に
格納されているレコードのうち，或る検索条件を満たす
ものを取出す」と云う処理を実行する際、ページ長を超
えるようなレコードが含まれる場合であってもプロセッ
サ台数に見合った処理性能の向上を図ることが可能とな
る等の実用上多大なる効果が奏せられる。

【図面の簡単な説明】 第１図は本発明の一実施例に係るレコード格納方式の概
念を模式的に示す図、第２図は本発明の別の実施例を示
すツリー状のレコード格納形態を模式的に示す図、第３
図および第４図はそれぞれ実施例方式を実現する上での
プロセッサにおける処理プログラムの例を示す図であ
る。 また第５図は２次記憶装置に格納される完結ページの例
を示す図、第６図は２次記憶装置に格納される非完結ペ
ージの例を示す図、第７図は完結ページに対する並列プ
ログラムの例を示す図、第８図は非完結ページを含む場
合の並列プログラムの例を示す図である。 ａ……完結ページ、ｂ……非完結ページ、ｃ……連結ペ
ージ数,d……別ファイル。

Claims (1)

【特許請求の範囲】
1. 【請求項１】２次記憶装置とそれぞれが主記憶装置を具
   備する複数のプロセッサとを備え、上記２次記憶装置に
   一定長のページを単位として格納された種々の大きさの
   レコードを前記プロセッサに選択的に読み出して並列処
   理する並列処理装置のレコード格納方式において、 ページ長を越えない１つまたは複数のレコードはそのペ
   ージ長を越えない範囲でまとめて１ページとし、ページ
   長を越えるレコードについては連続する複数のページに
   分けて、当該レコードを前記２次記憶装置中に格納する
   レコード格納手段と、 このレコード格納手段がレコードを格納する際、各ペー
   ジについての連結ページ数の情報を、前記２次記憶装置
   中の上記各ページの格納領域とは別に設定された格納領
   域に格納する連結ページ数情報格納手段と、 前記２次記憶装置に格納されたレコードを前記複数のプ
   ロセッサがそれぞれ読み出す際に各プロセッサは前記連
   結ページ数情報格納手段によって格納された連結ページ
   数情報を排他的に当該各プロセッサの主記憶装置に読み
   出す読み出し手段と、 この読み出し手段が読み出した連結ページ数情報を参照
   して当該プロセッサが読み出すページを決定する読み出
   しページ決定手段と を有することを特徴とするレコード格納方式。