JPH09330324A - 並列検索技術 - Google Patents

並列検索技術

Info

Publication number
JPH09330324A
JPH09330324A JP9057583A JP5758397A JPH09330324A JP H09330324 A JPH09330324 A JP H09330324A JP 9057583 A JP9057583 A JP 9057583A JP 5758397 A JP5758397 A JP 5758397A JP H09330324 A JPH09330324 A JP H09330324A
Authority
JP
Japan
Prior art keywords
search
list
data
processing system
parallel
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.)
Pending
Application number
JP9057583A
Other languages
English (en)
Inventor
Peter Graham Braun Anthony
ペーター グラハム ブラウン アンソニー
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Services Ltd
Original Assignee
Fujitsu Services Ltd
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 Fujitsu Services Ltd filed Critical Fujitsu Services Ltd
Publication of JPH09330324A publication Critical patent/JPH09330324A/ja
Pending 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/24—Querying
    • G06F16/245—Query processing
    • G06F16/2453—Query optimisation
    • G06F16/24532—Query optimisation of parallel queries
    • 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/953—Organization of data
    • Y10S707/954—Relational
    • 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/99933—Query processing, i.e. searching

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

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は並列検索技術に関し、全
てそれに限定される訳ではないが、特に関連データベー
スを並列的に検索する技術に関するものである。
【０００２】
【従来の技術】関連データベース管理システム(relatio
nal database management system:ＲＤＢＭＳ）におい
て、データベース格納スペースは、通常複数のディスク
上に格納される１又はそれ以上のファイルを有する。Ｒ
ＤＢＭＳにとっては、関連データベースを検索する際そ
れらのファイル各々をできるだけ迅速に読み取ることが
望ましい。従って、この問題を解決するための種々の解
法が提案されている。
【０００３】提案された最初の解法においては、ファイ
ルが複数の断片(fragments)に分割され、その分割され
た断片がそれぞれデータスペースに格納される。ファイ
ル検索時、独立したスレッド(thread)が、全てのスレッ
ドをビジー状態に維持するため用いられる各断片・処理
スケジューリング、スレッドスケジューリング及び多重
プロセッサハードウェアに対して起動される。ＲＤＭＢ
Ｓはどこにデータが格納されるか関知しないため、スレ
ッドは相互に干渉してもしなくてもよいが、２つのスレ
ッドが同じディスクを同時にアクセスしたときには干渉
が生じ、それは頻繁なヘッド運動をもたらし、またデー
タ転送速度を減少させる。
【０００４】提案された別の解法においては、ファイル
は複数の区画(partitions)に分割され、それら区画がそ
れぞれ独立して実行可能な異なった処理に送られる。そ
れらの処理はデータの物理的配置について関知しないた
め、相互に干渉してもしなくてもよい。
【０００５】提案された更に別の解法においては、低レ
ベルの処理がユーザの入力／出力作業を監視し、そして
連続的なアクセスが用いられているようであるときに
は、アプリケーション要求を見越し、その処理は大規模
多重ブロック読取を起動する。
【０００６】更にまた、ディスクの各セットがそれ自身
のプロセッサを有するために検索が多重プロセッサ間で
分割され得るような「大量で並列的な」解法も提案され
ている。
【０００７】
【発明が解決しようとする課題】本発明は、並列検索を
行う技術であって改良されたものを提供することを目的
とする。
【０００８】
【課題を解決するための手段】本発明によれば、複数の
データ格納ユニット、及び１又はそれ以上のファイル内
で検索されるべきデータ領域のリストを特定する検索要
求を生成するアプリケーションを具備するデータ処理シ
ステムであって、(a) ファイルがデータ格納ユニット
にマッピングされる方法を示すマッピングテーブルをク
リエイトする手段、(b) 複数の検索リストをクリエイ
トするためデータ領域の前記リスト及び前記マッピング
テーブルを利用する手段、ここで１つの検索リストは複
数のデータ格納ユニットの各々と関連し、各検索リスト
はデータ格納ユニットのそれぞれ１つにマッピングされ
るデータ領域又はそれらの部分を特定する、及び(c)
それぞれのデータ格納ユニットに対する複数の検索を、
検索リストを用いて並列に開始する手段、を具備するこ
とを特徴とするデータ処理システムが提供される。
【０００９】
【実施例】以下、本発明による並列検索技術の一例につ
いて、添付図面を参照しつつ説明する。
【００１０】図１は、オペレーティングシステム１１及
びアプリケーションソフトウェア１２を有するホストプ
ロセッサ１０を具備するコンピュータシステムを示す。
例えば、このホストプロセッサは本願の出願人であるイ
ンターナショナルコンピュータ社（ＩＣＬ）製の「ＩＣ
Ｌ ＤＲＳ ６０００プロセッサ」でよく、またオペレ
ーティングシステムもＩＣＬ製の「ＩＣＬ ＮＸオペレ
ーティングシステム」でよい。
【００１１】ホストプロセッサは、各々が複数のディス
クドライブ１４と接続される複数のＳＣＳＩチャネル１
３（本実施例では２つ）を有する。各ＳＣＳＩチャネル
はまた、ディスクに格納されたデータの検索を行うた
め、そのチャネルに接続される検索加速ユニット１５を
有する。本実施例においては、検索加速ユニット１５は
ＩＣＬ製の「ＩＣＬ ＳＣＡＦＳユニット」である。
【００１２】アプリケーションソフトウェアは、関連デ
ータベース管理システム（ＲＤＢＭＳ）１６、照会マネ
ージャ１７及び並列検索マネージャ１８を有する。ＲＤ
ＭＢＳ１６及び照会マネージャ１７は従来のものである
ため、それらについての詳細な説明は省略する。一方、
並列検索マネージャ１８については、以下、より詳細に
説明する。
【００１３】オペレーティングシステムは、ファイル格
納マネージャ・論理ボリュームマネージャ１９、ＳＣＡ
ＦＳドライバ２０、スケジューラ２１及びファイル格納
マッピング部２２を有する。ファイル格納マネージャ・
論理ボリュームマネージャ１９は従来のものでよいた
め、これについての詳細な説明は省略する。ＳＣＡＦＳ
ドライバ２０はＩＣＬ製のものであり、オペレーティン
グシステムとＳＣＡＦＳユニットとの間のインターフェ
ースを行う。ファイル格納マッピング部２２について
は、以下、より詳細に説明する。
【００１４】ＲＤＢＭＳ１６は、ディスク上に格納され
た関連データベースを管理する。データベース格納スペ
ースは複数のファイルからなる。各ファイルは、各々が
近接してアドレスされた１セットのブロックからなる複
数のデータ領域（以下、「広さ」と称する）を有する。
【００１５】ファイル格納マッピング部２２の機能は、
特定されたファイルを物理的ディスク上にマッピングす
る方法を示すマッピングテーブルを生成することにあ
る。呼び出しがあると、ファイル格納マッピング部２２
はファイル格納マネージャ・論理ボリュームマネージャ
１９とのインターフェースを行い、ファイルに関するマ
ッピング情報を検索する。また、他のユーザによる再配
置(relocation)動作に対抗するため、ファイルをロック
するようにしてもよい。ファイル格納マッピング部２２
は、ツリー構造としてファイルのマッピングを示すマッ
ピングテーブルを、テーブル内のエントリーの数の指示
と共に、戻す。
【００１６】マッピングテーブルは、各々がツリー構造
内の要素を示す一連のエントリーを含む。各エントリー
は以下のフィールドを有する。 「レベル番号」 「要素の数」 「タイプ(type)」 「タイプ依存データ」
【００１７】ここで、「レベル番号」はツリー構造内の
要素のレベルを示すものであり、レベル０がツリーの底
部である。
【００１８】また、「要素の数」は、ツリー構造の次の
レベルにおいて、この要素にどれくらいの数の要素（も
しあれば）が付されるのかを示すものである。
【００１９】また、「タイプ」は要素のタイプ（型）を
示すものであり、以下のようなタイプが規定されてい
る。 「ファイルシステム」：ファイルシステムに格納される
ファイルである。 「未加工(raw)」：物理的ディスクの全部又は一部とし
て格納された論理ボリュームである。 「連結(concat)」：１又はそれ以上の要素論理ボリュー
ムの連結である論理ボリュームである。 「ストライプ(striped)」：固定されたストライプサイ
ズで同サイズの要素論理ボリュームのセットにストライ
プされる論理ボリュームである。ここで、「ストライ
プ」を行うということは、論理的に、ボリュームの連続
セグメントを要素ボリュームの固定されたセットに対
し、ａ、ｂ、ｃ、ａ、ｂ、ｃ、…の如く連続的(round r
obin basis)に割り当てることをいう。 「ミラー(mirrored)」：２又はそれ以上の同サイズの論
理ボリュームについて複製又は繰り返されている情報が
ミラー処理（鏡映処理）されている論理ボリュームであ
る。
【００２０】また、「タイプ依存データ」は以下のよう
に特定される。 「ファイルシステム」：名称 「未加工」：ディスクの名称、オフセット及び長さ 「連結」：論理ボリュームの名称及びサイズ 「ストライプ」：ストライプサイズ 「ミラー(mirrored)」：サイズ
【００２１】ディスク名称は、ディスクがどのチャネル
に付されるか、及びそのチャネル上のそのＳＣＳＩアド
レスを示すものである。
【００２２】例えば、ファイル用のマッピングテーブル
は以下のようなエントリーを含むことができる。 レベル番号 要素の数 タイプ タイプ依存データ ０ ３ 連結 ボリュームＡ、サイズ＝８Ｍｂ １ ０ 未加工 ディスク１、オフセット＝０、 長さ＝２．５Ｍｂ １ ０ 未加工 ディスク２、オフセット４８ｋ、 長さ＝３Ｍｂ １ ０ 未加工 ディスク３、オフセット２Ｍｂ、 長さ＝２．５Ｍｂ
【００２３】このマッピングテーブルは、論理ボリュー
ムＡにマッピングされるファイルを示すものである。具
体的には、各々が独立した物理的ディスクに格納される
３つの断片に順にマッピングされる。図２に示すよう
に、このマッピングはツリー構造として図表的に表すこ
とができる。
【００２４】ＲＤＢＭＳは、データベース照会を受信す
ると、その照会を分析して、照会に対して回答するため
にどのファイル及びそれらファイル内のどの範囲をアク
セスする必要があるか発見する。この分析から、ＲＤＢ
ＭＳは複数のエントリーからなるデータベース範囲リス
トを生成する。なお、データベース範囲リストは、アク
セスされるべき範囲ごとに１つ生成される。各エントリ
ーは、以下の項目を含む。 「ファイルの参照（ファイル記述子又はファイルのフル
ネーム）」 「ファイルのスタートに関連する範囲のスタートのオフ
セット」 「この範囲内で検索されるべきデータ領域の長さ」
【００２５】ＲＤＭＢＳは、その後、並列検索マネージ
ャにバルク(bulk)入力要求を送る。このバルク入力要求
は、以下の２つの項目からなる。 「検索されるべき範囲の数」 「データスペース範囲リストに対するポインタ」
【００２６】図３は、並列検索マネージャ１８がＲＤＢ
ＭＳからバルク入力要求を受け付けたときのの動作を示
すフロー図である。
【００２７】（ステップ３１）並列検索マネージャは、
まずデータスペース範囲リストを走査してこのリスト内
でどのファイルが参照されるのか特定する。このステッ
プは、以下の情報を有するファイルリストを生成する。 「ファイルの数」 「ファイルに対する１セットのポインタ」
【００２８】（ステップ３２）ファイルリスト内の各フ
ァイルについて、並列検索マネージャはシステム呼び出
しを介してファイル格納マッピング部２２に対する要求
を作成する。各要求に応答して、ファイル格納マッピン
グ部２２は、どのようにファイルが物理的ディスク上に
マッピングされるかを示すマッピングテーブルを、上述
のように戻す。
【００２９】（ステップ３３）マッピング部により戻さ
れたマッピングテーブルを用いて、並列検索マネージャ
は、検索に含めることができる物理的ディスクのリス
ト、及び各ディスクのデータを有することができる１又
は複数のファイルのリストを構築する。
【００３０】（ステップ３４）並列検索マネージャはそ
の後、検索に含めることができる物理的ディスクの各々
を順々に選択する外側ループ(outer loop)を実行する。
この外側ループ内には、現在選択されているディスク上
のデータを有することができるファイルの各々を順々に
選択する内側ループ(inner loop)がある。内側ループ
は、「検索リストをクリエイトする」ルーチンを有す
る。このルーチンは、選択されたディスク上にマッピン
グを行う選択されたファイルの範囲又は部分的範囲を確
認・識別する検索リストを生成する。検索リスト内の範
囲は論理的な項（ファイル、オフセット、長さとしての
もの）で識別されるので、ディスクミラー(disk mirro
r)処理が失敗したりファイルシステムそれ自体が片づけ
られたりしても、リストは依然として有効である。
【００３１】以下、図３を参照して「検索リストをクリ
エイトする」ルーチンについて詳細に説明する。
【００３２】（ステップ３５）要求された検索リストが
全てクリエイトされると、特定されたディスクの特定さ
れた範囲を介して検索を開始するため、各リストはその
要求により別個にＳＣＡＦＳドライバ２０に移されても
よい。
【００３３】ＳＣＡＦＳドライバ２０は、ファイルオフ
セットをディスクオフセット（ディスクアドレス）へ翻
訳し、そしてリストをそれぞれのＳＣＡＦＳユニットへ
移す。幾つかのＳＣＡＦＳ検索が並列的に開始される
と、それにより影響を受けた全てのディスクが同時にビ
ジー状態となる。各ＳＣＡＦＳユニットは要求された検
索を行い、そして選択された行又は記録のストリームを
ホストに戻す。
【００３４】それに代えて、第１の非空(non-empty)検
索リストが生成されると直ちにディスク検索が開始され
ることも可能である。並列検索の数を制限し、そして実
行されている検索を終了させながら新たな検索リストを
生成することもまた可能である。並列ディスク検索を異
なるＳＣＳＩチャネルに割り当て、システム資源(resou
rces)上の負荷を拡散させることがより好ましいので、
このことは有用である。
【００３５】（ステップ３６）並列検索マネージャは、
各ストリーム上の戻りデータをチェックし、ＲＤＢＭＳ
が有効になったときに、それらＲＤＢＭＳについての全
てのストリームの結果を結合させ、又は組み合わせる。
【００３６】図４は、上述の「検索リストをクリエイト
する」ルーチンを示す図である。このルーチンは、現在
の目標ディスクへマッピングを行う現在の目標ファイル
の部分を特定するものである。
【００３７】（ステップ４１）「検索リストをクリエイ
トする」ルーチンは、ＲＤＢＭＳから送られたデータベ
ース範囲リストを走査し、ここからファイル範囲リスト
をクリエイトする。このファイル範囲リストは、現在選
択されているファイル内においてオフセット昇順で検索
されるべき複数の範囲のリストからなる。
【００３８】（ステップ４２）このルーチンは、バイト
カウント値をゼロに初期化し、ファイル範囲リスト上の
最初の範囲を選択する。更にこのルーチンは、マッピン
グテーブルの開始点にポインタを置く。
【００３９】（ステップ４３）このルーチンはその後、
ポインタをマッピングテーブルを介して進め、物理的デ
ィスク断片と関係する次のエントリー（即ち、「未処
理」タイプのエントリー）を検索する
【００４０】（ステップ４４）断片に関する次のエント
リーが発見されると、このルーチンはその断片の長さを
付加することによりバイトカウントをイクリメントす
る。従って、バイトカウントは断片の終端の位置を示す
ことになる。
【００４１】（ステップ４５）このルーチンはその後、
バイトカウントが現在選択されている範囲のオフセット
値より大きいか否か、即ちその範囲が（少なくとも部分
的に）断片にマッピングするか否かをチェックする。も
し大きければ、このルーチンはステップ４６に進み、そ
うでなかったら次の断片を検索するため上述のステップ
４３に戻る。
【００４２】（ステップ４６）このルーチンは、断片が
目標ディスク（即ち、現在選択されているディスク）上
にあるか否かチェックする。もしあるなら、このルーチ
ンはステップ４７に進み、そうでなかったらステップ５
０に進む。
【００４３】（ステップ４７）断片が目標ディスク上に
あれば、このルーチンは範囲と断片との重複を特定す
る。その後、出力検索リスト内のエントリーをクリエイ
トする。このエントリーは、ファイル名、オフセット及
び重複領域の長さを含んでいる。（付加的なリフレッシ
ュ方法として、ディスクオフセットはまたエントリー内
に含まれることができ、そしてディスク検索範囲を決定
し、ディスクヘッド運動を最小にするため用いられるこ
とができる。）
【００４４】（ステップ４８）このルーチンは、その
後、現在選択されている範囲が使い果たされたか否か、
即ちバイトカウントがその範囲のオフセットと長さとの
合計より大きいか否かをチェックする。もしその範囲が
使い果たされていれば、このルーチンはステップ４９に
進み、もし使い果たされていなければ（即ち、その範囲
が次の断片へ継続するならば）、このルーチンは上述の
ステップ４３に戻り、そして次の断片を検索する。
【００４５】（ステップ４９）もし現在選択されている
範囲が使い果たされていれば、ファイル範囲リスト内の
次の範囲がここで選択され、そしてルーチンは上述のス
テップ４５に戻る。
【００４６】（ステップ５０）もし現在選択されている
断片が目標ディスク上になければ、バイトカウントがそ
の範囲のオフセットと長さとの合計より大きいか否か、
即ち現在選択されている範囲が断片内で終端しているか
否かチェックする。もし大きければ、このルーチンはス
テップ５１に進み、そうでなければ上述のステップ４３
に戻り次の断片を検索する。
【００４７】（ステップ５１）このルーチンは、ファイ
ル範囲リスト内で次の範囲を選択し、そしてステップ５
０に戻る。
【００４８】ステップ４３乃至５１からなる上述のルー
プは、処理すべきファイル範囲リスト内にこれ以上範囲
がないことが（ステップ４９又は５１で）分かるまで繰
り返される。その前（即ち、処理すべき断片がこれ以上
ないことが分かる前）にマッピングテーブルの終端に達
してしまうと、エラーが生ずる。
【００４９】ミラー処理されるボリュームのため、断片
の検索は１つのミラー処理にのみ従う。検索されるべき
ミラー処理についての実際の決定は、オペレーティング
システムにより行われる。
【００５０】要約すると、並列照会マネージャは、検索
されるべき範囲のリストを受け入れて、それらを検索の
ための能率的なシーケンスに組織する。このことは、達
成されるべきなかでも非常に高速のデータ検索を可能に
する。
【００５１】かかる解法により以下のような利益が得ら
れる。まず、多重処理又は多重糸的(multi-threading)
な解法の場合より構成が簡素になる。この解法は物理的
データ配置を考慮するため、ディスクヘッド運動を最小
にし、かつデータ入力速度を最大にするためにその配置
を最適化することができる。検索作業を、システム資源
の最高の活用を図るようにスケジュールすることができ
る。この解法は、多重プロセッサの可用性(availabilit
y)に依存せず、また１つのプロセッサのみが利用可能で
あるような場合でも非常に効果的である。
【００５２】本発明の趣旨を逸脱することなく、上述の
システムに対し多くの変更仕様が可能である。
【００５３】例えば、検索プロセッサを使用する代わり
に、ＲＤＢＭＳそれ自体によって検索を行ってもよい。
この場合、並列検索マネージャは、各ディスクについて
検索領域のリストをクリエイトするため上述と同じ方法
で使用される。ホストプロセッサ内のバルク入力マネー
ジャは、その後、ディスクドライバを介して一連の非同
期ブロック読取動作を駆動するためにこれらのリストを
使用し、それによってＲＤＢＭＳによる検索のため要求
されたデータをホストに読み込む。この可能性について
は、図５に開示されている。
【００５４】
【発明の効果】以上説明したように、本発明によれば、
並列検索を行う技術であって改良されたものを提供する
ことができる。
【図面の簡単な説明】
【図１】本発明による並列検索技術を用いるコンピュー
タシステムを示すブロック図である。
【図２】ファイルの１セットの物理的ディスクへのマッ
ピングを示すツリー構造を示す図である。
【図３】並列検索マネージャの動作を示すフローチャー
トである。
【図４】並列検索マネージャのルーチン形成部の動作を
示すフローチャートである。
【図５】本発明による並列検索技術を用いる別のコンピ
ュータシステムを示すブロック図である。
【符号の説明】
１０ ホストプロセッサ １１ オペレーティングシステム １２ アプリケーションソフトウェア １３ ＳＣＳＩチャネル １４ ディスクドライブ １５ 検索加速ユニット １６ 関連データベース管理システム（ＲＤＢＭＳ） １７ 照会マネージャ １８ 並列検索マネージャ １９ ファイル格納マネージャ・論理ボリュームマネー
ジャ ２０ ＳＣＡＦＳドライバ ２１ スケジューラ２１ ２２ ファイル格納マッピング部

Claims (8)

    【特許請求の範囲】
  1. 【請求項１】 複数のデータ格納ユニット（１４）、及
    び１又はそれ以上のファイル内で検索されるべきデータ
    領域のリストを特定する検索要求を生成するアプリケー
    ション（１７）を具備するデータ処理システムであっ
    て、(a) ファイルが前記データ格納ユニットにマッピ
    ングされる方法を示すマッピングテーブルをクリエイト
    する手段（２２）、(b) 複数の検索リストをクリエイ
    トするためデータ領域の前記リスト及び前記マッピング
    テーブルを利用する手段（１８）、ここで１つの検索リ
    ストは複数のデータ格納ユニットの各々と関連し、各検
    索リストはデータ格納ユニットのそれぞれ１つにマッピ
    ングされるデータ領域又はそれらの部分を特定する、及
    び(c) それぞれのデータ格納ユニットに対する複数の
    検索を、検索リストを用いて並列に開始する手段（１
    ８）、を具備することを特徴とするデータ処理システ
    ム。
  2. 【請求項２】 請求項１に記載のデータ処理システムで
    あって、複数の検索リストをクリエイトするためデータ
    領域の前記リスト及び前記マッピングテーブルを利用す
    る前記手段が、(a) 前記データ格納ユニットの各々に
    ついては外側ループを実行し、前記ファイルの各々につ
    いては内側ループを実行する手段、及び(b) 前記内側
    ループにおいて、特定の目標ディスクにマッピングする
    特定の目標ファイル内のデータ領域又はそれらの部分を
    発見する手段、を具備することを特徴とするデータ処理
    システム。
  3. 【請求項３】 請求項１又は２に記載のデータ処理シス
    テムであって、更に前記複数の検索の結果を組み合わ
    せ、その組み合わされた結果を前記アプリケーションに
    戻す手段を具備することを特徴とするデータ処理システ
    ム。
  4. 【請求項４】 請求項１、２又は３に記載のデータ処理
    システムであって、前記アプリケーションが関連データ
    ベース管理システムであることを特徴とするデータ処理
    システム。
  5. 【請求項５】 請求項１、２、３又は４に記載のデータ
    処理システムであって、前記データ格納ユニットは磁気
    ディスク格納ユニットであることを特徴とするデータ処
    理システム。
  6. 【請求項６】 請求項１、２、３、４又は５に記載のデ
    ータ処理システムであって、マッピングテーブルをクリ
    エイトする前記手段がデータ処理システムのオペレーテ
    ィングシステム内にあることを特徴とするデータ処理シ
    ステム。
  7. 【請求項７】 請求項１、２、３、４、５又は６に記載
    のデータ処理システムであって、更に前記検索を並列に
    行う複数の検索加速ユニットを有することを特徴とする
    データ処理システム。
  8. 【請求項８】 並列検索マネージャであって、(a) １
    又はそれ以上のファイル内で検索されるべきデータ領域
    のリストを特定する検索要求を受け入れる手段、(b)
    ファイルが複数のデータ格納ユニットにマッピングされ
    る方法を示すマッピングテーブルをクリエイトする手
    段、(c) 複数の検索リストをクリエイトするためデー
    タ領域の前記リスト及び前記マッピングテーブルを利用
    する手段、ここで１つの検索リストは複数のデータ格納
    ユニットの各々と関連し、各検索リストはデータ格納ユ
    ニットのそれぞれ１つにマッピングされるデータ領域又
    はそれらの部分を特定する、及び(d) それぞれのデー
    タ格納ユニットに対する複数の検索を、検索リストを用
    いて並列に開始する手段、を具備することを特徴とする
    並列検索マネージャ。
JP9057583A 1996-03-15 1997-03-12 並列検索技術 Pending JPH09330324A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GBGB9605473.9A GB9605473D0 (en) 1996-03-15 1996-03-15 Parallel searching technique
GB9605473.9 1996-03-15

Publications (1)

Publication Number Publication Date
JPH09330324A true JPH09330324A (ja) 1997-12-22

Family

ID=10790449

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9057583A Pending JPH09330324A (ja) 1996-03-15 1997-03-12 並列検索技術

Country Status (4)

Country Link
US (1) US5884303A (ja)
EP (1) EP0795834A1 (ja)
JP (1) JPH09330324A (ja)
GB (1) GB9605473D0 (ja)

Families Citing this family (99)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6466933B1 (en) 1999-09-21 2002-10-15 International Business Machines Corporation Delayed delivery of query results or other data from a federated server to a federated client until such information is needed
US6792416B2 (en) 1999-09-21 2004-09-14 International Business Machines Corporation Managing results of federated searches across heterogeneous datastores with a federated result set cursor object
US7197491B1 (en) 1999-09-21 2007-03-27 International Business Machines Corporation Architecture and implementation of a dynamic RMI server configuration hierarchy to support federated search and update across heterogeneous datastores
US7113939B2 (en) * 1999-09-21 2006-09-26 International Business Machines Corporation Architecture to enable search gateways as part of federated search
US6370541B1 (en) 1999-09-21 2002-04-09 International Business Machines Corporation Design and implementation of a client/server framework for federated multi-search and update across heterogeneous datastores
US7509322B2 (en) 2001-01-11 2009-03-24 F5 Networks, Inc. Aggregated lock management for locking aggregated files in a switched file system
US8195760B2 (en) * 2001-01-11 2012-06-05 F5 Networks, Inc. File aggregation in a switched file system
US20040133606A1 (en) * 2003-01-02 2004-07-08 Z-Force Communications, Inc. Directory aggregation for files distributed over a plurality of servers in a switched file system
TW561358B (en) * 2001-01-11 2003-11-11 Force Corp Z File switch and switched file system
US7512673B2 (en) 2001-01-11 2009-03-31 Attune Systems, Inc. Rule based aggregation of files and transactions in a switched file system
US8239354B2 (en) 2005-03-03 2012-08-07 F5 Networks, Inc. System and method for managing small-size files in an aggregated file system
US7788335B2 (en) * 2001-01-11 2010-08-31 F5 Networks, Inc. Aggregated opportunistic lock and aggregated implicit lock management for locking aggregated files in a switched file system
US7418441B2 (en) 2001-02-28 2008-08-26 International Business Machines Corporation Data loading from a remote data source record by record
US7634756B2 (en) 2001-03-22 2009-12-15 Robert Dean Bjornson Method and apparatus for dataflow creation and execution
US6691109B2 (en) * 2001-03-22 2004-02-10 Turbo Worx, Inc. Method and apparatus for high-performance sequence comparison
US7614036B2 (en) * 2001-03-22 2009-11-03 Robert D Bjornson Method and system for dataflow creation and execution
US6963865B2 (en) * 2001-04-05 2005-11-08 International Business Machines Corporation Method system and program product for data searching
US7146524B2 (en) 2001-08-03 2006-12-05 Isilon Systems, Inc. Systems and methods for providing a distributed file system incorporating a virtual hot spare
US7685126B2 (en) * 2001-08-03 2010-03-23 Isilon Systems, Inc. System and methods for providing a distributed file system utilizing metadata to track information about data stored throughout the system
CN1692356B (zh) 2002-11-14 2014-06-04 易斯龙系统公司 用于对现存文件重新条带化的方法
US7464088B1 (en) * 2003-09-08 2008-12-09 Sage-N Research, Inc. Architecture for efficient pattern match operations
US9183256B2 (en) 2003-09-19 2015-11-10 Ibm International Group B.V. Performing sequence analysis as a relational join
US20050166149A1 (en) * 2004-01-23 2005-07-28 Microsoft Corporation Table of contents display
US7590620B1 (en) 2004-06-18 2009-09-15 Google Inc. System and method for analyzing data records
US7574424B2 (en) * 2004-10-13 2009-08-11 Sybase, Inc. Database system with methodology for parallel schedule generation in a query optimizer
US8055711B2 (en) 2004-10-29 2011-11-08 Emc Corporation Non-blocking commit protocol systems and methods
US8238350B2 (en) 2004-10-29 2012-08-07 Emc Corporation Message batching with checkpoints systems and methods
US8051425B2 (en) 2004-10-29 2011-11-01 Emc Corporation Distributed system with asynchronous execution systems and methods
US7885970B2 (en) * 2005-01-20 2011-02-08 F5 Networks, Inc. Scalable system for partitioning and accessing metadata over multiple servers
US20060167838A1 (en) * 2005-01-21 2006-07-27 Z-Force Communications, Inc. File-based hybrid file storage scheme supporting multiple file switches
US7958347B1 (en) 2005-02-04 2011-06-07 F5 Networks, Inc. Methods and apparatus for implementing authentication
US8126870B2 (en) * 2005-03-28 2012-02-28 Sybase, Inc. System and methodology for parallel query optimization using semantic-based partitioning
US20070088706A1 (en) * 2005-10-17 2007-04-19 Goff Thomas C Methods and devices for simultaneously accessing multiple databases
US7386675B2 (en) * 2005-10-21 2008-06-10 Isilon Systems, Inc. Systems and methods for using excitement values to predict future access to resources
US7797283B2 (en) * 2005-10-21 2010-09-14 Isilon Systems, Inc. Systems and methods for maintaining distributed data
US7917474B2 (en) * 2005-10-21 2011-03-29 Isilon Systems, Inc. Systems and methods for accessing and updating distributed data
US7788303B2 (en) * 2005-10-21 2010-08-31 Isilon Systems, Inc. Systems and methods for distributed system scanning
US7551572B2 (en) 2005-10-21 2009-06-23 Isilon Systems, Inc. Systems and methods for providing variable protection
US7848261B2 (en) * 2006-02-17 2010-12-07 Isilon Systems, Inc. Systems and methods for providing a quiescing protocol
US7756898B2 (en) * 2006-03-31 2010-07-13 Isilon Systems, Inc. Systems and methods for notifying listeners of events
US8417746B1 (en) 2006-04-03 2013-04-09 F5 Networks, Inc. File system management with enhanced searchability
US8539056B2 (en) * 2006-08-02 2013-09-17 Emc Corporation Systems and methods for configuring multiple network interfaces
US7590652B2 (en) 2006-08-18 2009-09-15 Isilon Systems, Inc. Systems and methods of reverse lookup
US7899800B2 (en) 2006-08-18 2011-03-01 Isilon Systems, Inc. Systems and methods for providing nonlinear journaling
US7680836B2 (en) 2006-08-18 2010-03-16 Isilon Systems, Inc. Systems and methods for a snapshot of data
US7953704B2 (en) * 2006-08-18 2011-05-31 Emc Corporation Systems and methods for a snapshot of data
US7882071B2 (en) 2006-08-18 2011-02-01 Isilon Systems, Inc. Systems and methods for a snapshot of data
US7676691B2 (en) 2006-08-18 2010-03-09 Isilon Systems, Inc. Systems and methods for providing nonlinear journaling
US7752402B2 (en) 2006-08-18 2010-07-06 Isilon Systems, Inc. Systems and methods for allowing incremental journaling
US7822932B2 (en) * 2006-08-18 2010-10-26 Isilon Systems, Inc. Systems and methods for providing nonlinear journaling
US7680842B2 (en) * 2006-08-18 2010-03-16 Isilon Systems, Inc. Systems and methods for a snapshot of data
US20080065591A1 (en) * 2006-09-08 2008-03-13 Leon Guzenda Configurable software database parallel query system and method
US8286029B2 (en) 2006-12-21 2012-10-09 Emc Corporation Systems and methods for managing unavailable storage devices
US7593938B2 (en) * 2006-12-22 2009-09-22 Isilon Systems, Inc. Systems and methods of directory entry encodings
US7509448B2 (en) 2007-01-05 2009-03-24 Isilon Systems, Inc. Systems and methods for managing semantic locks
US7779048B2 (en) * 2007-04-13 2010-08-17 Isilon Systems, Inc. Systems and methods of providing possible value ranges
US8966080B2 (en) * 2007-04-13 2015-02-24 Emc Corporation Systems and methods of managing resource utilization on a threaded computer system
US7900015B2 (en) * 2007-04-13 2011-03-01 Isilon Systems, Inc. Systems and methods of quota accounting
WO2008130983A1 (en) * 2007-04-16 2008-10-30 Attune Systems, Inc. File aggregation in a switched file system
WO2008147973A2 (en) * 2007-05-25 2008-12-04 Attune Systems, Inc. Remote file virtualization in a switched file system
US7966289B2 (en) * 2007-08-21 2011-06-21 Emc Corporation Systems and methods for reading objects in a file system
US7882068B2 (en) 2007-08-21 2011-02-01 Isilon Systems, Inc. Systems and methods for adaptive copy on write
US7949692B2 (en) 2007-08-21 2011-05-24 Emc Corporation Systems and methods for portals into snapshot data
US8180747B2 (en) 2007-11-12 2012-05-15 F5 Networks, Inc. Load sharing cluster file systems
US8117244B2 (en) 2007-11-12 2012-02-14 F5 Networks, Inc. Non-disruptive file migration
US8548953B2 (en) * 2007-11-12 2013-10-01 F5 Networks, Inc. File deduplication using storage tiers
US20090204705A1 (en) * 2007-11-12 2009-08-13 Attune Systems, Inc. On Demand File Virtualization for Server Configuration Management with Limited Interruption
US20090204650A1 (en) * 2007-11-15 2009-08-13 Attune Systems, Inc. File Deduplication using Copy-on-Write Storage Tiers
US8352785B1 (en) 2007-12-13 2013-01-08 F5 Networks, Inc. Methods for generating a unified virtual snapshot and systems thereof
US8224864B1 (en) * 2008-01-07 2012-07-17 Network Appliance, Inc. Striping directories across a striped volume set by the filenames contained in the directories
US7949636B2 (en) * 2008-03-27 2011-05-24 Emc Corporation Systems and methods for a read only mode for a portion of a storage system
US7984324B2 (en) 2008-03-27 2011-07-19 Emc Corporation Systems and methods for managing stalled storage devices
US7953709B2 (en) * 2008-03-27 2011-05-31 Emc Corporation Systems and methods for a read only mode for a portion of a storage system
US7870345B2 (en) 2008-03-27 2011-01-11 Isilon Systems, Inc. Systems and methods for managing stalled storage devices
US8549582B1 (en) 2008-07-11 2013-10-01 F5 Networks, Inc. Methods for handling a multi-protocol content name and systems thereof
US10721269B1 (en) 2009-11-06 2020-07-21 F5 Networks, Inc. Methods and system for returning requests with javascript for clients before passing a request to a server
US9195500B1 (en) 2010-02-09 2015-11-24 F5 Networks, Inc. Methods for seamless storage importing and devices thereof
US8204860B1 (en) 2010-02-09 2012-06-19 F5 Networks, Inc. Methods and systems for snapshot reconstitution
US8347100B1 (en) 2010-07-14 2013-01-01 F5 Networks, Inc. Methods for DNSSEC proxying and deployment amelioration and systems thereof
US9286298B1 (en) 2010-10-14 2016-03-15 F5 Networks, Inc. Methods for enhancing management of backup data sets and devices thereof
US8396836B1 (en) 2011-06-30 2013-03-12 F5 Networks, Inc. System for mitigating file virtualization storage import latency
US8463850B1 (en) 2011-10-26 2013-06-11 F5 Networks, Inc. System and method of algorithmically generating a server side transaction identifier
US9020912B1 (en) 2012-02-20 2015-04-28 F5 Networks, Inc. Methods for accessing data in a compressed file system and devices thereof
US9519501B1 (en) 2012-09-30 2016-12-13 F5 Networks, Inc. Hardware assisted flow acceleration and L2 SMAC management in a heterogeneous distributed multi-tenant virtualized clustered system
US10375155B1 (en) 2013-02-19 2019-08-06 F5 Networks, Inc. System and method for achieving hardware acceleration for asymmetric flow connections
US9554418B1 (en) 2013-02-28 2017-01-24 F5 Networks, Inc. Device for topology hiding of a visited network
US10552044B2 (en) * 2014-03-27 2020-02-04 Hitachi, Ltd. Storage apparatus, data processing method and storage system wherein compressed data is read in parallel, said data stored in buffer by size and read from said buffer, in order of when said data is stored in said buffer
US11838851B1 (en) 2014-07-15 2023-12-05 F5, Inc. Methods for managing L7 traffic classification and devices thereof
US10182013B1 (en) 2014-12-01 2019-01-15 F5 Networks, Inc. Methods for managing progressive image delivery and devices thereof
US11895138B1 (en) 2015-02-02 2024-02-06 F5, Inc. Methods for improving web scanner accuracy and devices thereof
US10834065B1 (en) 2015-03-31 2020-11-10 F5 Networks, Inc. Methods for SSL protected NTLM re-authentication and devices thereof
US10404698B1 (en) 2016-01-15 2019-09-03 F5 Networks, Inc. Methods for adaptive organization of web application access points in webtops and devices thereof
US10797888B1 (en) 2016-01-20 2020-10-06 F5 Networks, Inc. Methods for secured SCEP enrollment for client devices and devices thereof
US10412198B1 (en) 2016-10-27 2019-09-10 F5 Networks, Inc. Methods for improved transmission control protocol (TCP) performance visibility and devices thereof
US10567492B1 (en) 2017-05-11 2020-02-18 F5 Networks, Inc. Methods for load balancing in a federated identity environment and devices thereof
US10782894B1 (en) * 2017-07-31 2020-09-22 EMC IP Holding Company, LLC Reducing overlap through shuffle and keeping relationship balance on mapped RAID system and method
US11223689B1 (en) 2018-01-05 2022-01-11 F5 Networks, Inc. Methods for multipath transmission control protocol (MPTCP) based session migration and devices thereof
US10833943B1 (en) 2018-03-01 2020-11-10 F5 Networks, Inc. Methods for service chaining and devices thereof
US12003422B1 (en) 2018-09-28 2024-06-04 F5, Inc. Methods for switching network packets based on packet data and devices

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4967341A (en) * 1986-02-14 1990-10-30 Hitachi, Ltd. Method and apparatus for processing data base
GB8719572D0 (en) * 1987-08-19 1987-09-23 Krebs M S Sigscan text retrieval system
US5301310A (en) * 1991-02-07 1994-04-05 Thinking Machines Corporation Parallel disk storage array system with independent drive operation mode
US5542064A (en) * 1991-11-21 1996-07-30 Hitachi, Ltd. Data read/write method by suitably selecting storage units in which multiple copies of identical data are stored and apparatus therefor
US5596744A (en) * 1993-05-20 1997-01-21 Hughes Aircraft Company Apparatus and method for providing users with transparent integrated access to heterogeneous database management systems
US5715443A (en) * 1994-07-25 1998-02-03 Apple Computer, Inc. Method and apparatus for searching for information in a data processing system and for providing scheduled search reports in a summary format
US5701473A (en) * 1995-03-17 1997-12-23 Unisys Corporation System for optimally storing a data file for enhanced query processing
US5745915A (en) * 1995-03-17 1998-04-28 Unisys Corporation System for parallel reading and processing of a file

Also Published As

Publication number Publication date
EP0795834A1 (en) 1997-09-17
US5884303A (en) 1999-03-16
GB9605473D0 (en) 1996-05-15

Similar Documents

Publication Publication Date Title
JPH09330324A (ja) 並列検索技術
US7054893B2 (en) Method and apparatus for relocating data related to database management system
US7213025B2 (en) Partitioned database system
US6772163B1 (en) Reduced memory row hash match scan join for a partitioned database system
US5317727A (en) Method apparatus for determining prefetch operating for a data base
US5649181A (en) Method and apparatus for indexing database columns with bit vectors
US5404510A (en) Database index design based upon request importance and the reuse and modification of similar existing indexes
US7158996B2 (en) Method, system, and program for managing database operations with respect to a database table
US6438562B1 (en) Parallel index maintenance
JPH09212528A (ja) データベースを記憶する方法、データベースからレコードを検索する方法、および、データベース記憶／検索システム
US7080072B1 (en) Row hash match scan in a partitioned database system
JP2003150418A (ja) データベース管理システムの静的な情報を取得する手段を有する記憶装置
US7203686B1 (en) Partition join in a partitioned database system
US6470331B1 (en) Very large table reduction in parallel processing database systems
US7188334B1 (en) Value-ordered primary index and row hash match scan
JPH06314299A (ja) データベース管理方法
US20020138464A1 (en) Method and apparatus to index a historical database for efficient multiattribute SQL queries
JPH02297670A (ja) データベース検索方式
JPH04336340A (ja) ディスクキャッシュアクセス制御方式
JPH0962696A (ja) データベース管理システム
JP2748986B2 (ja) バッファ管理方式
JP2000348063A (ja) データベース管理方法およびシステム
JP3236999B2 (ja) データベース管理方法およびシステム
JP3156199B2 (ja) データベース管理方法およびシステム
JP3060222B2 (ja) デ―タベ―ス管理方法およびシステム