JPH0776936B2 - アクセス経路選択方法 - Google Patents

アクセス経路選択方法

Info

Publication number
JPH0776936B2
JPH0776936B2 JP1154809A JP15480989A JPH0776936B2 JP H0776936 B2 JPH0776936 B2 JP H0776936B2 JP 1154809 A JP1154809 A JP 1154809A JP 15480989 A JP15480989 A JP 15480989A JP H0776936 B2 JPH0776936 B2 JP H0776936B2
Authority
JP
Japan
Prior art keywords
index
rows
page
data
access
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.)
Expired - Lifetime
Application number
JP1154809A
Other languages
English (en)
Other versions
JPH0254347A (ja
Inventor
ジヨセフイン・ミユ‐クウンブ・チヤング
アキラ・シバミヤ
ヤン・ワング
Original Assignee
インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン filed Critical インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン
Publication of JPH0254347A publication Critical patent/JPH0254347A/ja
Publication of JPH0776936B2 publication Critical patent/JPH0776936B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

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/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • 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/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2272—Management thereof
    • 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
    • G06F16/24534—Query rewriting; Transformation
    • G06F16/24542—Plan optimisation
    • 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Operations Research (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は情報の管理、特にデータベース管理システムに
関する。
B.従来技術 データベース管理システムは、データを記録し保守する
ためのコンピユータ・システムである。リレーシヨナル
・データベース管理システムにおいて、データはテーブ
ル中の行として記憶され、テーブルの集まりがデータベ
ースと呼ばれる。データベースに対して要求又はコマン
ド（照会と呼ばれる）を出すことによりデータを操作
（選択、更新、挿入又は削除）することができる。リレ
ーシヨナル・データベース管理システムのデータ照会及
び操作言語、例えばSQLにおいて、要求は非手続き的
（ナビゲーシヨン的（navigational）とも呼ばれる）で
ある。即ち、ユーザーは、単に欲するものを指定するだ
けでよく、それをどのようにして達成するかを指定する
ことはない。システムのオプテイマイザが、ユーザーに
代つてデータを取得する最適の方法（又はアクセス経
路）を決定しなければならない。データにアクセスする
１つの方法は、探索基準に適合する行を求めてテーブル
中の各行を順次に操作することである。これは、最初か
ら最後までテーブル全体を順に走査するので、テーブル
走査として知られている。
データの行は、物理的記憶装置、通常はデイスク・ドラ
イブ又はフアイル上のページ上に記憶される。たとえ所
定のページのうち１行しか必要がなくても、データはペ
ージ単位で物理的記憶装置とコンピユータ・システムの
処理装置との間を転送される。物理的記憶装置と処理装
置との間のデータ転送に要する時間は、処理装置におけ
るデータの処理に要する時間よりも何倍も長い。さら
に、別個の物理的ページにランダムにアクセスするのに
要する時間は、隣接したページに順次にアクセスするの
に必要な時間よりも10倍程度長い。リレーシヨナル・デ
ータベース中のデータを操作するために、行は、最初に
物理的記憶装置から処理装置に転送され、次に処理装置
中で処理され、最後に物理的記憶装置に転送されなけれ
ばならない。転送は処理よりも長い時間がかかるので、
データを操作するのに必要な全時間は、転送の数が減少
できるならば大幅に減少できる。
多くのリレーシヨナル・データベース・システムは、そ
のテーブルのためにインデツクスを維持している。イン
デツクスは行とは別個に記憶されたリストであり、行を
選択された順次でアクセスするために使用される。イン
デツクスは、多くのインデツクス・エントリより構成さ
れ、その各々はキー値と、そのキー値を含む１つ以上の
行の識別子又は上記行に対するポインタを含んでいる。
インデツクスは物理的にインデツクス・ページに記憶さ
れる。
インデツクスのページを記憶する１つの方法はＢ木とし
てであり、これは根ページを有し、中間ページがルート
にぶら下がり、葉ページが木の最下位レベルで中間ペー
ジにぶら下がつている。Ｂ木という用語は「平衡木（ba
lanced tree）」の短縮形であり、そのような根又は中
間インデツクス・ページの各々が指すページが平衡して
いる即ちほぼ等しい数であるものを意味する。Ｂ木の葉
ページはインデツクス・エントリを含んでいる。インデ
ツクスにより指定された順序でテーブルの行を走査する
ために、インデツクスの葉ページが順次に走査され、各
葉ページ上のインデツクス・エントリがインデツクス順
で行をアクセスするために使われる。この走査はインデ
ツクス順序走査又は単にインデツクス走査と呼ばれる。
従来技術において、２つの型のインデツクス構成、即ち
完全クラスタ型及び非クラスタ型が存在する。インデツ
クスの葉ページを順次に走査する時に各データ・ページ
が１度だけしかアクセスされないならば、インデツクス
は完全クラスタ型である。この事が起きるためには、イ
ンデツクス順にアクセスされる時にデータ行は、それら
が物理的記憶装置のデータ・ページに記憶されているの
と同じ順序になっていなければならない。クラスタ化イ
ンデツクスのインデツクス走査（これはクラスタ化イン
デツクス走査とも呼ばれる）は高速である。というの
は、同じデータ・ページに対する重複アクセスが存在し
ないのでデータ・ページ・アクセスの数が最小限にな
り、またインデツクスの葉ページ及びデータ・ページの
両者がランダムではなく順次的にアクセスできるからで
ある。
インデツクスの葉ページが順次に走査される時にデータ
・ページがランダムに前後にアクセスされるならば、イ
ンデツクスは非クラスタ的である。非クラスタ的インデ
ツクスのインデツクス走査（これは非クラスタ的インデ
ツクス走査とも呼ばれる）は非常に遅い。というのは、
インデツクスにより離れたデータ・ページがランダムに
アクセスされ処理装置の主記憶に転送されるがそのよう
なページの各々の上にある多くの行から１行しかアクセ
スされないからである。
照会中のサーチ基準としてインデツクスのキーが使われ
る時、インデツクスはしばしば、サーチ基準に適合する
データ行を識別するための効率的なアクセス経路を提供
できる。いくつかの基準を有する複雑な照会が与えられ
る時、データベース・システムのオプテイマイザはしば
しば多数のインデツクスが利用可能であり、その各々は
サーチ基準と同じキーを有する。そこでオプテイマイザ
はデータ行をアクセスするための最良のインデツクスを
選択しなければならない。
C.発明が解決しようとする課題 従来技術は、照会に関するアクセス経路としてクラスタ
型インデツクス走査の望ましいことを教えている。しか
し、これまで、データの物理的クラスタリングは、全か
無が式に考えられてきた。クラスタリングの程度を考慮
に入れることがなければ、オプテイマイザは比較的多く
クラスタ化されたインデツクスと比較的少なくクラスタ
化されたインデツクスとを区別することができず、より
効率的でない経路を選択することがあり、不必要な物理
データ・ページのアクセスを生じることがある。
本発明の１つの目的は、インデツクスの物理的クラスタ
リングの程度を測定することである。
本発明の他の目的は、データベース管理システムに関し
てアクセス経路を選択する時にそのようなクラスタリン
グの程度を使用するための方法を提供することである。
本発明の他の目的は、インデツクスのクラスタリングの
程度に基いて、インデツクス走査中に必要なページのア
クセスを正確に評価することによりアクセス経路を選択
することである。
D.課題を解決するための手段 これらの目的は、リレーシヨナル・データベースのテー
ブルのインデツクス走査の間にアクセスされるデータ・
ページの数を評価するための方法によって達成される。
本発明の方法は最初にクラスタリング係数を計算する。
これは、インデツクス順の時に、データ・ページに記憶
されているのと同じ順序になっている行の数に直接、比
例する。このクラスタリング係数は、インデツクス走査
中にアクセスされるページの数を評価するために使われ
る。次に、アクセスされるページの数は、照会、結合
（join）、又はその他のインデツクスされたデータベー
ス操作に関するアクセス経路を選択するのに使用でき
る。
クラスタリング係数は、好ましくはクラスタ化した行の
行全体に対する比に、１よりも大きな因子を掛けること
により計算される。この因子は、近くのページ上にある
が、互いに隣り合つてはいないページ上の行にアクセス
する利点を考慮するためのものである。
E.実施例 Ｅ−１、クラスタ化したインデツクス 第１図に示すように、従業員データの行12を有するデー
タベース・テーブル10が、従業員の雇用された順番にデ
ータ・ページ13上に物理的に記憶されている。そのよう
なテーブル10は、名字のアルファベツトの増加する順
（昇順）に行12を配置するための第１のインデツクス1
4、年令の昇順に行を配置するための第２のインデツク
ス16、及び給与の減少する順（降順）に行を配置するた
めの第３のインデツクス18を有する。各インデツクス1
4、16、18は、多数のインデツクス・エントリ20を含ん
でいる。各インデツクス・エントリはキー値22（例えば
名字、年令又は給与）及びそのキー値を含む１つ以上の
行12へのポインタ24またはその行の識別子を含む。イン
デツクス14、16、18は物理的にはインデツクス・ページ
上に記憶されている。第２図は完全にクラスタ化したＢ
木インデツクス26を示す。木の根ページ28は図の上部に
あり、葉ページ30は下部にあり、中間ページ32は根と葉
との間にある。
本発明を理解するために、第１図の従業員テーブル10に
対して行なわれる下記の照会を考える。SELECT LAST.NA
MES FROM EMPLOYEE TABLE WHERE AGE＞＝40 AND SALARY
＜＝＄40,000 この照会は、少なくとも40才で且つ給与が40000ドル以
下の全ての従業員の名字を要求する。年令が40以上で且
つ給与が＄40000以下であるという条件は、この照会に
関するサーチ基準である。従業員テーブル10を見れば、
ThomasとSandersonだけがこれらの基準の両者を満足す
る。
それによつて、どの行がこれらのサーチ基準を満足する
かをオプテイマイザが決定できる最も単純なアクセス経
路は、テーブル走査、即ちテーブル10中の全ての行12
を、それらが記憶されている順序で順次に走査すること
である。各行がサーチ基準に適合するか否かを判定する
ために各行が検査される。第１図の従業員テーブルに関
して、テーブル走査は、３つのデータ・ページが主記憶
に転送され、テーブルの全部で６つの行が処理される必
要がある。いくつかの仮定をすると、このサーチを行な
うのに必要な時間は次のように評価できる。ページの順
次アクセスの各々は約２ミリ秒（2ms）必要であり、各
ランダム・アクセスは20ms、そして各行の処理は約0.1m
s必要である。従って、従業員テーブル10のテーブル走
査に必要な全時間は、次の通りである。
同じ照会は、年令インデツクス16を使つて、サーチ基準
AGE＞＝40を満足する行のみをアクセスするように部分
的インデツクス走査を実行することにより満足させられ
る。このアクセス経路を用いると、年令のサーチ基準に
適合する最初のエントリ、即ち40以上の最初のエントリ
が、年令（AGE）インデツクス16から探索される。次に
インデツクス中のその地点から前方へインデツクス走査
が行なわれる。第１データ・ページがランダムにアクセ
スされ、Matthewsの行が処理され捨てられる。次に第３
データ・ページが再びランダムにアクセスされ、Thomas
の行が処理され、次に第１データ・ページのBakerの行
が処理され、最後に第２データ・ページのSandersonの
行が処理される。これは完全に非クラスタ化したインデ
ツクス走査の例であり、サーチ基準の１つを満足するよ
うなインデツクスにより識別される各行は、その行を処
理するためにランダムなページのアクセスが必要であ
る。この非クラスタ的なインデツクス走査のコストの総
計は下記の通りである。
完全にクラスタ化したインデツクスによるクラスタ化イ
ンデツクス走査は、この例のオプシヨンとしては利用不
可能である。サーチ基準に対応するインデツクス、年令
インデツクス16及び給与インデツクス18のいずれも、完
全にはクラスタ化していない。従つて、従来技術によれ
ば、これらのインデツクスのいずれも、この照会に関す
るアクセス経路としては等しく効率的であり、従来技術
の方法を用いたアクセス経路選択のオプテイマイザはそ
れに従つて選択を行なうであろう。
第１図を視察すると、給与インデツクス18は、完全には
クラスタ化されていないが、ほぼクラスタ化されている
ことがわかる。給与インデツクス18によるインデツクス
走査は時間の消費がより少なく、従つて従業員テーブル
10全体のテーブル走査又は前記の年令インデツクス16に
よるインデツクス走査のどちらよりも効率的である。こ
の照会に関するアクセス経路として給与インデツクス18
を使用すると、給与のサーチ基準に適合する最初のエン
トリ、即ち＄40000以下の給与を有するものがインデツ
クスにより探索される。最初のそのようなエントリは給
与インデツクス18の第２インデツクス・ページ上に現れ
る。次にこのインデツクスの残りにわたつてインデツク
ス走査が行なわれ、インデツクスにより識別された各行
が照会に従つて処理される。例えば、第３のデータ・ペ
ージが転送され（ランダム・アクセス）、Thomasの行が
処理され選択される。次に、第２のデータ・ページ（再
び、ランダム・アクセス）が転送され、Sandersonの行
が処理され捨てられる。最後に、Jeffriesの行が処理さ
れる。Jeffriesの行はSandersonの行の次にクラスタ化
されているので、これはデータ・ページのアクセスを必
要としない。アクセス経路として給与インデツクス18を
用いたコストの合計は従つて下記の通りである。
従つて、比較的クラスタ化した給与インデツクス18は、
完全に非クラスタ的な年令インデツクス16よりも、この
照会に関して良好なアクセス経路を与える。
現実的な設定では、関与する行及びページの数は、上記
の例で使われた数字よりも何桁も大きい。100万行のデ
ータベース・テーブル、５万データ・ページにわたつて
拡がつたテーブルの行及び５千ページにわたるインデツ
クスのエントリを有するデータベースにおいて、行の２
％を最終的に選択するサーチ基準を持つ照会を行なう
時、順時テーブル走査、完全に非クラスタ的なインデツ
クス走査、又は90％のクラスタリングの度合を有するイ
ンデツクス走査に関して、次のようにテーブルのアクセ
スに必要な時間のおおまかな評価を行なうことができ
る。
順次走査 非クラスタ的インデツクス走査 90％のクラスタリングを有するインデツクス走査 最適のアクセス経路は明らかに、90％クラスタ化された
インデツクスを経由するものである。しかし、アクセス
経路選択の従来技術の方法は、この事を識別することが
できなかった。
Ｅ−２、クスタリングの程度 本発明において、「クラスタリングの程度」とは、与え
られたインデツクスの中のクラスタ化された行の数をテ
ーブルの中の行の総数で割つたものと定義される。従つ
て、クラスタリングの程度は、インデツクス順の時に、
行が記憶されている順序と同じ順序である行の数に比例
する。
クラスタ化された行の数は、テーブル全体をインデツク
ス走査することにより決定しうる。行は、もしそれが、
インデツクスにより以前に指定された行の直後に物理的
に記憶されているならば、クラスタ化されていると考え
られる。もしインデツクスの全ての行がこの定義に従っ
てクラスタ化されていれば、インデツクスは従来技術で
理解されるように完全にクラスタ化されている。もしテ
ーブルの行の90％が、インデツクス順の直前の行の後に
続いていれば、本発明によればインデツクスは90％クラ
スタ化されている。クラスタリングの程度のこの測度
は、テーブル対するインデツクスを用いたアクセス経路
の間で選択を行ない時に非常に有意義である。
Ｅ−３クラスタリングの程度を用いたアクセス経路選択 データベース・テーブルに対する照会が与えられた時、
オプテイマイザの仕事は、その照会に関する最速のアク
セス経路を選択することである。オプテイマイザは、テ
ーブル全体にわたる順次テーブル走査、又は照会のサー
チ基準の１つに対応するインデツクスを用いたインデツ
クス走査の間で選択を行なうことができる。２以上のサ
ーチ基準が対応インデツクスを有する場合、オプテイマ
イザは代替的な候補インデツクスの間で選択を行なわな
ければならない。
下記の例１は、テーブルに関する最速のインデツクス使
用アクセス経路を決定するための疑似コードで書かれた
プログラム断片を示す。
表１のプログラム断片は下記のように動作する。行101
〜105はデータベース・テーブルについての情報及びど
の候補インデツクスが考慮されているかに依存しない単
位時間に関する情報を集める。行101で、NRはテーブル
中の行の総数を記憶する。行102で、NPはNR行が記憶さ
れているデータ・ページの総数を記憶する。行103〜104
で、TARは１回のランダム・ページ・アクセスに必要な
時間を記憶し、TASは１回の順次ページ・アクセスに必
要な時間を記憶する。TARは典型的にはTASよりもずつと
大きい。行105のTPRは、データベース・システムのCPU
中で１つの行を処理するのに必要な時間を記憶する。
行106〜120の間のDOループは、オプテイマイザに与えら
れる照会中のサーチ基準の１つに対応する各インデツク
スを考慮する。クラスタリングの程度DCは行108で、候
補インデツクスに関するクラスタ化した行の数NCRを、
テーブル中の行の総数NRで割る事により計算される。ク
ラスタ化した行の数NCRは、考慮中のインデツクスを用
いてインデツクス走査を行ない、インデツクス走査中に
以前にアクセスされた行の直後に物理的に記憶された行
の数を計数することにより計算される。クラスタ化され
た行の数NCRは、インデツクスのクラスタリングの程度
を知る必要が生じる毎にインデツクス走査を行なうので
はなく、各インデツクス毎に１度だけ計算して記憶して
おく事が好ましい。
インデツクス中の葉ページの数NLPは行109で記憶され
る。行110はインデツクス中のレベルの数NLを計算す
る。第２図を参照すると、インデツクス26は３つのレベ
ルを有している。即ち根ページ28のレベル、中間ページ
32の１つのレベル及び葉ページ30のレベルである。レベ
ル数NLは、インデツクス走査中に必要なページ・アクセ
スの数の計算に含まれている。というのはインデツクス
の葉ページ30が走査される以前に、インデツクスに対応
する照会のサーチ基準を満足するインデツクス・エント
リ20を有する最初の葉ページ30に至るまでインデツクス
木26を探索しなければならないからである。
インデツクスのフイルタ因子FFは行111〜112で、インデ
ツクスに対応する選択基準に適合する行の数NRIを、テ
ーブル中の行の総数NRで割つたものとして計算される。
インデツクスのサーチ基準に適合する行の数NRIと行の
総数NRとの差はアクセスの効率を反映している。という
のはテーブルの全行NRにわたるテーブル走査（その多く
はサーチ基準に適合しない）の代りに、サーチ基準の１
つを満足する僅かの行NRIの走査を行なうからである。
従つてフイルタ因子FFは、インデツクス走査の期間中に
不適合行を消去する最のインデツクスの選択性に対応す
る。
インデツクス走査はランダム・ページ・アクセスと順次
ページ・アクセスの組み合せを必要とする。以前に説明
したように、ランダム・ページ・アクセスは、典型的な
場合、順次ページ・アクセスよりも10倍位長い実行時間
を要する。従つてそれはインデツクス走査に必要な合計
時間の相当大きな部分に寄与する。ランダム・ページ・
アクセスは、インデツクス木26を探索し、別のデータ・
ページ13上に散らばつた非クラスタ的な行にアクセスす
る必要がある。インデツクス木26を探索するのに必要な
ランダム・ページ・アクセスの数は、行110で計算され
た、インデツクス中のレベルの数NLに等しい。非クラス
タ的な行にアクセスするのに必要なページ・アクセスの
数は、インデツクスに対応するサーチ基準に適合する非
クラスタ行の数に等しいことが仮定される。テーブル中
の非クラスタ行の総数は、１とインデツクスに関するク
ラスタリングの程度DCとの差にテーブル中の全行数NRを
掛けたものとして計算される。インデツクスの対応する
サーチ基準に適合する非クラスタ的な行の数は、前記の
総和にインデツクスのフイルタ因子FFを掛けることによ
り計算される。これに対してインデツクス・レベルの数
NLが加算され、インデツクス走査に必要なランダム・ペ
ージ・アクセスの数NARが得られる。
インデツクス走査に必要な順次ページ・アクセスの数NA
Sは行114で計算される。インデツクス木が一旦、探索さ
れると、インデツクスの葉ページ30は順番にアクセスさ
れるので、順次ページ・アクセスが要求される。部分イ
ンデツクス走査中にアクセスされる葉ページ30の数は、
インデツクス中の葉ページの数NLPに（非適合行を消去
する際のインデツクスの選択性を反映させるように）イ
ンデツクスのフイルタ因子FFを掛けたものである。アク
セスされるべきクラスタ化した行の数は、クラスタ化し
且つ候補インデツクスに対応するサーチ基準に適合する
データ・ページ13の数に等しい。この数は、データ・ペ
ージの数NPに、インデツクスのフイルタ因子FF及びイン
デツクスのクラスタリングの程度DCの両者を掛けること
により計算される。順次アクセスの総数NASは、前記の
積に、上述のアクセスされるべきインデツクス葉ページ
の数を加算したものに等しい。
行113及び114でランダム及び順次ページ・アクセスの数
NAL、NASを計算した後、行115でページ・アクセスに必
要な全時間が、それらの数字に、各々に必要な時間を掛
けることにより計算される。これに、行116〜117で計算
される、インデツクス走査に関して必要な全処理時間が
加算され、その照会に関してテーブルへのアクセス経路
としてインデツクスを用いた場合の合計時間TIMEが評価
される。行119で、もし合計時間TIMEが、これまでに考
察したインデツクスの内で最短であれば、インデツクス
名が保存される。全ての候補インデツクスが行106〜120
のDCループで考察された後、その名前が現在保存されて
いるインデツクスは、全ての候補インデツクスのクラス
タリングの程度を考慮に入れて、最短の合計時間TIMEの
評価値を有している。もし照会に関するアクセス経路と
して、そのようにして識別されたインデツクスが使用さ
れると、そのインデツクスは他のどの候補インデツクス
よりも速く照会を処理するであろう。次にこのインデツ
クスの名前はオプテイマイザに渡され、照会に関するア
クセス経路を最終的に選択する時重要な因子として使用
される。
Ｅ−４、数値例 本発明の有用性及び利点をより良く（説明するために、
クラスタリングの程度DCが６％と、90％の２つのインデ
ツクスを用いたアクセス経路の比較の考察を行なう。従
来技術においてこれらのインデックスは等しく非クラス
タ的であると考えられ、それらの間の選択は任意的に行
なわれた事に留意されたい。
テーブルは1000000行を有し（NR＝1000000）、行は5000
0データ・ページにわたって分散している（NP＝50000）
ものと仮定する。さらにインデツクスは等しく選択的で
あり、２％のフイルタ因子を有する（FF＝２％）と仮定
する。さらに各インデツクスは５レベルの木の中に（NL
＝５）、5000の葉ページを有している（NLP＝5000）と
仮定する。最後に、ランダム・ページ・アクセスは20ミ
リ秒（TAR＝20ms）、順次ページ・アクセスは２ミリ秒
（TAS＝2ms）、そして１行を処理する時間は0.1ms（TPR
＝0.1ms）であると仮定する。
各インデツクスをアクセス経路として用いることにより
課される予測合計時間TIMEは次のように計算される。
性能における４倍の改善、即ち合計時間の75％の減少
が、テーブルへのアクセス経路として90％クラスタ化イ
ンデツクスを用いることにより達成される。これはラン
ダム・ページ・アクセスの数の大幅な減少によるもので
ある。表２の行113に示すように、60％クラスタ化した
インデツクスは8005回のランダム・ページ・アクセスを
必要とする。90％クラスタ化したインデツクスは2005回
のランダム・アクセスしか必要とせず、60％クラスタ化
したインデチクスに対して75％の減少を示し、且つ300
回の順次ページ、アクセスの増加というコストしか必要
としない。たとえ順次ページ・アクセスがランダム・ペ
ージ・アクセスよりも10倍速くないとしても、このトレ
ード・オフは行なう価値がある。しかし、これまではア
クセス経路オプテイマイザは、比較的よりクラスタ化し
たインデツクスを用いることにより得られる時間の節約
を識別することができなかつた。これらの時間の節約
は、クラスタリングの程度がより高いインデツクスを用
いることにより照会の処理に必要な全時間が75％減少し
た事からも証拠付けられるように、かなりのものになる
可能性がある。
説明のために本発明の特定の実施例を説明してきたが、
本発明の技術思想から逸脱することなく種々の変型や拡
張が可能である。例えば、クラスタリングの程度は、単
に全行に対するクラスタ化した行の比として計算するで
なく、非隣接行であるにもかかわらず、隣接又は近接し
たデータ・ページ上にある行を順次にアクセスする利点
を考慮するために、１よりも大きな乗数を掛ける事もあ
り得る。そのような乗数を用いることは、実際の状態を
より正確に反映する。但しその場合、クラスタリングの
程度は最大値が１に制限される。
本発明は、リレーシヨナル・データベースの照会だけに
限定されず、リレーシヨナル・データベース・テーブル
の結合（join）におけるアクセス経路の最適化にも容易
に適用される。さらに、リレーシヨナル・データベース
管理システムの分野以外に、他のデータ処理アプリケー
シヨンにおけるページ・アクセスを評価するという広い
領域でも本発明は価値を有している。リレーシヨナル・
データベースの分野以外では、データは「レコード」中
に記憶され、（上記のインデツクスに類似の）別の構造
がレコードに順次にアクセスするために使われている。
F.発明の効果 本発明を用いれば、データベースの操作時等に、最適の
インデツクス等を選択することができ、操作に必要な時
間を短縮することができる。
【図面の簡単な説明】
第１図はリレーシヨナル・データベース・テーブル及び
３つのインデツクスの例を示す図、 第２図は完全にクラスタ化したＢ木インデツクスを示す
図、 第３図は非クラスタ的なＢ木インデツクスを示す図であ
る。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ヤン・ワング アメリカ合衆国カリフオルニア州サニイヴ アレ、プレストウイツク・コート766番地 (56)参考文献 情報処理学会第23回（昭和56年後期）全 国大会講演論文集 Ｐ．513−514 情報処理学会第20回（昭和54年）全国大 会講演論文集 Ｐ．739−740 「ｂｉｔ別冊コンピュータ・サイエンス ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖ ｅｙｓ’84」（1986）共立出版 Ｐ．37− 71

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】処理装置と物理的な記憶装置を有している
    データ処理システムにおいて、データベーステーブル内
    に存在するデータページを最短時間で前記物理記憶装置
    から前記処理装置に転送するための最適化方法であっ
    て、前記データベーステーブルは前記物理記憶装置内の
    複数のデータページにまたがっており、複数のデータ行
    と該データ行を参照するためのエントリを含む複数のイ
    ンデックスとから構成され、前記最適化方法は、 サーチ基準を特定するデータベース操作コマンドを取得
    するステップと、 前記サーチ基準に係わる複数のインデックスを選択する
    ステップと、 前記選択されたインデックスに係わるクラスタリングの
    程度をそれぞれ求めるステップであって、前記クラスタ
    リングの程度は前記データ行がデータページに格納され
    ているときの順番と前記インデックスに格納されている
    順番との一致している度合いが大きいほど高いことを特
    徴とするものであり、 各々の前記選択されたインデックスに関する前記クラス
    タリングの程度と前記サーチ基準を用いて前記物理記憶
    装置からページ転送を行う全所要時間を計算するステッ
    プと、 前記計算の結果、最も前記全所要時間が短い前記選択さ
    れたインデックスに係わる順番で、前記物理記憶装置か
    ら前記処理装置に対してデータページを転送するステッ
    プと、 を含む方法。
JP1154809A 1988-07-15 1989-06-19 アクセス経路選択方法 Expired - Lifetime JPH0776936B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/219,622 US5043872A (en) 1988-07-15 1988-07-15 Access path optimization using degrees of clustering
US219622 1988-07-15

Publications (2)

Publication Number Publication Date
JPH0254347A JPH0254347A (ja) 1990-02-23
JPH0776936B2 true JPH0776936B2 (ja) 1995-08-16

Family

ID=22820033

Family Applications (1)

Application Number Title Priority Date Filing Date
JP1154809A Expired - Lifetime JPH0776936B2 (ja) 1988-07-15 1989-06-19 アクセス経路選択方法

Country Status (3)

Country Link
US (1) US5043872A (ja)
EP (1) EP0351388A3 (ja)
JP (1) JPH0776936B2 (ja)

Families Citing this family (67)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0360387B1 (en) * 1988-09-23 1996-05-08 International Business Machines Corporation Data base management system
US5161223A (en) * 1989-10-23 1992-11-03 International Business Machines Corporation Resumeable batch query for processing time consuming queries in an object oriented database management system
US5241648A (en) * 1990-02-13 1993-08-31 International Business Machines Corporation Hybrid technique for joining tables
EP0444358B1 (en) * 1990-02-27 1998-08-19 Oracle Corporation Dynamic optimization of a single relation access
US5261088A (en) * 1990-04-26 1993-11-09 International Business Machines Corporation Managing locality in space reuse in a shadow written B-tree via interior node free space list
JPH0415839A (ja) * 1990-05-10 1992-01-21 Toshiba Corp 分散データベース管理装置
US5355473A (en) * 1991-06-20 1994-10-11 Lawrence Au Indexed record locating and counting mechanism
JPH077422B2 (ja) * 1991-08-23 1995-01-30 インターナショナル・ビジネス・マシーンズ・コーポレイション コンピュータ処理データベース・システムにおけるジョインの実行方法及びシステム
US5301317A (en) * 1992-04-27 1994-04-05 International Business Machines Corporation System for adapting query optimization effort to expected execution time
US5404510A (en) * 1992-05-21 1995-04-04 Oracle Corporation Database index design based upon request importance and the reuse and modification of similar existing indexes
US5412806A (en) * 1992-08-20 1995-05-02 Hewlett-Packard Company Calibration of logical cost formulae for queries in a heterogeneous DBMS using synthetic database
US5765146A (en) * 1993-11-04 1998-06-09 International Business Machines Corporation Method of performing a parallel relational database query in a multiprocessor environment
CA2124094C (en) * 1994-05-20 1999-07-20 K. Bernhard Schiefer Method and apparatus for optimizing data retrieval using index scanning
US5758144A (en) * 1994-06-24 1998-05-26 International Business Machines Corporation Database execution cost and system performance estimator
US5664172A (en) * 1994-07-19 1997-09-02 Oracle Corporation Range-based query optimizer
US5671403A (en) * 1994-12-30 1997-09-23 International Business Machines Corporation Iterative dynamic programming system for query optimization with bounded complexity
US5548755A (en) * 1995-02-17 1996-08-20 International Business Machines Corporation System for optimizing correlated SQL queries in a relational database using magic decorrelation
US5778354A (en) * 1995-06-07 1998-07-07 Tandem Computers Incorporated Database management system with improved indexed accessing
GB9526096D0 (en) 1995-12-20 1996-02-21 British Telecomm Specifying indexes for relational databases
US5778364A (en) * 1996-01-02 1998-07-07 Verity, Inc. Evaluation of content of a data set using multiple and/or complex queries
US5670912A (en) * 1996-01-31 1997-09-23 Motorola, Inc. Variable supply biasing method and apparatus for an amplifier
US5913205A (en) * 1996-03-29 1999-06-15 Virage, Inc. Query optimization for visual information retrieval system
US5924088A (en) * 1997-02-28 1999-07-13 Oracle Corporation Index selection for an index access path
US5903888A (en) * 1997-02-28 1999-05-11 Oracle Corporation Method and apparatus for using incompatible types of indexes to process a single query
US6047284A (en) 1997-05-14 2000-04-04 Portal Software, Inc. Method and apparatus for object oriented storage and retrieval of data from a relational database
US6285996B1 (en) * 1997-07-10 2001-09-04 International Business Machines Corp. Run-time support for user-defined index ranges and index filters
US6266663B1 (en) 1997-07-10 2001-07-24 International Business Machines Corporation User-defined search using index exploitation
US6192358B1 (en) 1997-07-10 2001-02-20 Internatioanal Business Machines Corporation Multiple-stage evaluation of user-defined predicates
US6253196B1 (en) 1997-07-10 2001-06-26 International Business Machines Corporation Generalized model for the exploitation of database indexes
US6278994B1 (en) 1997-07-10 2001-08-21 International Business Machines Corporation Fully integrated architecture for user-defined search
US6219662B1 (en) 1997-07-10 2001-04-17 International Business Machines Corporation Supporting database indexes based on a generalized B-tree index
US6278990B1 (en) 1997-07-25 2001-08-21 Claritech Corporation Sort system for text retrieval
US5940819A (en) * 1997-08-29 1999-08-17 International Business Machines Corporation User specification of query access paths in a relational database management system
US7711672B2 (en) * 1998-05-28 2010-05-04 Lawrence Au Semantic network methods to disambiguate natural language meaning
US8396824B2 (en) * 1998-05-28 2013-03-12 Qps Tech. Limited Liability Company Automatic data categorization with optimally spaced semantic seed terms
US20070294229A1 (en) * 1998-05-28 2007-12-20 Q-Phrase Llc Chat conversation methods traversing a provisional scaffold of meanings
US6112197A (en) * 1998-05-29 2000-08-29 Oracle Corporation Method and apparatus for transmission of row differences
US6389425B1 (en) 1998-07-09 2002-05-14 International Business Machines Corporation Embedded storage mechanism for structured data types
US6470330B1 (en) * 1998-11-05 2002-10-22 Sybase, Inc. Database system with methods for estimation and usage of index page cluster ratio (IPCR) and data page cluster ratio (DPCR)
US6397204B1 (en) 1999-06-25 2002-05-28 International Business Machines Corporation Method, system, and program for determining the join ordering of tables in a join query
US6374235B1 (en) 1999-06-25 2002-04-16 International Business Machines Corporation Method, system, and program for a join operation on a multi-column table and satellite tables including duplicate values
US6446063B1 (en) 1999-06-25 2002-09-03 International Business Machines Corporation Method, system, and program for performing a join operation on a multi column table and satellite tables
GB9915465D0 (en) 1999-07-02 1999-09-01 Lenzie Robert S Identified preferred indexes for databases
RU2163393C1 (ru) * 2000-02-01 2001-02-20 Халин Евгений Васильевич Автоматизированная система учета несчастных случаев на производстве
US6678675B1 (en) 2000-03-30 2004-01-13 Portal Software, Inc. Techniques for searching for best matches in tables of information
US8099393B2 (en) 2002-03-22 2012-01-17 Oracle International Corporation Transaction in memory object store
US7447786B2 (en) * 2003-05-09 2008-11-04 Oracle International Corporation Efficient locking of shared data that is accessed for reads in a cluster database
US20050197860A1 (en) * 2004-02-23 2005-09-08 Rademr, Inc. Data management system
US8046354B2 (en) * 2004-09-30 2011-10-25 International Business Machines Corporation Method and apparatus for re-evaluating execution strategy for a database query
AU2005100125B4 (en) * 2005-02-11 2006-11-30 Mojarrabi, Bahram Mr Scale free network of urban traffic
US8223935B2 (en) 2005-04-30 2012-07-17 Oracle International Corporation Revenue management systems and methods
US8116326B2 (en) 2005-06-28 2012-02-14 Oracle International Corporation Revenue management system and method
US7809675B2 (en) * 2005-06-29 2010-10-05 Oracle International Corporation Sharing state information among a plurality of file operation servers
EP1938193A4 (en) 2005-07-28 2010-08-04 Oracle Int Corp SYSTEM AND METHOD FOR MANAGING RECIPES
US8223777B2 (en) 2005-11-15 2012-07-17 Oracle International Corporation Gateway for achieving low latency and high availability in a real time event processing system
US7930559B1 (en) * 2006-06-30 2011-04-19 Emc Corporation Decoupled data stream and access structures
US7640262B1 (en) * 2006-06-30 2009-12-29 Emc Corporation Positional allocation
US8789028B2 (en) * 2006-06-30 2014-07-22 International Business Machines Corporation Memory access monitoring
US20080189268A1 (en) * 2006-10-03 2008-08-07 Lawrence Au Mechanism for automatic matching of host to guest content via categorization
US8200660B2 (en) * 2009-10-22 2012-06-12 Hewlett-Packard Development Company, L.P. System and method for executing queries
US9171044B2 (en) * 2010-02-16 2015-10-27 Oracle International Corporation Method and system for parallelizing database requests
US10417611B2 (en) 2010-05-18 2019-09-17 Salesforce.Com, Inc. Methods and systems for providing multiple column custom indexes in a multi-tenant database environment
US8935233B2 (en) * 2010-09-28 2015-01-13 International Business Machines Corporation Approximate index in relational databases
JP6020448B2 (ja) 2011-06-08 2016-11-02 日本電気株式会社 データベース性能予測装置及びデータベース予測方法
US10108648B2 (en) * 2011-07-13 2018-10-23 Salesforce.Com, Inc. Creating a custom index in a multi-tenant database environment
US10459810B2 (en) 2017-07-06 2019-10-29 Oracle International Corporation Technique for higher availability in a multi-node system using replicated lock information to determine a set of data blocks for recovery
CN119862220A (zh) * 2024-12-09 2025-04-22 清华大学 一种数据库原生时间序列聚类方法和装置

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4631673A (en) * 1985-01-22 1986-12-23 International Business Machines Corporation Method for refreshing multicolumn tables in a relational data base using minimal information
US4769772A (en) * 1985-02-28 1988-09-06 Honeywell Bull, Inc. Automated query optimization method using both global and parallel local optimizations for materialization access planning for distributed databases
US4817050A (en) * 1985-11-22 1989-03-28 Kabushiki Kaisha Toshiba Database system
US4805134A (en) * 1986-01-09 1989-02-14 International Business Machines Corporation Electronic system for accessing graphical and textual information

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
「ｂｉｔ別冊コンピュータ・サイエンスＡＣＭＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓ’８４」（１９８６）共立出版Ｐ．３７−７１
情報処理学会第２０回（昭和５４年）全国大会講演論文集Ｐ．７３９−７４０
情報処理学会第２３回（昭和５６年後期）全国大会講演論文集Ｐ．５１３−５１４

Also Published As

Publication number Publication date
JPH0254347A (ja) 1990-02-23
EP0351388A3 (en) 1992-10-14
US5043872A (en) 1991-08-27
EP0351388A2 (en) 1990-01-17

Similar Documents

Publication Publication Date Title
JPH0776936B2 (ja) アクセス経路選択方法
US5758146A (en) Method and apparatus for optimizing data retrieval using index scanning
O'Neil et al. Multi-table joins through bitmapped join indices
US6161109A (en) Accumulating changes in a database management system by copying the data object to the image copy if the data object identifier of the data object is greater than the image identifier of the image copy
US6778977B1 (en) Method and system for creating a database table index using multiple processors
JP2583010B2 (ja) 多層インデックス構造におけるローカルインデックステーブル及び大域インデックステーブルの間の一貫性を維持する方法
US7987200B2 (en) Method and apparatus for predicting selectivity of database query join conditions using hypothetical query predicates having skewed value constants
US9430526B2 (en) Method and system for temporal aggregation
US5899986A (en) Methods for collecting query workload based statistics on column groups identified by RDBMS optimizer
US5758144A (en) Database execution cost and system performance estimator
US5265244A (en) Method and system for facilitating processing of statistical inquires on stored data accessible through a data access structure
US6266660B1 (en) Secondary index search
US6122644A (en) System for halloween protection in a database system
US20030061244A1 (en) System and method for database query optimization
JPH10143538A (ja) 一般化されたキーインデックス
US7319995B2 (en) Method and system for inclusion hash joins and exclusion hash joins in relational databases
US20050262158A1 (en) System and method for externally providing database optimizer statistics
JP4071816B1 (ja) 合成関係演算を利用したマルチオペレーション・プロセッシングを用いたデータベースのクエリー処理システム
US6944633B1 (en) Performing a join in a partitioned database system
CA2433377A1 (en) Computing frequent value statistics in a partitioned relational database
JP3653333B2 (ja) データベース管理方法およびシステム
Luo Partial materialized views
US7127457B1 (en) Method and system for executing database queries
Kumar et al. The effect of join selectives on optimal nesting order
JPH032938A (ja) データベース処理方法