JPH0212461A - リレーシヨナル・データベース・システムの問合せ文処理方法 - Google Patents
リレーシヨナル・データベース・システムの問合せ文処理方法Info
- Publication number
- JPH0212461A JPH0212461A JP1085892A JP8589289A JPH0212461A JP H0212461 A JPH0212461 A JP H0212461A JP 1085892 A JP1085892 A JP 1085892A JP 8589289 A JP8589289 A JP 8589289A JP H0212461 A JPH0212461 A JP H0212461A
- Authority
- JP
- Japan
- Prior art keywords
- data
- sort
- sorted
- disk
- rds
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2453—Query optimisation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2455—Query execution
- G06F16/24553—Query execution of query operations
- G06F16/24554—Unary operations; Data partitioning operations
- G06F16/24556—Aggregation; Duplicate elimination
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2457—Query processing with adaptation to user needs
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99932—Access augmentation or optimizing
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99937—Sorting
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明は、コンピユータ化されたデータベースに関し、
さらに詳しくは、リレーショナル・データベースにおけ
るデータのソート方法に関する。
さらに詳しくは、リレーショナル・データベースにおけ
るデータのソート方法に関する。
Ｂ、従来技術及びその問題点
データベースは、将来のユーザからのリクエストに応じ
た検索のために、大量のデータをストアするのに使われ
る。ユーザは、アプリケーション・プログラムであるこ
ともあるし、人力デバイスを通じてデータベース・シス
テムとインターラクトするエンド・ユーザであってもよ
い。関連づけられたデータのグループは、普通にリレー
ショナル・データベースで使われているように、データ
・ファイルまたはテーブルと呼ばれる。テーブル中のデ
ータの行（ロー）は論理レコードと呼ばれ、データのカ
ラム（中間）はフィールドと呼ばれる。リレーショナル
・データベース・システムでは、ユーザは、データをテ
ーブルとしてのみ知覚し、その他の組織形態、たとえば
データの階層構造の形では知覚しない。
た検索のために、大量のデータをストアするのに使われ
る。ユーザは、アプリケーション・プログラムであるこ
ともあるし、人力デバイスを通じてデータベース・シス
テムとインターラクトするエンド・ユーザであってもよ
い。関連づけられたデータのグループは、普通にリレー
ショナル・データベースで使われているように、データ
・ファイルまたはテーブルと呼ばれる。テーブル中のデ
ータの行（ロー）は論理レコードと呼ばれ、データのカ
ラム（中間）はフィールドと呼ばれる。リレーショナル
・データベース・システムでは、ユーザは、データをテ
ーブルとしてのみ知覚し、その他の組織形態、たとえば
データの階層構造の形では知覚しない。
これらのデータベース・システムは、典型的な場合、デ
ータベース・マネジャーという、ユーザ・インターフェ
ースを介して入力される様々なコマンドに応答してデー
タを記憶・編集・更新・挿入・削除・検索するコンピュ
ータ・プログラムが含まれている。データベース・マネ
ジャーは、データベースに対するユーザからのすべての
リクエストを処理し、上記のような様々な機能を実行す
る。
ータベース・マネジャーという、ユーザ・インターフェ
ースを介して入力される様々なコマンドに応答してデー
タを記憶・編集・更新・挿入・削除・検索するコンピュ
ータ・プログラムが含まれている。データベース・マネ
ジャーは、データベースに対するユーザからのすべての
リクエストを処理し、上記のような様々な機能を実行す
る。
特に、データ検索に関しては、サーチ・コマンド、つま
りデータベース・マネジャーがそれに応答して要求デー
タを供給するところの”問合せ”を定式化するために、
多数のコンピュータ言語が考案されている。これらの問
合せは、基本的には、コンピュータ及び関連するデータ
ベース・マネジャーをして所望のサーチを実行させるべ
く符号化されたサーチ・インストラクションである。
りデータベース・マネジャーがそれに応答して要求デー
タを供給するところの”問合せ”を定式化するために、
多数のコンピュータ言語が考案されている。これらの問
合せは、基本的には、コンピュータ及び関連するデータ
ベース・マネジャーをして所望のサーチを実行させるべ
く符号化されたサーチ・インストラクションである。
データベースでの問合せを定式化するためのこれらの言
語には、いくつかの問題点がある。まず、問合せ言語の
多くが普通のプログラミング言語と異なっている。した
がって、ユーザにプログラミングの経験があっても、デ
ータベースから有意なデータを取り出すためだけに、全
く新しいコマンドのセットを学習しなければならなかっ
た。コンピュータ経験が全くないユーザ、例えば多くの
ターミナル・オペレータの場合には、データベースとイ
ンターラクトするためだけに、１種のコンピュータ・プ
ログラミングを学習しなければならなかった。さらに、
かかる問合せ言語は高度かつ複雑なシンタックス及びセ
マンテイクス・ルールを必要とするので、データを首尾
よく検索できる人間は、高度かつ高価な訓練をつんだ少
数の者に限られていた。このため、かかるコンピュータ
・システムのユーティリティに悪＃響が及び、広範な数
の人間による使用を不可能としていた。
語には、いくつかの問題点がある。まず、問合せ言語の
多くが普通のプログラミング言語と異なっている。した
がって、ユーザにプログラミングの経験があっても、デ
ータベースから有意なデータを取り出すためだけに、全
く新しいコマンドのセットを学習しなければならなかっ
た。コンピュータ経験が全くないユーザ、例えば多くの
ターミナル・オペレータの場合には、データベースとイ
ンターラクトするためだけに、１種のコンピュータ・プ
ログラミングを学習しなければならなかった。さらに、
かかる問合せ言語は高度かつ複雑なシンタックス及びセ
マンテイクス・ルールを必要とするので、データを首尾
よく検索できる人間は、高度かつ高価な訓練をつんだ少
数の者に限られていた。このため、かかるコンピュータ
・システムのユーティリティに悪＃響が及び、広範な数
の人間による使用を不可能としていた。
構造化問合せ言語（ＳＱＬ）は、エンド・ユーザが情報
を検索するべくデータベース・マネジャーとインターフ
ェースするにあたって利用されるインターラクテイブな
問合せ言語であり、かつデータベース・マネジャーを介
してデータベース中のデータにアクセスすべくアプリケ
ーション・プログラム中に埋め込むことのできるデータ
ベース・プログラミング言語である。ＳＱＬは、必要と
される情報のタイプを指定するための簡便な方法である
。
を検索するべくデータベース・マネジャーとインターフ
ェースするにあたって利用されるインターラクテイブな
問合せ言語であり、かつデータベース・マネジャーを介
してデータベース中のデータにアクセスすべくアプリケ
ーション・プログラム中に埋め込むことのできるデータ
ベース・プログラミング言語である。ＳＱＬは、必要と
される情報のタイプを指定するための簡便な方法である
。
かかる問合せ言語の代表は標準問合せ言語、つまり’Ｓ
ＱＬ”であり、その詳細は、ＡＮＡ Ｄａｔａｂａｓ
ｅ Ｌ ａｎｇｕａ８ｅ Ｓ Ｑ Ｌ 、 Ｓ ｔ
ａｎｄａｒｄ Ｘ ３ 。
ＱＬ”であり、その詳細は、ＡＮＡ Ｄａｔａｂａｓ
ｅ Ｌ ａｎｇｕａ８ｅ Ｓ Ｑ Ｌ 、 Ｓ ｔ
ａｎｄａｒｄ Ｘ ３ 。
１３５−１９８６、Ａ−ｍｅｒｉｃａｎ Ｎａｔｉｏ
ｎａｌ ５ｔａｎｄａｒｄ Ｉ ｎ５ｔｉｔｕｔｅ
刊に記述されている。ＳＱＬの詳細な説明は、” Ｉ
ＢＭ Ｄａｔａｂａｓｅ ２ ５ＱＬＲｅｆｅｒｅ
ｎｃｅ ”ドキュメント番号５Ｃ２６−４３４６−３、
ＩＢＭ社刊にても行われている。
ｎａｌ ５ｔａｎｄａｒｄ Ｉ ｎ５ｔｉｔｕｔｅ
刊に記述されている。ＳＱＬの詳細な説明は、” Ｉ
ＢＭ Ｄａｔａｂａｓｅ ２ ５ＱＬＲｅｆｅｒｅ
ｎｃｅ ”ドキュメント番号５Ｃ２６−４３４６−３、
ＩＢＭ社刊にても行われている。
リレーショナル・データベース・システムの大きな利点
は、ユーザの制御による陽の（ｅｘｐｌｉｃｉｔ ）操
作を実行する代りに、データベースがユーザから独立し
て入力を受は取り、もってデータ検索性能を向上させる
ことにある。ユーザは、データベースから検索したい情
報のタイプを指示するだけでよい。例えば、ユーザが２
つの異なるデータ・テーブルの情報を欲するとき、リレ
ーショナル・データベース・システムは、両方のテーブ
ルから最も効率よく情報を検索する方法を導き出す。
は、ユーザの制御による陽の（ｅｘｐｌｉｃｉｔ ）操
作を実行する代りに、データベースがユーザから独立し
て入力を受は取り、もってデータ検索性能を向上させる
ことにある。ユーザは、データベースから検索したい情
報のタイプを指示するだけでよい。例えば、ユーザが２
つの異なるデータ・テーブルの情報を欲するとき、リレ
ーショナル・データベース・システムは、両方のテーブ
ルから最も効率よく情報を検索する方法を導き出す。
リレーショナル・データベース・システムより前のデー
タベース・システムにあっては、プログラマが情報の検
索方法をコントロールしていた。
タベース・システムにあっては、プログラマが情報の検
索方法をコントロールしていた。
リレーショナル・データベース・システムでは、システ
ムが情報の検索方法を決定する。
ムが情報の検索方法を決定する。
多くのデータベース処理システムにおいて、ソート機能
（ファンクション〉はシステムの重要な一部である。デ
ータベース処理システムの計算能力の半分がソート・フ
ァンクションだけに用いられることさえあり得る。リレ
ーショナル・データベースでは、ユーザが出力をある順
番で並べたいときに、ユーザによってソート・コマンド
が利用される。また、システムがユーザのために能率よ
く情報を検索するためには、ソート・ファンクションが
必要であると判断した場合に、データベース・システム
によって用いられる、陰の（ｉｍｐｌ １ｃｉｔ ）ソ
ートというものもある。例えば、２つのテーブルを効率
よく結合したいときに、リレーショナル・データベース
・システムはソートを利用する。
（ファンクション〉はシステムの重要な一部である。デ
ータベース処理システムの計算能力の半分がソート・フ
ァンクションだけに用いられることさえあり得る。リレ
ーショナル・データベースでは、ユーザが出力をある順
番で並べたいときに、ユーザによってソート・コマンド
が利用される。また、システムがユーザのために能率よ
く情報を検索するためには、ソート・ファンクションが
必要であると判断した場合に、データベース・システム
によって用いられる、陰の（ｉｍｐｌ １ｃｉｔ ）ソ
ートというものもある。例えば、２つのテーブルを効率
よく結合したいときに、リレーショナル・データベース
・システムはソートを利用する。
ソート・ファンクションは、処理システムにおいて高価
なファンクションだと言える。なぜなら、ソート・コマ
ンドには比較（コンベア）命令が必要であり、比較命令
を実行するのに多くの処理時間が費やされるからである
。さらに加えて、多量のデータがソート対象となるとき
、データベース・システムは、ソートされつつあるデー
タの中間部分を、ディスクまたはハード・ファイルに書
き込むことになる。データのこの部分は、読み戻されて
、さらにソートされる。
なファンクションだと言える。なぜなら、ソート・コマ
ンドには比較（コンベア）命令が必要であり、比較命令
を実行するのに多くの処理時間が費やされるからである
。さらに加えて、多量のデータがソート対象となるとき
、データベース・システムは、ソートされつつあるデー
タの中間部分を、ディスクまたはハード・ファイルに書
き込むことになる。データのこの部分は、読み戻されて
、さらにソートされる。
ソート対象のすべてのデータがＣＰＵのメモリに一時に
ストアできるならば、Ｉ１０操作を伴う外部（エクスタ
ーナル）ソートは不要である。ソート対象のすべてのデ
ータがＣＰＵのメモリに一時にストアできないならば、
当該データの一部をストアし、結果をディスクにストア
し、さらにハード・ファイル上のソートされたデータの
一部をメモリに読み戻してデータの別の未ソート部分と
ともにソートすることになる。
ストアできるならば、Ｉ１０操作を伴う外部（エクスタ
ーナル）ソートは不要である。ソート対象のすべてのデ
ータがＣＰＵのメモリに一時にストアできないならば、
当該データの一部をストアし、結果をディスクにストア
し、さらにハード・ファイル上のソートされたデータの
一部をメモリに読み戻してデータの別の未ソート部分と
ともにソートすることになる。
書込及びファイルからの読戻しは、ソート操作の際に何
回も行われ得る。Ｉ１０操作を実行するのに費やされる
時間は、ソート操作の中で極めて高価なものとなり得る
。
回も行われ得る。Ｉ１０操作を実行するのに費やされる
時間は、ソート操作の中で極めて高価なものとなり得る
。
ソートの時間的性能は、いくつかの理由で、リレーショ
ナル・データベース・プロダクトの重要な競争尺度であ
る。第一に、ソート操作は、リレーショナル・データベ
ース・システムにおいて最も頻繁に使用される操作であ
る。第二に、ソート操作を利用する問合せのパフォーマ
ンスの向上は、問合せの結果待ち時間の短縮という形を
とるがゆえに、エンド・ユーザにとって知覚可能である
。
ナル・データベース・プロダクトの重要な競争尺度であ
る。第一に、ソート操作は、リレーショナル・データベ
ース・システムにおいて最も頻繁に使用される操作であ
る。第二に、ソート操作を利用する問合せのパフォーマ
ンスの向上は、問合せの結果待ち時間の短縮という形を
とるがゆえに、エンド・ユーザにとって知覚可能である
。
したがって、リレーショナル・データベースにおけるソ
ートのパフォーマンスは、データベース・プロダクトの
重要な競争ベンチ・マークとなる。
ートのパフォーマンスは、データベース・プロダクトの
重要な競争ベンチ・マークとなる。
リレーショナル・データベース及びＳＱＬ言語について
の詳細な説明は、Ｄａｔｅ、 Ｃ，Ｊ、 ＡｎＩ ｎｔ
ｒｏｄｕｃｔｉｏｎ ｔｏ Ｄ ａｔａｂａｓｅ
Ｓ ａｔｅｍｓ。
の詳細な説明は、Ｄａｔｅ、 Ｃ，Ｊ、 ＡｎＩ ｎｔ
ｒｏｄｕｃｔｉｏｎ ｔｏ Ｄ ａｔａｂａｓｅ
Ｓ ａｔｅｍｓ。
Ｔｈｅ Ｓｙｓｔｅｍｓ ＰｒｏｇｒａｍｍｉｎｇＳ
ｅｒｉｅｓ、 Ｖｏｌｕｍｅｌ、Ｆｏｕｒｔｈ Ｅｄ
ｉｔｉｏｎ、 Ａｄｄｉｓｏｎ −ＷｅｓｌｅｙＰｕｂ
ｌｉｓｈｉｎｇ Ｃｏｍｐａｎｙ、１９８６を参考に
されたい。
ｅｒｉｅｓ、 Ｖｏｌｕｍｅｌ、Ｆｏｕｒｔｈ Ｅｄ
ｉｔｉｏｎ、 Ａｄｄｉｓｏｎ −ＷｅｓｌｅｙＰｕｂ
ｌｉｓｈｉｎｇ Ｃｏｍｐａｎｙ、１９８６を参考に
されたい。
Ｃ１問題点を解決するための手段
したがって、本発明の目的は、リレーショナル・データ
ベースにおけるソート操作のパフォーマンスを向上させ
ることにある。
ベースにおけるソート操作のパフォーマンスを向上させ
ることにある。
大量のデータ、すなわちＣＰＵのメモリに一時にストア
できる量よりも多いデータをソートするときには、メモ
リに一時にストアできる量だけのデータが使用され、次
いでハード・ファイル・ディスクにストアされる。典型
的には、ソート後の順番でディスクにストアされる。続
いて、後続グループのデータがＣＰＵのメモリにストア
され、ソートされ、そしてディスクにストアされる。こ
のようなステップが全データが別々にグループ化され、
ソートされ、そして別々にディスクにストアされ尽くす
まで、繰り返される。
できる量よりも多いデータをソートするときには、メモ
リに一時にストアできる量だけのデータが使用され、次
いでハード・ファイル・ディスクにストアされる。典型
的には、ソート後の順番でディスクにストアされる。続
いて、後続グループのデータがＣＰＵのメモリにストア
され、ソートされ、そしてディスクにストアされる。こ
のようなステップが全データが別々にグループ化され、
ソートされ、そして別々にディスクにストアされ尽くす
まで、繰り返される。
ディスクに置かれたソート済データのグループは、次に
一緒にマージされる。すべてのグループについてその第
１の部分が持ち寄られ、ソートされ、そしてディスクに
ストアされ直す、このようなステップが、データ・グル
ープの残りの部分が一緒にソートされ、ディスクにスト
アされ直すまで続く。
一緒にマージされる。すべてのグループについてその第
１の部分が持ち寄られ、ソートされ、そしてディスクに
ストアされ直す、このようなステップが、データ・グル
ープの残りの部分が一緒にソートされ、ディスクにスト
アされ直すまで続く。
本発明によれば、最終ソート済データをディスクに書き
出すＩ１０操作をなくすことにより、ユーザに見える形
でリレーショナル・データベースのパフォーマンスが向
上する。ソート後の結果をディスクに書き出す代りに、
データが最終ソート順序に組み込まれると、該データが
ユーザへ提示される。最終ソート済データをディスクへ
書き込んだ後にメモリに読み戻すオーバーヘッドがなく
なる。データが実際に並べられると、その整理済となっ
たところのデータがリクエスターに渡されるので、リク
エスターはデータ全部が整理され尽くすまで待つ必要が
ない。
出すＩ１０操作をなくすことにより、ユーザに見える形
でリレーショナル・データベースのパフォーマンスが向
上する。ソート後の結果をディスクに書き出す代りに、
データが最終ソート順序に組み込まれると、該データが
ユーザへ提示される。最終ソート済データをディスクへ
書き込んだ後にメモリに読み戻すオーバーヘッドがなく
なる。データが実際に並べられると、その整理済となっ
たところのデータがリクエスターに渡されるので、リク
エスターはデータ全部が整理され尽くすまで待つ必要が
ない。
本発明を用いる、リレーショナル・データベース・マネ
ジヤーの一要素であるソート・サービスは、データ行を
受は取って、それらをリクエストに応じて昇順または降
順に並べる。
ジヤーの一要素であるソート・サービスは、データ行を
受は取って、それらをリクエストに応じて昇順または降
順に並べる。
ソートには２つの主要な部分がある。第１はインサート
・フェーズである。ここでは、リレーシヨナル・データ
・サービス（ＲＤＳ）から受は取ったデータ行を、並べ
換えて順序ストリングにする。第２は、データ行をすべ
て受は取った後に実行されるマージ・フェーズである。
・フェーズである。ここでは、リレーシヨナル・データ
・サービス（ＲＤＳ）から受は取ったデータ行を、並べ
換えて順序ストリングにする。第２は、データ行をすべ
て受は取った後に実行されるマージ・フェーズである。
マージ・フェースは、順序ストリングを受は取って、整
理された単一のデータ・ストリングにマージする。従前
のデータベース管理システムでは、この最終データ・ス
トリングをディスクの一部フアイルに出力していた。デ
ィスクへの書込をここではディスク出力モードと呼ぶこ
とにする。本発明では、高速直接出力モードの下で、Ｒ
ＤＳは必要に応じて最終ソート結果のデータを読み取る
ことができる。
理された単一のデータ・ストリングにマージする。従前
のデータベース管理システムでは、この最終データ・ス
トリングをディスクの一部フアイルに出力していた。デ
ィスクへの書込をここではディスク出力モードと呼ぶこ
とにする。本発明では、高速直接出力モードの下で、Ｒ
ＤＳは必要に応じて最終ソート結果のデータを読み取る
ことができる。
オプテイマイザ・ルーチンは、所与の問合せ文に対して
、ディスク出力モード又は高速直接出力モードのどちら
が効率的かを判断する。モードの選択は、問合せ文がソ
ート済データを使う回数が１回だけかそれとも複数回か
に応じて決まる。
、ディスク出力モード又は高速直接出力モードのどちら
が効率的かを判断する。モードの選択は、問合せ文がソ
ート済データを使う回数が１回だけかそれとも複数回か
に応じて決まる。
いくつかのＳＱＬ操作、例えば、０ＲＤＥＲＢＹ％ＧＲ
ＯＵＰ ＢＹ、あるいはＭＥＲＧＥ／ＪＯＩＮの外部
パスにおいては、直接出力モードの方が、マージ・フェ
ーズのオーバヘッドの多くを除去できる点で、ディスク
出力モードよりも効率がよい。インサート・フェーズは
、出力が出力ファイルの形をとろうとも、あるいは出力
がＲＤＳへ直接向かおうとも、そういったことに関係な
く、同じように実行される。
ＯＵＰ ＢＹ、あるいはＭＥＲＧＥ／ＪＯＩＮの外部
パスにおいては、直接出力モードの方が、マージ・フェ
ーズのオーバヘッドの多くを除去できる点で、ディスク
出力モードよりも効率がよい。インサート・フェーズは
、出力が出力ファイルの形をとろうとも、あるいは出力
がＲＤＳへ直接向かおうとも、そういったことに関係な
く、同じように実行される。
マージ・フェースの開始時に、ソート・サービスは、最
終ソート済データをディスクに整理済−時フアイルの形
で置く必要性をＲＤＳのオプテイマイザ・ルーチンが表
示しているか否かを知るためのテストを行う。データを
ディスクに置く必要がないならば、ソート・サービスは
、最終パスに達するまでマージを続ける。
終ソート済データをディスクに整理済−時フアイルの形
で置く必要性をＲＤＳのオプテイマイザ・ルーチンが表
示しているか否かを知るためのテストを行う。データを
ディスクに置く必要がないならば、ソート・サービスは
、最終パスに達するまでマージを続ける。
最終バスであることの認識は、残っている順序ストリン
グの数もマージ・バッファの数と比較することにより行
われる。マージ・バッファの数が順序ストリングの数基
上であるなら、最終バスに至ったわけである。これは、
全順序ストリングのトップ・エントリから選んだ行の各
々が、最終ソート出力における後続エントリになること
を意味する。ソート・サービスが最終マージ・パスの開
始準備が整ったことを認識し、しかも高速直接出力を行
うときは、ＲＤＳにリターンして、ＲＤＳからのソート
・フェッチの受入準備の整ったことを表示する。ＲＤＳ
がソート・フェッチを行うと、ソート・サービスは残っ
ている順序ストリングの中から後続の行を正しく選び、
それをＲＤＳに返す。このプロセスは、すべての行がＲ
ＤＳに返されるまで繰り返される。
グの数もマージ・バッファの数と比較することにより行
われる。マージ・バッファの数が順序ストリングの数基
上であるなら、最終バスに至ったわけである。これは、
全順序ストリングのトップ・エントリから選んだ行の各
々が、最終ソート出力における後続エントリになること
を意味する。ソート・サービスが最終マージ・パスの開
始準備が整ったことを認識し、しかも高速直接出力を行
うときは、ＲＤＳにリターンして、ＲＤＳからのソート
・フェッチの受入準備の整ったことを表示する。ＲＤＳ
がソート・フェッチを行うと、ソート・サービスは残っ
ている順序ストリングの中から後続の行を正しく選び、
それをＲＤＳに返す。このプロセスは、すべての行がＲ
ＤＳに返されるまで繰り返される。
本発明を用いてパフォーマンスが向上する主要な領域が
２つある。第１は、ソート済の全データのディスクへの
書込及び読出しを実行しないで済ませるようにしたので
、トータルのソート時間が減少することである。第２は
、ソート済の各々の行について、応答時間が改善される
ことである。
２つある。第１は、ソート済の全データのディスクへの
書込及び読出しを実行しないで済ませるようにしたので
、トータルのソート時間が減少することである。第２は
、ソート済の各々の行について、応答時間が改善される
ことである。
その理由は、すべてのデータがソートされ尽くすのを待
ってからソート済データなＲＤＳを介してユーザに返す
のではなくて、レコードが最終ソート順に配されたなら
、レコードをＲＤＳを介してユーザに返すようにしたか
らである。
ってからソート済データなＲＤＳを介してユーザに返す
のではなくて、レコードが最終ソート順に配されたなら
、レコードをＲＤＳを介してユーザに返すようにしたか
らである。
Ｄ、実施例
第１Ａ図と第１Ｂ図は、本発明を実施するのに用いられ
る処理装置の概要を示す。
る処理装置の概要を示す。
第１Ａ図は、１８Ｍ社のパーソナル・システム／２（商
標）で用いられているような、パーソナル・コンピュー
タ・アーキテクチャの１例を示す。
標）で用いられているような、パーソナル・コンピュー
タ・アーキテクチャの１例を示す。
このアーキテクチャの焦点は、マイクロプロセッサ１か
らなる。マイクロプロセッサ１はパス２につながれる。
らなる。マイクロプロセッサ１はパス２につながれる。
パス２は、データ・ラインのセット、アドレス・ライン
のセット、及びコントロール・ラインのセットからなる
。複数のＩ１０デバイス、メモリ、記憶装置３〜８が、
それぞれアダプタ９〜１４を介して、パス２に接続され
ている。例えば、デイスプレィ４は１８Ｍパーソナル／
システム・カラー・デイスプレィ８５１４であってよく
、その場合は、アダプタ１０をブレナ・ボードに集積化
することができる。その他のデバイス３．５〜８及びア
ダプタ９．１１〜１４は、１８Ｍパーソナル・システム
／２の一部として含まれていてもよいし、ＩＢＭ社製の
プラグ・イン・オプションとしてアベイラブルであって
もよい。例えば、ＲＡＭ６、ＲＯＭ７、及びこれに対応
するアダプタ１２．１３は、１８Ｍパーソナル・システ
ム／２の標準装備ではあるけれども、ＲＡＭ６を補うた
めにプラグ・イン・メモリ・エクスパンション・オプシ
ョンを介してＲＡＭをさらに付加してもよい。
のセット、及びコントロール・ラインのセットからなる
。複数のＩ１０デバイス、メモリ、記憶装置３〜８が、
それぞれアダプタ９〜１４を介して、パス２に接続され
ている。例えば、デイスプレィ４は１８Ｍパーソナル／
システム・カラー・デイスプレィ８５１４であってよく
、その場合は、アダプタ１０をブレナ・ボードに集積化
することができる。その他のデバイス３．５〜８及びア
ダプタ９．１１〜１４は、１８Ｍパーソナル・システム
／２の一部として含まれていてもよいし、ＩＢＭ社製の
プラグ・イン・オプションとしてアベイラブルであって
もよい。例えば、ＲＡＭ６、ＲＯＭ７、及びこれに対応
するアダプタ１２．１３は、１８Ｍパーソナル・システ
ム／２の標準装備ではあるけれども、ＲＡＭ６を補うた
めにプラグ・イン・メモリ・エクスパンション・オプシ
ョンを介してＲＡＭをさらに付加してもよい。
ＲＯＭ７の中には、マイクロプロセッサ１によって実行
される、ＢＩＯ３（基本人出力オペレーティング・シス
テム）として知られる複数の命令が記憶されている。Ｂ
ＩＯ８は、コンピュータの基本動作をコントロールする
。Ｏ５／２（商標）等のオペレーティング・システムは
メモリ６にロードされ、ＲＯＭ７に記憶されたＢＩＯ８
と協同する。もつとも、ＢＩＯ５の一部ないし全部をＲ
ＯＭ７ではなくメモリ６に記憶させてもよい。そうする
ことにより、基本的なシステム動作の修正を、ＢＩＯＳ
プログラムの変更によって吸収し、かつ変更したＢＩＯ
ＳプログラムをＲＡＭ６に即座にロードすることができ
る。
される、ＢＩＯ３（基本人出力オペレーティング・シス
テム）として知られる複数の命令が記憶されている。Ｂ
ＩＯ８は、コンピュータの基本動作をコントロールする
。Ｏ５／２（商標）等のオペレーティング・システムは
メモリ６にロードされ、ＲＯＭ７に記憶されたＢＩＯ８
と協同する。もつとも、ＢＩＯ５の一部ないし全部をＲ
ＯＭ７ではなくメモリ６に記憶させてもよい。そうする
ことにより、基本的なシステム動作の修正を、ＢＩＯＳ
プログラムの変更によって吸収し、かつ変更したＢＩＯ
ＳプログラムをＲＡＭ６に即座にロードすることができ
る。
パーソナル・システム／２とＯ８／２に関しては、以下
のマニュアルを参照されたい。
のマニュアルを参照されたい。
ＩＢＭ コーポレーション、パーツ・ナンバー６８Ｘ
２２２４、オーダー・ナンバー ８６８Ｘ−コーポレー
ション、パーツ・ナンバー ６８Ｘ２２５６、オーダー
・ナンバー ５６８Ｘ−２２５Ｒｅｆｅｒｅｎｃｅ、
Ｉ ＢＭ コーポレーション、パーツ・ナンバー
６２８０２０１、オーダー・ナンバー５８７１−ＡＡＡ
。
２２２４、オーダー・ナンバー ８６８Ｘ−コーポレー
ション、パーツ・ナンバー ６８Ｘ２２５６、オーダー
・ナンバー ５６８Ｘ−２２５Ｒｅｆｅｒｅｎｃｅ、
Ｉ ＢＭ コーポレーション、パーツ・ナンバー
６２８０２０１、オーダー・ナンバー５８７１−ＡＡＡ
。
１ａｃｏｂｕｃｅｉ、 Ｅｄ、 ＯＳ／２ Ｐｒｏ
ｒａｍｍｅｒ ５Ｇｕｉｄｅ、 ＭｃＧｒａｗ Ｈｉ
ｌｌ、１９８８゜本発明の装置では、リレーショナル・
データベース・マネジヤー等のアプリケーション・プロ
グラム１８は、メモリ６にロードされたり、あるいはメ
ディア５に常駐したりする。メディア５はディスケット
またはハード・ファイルを含むが、これに限定されるも
のではない。リレーショナル・データベース・マネジヤ
ー２０は、オペレーティング・システム１５の拡張と考
えてもよい。
ｒａｍｍｅｒ ５Ｇｕｉｄｅ、 ＭｃＧｒａｗ Ｈｉ
ｌｌ、１９８８゜本発明の装置では、リレーショナル・
データベース・マネジヤー等のアプリケーション・プロ
グラム１８は、メモリ６にロードされたり、あるいはメ
ディア５に常駐したりする。メディア５はディスケット
またはハード・ファイルを含むが、これに限定されるも
のではない。リレーショナル・データベース・マネジヤ
ー２０は、オペレーティング・システム１５の拡張と考
えてもよい。
リレーショナル・データベース・マネジヤー２０は、リ
レーショナル・データベース・マネジヤー・タスクの包
括的なセットを含んでなる。リレーショナル・データベ
ース・マネジヤー・タスクには、ソート・タスク２３、
リレーショナル・データ・サービス・タスク２５、及び
オプテイマイザ・タスク２７が含まれるけれども、これ
らに限定されるわけではない。
レーショナル・データベース・マネジヤー・タスクの包
括的なセットを含んでなる。リレーショナル・データベ
ース・マネジヤー・タスクには、ソート・タスク２３、
リレーショナル・データ・サービス・タスク２５、及び
オプテイマイザ・タスク２７が含まれるけれども、これ
らに限定されるわけではない。
リレーショナル・データベース・マネジヤー２０は、リ
レーショナル・データベース・マネジヤー・タスクの包
括的なセットであり、マイクロプロセッサ１にインスト
ラクションを与えて、第１Ａ図及び第１Ｂ図に示される
処理システムをしてリレーショナル・データベース機能
を営ませる。
レーショナル・データベース・マネジヤー・タスクの包
括的なセットであり、マイクロプロセッサ１にインスト
ラクションを与えて、第１Ａ図及び第１Ｂ図に示される
処理システムをしてリレーショナル・データベース機能
を営ませる。
メモリ６にロードされたアプリケーション・プログラム
１８は、メモリ６に先にロードされたオペレーティング
・システムと協同する。
１８は、メモリ６に先にロードされたオペレーティング
・システムと協同する。
第１Ａ図及び第１Ｂ図の処理システムにおいて、オペレ
ータは、キーボード３のオペレータ・コントロール・キ
ーを介して、リレーショナル・データベース・マネジヤ
ー２０にアクセスする。バス２を介してデイスプレィ４
、メディア・ストレージ５、及びメモリ６に接続された
プロセッサ１は、キーボードによってドライブされる。
ータは、キーボード３のオペレータ・コントロール・キ
ーを介して、リレーショナル・データベース・マネジヤ
ー２０にアクセスする。バス２を介してデイスプレィ４
、メディア・ストレージ５、及びメモリ６に接続された
プロセッサ１は、キーボードによってドライブされる。
ユーザが、キーボード３を介して、リレーショナル・デ
ータベース・マネジヤー２０とインターラクトするアプ
リケーション・プログラムとインターラクトするとき、
リレーショナル・データベース・マネジヤー２０とその
データはデイスプレィ４を通してユーザに表示される。
ータベース・マネジヤー２０とインターラクトするアプ
リケーション・プログラムとインターラクトするとき、
リレーショナル・データベース・マネジヤー２０とその
データはデイスプレィ４を通してユーザに表示される。
データベース・マネジャー２０とインターラクトするユ
ーザに加えて、アプリケーション１８も、アプリケーシ
ョン１８中のＳＱＬコマンドを介してデータベース・マ
ネジャー２０とインターラクトすることができる。
ーザに加えて、アプリケーション１８も、アプリケーシ
ョン１８中のＳＱＬコマンドを介してデータベース・マ
ネジャー２０とインターラクトすることができる。
本発明の説明を、第２Ａ図及び第２Ｂ図に示すデータベ
ース・テーブルを参照して行う。ＳＱＬ言語では、第２
Ａ図のデータベース・テーブル２２は、ユーザによって
、以下のように定義される。
ース・テーブルを参照して行う。ＳＱＬ言語では、第２
Ａ図のデータベース・テーブル２２は、ユーザによって
、以下のように定義される。
ＣＲＥＡＴＥ ＴＡＢＬＥ ５ＴＡＦＦ（ＩＤ
ＩＮＴＥＧＥＲ。
ＩＮＴＥＧＥＲ。
ＮＡＭＥ ＶＡＲＣＨＡＲ（１０））ＣＲＥＡＴＥ
ＴＡＢＬＥ（テーブル作成）は、ＳＱＬデータ定義文
の１例である。ＣＲＥＡＴＥＴＡＢＬＥ文の各々は、作
成されるテーブル２２の名前２４、そのカラム２６と２
８の名前、及びこれらのカラムのデータ・タイプを与え
る。ユーザがテーブル作成文を実行した後、テーブルは
最初は空である。つまり、テーブルにはデータ行２０２
が１つも存在していない。しかしながら、ユーザはＳＱ
ＬのｌＮ５ＥＲＴ（挿入）文を使って直ちにデータ行２
０２を挿入し、第２Ａ図に示されるようなテーブルを作
ることができる。こうして、ユーザは、このテーブルに
関して、第２Ｂ図に示されるような作成済の他のテーブ
ルと一緒に、有用な操作をなすことが可能になる。例え
ば、ユーザはテーブル２２のデータをＩＤ番号順に並べ
ることもできるし、テーブル２２を別のテーブル２１と
結合（ｊｏｉｎ ）することもできる。（ここで、テー
ブル２１は、ＩＤ番号、部門（ＤＥＰＴ）、及び給料（
ＳＡＬＡｒＬＹ）という３つのカラムを持っている。）
また、ユーザは、最高給料を選んだり部門毎にグループ
化したりするＧＲＯＵＰＢＹ操作を実行することだって
できる。マルチプル・テーブルを一時に２つ結合するた
めにＭＥＲＧＥ ＪＯＩＮ操作が用いられたなら、リ
レーショナル・データベース・マネジヤーは、インデッ
クスが使えない場合には、テーブルの行をシーケンシャ
ルに並べるためにソート操作を実行する。第３図を参照
するに、ユーザ１９またはアプリケーション１８は、望
む操作のための文（ステートメント）を入力する（ステ
ップ３１）。例えば、ユーザまたはアプリケーションが
以下の文を発することが考えられる。
ＴＡＢＬＥ（テーブル作成）は、ＳＱＬデータ定義文
の１例である。ＣＲＥＡＴＥＴＡＢＬＥ文の各々は、作
成されるテーブル２２の名前２４、そのカラム２６と２
８の名前、及びこれらのカラムのデータ・タイプを与え
る。ユーザがテーブル作成文を実行した後、テーブルは
最初は空である。つまり、テーブルにはデータ行２０２
が１つも存在していない。しかしながら、ユーザはＳＱ
ＬのｌＮ５ＥＲＴ（挿入）文を使って直ちにデータ行２
０２を挿入し、第２Ａ図に示されるようなテーブルを作
ることができる。こうして、ユーザは、このテーブルに
関して、第２Ｂ図に示されるような作成済の他のテーブ
ルと一緒に、有用な操作をなすことが可能になる。例え
ば、ユーザはテーブル２２のデータをＩＤ番号順に並べ
ることもできるし、テーブル２２を別のテーブル２１と
結合（ｊｏｉｎ ）することもできる。（ここで、テー
ブル２１は、ＩＤ番号、部門（ＤＥＰＴ）、及び給料（
ＳＡＬＡｒＬＹ）という３つのカラムを持っている。）
また、ユーザは、最高給料を選んだり部門毎にグループ
化したりするＧＲＯＵＰＢＹ操作を実行することだって
できる。マルチプル・テーブルを一時に２つ結合するた
めにＭＥＲＧＥ ＪＯＩＮ操作が用いられたなら、リ
レーショナル・データベース・マネジヤーは、インデッ
クスが使えない場合には、テーブルの行をシーケンシャ
ルに並べるためにソート操作を実行する。第３図を参照
するに、ユーザ１９またはアプリケーション１８は、望
む操作のための文（ステートメント）を入力する（ステ
ップ３１）。例えば、ユーザまたはアプリケーションが
以下の文を発することが考えられる。
Ｓ Ｅ Ｌ Ｅ ＣＴ ＊ Ｆ ＲＯＭ
Ｓ Ｔ Ａ Ｆ ＦＯＲＤＥＲＢＹ ＩＤ コマンドＳ Ｅ Ｌ Ｅ ＣＴ ＊は、ある行のすべ
てのカラムを取得するのに用いられる。
Ｓ Ｔ Ａ Ｆ ＦＯＲＤＥＲＢＹ ＩＤ コマンドＳ Ｅ Ｌ Ｅ ＣＴ ＊は、ある行のすべ
てのカラムを取得するのに用いられる。
第１Ａ図及び第１Ｂ図のオプテイマイザ２７は、ユーザ
またはアプリケーションが入力した操作文にどの出力モ
ードを使うかを決定する（第３図のステップ３２）。デ
フォルトはディスク出力モードであるけれども（ステッ
プ３４）、あるソート・プランのために、オプティマイ
ズ・ルーチン３２によって、モードが高速直接出力モー
ドに変更される場合がある。オプテイマイザ２７は、リ
レーショナル・データ・サービス２５の一構成要素であ
り、データ・アクセスのいくつかの方法、すなわちプラ
ンのうち、所与の問合せ文に使うべきものはどれである
かを決定する。例えば、インデックスを使うべきか、シ
ーケンシャルなスキャニングにするのか、またはソート
操作を実行すべきなのか、といったことを決定する。オ
プティマイズ・ルーチン（第３図のステップ３２）の詳
細な説明は第７図で行うが、このルーチンは、オプテイ
マイザ２７が問合せ文の処理に必要なすべてのプランを
作成した後に呼び出されるものである。プランは、問合
せの結果を作成するために用いられるジョイン（結合）
やテーブル・アクセス等のテーブル操作を表現する。例
えば、ジョイン・プランには、２つのプランがある。１
つは外部（ｏｕｔｅｒ ）テーブル用であり、他の１つ
は内部（１ｎｎｅｒ ）テーブル用である。外部テーブ
ルへのアクセスは、まず、内部テーブルのマツチする行
を外部テーブルの各行と結合させつつ、行われる。オプ
テイマイザ・ルーチン８２は、問合せのためのプランご
とに呼び出される。ソート・プランが最初作成されたと
き、そのプランはディスク出力オプションを伴っている
。以下で述べるオプテイマイザ・ルーチン３２は、ある
ソート・プランのディスク出力オプションを、高速直接
出力オプションに変えることができる。
またはアプリケーションが入力した操作文にどの出力モ
ードを使うかを決定する（第３図のステップ３２）。デ
フォルトはディスク出力モードであるけれども（ステッ
プ３４）、あるソート・プランのために、オプティマイ
ズ・ルーチン３２によって、モードが高速直接出力モー
ドに変更される場合がある。オプテイマイザ２７は、リ
レーショナル・データ・サービス２５の一構成要素であ
り、データ・アクセスのいくつかの方法、すなわちプラ
ンのうち、所与の問合せ文に使うべきものはどれである
かを決定する。例えば、インデックスを使うべきか、シ
ーケンシャルなスキャニングにするのか、またはソート
操作を実行すべきなのか、といったことを決定する。オ
プティマイズ・ルーチン（第３図のステップ３２）の詳
細な説明は第７図で行うが、このルーチンは、オプテイ
マイザ２７が問合せ文の処理に必要なすべてのプランを
作成した後に呼び出されるものである。プランは、問合
せの結果を作成するために用いられるジョイン（結合）
やテーブル・アクセス等のテーブル操作を表現する。例
えば、ジョイン・プランには、２つのプランがある。１
つは外部（ｏｕｔｅｒ ）テーブル用であり、他の１つ
は内部（１ｎｎｅｒ ）テーブル用である。外部テーブ
ルへのアクセスは、まず、内部テーブルのマツチする行
を外部テーブルの各行と結合させつつ、行われる。オプ
テイマイザ・ルーチン８２は、問合せのためのプランご
とに呼び出される。ソート・プランが最初作成されたと
き、そのプランはディスク出力オプションを伴っている
。以下で述べるオプテイマイザ・ルーチン３２は、ある
ソート・プランのディスク出力オプションを、高速直接
出力オプションに変えることができる。
第７図のオプテイマイザ・ルーチン３２では、まず、当
該プランがテーブル・アクセス・プランであるか否かの
判断が行われる（ステップ１２１）。テーブル・アクセ
ス・プランは、−時にテーブルを１行ずつ読み俄るリク
エストである。当該プランがテーブル・アクセス・プラ
ンであるならば、ステップ１２３において、該プランが
問合せのルート・プランであるか否かの判断が行われる
。
該プランがテーブル・アクセス・プランであるか否かの
判断が行われる（ステップ１２１）。テーブル・アクセ
ス・プランは、−時にテーブルを１行ずつ読み俄るリク
エストである。当該プランがテーブル・アクセス・プラ
ンであるならば、ステップ１２３において、該プランが
問合せのルート・プランであるか否かの判断が行われる
。
ルート・プランは、問合せの最終結果を生成する。
もしルート・プランでないなら、ルーチンは高速直接出
力をイネーブルにする（活動させる）ことなくリターン
する。もしルート・プランであるなら、ステップ１２５
へ進み、テーブル・アクセス・プランがソート人力ブラ
ンを有するか否かが判断される。判断結果がイエスであ
るなら、高速直接出力がイネーブルとされる（ステップ
１２７）。
力をイネーブルにする（活動させる）ことなくリターン
する。もしルート・プランであるなら、ステップ１２５
へ進み、テーブル・アクセス・プランがソート人力ブラ
ンを有するか否かが判断される。判断結果がイエスであ
るなら、高速直接出力がイネーブルとされる（ステップ
１２７）。
そうでないならば、高速直接出力はイネーブルとされず
、ルーチンを出ることになる。
、ルーチンを出ることになる。
もし当該プランがテーブル・アクセス・プランでなかっ
たならば（ステップ１２１）、ステップ１２９へ進んで
、該プランがジョイン・プランであるか否かの判断が行
われる。ジョイン・プランは、２つのテーブルにアクセ
スし、かつこれらを組み合わせることを表わす。判断結
果がノーであるなら、高速直接出力は活動せず、ルーチ
ンを出る。もしジョイン・プランであるなら、ステップ
１３１へ進み、ジゴイン・プランの外部プランがテーブ
ル・アクセス・プランであるか否かの判断が行われる。
たならば（ステップ１２１）、ステップ１２９へ進んで
、該プランがジョイン・プランであるか否かの判断が行
われる。ジョイン・プランは、２つのテーブルにアクセ
スし、かつこれらを組み合わせることを表わす。判断結
果がノーであるなら、高速直接出力は活動せず、ルーチ
ンを出る。もしジョイン・プランであるなら、ステップ
１３１へ進み、ジゴイン・プランの外部プランがテーブ
ル・アクセス・プランであるか否かの判断が行われる。
判断結果がノーであるなら、高速直接出力は活動せず、
ルーチンを出る。判断結果がイエスなら、ステップ１３
３へ進み、該テーブル・アクセス・プランが人力ソード
・プランを有するか否かの判断が行われる。答がイエス
なら、当該ソート・プランのために高速直接出力が活動
化して、ルーチンを出る。答がノーなら、高速直接出力
は活動せず、ルーチンを出る。
ルーチンを出る。判断結果がイエスなら、ステップ１３
３へ進み、該テーブル・アクセス・プランが人力ソード
・プランを有するか否かの判断が行われる。答がイエス
なら、当該ソート・プランのために高速直接出力が活動
化して、ルーチンを出る。答がノーなら、高速直接出力
は活動せず、ルーチンを出る。
第３図に戻ると、ユーザ／アプリケーションが問合せ文
を入力しくステップ３１）、さらにオプテイマイザが当
該操作のために適切な出力モードを判断した後、リレー
ショナル・データ・サービス２５は、ディスク５にスト
ア済のテーブル２２（第２Ａ図）から、行２１１〜２１
８を、−度に１行ずつ取り出すくステップ３３）。０Ｒ
ＤＥＲＢＹ文を含むいくつかの問合せ文は、リレーショ
ナル・データベース・マネジヤー２０に対して、データ
２０２（第２Ａ図）の行を要求した順に取得するために
、ソート操作を実行することを要請する。
を入力しくステップ３１）、さらにオプテイマイザが当
該操作のために適切な出力モードを判断した後、リレー
ショナル・データ・サービス２５は、ディスク５にスト
ア済のテーブル２２（第２Ａ図）から、行２１１〜２１
８を、−度に１行ずつ取り出すくステップ３３）。０Ｒ
ＤＥＲＢＹ文を含むいくつかの問合せ文は、リレーショ
ナル・データベース・マネジヤー２０に対して、データ
２０２（第２Ａ図）の行を要求した順に取得するために
、ソート操作を実行することを要請する。
第３図に示されるように、ソート・ファンクション２８
には８つの大きなフェーズがある。インサート・フェー
ズ４１では、ソート２３が行を未知の順序で受は取る。
には８つの大きなフェーズがある。インサート・フェー
ズ４１では、ソート２３が行を未知の順序で受は取る。
インサート・フェーズ４１の詳しい説明は第４図で行う
。ソート２３のオーブン・フェーズ４５では、ソート２
３がソート済の順で返すべくデータを準備する。オーブ
ン・フェーズ４３の詳しい説明は第５図で行う。ソート
２８のフェッチ・フェーズ５１では、データがリレーシ
ョナル・データ・サービス２５を経て、コーラ−（ｃａ
ｌ ｌｅｒ ）へ、ソート済の順序で返される。
。ソート２３のオーブン・フェーズ４５では、ソート２
３がソート済の順で返すべくデータを準備する。オーブ
ン・フェーズ４３の詳しい説明は第５図で行う。ソート
２８のフェッチ・フェーズ５１では、データがリレーシ
ョナル・データ・サービス２５を経て、コーラ−（ｃａ
ｌ ｌｅｒ ）へ、ソート済の順序で返される。
フェッチ・フェーズ５１の詳しい説明は第６図で行う。
リレーショナル・データ・サービス２５がテーブル２２
から行２１１を受は取ると（第３図のステップ３３）、
リレーショナル・データ・サービス２５は、この行２１
１を、ソート・インサート・フェーズにあるソート・フ
ァンクション２３へ渡す（ステップ４１）。ソート・イ
ンサート・フェーズでは、データ行がデータベース・マ
ネジャー２０のリレーショナル・データ・サービス要素
２５によって受は取られる。このデータは未整理の形で
受は増られる。しかも、受は取られることになるデータ
量を示す微衷は何もない。
から行２１１を受は取ると（第３図のステップ３３）、
リレーショナル・データ・サービス２５は、この行２１
１を、ソート・インサート・フェーズにあるソート・フ
ァンクション２３へ渡す（ステップ４１）。ソート・イ
ンサート・フェーズでは、データ行がデータベース・マ
ネジャー２０のリレーショナル・データ・サービス要素
２５によって受は取られる。このデータは未整理の形で
受は増られる。しかも、受は取られることになるデータ
量を示す微衷は何もない。
ソート・インサート・フェーズの詳しい説明を、第４図
及び第８図を参照して行う。ソート・インサート・フェ
ーズの間、ソートは、リレーショナル・データ・サービ
ス２５から呼ばれる度に１デ一タ行を受は取る。ステッ
プ６１では、内部バッファ６２（第８図）の中に当該デ
ータに利用可能なスペースがあるか否かのテストが行わ
れる。スペースがあるなら、ソート２３は、（第２Ａ図
の）データ２１１〜２１８を、受は取った順に内部バッ
ファ６２に置く（ステップ６５）。次にソート２３は、
バッファ６２内のデータ行をポイントするべく、バラン
ス・バイナリ−・ツリー（ｂａｌａｎｃｅｄｂｉｎａｒ
ｙ ｔｒｅｅ ） （３４のためのエントリを作成する
（ステップ６７）。バイナリ−・ツリー６４は、ソート
後の順番のデータを追跡するのに使われる。
及び第８図を参照して行う。ソート・インサート・フェ
ーズの間、ソートは、リレーショナル・データ・サービ
ス２５から呼ばれる度に１デ一タ行を受は取る。ステッ
プ６１では、内部バッファ６２（第８図）の中に当該デ
ータに利用可能なスペースがあるか否かのテストが行わ
れる。スペースがあるなら、ソート２３は、（第２Ａ図
の）データ２１１〜２１８を、受は取った順に内部バッ
ファ６２に置く（ステップ６５）。次にソート２３は、
バッファ６２内のデータ行をポイントするべく、バラン
ス・バイナリ−・ツリー（ｂａｌａｎｃｅｄｂｉｎａｒ
ｙ ｔｒｅｅ ） （３４のためのエントリを作成する
（ステップ６７）。バイナリ−・ツリー６４は、ソート
後の順番のデータを追跡するのに使われる。
ステップ６１にて内部バッファ６２が満杯なら、データ
は、全バッファの全データを組み合わせた整理済順序ス
トリング６６（第８図）としてディスクに書き込まれる
（ステップ６３）。リレーショナル・データ・サービス
２５からさらに行を受は取ると、内部バッファ６２は再
び充填されていき、受は取ったデータを処理するのに要
する回数だけ処理が繰り返される。内部バッファ６２が
ディスク５へ書き込まれる度に（ステップ６３）、新た
に充填されたバッファ６２からの全データから新たな順
序ストリンク６６が形成されるわけである。
は、全バッファの全データを組み合わせた整理済順序ス
トリング６６（第８図）としてディスクに書き込まれる
（ステップ６３）。リレーショナル・データ・サービス
２５からさらに行を受は取ると、内部バッファ６２は再
び充填されていき、受は取ったデータを処理するのに要
する回数だけ処理が繰り返される。内部バッファ６２が
ディスク５へ書き込まれる度に（ステップ６３）、新た
に充填されたバッファ６２からの全データから新たな順
序ストリンク６６が形成されるわけである。
第３図を再び参照すると、リレーショナル・データ・サ
ービス２５によってすべての行がテーブルから取り出さ
れてソート・インサート・フェーズへ送られてしまった
なら（ステップ３７）、リレーショナル・データ・サー
ビス２５は、ソートの対象であるデータの終了を合図す
る（ステップ４３）。ソート・ファンクションの第２フ
エースであるソート・オーブン４５は、ソート２３に渡
すデータ行がもはやないことを知らせるリレーショナル
・データ・サービス（ＲＤＳ）２５からのコールによっ
て呼び出される。ここで、ソート２３は、ソート済の行
をＲＤＳ２５へ返す準備を行う。
ービス２５によってすべての行がテーブルから取り出さ
れてソート・インサート・フェーズへ送られてしまった
なら（ステップ３７）、リレーショナル・データ・サー
ビス２５は、ソートの対象であるデータの終了を合図す
る（ステップ４３）。ソート・ファンクションの第２フ
エースであるソート・オーブン４５は、ソート２３に渡
すデータ行がもはやないことを知らせるリレーショナル
・データ・サービス（ＲＤＳ）２５からのコールによっ
て呼び出される。ここで、ソート２３は、ソート済の行
をＲＤＳ２５へ返す準備を行う。
本発明によれば、ソート済行のＲＤＳ２５への返し方と
して、２つのモードのどちらかが選ばれる。１つはディ
スク出力モードであり、すべてのソート済データが整理
済−時フアイルの形でディスクに書き込まれることにな
る。もう１つのモードは高速直接モードと呼ばれる。こ
のモードでは、１つ１つの行が最終的なソート済順序に
配置されたなら、当該性を、リクエストを出したユーザ
／アプリケーションへＲＤＳ２５を介して、直接返すこ
とが可能である。どちらのモードが有利であるかは、結
果の使われ方によって決まる。ソート済データの使用回
数が１回だけであるとオプテイマイザ・ルーチン３２（
第７図）によって判断されるなら、ファイルに書き込ん
で後でそれを検索する手間を省くために、ソート済デー
タを直に返すのが最良である。しかしながら、ソート済
データが２回以上使われるのなら、該データは複数回の
使用に先立って一旦ソートされたにすぎないわけだから
、データをディスクに書き込むのが最良である。例えば
、オプテイマイザ・ルーチン３２（第７図）によって、
プランがルート・プランだと判断された場合、ソート済
データは１度だけ使われることになるのであって、高速
直接出力モードが活性化される。また、外部テーブルが
結合される場合も、ソート済データは１回使われるだけ
であり、高速直接出力モードが活性化される。そうでな
い場合は、内部テーブルが結合され、ソート済データは
２回以上使用されることになる。この場合、高速直接出
力モードは活動を開始しない。
して、２つのモードのどちらかが選ばれる。１つはディ
スク出力モードであり、すべてのソート済データが整理
済−時フアイルの形でディスクに書き込まれることにな
る。もう１つのモードは高速直接モードと呼ばれる。こ
のモードでは、１つ１つの行が最終的なソート済順序に
配置されたなら、当該性を、リクエストを出したユーザ
／アプリケーションへＲＤＳ２５を介して、直接返すこ
とが可能である。どちらのモードが有利であるかは、結
果の使われ方によって決まる。ソート済データの使用回
数が１回だけであるとオプテイマイザ・ルーチン３２（
第７図）によって判断されるなら、ファイルに書き込ん
で後でそれを検索する手間を省くために、ソート済デー
タを直に返すのが最良である。しかしながら、ソート済
データが２回以上使われるのなら、該データは複数回の
使用に先立って一旦ソートされたにすぎないわけだから
、データをディスクに書き込むのが最良である。例えば
、オプテイマイザ・ルーチン３２（第７図）によって、
プランがルート・プランだと判断された場合、ソート済
データは１度だけ使われることになるのであって、高速
直接出力モードが活性化される。また、外部テーブルが
結合される場合も、ソート済データは１回使われるだけ
であり、高速直接出力モードが活性化される。そうでな
い場合は、内部テーブルが結合され、ソート済データは
２回以上使用されることになる。この場合、高速直接出
力モードは活動を開始しない。
ＲＤＳ２５は、ソート２３を要求するＳＱＬ文をブレ・
コンパイルする。ＲＤＳ２５は、ソート済データをＲＤ
Ｓ２５へ直に返す方が効率がよいのか、それともディス
クへ書き出す方が効率がよいのかを判断するプロセスを
経る。判断のためのファクタは、データの使用回数が１
回か、それとも複数回か、ということである。ＲＤＳ２
５は、要求された操作タイプを調べることによって、こ
のことを認識する。一般的に言って、０ＲＤＥＲＢＹま
たはＧＲＯＵＰ ＢＹ操作が要求されているのであれ
ば、データをＲＤＳ２５へ直接に返すことができる。し
かしながら、ＭＥＲＧＥ／ＪＯＩＮ操作の場合には、出
力モードは、データの処理されつつある部分に依存する
ことになる。
コンパイルする。ＲＤＳ２５は、ソート済データをＲＤ
Ｓ２５へ直に返す方が効率がよいのか、それともディス
クへ書き出す方が効率がよいのかを判断するプロセスを
経る。判断のためのファクタは、データの使用回数が１
回か、それとも複数回か、ということである。ＲＤＳ２
５は、要求された操作タイプを調べることによって、こ
のことを認識する。一般的に言って、０ＲＤＥＲＢＹま
たはＧＲＯＵＰ ＢＹ操作が要求されているのであれ
ば、データをＲＤＳ２５へ直接に返すことができる。し
かしながら、ＭＥＲＧＥ／ＪＯＩＮ操作の場合には、出
力モードは、データの処理されつつある部分に依存する
ことになる。
ＭＥＲＧＥ／ＪＯＩＮの外部バス（ｏｕｔｅｒ ｐａｓ
ｓ ）が実行されるとき、パフォーマンス向上のために
直接出力モードを使うことができる。ＭＥ ＦｔＧＥ／
ＪＯＩＮ操作の際に要求されるその他のすべてのソート
については、ディスクへ出力するモードの方が好ましい
。ＲＤＳ２５のオプテイマイザ２７は、ユーザ／アプリ
ケーションによるアクションの特別な知識を必要とせず
に、ソート出力に最適な方法を選択する。
ｓ ）が実行されるとき、パフォーマンス向上のために
直接出力モードを使うことができる。ＭＥ ＦｔＧＥ／
ＪＯＩＮ操作の際に要求されるその他のすべてのソート
については、ディスクへ出力するモードの方が好ましい
。ＲＤＳ２５のオプテイマイザ２７は、ユーザ／アプリ
ケーションによるアクションの特別な知識を必要とせず
に、ソート出力に最適な方法を選択する。
ソート・オーブン・フェーズ４５の詳細は、第５図、第
８図、及び第９図で説明する。ＲＤＳ２５のオプテイマ
イザ２７がディスクへ出力するモードを選ぶと、以下の
ステップが実行される。
８図、及び第９図で説明する。ＲＤＳ２５のオプテイマ
イザ２７がディスクへ出力するモードを選ぶと、以下の
ステップが実行される。
まず、ソート２３は、内部バッファ６２（第８図）に残
っているデータを、整理済順序ストリング６６としてデ
ィスク５へ書き込む（ステップ７７）。ディスクにある
順序ストリングが１つだけであるならば（ステップ８４
）、データは最終的なソート済順序に並んでいる。そし
てソート２３は、順序ストリング６６の第１ページを読
み取る（ステップ８９）。ソート・オーブン・フェーズ
４５はこれで完了する。ディスクにある順序ストリング
が複数ならば、ソート２３は、マージ（ｍｅｒｇｅ ）
操作によってそれらをまとめて、単一の順序ストリング
にしなければならない（ステップ８１）。マージ操作（
第９回）には、各順序ストリング６６の先頭（トップ）
行２２１を比較すること、全体的に整理された順序の中
の次の行を順序ストリングの中から選ぶこと、及びそれ
をマージ済順序ストリング６８の中に置くことが含まれ
る。このプロセスは、すべてのソート済データをその内
容とする最終順序ストリング６８がディスクに１つだけ
残る状態が来るまで、続けられる。
っているデータを、整理済順序ストリング６６としてデ
ィスク５へ書き込む（ステップ７７）。ディスクにある
順序ストリングが１つだけであるならば（ステップ８４
）、データは最終的なソート済順序に並んでいる。そし
てソート２３は、順序ストリング６６の第１ページを読
み取る（ステップ８９）。ソート・オーブン・フェーズ
４５はこれで完了する。ディスクにある順序ストリング
が複数ならば、ソート２３は、マージ（ｍｅｒｇｅ ）
操作によってそれらをまとめて、単一の順序ストリング
にしなければならない（ステップ８１）。マージ操作（
第９回）には、各順序ストリング６６の先頭（トップ）
行２２１を比較すること、全体的に整理された順序の中
の次の行を順序ストリングの中から選ぶこと、及びそれ
をマージ済順序ストリング６８の中に置くことが含まれ
る。このプロセスは、すべてのソート済データをその内
容とする最終順序ストリング６８がディスクに１つだけ
残る状態が来るまで、続けられる。
第３図に戻って説明すると、ディスク出力モードの際に
は、フェッチ・フェーズ５１と呼ばれるソート２３の第
３フエーズが、インサート・フェーズ４１及びオーブン
・フェーズ４５の完了後に呼び出される。フェッチ・フ
ェーズ５１は、ＲＤＳがソート済データの行ごとにフェ
ッチ・リクエストを出すことからなる（ステップ４４）
。フェッチの各々に応答して、ソート２３は、ディスク
上の最終順序ストリングから１デ一タ行を検索し、ＲＤ
Ｓ２５へ渡す。
は、フェッチ・フェーズ５１と呼ばれるソート２３の第
３フエーズが、インサート・フェーズ４１及びオーブン
・フェーズ４５の完了後に呼び出される。フェッチ・フ
ェーズ５１は、ＲＤＳがソート済データの行ごとにフェ
ッチ・リクエストを出すことからなる（ステップ４４）
。フェッチの各々に応答して、ソート２３は、ディスク
上の最終順序ストリングから１デ一タ行を検索し、ＲＤ
Ｓ２５へ渡す。
上記ディスク出力モードは、ソート済データを繰り返し
使用することになるときに用いられる。
使用することになるときに用いられる。
この場合、高速直接出力モードは活動せず、ソート・フ
ァンクション２３は上述の如くして作動する。高速直接
モードが活動するのは、ＲＤＳによってソート済データ
が１回だけアクセスされる場合である。ＲＤＳは、０Ｒ
ＤＥＲＢＹ、Ｇ１’ｔＯＵＰ ＢＹ、 あるいはＭＥ
ＦｔＧＥ／ＪＯＩＮの外部パス等のＳＱＬ操作の場合に
、高速直接出力モードを活動させる。
ァンクション２３は上述の如くして作動する。高速直接
モードが活動するのは、ＲＤＳによってソート済データ
が１回だけアクセスされる場合である。ＲＤＳは、０Ｒ
ＤＥＲＢＹ、Ｇ１’ｔＯＵＰ ＢＹ、 あるいはＭＥ
ＦｔＧＥ／ＪＯＩＮの外部パス等のＳＱＬ操作の場合に
、高速直接出力モードを活動させる。
直接出力モードの場合、ソート２３は、上述のような３
つのフェーズを経過する。インサート・フェーズ４１（
第４図）は、ディスク出力モード又は直接出力モードの
選択に関係なしに、どちらのモードの場合も同様に実行
される。しかしながら、オーブン・フェーズ４５（第５
図）とフェッチ・フェーズ５１（第６図）は、直接出力
モードが選ばれた場合に変更されることになる。
つのフェーズを経過する。インサート・フェーズ４１（
第４図）は、ディスク出力モード又は直接出力モードの
選択に関係なしに、どちらのモードの場合も同様に実行
される。しかしながら、オーブン・フェーズ４５（第５
図）とフェッチ・フェーズ５１（第６図）は、直接出力
モードが選ばれた場合に変更されることになる。
第３図を参照すると、ソート２３がＲＤＳ２５によって
呼ばれてオーブンした場合（ステップ４１）、ＲＤＳが
エンド・才ブ・データ（ステップ４３）、及びフェッチ
操作の準備を知らせる。第５図に示すようにソート・オ
ーブン・フェーズ４５では、ＲＤＳが高速直接出力モー
ドを活動させたか否かを知るためのテストが行われる（
ステップ７３）。もし高速直接出力モードが活性化され
ていたなら、最終のソート済データが整理済の一部フア
イルの形でディスクに置かれることはない。
呼ばれてオーブンした場合（ステップ４１）、ＲＤＳが
エンド・才ブ・データ（ステップ４３）、及びフェッチ
操作の準備を知らせる。第５図に示すようにソート・オ
ーブン・フェーズ４５では、ＲＤＳが高速直接出力モー
ドを活動させたか否かを知るためのテストが行われる（
ステップ７３）。もし高速直接出力モードが活性化され
ていたなら、最終のソート済データが整理済の一部フア
イルの形でディスクに置かれることはない。
ソート２３は、すべてのデータがメモリにあるか否かを
テストする（ステップ７１、第５図）。
テストする（ステップ７１、第５図）。
もしすべてのデータがメモリにあるならば、ソート２３
は、バッファ内のデータ行を指すポインタのアレイを作
成する（ステップ７５）。次にソート２３はＲＤＳ２５
にリターンし、ソート２３がＲＤＳ２５からのソート・
フェッチを受は入れる準備ができたことを表示する（ス
テップ９１）。
は、バッファ内のデータ行を指すポインタのアレイを作
成する（ステップ７５）。次にソート２３はＲＤＳ２５
にリターンし、ソート２３がＲＤＳ２５からのソート・
フェッチを受は入れる準備ができたことを表示する（ス
テップ９１）。
メモリに適合するデータを上回るデータがあり、かつ高
速直接出力モードが選択されていた場合には、ソートは
、既述のようにステップ７７．７９、及び８１（第５図
）を実行する。順序ストリングが多数ある場合、ソート
は、最終バスのための準備が整うまで、それらのマージ
を続行する。最終バスの段階に至ったかどうかは、残っ
ている順序ストリングの数をマージ・バッファの数と比
較することによってわかる（ステップ７９）。マージ・
バッファの数が順序ストリングの数以上であれば、最終
パスである。このとき、すべての順序ストリングの先頭
エントリから選ばれた行の各々が、最終ソート済出力に
おける後続エントリである（ステップ８９）。ソートが
最終マージ・バスを始められる（つまり、マージ・パス
が必要だったとしても、せいぜい１回だけ）と認識した
なら、ＲＤＳ２５にリターンし、ソート２３がＦｔＤＳ
２５からのソート・フェッチを受は入れられることを表
示する（ステップ９１）。
速直接出力モードが選択されていた場合には、ソートは
、既述のようにステップ７７．７９、及び８１（第５図
）を実行する。順序ストリングが多数ある場合、ソート
は、最終バスのための準備が整うまで、それらのマージ
を続行する。最終バスの段階に至ったかどうかは、残っ
ている順序ストリングの数をマージ・バッファの数と比
較することによってわかる（ステップ７９）。マージ・
バッファの数が順序ストリングの数以上であれば、最終
パスである。このとき、すべての順序ストリングの先頭
エントリから選ばれた行の各々が、最終ソート済出力に
おける後続エントリである（ステップ８９）。ソートが
最終マージ・バスを始められる（つまり、マージ・パス
が必要だったとしても、せいぜい１回だけ）と認識した
なら、ＲＤＳ２５にリターンし、ソート２３がＦｔＤＳ
２５からのソート・フェッチを受は入れられることを表
示する（ステップ９１）。
第３図を参照すると、オープン・フェーズ・ステップ４
５が完了した後、ＲＤＳ２５はソート２３からソート済
データ行を取り出せる状態にある。
５が完了した後、ＲＤＳ２５はソート２３からソート済
データ行を取り出せる状態にある。
ソート・フェッチ・フェーズ５１の詳しい説明は第６図
で行う。ＲＤＳがソート・フェッチ操作のためにソート
を呼ぶたびに、ソート・フェッチは、後続行の有無を判
断する（ステップ１０１）。後続行がなければ、ソート
・フェッチは、ＲＤＳのためにデータ終了表示子をセッ
トして（ステップ１０３）、ＲＤＳへ戻る（ステップ１
１７）。後続行があって、かつ高速直接が選択されてい
た場合には、データがディスクから来るのか、それとも
メモリから来るのかを判断するテストが行われる（ステ
ップ１０７）。すべてのデータがメモリにあるならば、
ソート・フェッチはバッファから後続行を選び、該行を
ＲＤＳに返す（ステップ１１３．１１５）。データがデ
ィスク上の順序ストリングから来るならば、ソート・フ
ェッチ・フェースは全ストリングの先頭（トップ）から
後続行を選択する（ステップ１０９）。このことは第９
図に示されている。当該データ行はＲＤＳに渡される（
ステップ１１５）。順序ストリングが多数あるとき、直
接出力を伴うソートは、実際、残りのすべての行が単一
の整理済ストリングにマージされるのに先立って、デー
タ行を返す。ＲＤＳは、すべての行がＲＤＳに返される
まで、フェッチ・コールの処理を続行する。ＲＤＳにと
って、データが高速直接出力モードで返されるのか否か
はトランスペアレントである。
で行う。ＲＤＳがソート・フェッチ操作のためにソート
を呼ぶたびに、ソート・フェッチは、後続行の有無を判
断する（ステップ１０１）。後続行がなければ、ソート
・フェッチは、ＲＤＳのためにデータ終了表示子をセッ
トして（ステップ１０３）、ＲＤＳへ戻る（ステップ１
１７）。後続行があって、かつ高速直接が選択されてい
た場合には、データがディスクから来るのか、それとも
メモリから来るのかを判断するテストが行われる（ステ
ップ１０７）。すべてのデータがメモリにあるならば、
ソート・フェッチはバッファから後続行を選び、該行を
ＲＤＳに返す（ステップ１１３．１１５）。データがデ
ィスク上の順序ストリングから来るならば、ソート・フ
ェッチ・フェースは全ストリングの先頭（トップ）から
後続行を選択する（ステップ１０９）。このことは第９
図に示されている。当該データ行はＲＤＳに渡される（
ステップ１１５）。順序ストリングが多数あるとき、直
接出力を伴うソートは、実際、残りのすべての行が単一
の整理済ストリングにマージされるのに先立って、デー
タ行を返す。ＲＤＳは、すべての行がＲＤＳに返される
まで、フェッチ・コールの処理を続行する。ＲＤＳにと
って、データが高速直接出力モードで返されるのか否か
はトランスペアレントである。
本発明によれば、ソートに関連するオーバーへラドが減
少し、ソート済データのコーラ−（ｃａｌｌｅｒ）への
リターンが速くなる。その結果、２つの利点が生じる。
少し、ソート済データのコーラ−（ｃａｌｌｅｒ）への
リターンが速くなる。その結果、２つの利点が生じる。
１つはシステムの負荷が減ることであり、その分他のフ
ァンクションに能力を振り向けることができる。もう１
つは、ソート・ファンクションのユーザへの応答時間と
スルーブツトの改善である。
ァンクションに能力を振り向けることができる。もう１
つは、ソート・ファンクションのユーザへの応答時間と
スルーブツトの改善である。
本発明の高速直接出力法においては、ソートは、最終ソ
ート済データを、従来のデータベース・システムの場合
のようにディスク上の一部フアイルに書き出さない。そ
の代り、ソートはデータをコーラ−へ直に返す。この方
法では、すべてのデータが最終ソート済順序になるのを
待たないで、ソート済データをコーラ−へ返し始めるこ
とができる。
ート済データを、従来のデータベース・システムの場合
のようにディスク上の一部フアイルに書き出さない。そ
の代り、ソートはデータをコーラ−へ直に返す。この方
法では、すべてのデータが最終ソート済順序になるのを
待たないで、ソート済データをコーラ−へ返し始めるこ
とができる。
本発明の高速直接出力法を使うなら、ソートがデータを
最終的なソート済順序に配置し始めたことを認識すると
、ソートは、ソート済順序における後続行として１つの
行を取り出すや否や当該行をコーラ−へ直に渡す。
最終的なソート済順序に配置し始めたことを認識すると
、ソートは、ソート済順序における後続行として１つの
行を取り出すや否や当該行をコーラ−へ直に渡す。
この技術からいくつかの利点が得られる。最終ソート済
データをディスク上の一部フアイルへ書き出した後にユ
ーザのリクエストに応じて読み戻すことをやめたので、
トータルのソート時間が削減される。また、ディスクの
読み書きがなくなったので、システムにとっての負荷が
減少し、その分他のユーザにシステムの能力を振り向け
ることができる。別の利点は、ソート済の各行の応答時
間である。すべての行をソートし尽くしてからコーラ−
へ行を返し始めるのではなくて、最終ソート済順序に行
が配置された直後に当該行が返されるので、各ソート済
行の応答時間は改善される。コーラ−がソート済データ
を取り戻したなら、コーラ−は直ちにそれをユーザに表
示することもできるし、オペレーションの別のステップ
で使うこともできる。何れにせよ、個々の応答時間の改
善は有益である。
データをディスク上の一部フアイルへ書き出した後にユ
ーザのリクエストに応じて読み戻すことをやめたので、
トータルのソート時間が削減される。また、ディスクの
読み書きがなくなったので、システムにとっての負荷が
減少し、その分他のユーザにシステムの能力を振り向け
ることができる。別の利点は、ソート済の各行の応答時
間である。すべての行をソートし尽くしてからコーラ−
へ行を返し始めるのではなくて、最終ソート済順序に行
が配置された直後に当該行が返されるので、各ソート済
行の応答時間は改善される。コーラ−がソート済データ
を取り戻したなら、コーラ−は直ちにそれをユーザに表
示することもできるし、オペレーションの別のステップ
で使うこともできる。何れにせよ、個々の応答時間の改
善は有益である。
Ｅ、効果
本発明によれば、リレーショナル・データベース・シス
テムにおけるソート操作のパフォーマンスが向上する。
テムにおけるソート操作のパフォーマンスが向上する。
第１Ａ図と第１Ｂ図は、それぞれ、本発明におけるデー
タ処理の概要を説明する図である。 第２Ａ図と第２Ｂ図は、それぞれ、リレーショナル・デ
ータベースにおいて使われるサンプルのテーブルを説明
する図である。 第３図は、本発明の方法の全体的な流れを示すフロー・
チャートである。 第４図は、ソート・インサート・フェーズを示すフロー
・チャートである。 第５図は、ソート・オーブン・フェースを示すフロー・
チャートである。 第６図は、ソート・フェッチ・フェースを示すフロー・
チャートである。 第７図は、出力モードを決定するオプテイマイザの処理
ステップを示すフロー・チャートである。 第８図は、メモリ内の内部バッファ中のデータと、ディ
スク上にできる多数の順序ストリングとの説明図である
。 第９図は、多数の順序ストリングを最終ソート済ストリ
ングにソートした結果を、ディスクへ、またはＲＤＳを
介してユーザへ渡す様子を示す説明図である。 出願人 インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人 弁理士 頓 宮 孝 （外１名） 第１日図 ＤＥＦＴ ＡＬＡＲＹ ４０Ｑ、００ ６５０．００ ９００．００ 第４図 第７図 エコ ｌｌｌ８ 図
タ処理の概要を説明する図である。 第２Ａ図と第２Ｂ図は、それぞれ、リレーショナル・デ
ータベースにおいて使われるサンプルのテーブルを説明
する図である。 第３図は、本発明の方法の全体的な流れを示すフロー・
チャートである。 第４図は、ソート・インサート・フェーズを示すフロー
・チャートである。 第５図は、ソート・オーブン・フェースを示すフロー・
チャートである。 第６図は、ソート・フェッチ・フェースを示すフロー・
チャートである。 第７図は、出力モードを決定するオプテイマイザの処理
ステップを示すフロー・チャートである。 第８図は、メモリ内の内部バッファ中のデータと、ディ
スク上にできる多数の順序ストリングとの説明図である
。 第９図は、多数の順序ストリングを最終ソート済ストリ
ングにソートした結果を、ディスクへ、またはＲＤＳを
介してユーザへ渡す様子を示す説明図である。 出願人 インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人 弁理士 頓 宮 孝 （外１名） 第１日図 ＤＥＦＴ ＡＬＡＲＹ ４０Ｑ、００ ６５０．００ ９００．００ 第４図 第７図 エコ ｌｌｌ８ 図
Claims (1)
- 【特許請求の範囲】 リレーショナル・データベース・システムにおける問合
せ文の処理方法であつて、 リレーショナル・データベース・マネジヤーによつて、
問合せ文を解析し、 上記解析結果に基づいて、上記問合せ文によるソート操
作の出力モードを選択する ことを特徴とする方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/179,181 US5089985A (en) | 1988-04-07 | 1988-04-07 | System and method for performing a sort operation in a relational database manager to pass results directly to a user without writing to disk |
| US179181 | 1988-04-07 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0212461A true JPH0212461A (ja) | 1990-01-17 |
| JP2510004B2 JP2510004B2 (ja) | 1996-06-26 |
Family
ID=22655565
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1085892A Expired - Fee Related JP2510004B2 (ja) | 1988-04-07 | 1989-04-06 | リレ―シヨナル・デ―タベ―ス・システムの問合せ文処理方法 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US5089985A (ja) |
| EP (1) | EP0336584B1 (ja) |
| JP (1) | JP2510004B2 (ja) |
| BR (1) | BR8901616A (ja) |
| CA (1) | CA1290456C (ja) |
| DE (1) | DE68927743T2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2012026140A1 (ja) * | 2010-08-25 | 2012-03-01 | 株式会社日立製作所 | データベース処理方法、データベース処理システム及びデータベースサーバ |
| JP2013033517A (ja) * | 2012-11-06 | 2013-02-14 | Hitachi Ltd | データベース処理方法及びデータベース処理システム |
| JPWO2016157271A1 (ja) * | 2015-03-27 | 2018-02-01 | 日本電気株式会社 | センサネットワークシステム |
Families Citing this family (35)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0833799B2 (ja) * | 1988-10-31 | 1996-03-29 | 富士通株式会社 | データ入出力制御方式 |
| EP0444358B1 (en) * | 1990-02-27 | 1998-08-19 | Oracle Corporation | Dynamic optimization of a single relation access |
| US5717928A (en) * | 1990-11-07 | 1998-02-10 | Matra Hachette Sa | System and a method for obtaining a mask programmable device using a logic description and a field programmable device implementing the logic description |
| JPH0827755B2 (ja) * | 1991-02-15 | 1996-03-21 | インターナショナル・ビジネス・マシーンズ・コーポレイション | データの単位を高速度でアクセスする方法 |
| US5794240A (en) * | 1992-05-26 | 1998-08-11 | Fujitsu Limited | Multi-threaded sorting system for a data processing system |
| US5765005A (en) * | 1992-06-01 | 1998-06-09 | Hitachi, Ltd. | Method for preparing form |
| US5423035A (en) * | 1992-12-23 | 1995-06-06 | Hughes Aircraft Company | Method for evaluating relational database queries with automatic indexing and ordering of join components |
| US5581473A (en) * | 1993-06-30 | 1996-12-03 | Sun Microsystems, Inc. | Method and apparatus for managing timing requirement specifications and confirmations and generating timing models and constraints for a VLSI circuit |
| US5630124A (en) | 1993-12-06 | 1997-05-13 | International Business Machines Corporation | System and method for assuring atomicity of distributed update requests in a parallel database |
| US6163783A (en) * | 1993-12-16 | 2000-12-19 | Bmc Software, Inc. | Check data operation for DB2 |
| US5579515A (en) * | 1993-12-16 | 1996-11-26 | Bmc Software, Inc. | Method of checking index integrity in a DB2 database |
| US5623693A (en) * | 1994-02-17 | 1997-04-22 | International Business Machines Corporation | System for performing action by sorting actions into immediate and deferred queues, processing immediate queue while still sorting, and appending deferred queue to immediate after sorting |
| US5689697A (en) * | 1994-06-27 | 1997-11-18 | International Business Machines Corporation | System and method for asynchronous database command processing |
| US5884297A (en) * | 1996-01-30 | 1999-03-16 | Telefonaktiebolaget L M Ericsson (Publ.) | System and method for maintaining a table in content addressable memory using hole algorithms |
| US5809501A (en) * | 1996-01-30 | 1998-09-15 | Telefonaktiebolaget L M Ericsson (Publ) | Method and system of database management in an asynchronous transfer mode (ATM) environment |
| US5799210A (en) | 1996-04-18 | 1998-08-25 | Oracle Corporation | Method for allocating either private or shared buffer memory for storing data from sort operations in accordance with an assigned value or threshold value |
| US5895465A (en) * | 1997-09-09 | 1999-04-20 | Netscape Communications Corp. | Heuristic co-identification of objects across heterogeneous information sources |
| US6263348B1 (en) * | 1998-07-01 | 2001-07-17 | Serena Software International, Inc. | Method and apparatus for identifying the existence of differences between two files |
| US6408292B1 (en) | 1999-08-04 | 2002-06-18 | Hyperroll, Israel, Ltd. | Method of and system for managing multi-dimensional databases using modular-arithmetic based address data mapping processes on integer-encoded business dimensions |
| US6385604B1 (en) | 1999-08-04 | 2002-05-07 | Hyperroll, Israel Limited | Relational database management system having integrated non-relational multi-dimensional data store of aggregated data elements |
| US20020029207A1 (en) | 2000-02-28 | 2002-03-07 | Hyperroll, Inc. | Data aggregation server for managing a multi-dimensional database and database management system having data aggregation server integrated therein |
| US7127416B1 (en) * | 2001-06-18 | 2006-10-24 | I2 Technologies Us, Inc. | Distributed processing of sorted search results in an electronic commerce system and method |
| US20030093566A1 (en) * | 2001-11-09 | 2003-05-15 | Jardin Cary A. | System and method for network and application transparent database acceleration |
| US7124137B2 (en) * | 2002-12-19 | 2006-10-17 | International Business Machines Corporation | Method, system, and program for optimizing processing of nested functions |
| US7243098B2 (en) * | 2002-12-19 | 2007-07-10 | International Business Machines Corporation | Method, system, and program for optimizing aggregate processing |
| US7080060B2 (en) * | 2003-01-08 | 2006-07-18 | Sbc Properties, L.P. | System and method for intelligent data caching |
| US7827282B2 (en) * | 2003-01-08 | 2010-11-02 | At&T Intellectual Property I, L.P. | System and method for processing hardware or service usage data |
| US7120864B2 (en) | 2004-01-27 | 2006-10-10 | International Business Machines Corporation | Eliminating superfluous namespace declarations and undeclaring default namespaces in XML serialization processing |
| US8046354B2 (en) * | 2004-09-30 | 2011-10-25 | International Business Machines Corporation | Method and apparatus for re-evaluating execution strategy for a database query |
| US7343367B2 (en) * | 2005-05-12 | 2008-03-11 | International Business Machines Corporation | Optimizing a database query that returns a predetermined number of rows using a generated optimized access plan |
| US8055665B2 (en) * | 2008-03-13 | 2011-11-08 | International Business Machines Corporation | Sorted search in a distributed directory environment using a proxy server |
| US7904464B2 (en) * | 2008-08-27 | 2011-03-08 | International Business Machines Corporation | Virtual list view support in a distributed directory |
| KR101679011B1 (ko) * | 2014-06-26 | 2016-11-24 | 주식회사 알티베이스 | 데이터베이스에서 데이터 이동을 처리하는 방법 및 장치 |
| CN106843803B (zh) * | 2016-12-27 | 2019-04-23 | 南京大学 | 一种基于归并树的全排序加速器及应用 |
| US12298911B2 (en) * | 2023-07-06 | 2025-05-13 | Sap Se | Spill-to-disk in projection operations |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4210961B1 (en) * | 1971-10-08 | 1996-10-01 | Syncsort Inc | Sorting system |
| US4514826A (en) * | 1981-05-18 | 1985-04-30 | Tokyo Shibaura Denki Kabushiki Kaisha | Relational algebra engine |
| US4510567A (en) * | 1981-05-18 | 1985-04-09 | International Business Machines Corp. | Qualifying and sorting file record data |
| US4417332A (en) * | 1981-06-15 | 1983-11-22 | Rca Corporation | Turntable speed control |
| JPS583031A (ja) * | 1981-06-30 | 1983-01-08 | Fujitsu Ltd | リレ−シヨナル・モデルにおけるジヨイン演算処理方式 |
| US4451901A (en) * | 1982-01-21 | 1984-05-29 | General Electric Company | High speed search system |
| US4628483A (en) * | 1982-06-03 | 1986-12-09 | Nelson Raymond J | One level sorting network |
| US4506326A (en) * | 1983-02-28 | 1985-03-19 | International Business Machines Corporation | Apparatus and method for synthesizing a query for accessing a relational data base |
| US4587628A (en) * | 1983-12-05 | 1986-05-06 | International Business Machines Corporation | Method and apparatus for dynamic invocation of utilities |
| US4611280A (en) * | 1984-03-12 | 1986-09-09 | At&T Bell Laboratories | Sorting method |
| US4829427A (en) * | 1984-05-25 | 1989-05-09 | Data General Corporation | Database query code generation and optimization based on the cost of alternate access methods |
| US4799152A (en) * | 1984-10-12 | 1989-01-17 | University Of Pittsburgh | Pipeline feedback array sorter with multi-string sort array and merge tree array |
| US4991134A (en) * | 1988-03-30 | 1991-02-05 | International Business Machines Corporation | Concurrent sorting apparatus and method using FIFO stacks |
-
1988
- 1988-04-07 US US07/179,181 patent/US5089985A/en not_active Expired - Lifetime
-
1989
- 1989-01-25 CA CA000589118A patent/CA1290456C/en not_active Expired - Lifetime
- 1989-03-16 EP EP89302582A patent/EP0336584B1/en not_active Expired - Lifetime
- 1989-03-16 DE DE68927743T patent/DE68927743T2/de not_active Expired - Fee Related
- 1989-04-06 JP JP1085892A patent/JP2510004B2/ja not_active Expired - Fee Related
- 1989-04-06 BR BR898901616A patent/BR8901616A/pt unknown
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2012026140A1 (ja) * | 2010-08-25 | 2012-03-01 | 株式会社日立製作所 | データベース処理方法、データベース処理システム及びデータベースサーバ |
| JP2012048332A (ja) * | 2010-08-25 | 2012-03-08 | Hitachi Ltd | データベース処理方法、データベース処理システム及びデータベースサーバ |
| US9348866B2 (en) | 2010-08-25 | 2016-05-24 | Hitachi, Ltd. | Database processing method, database processing system and database server |
| JP2013033517A (ja) * | 2012-11-06 | 2013-02-14 | Hitachi Ltd | データベース処理方法及びデータベース処理システム |
| JPWO2016157271A1 (ja) * | 2015-03-27 | 2018-02-01 | 日本電気株式会社 | センサネットワークシステム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0336584A2 (en) | 1989-10-11 |
| DE68927743T2 (de) | 1997-08-14 |
| US5089985A (en) | 1992-02-18 |
| EP0336584B1 (en) | 1997-02-05 |
| JP2510004B2 (ja) | 1996-06-26 |
| BR8901616A (pt) | 1989-11-21 |
| EP0336584A3 (en) | 1992-09-30 |
| DE68927743D1 (de) | 1997-03-20 |
| CA1290456C (en) | 1991-10-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0212461A (ja) | リレーシヨナル・データベース・システムの問合せ文処理方法 | |
| US6249783B1 (en) | Method and apparatus for efficiently executing built-in functions | |
| US6009265A (en) | Program product for optimizing parallel processing of database queries | |
| US5574900A (en) | System and method for optimizing parallel processing of database queries | |
| US5727196A (en) | Optimized query interface for database management systems | |
| EP0326927B1 (en) | Method and apparatus for processing a database | |
| US6694310B1 (en) | Data flow plan optimizer | |
| CA2104226A1 (en) | Database management system graphical query front end | |
| US20080059408A1 (en) | Managing execution of a query against selected data partitions of a partitioned database | |
| US5544298A (en) | Code generation and data access system | |
| US7720838B1 (en) | Methods and apparatus for joining tables from different data sources | |
| Smith et al. | Relational data base machines | |
| US8041726B2 (en) | System for executing a query having multiple distinct key columns | |
| US6269359B1 (en) | Relational data base system and method for rapidly realizing a query to a database | |
| JP2002366401A (ja) | 統合的データマート構築及び運用支援システム | |
| JPH07296009A (ja) | データベース統合検索装置 | |
| CN113886416A (zh) | 一种基于rbca模型构建的数据库的快速检索方法 | |
| JP3538322B2 (ja) | データベース管理システムおよび問合せの処理方法 | |
| JP3305782B2 (ja) | ソフトウェア標準化方法およびソフトウェア生産物の解析方法 | |
| JPS61170840A (ja) | 結合処理における中間データ生成方法 | |
| Kaiser et al. | A dialogue generator | |
| Patković et al. | Comparison of Spring JDBC and Hibernate Technologies in Interaction with PostgreSQL Database at Basic Level | |
| JPH01180630A (ja) | 情報検索装置 | |
| JP2000181691A (ja) | プログラム構造解析方式 | |
| JPH02166559A (ja) | データベース操作言語解析処理方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |