図面 (/)

技術 データ検索方法、プログラム及び装置

出願人 株式会社富士通ビー・エス・シー
発明者 茂庭健一毛利良男
出願日 2007年3月29日 (12年3ヶ月経過) 出願番号 2007-089568
公開日 2008年10月16日 (10年9ヶ月経過) 公開番号 2008-250546
状態 拒絶査定
技術分野 検索装置
主要キーワード 検査口 ベンチマークテスト フラグ配列 全件検索 ソート前 各項目値 データ検索プログラム レコード順
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年10月16日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (8)

課題

SQL構文のIN検索のような複数の検索値を持つ検索を短時間で実行することができるデータ検索方法を提供すること。

解決手段

フラグ配列確保機能21aは、検索対象項目について、項目値テーブル各項目値に対応した同数のフラグ配列を確保する。検索値ソート機能21bは、検索キーとして与えられた複数の検索値を昇順ソートする。比較機能21cは、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較する。そして、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する。検索結果出力機能21dは、インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合をサブセットとして出力する。

概要

背景

規模データベースには、多数のデータを表形式で管理し、複数の表を関連付けて運用するリレーショナルデータベース(RDB)が従来から用いられている。RDBはトランザクション処理に向いているため、各種の基幹システムに用いられているが、全件のソート更新検索といった処理には時間がかかる。

このようなRDBの弱点を克服するため、特許文献1には、成分分解法によるFAST(Filter Array Structure)構造が開示されている。FAST構造では、表形式のレコードの配列であるデータを順序、位置、値の成分に分解して管理することにより、全件を対象とした処理の高速化を可能としている。

特許第3581831号公報

概要

SQL構文のIN検索のような複数の検索値を持つ検索を短時間で実行することができるデータ検索方法を提供すること。フラグ配列確保機能21aは、検索対象項目について、項目値テーブル各項目値に対応した同数のフラグ配列を確保する。検索値ソート機能21bは、検索キーとして与えられた複数の検索値を昇順にソートする。比較機能21cは、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較する。そして、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する。検索結果出力機能21dは、インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合をサブセットとして出力する。

目的

本発明は、上述した従来技術の問題点に鑑みてなされたものであり、例えばSQL構文のIN検索のような複数の検索値を持つ検索を短時間で実行することができるデータ検索方法、プログラム及び装置を提供することを目的(課題)とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の項目について各項目に対応する項目値を有するレコードの配列を、項目毎に、ユニークな項目値をソートした配列である項目値テーブルと、レコードの配列順に当該レコードの項目値が格納されている前記項目値テーブル内の位置を記録した配列であるインデックス値テーブルとに分解して管理するデータ構造におけるデータ検索方法において、コンピュータが、検索対象項目について、前記項目値テーブルの各項目値に対応したフラグ配列を確保するフラグ配列確保手順、検索値をソートする検索値ソート手順、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較し、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する比較手順、前記インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合を出力する検索結果出力手順、を実行することを特徴とするデータ検索方法。

請求項2

前記フラグ配列確保手順から検索結果出力手順までの各手順は、複数の検索値をパラメータとして、いずれかの検索値に該当するレコードを結果集合として出力するSQL構文のIN検索に対する処理として実行されることを特徴とする請求項1に記載のデータ検索方法。

請求項3

複数の項目について各項目に対応する項目値を有するレコードの配列を、項目毎に、ユニークな項目値をソートした配列である項目値テーブルと、レコードの配列順に当該レコードの項目値が格納されている前記項目値テーブル内の位置を記録した配列であるインデックス値テーブルとに分解して管理するデータ構造におけるデータ検索プログラムにおいて、コンピュータを、検索対象項目について、前記項目値テーブルの各項目値に対応したフラグ配列を確保するフラグ配列確保手段、検索値をソートする検索値ソート手段、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較し、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する比較手段、前記インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合を出力する検索結果出力手段、として機能させることを特徴とするデータ検索プログラム。

請求項4

複数の項目について各項目に対応する項目値を有するレコードの配列を、項目毎に、ユニークな項目値をソートした配列である項目値テーブルと、レコードの配列順に当該レコードの項目値が格納されている前記項目値テーブル内の位置を記録した配列であるインデックス値テーブルとに分解して管理するデータ構造におけるデータ検索装置において、検索対象項目について、前記項目値テーブルの各項目値に対応したフラグ配列を確保するフラグ配列確保手段と、検索値をソートする検索値ソート手段と、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較し、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する比較手段と、前記インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合を出力する検索結果出力手段と、を備えることを特徴とするデータ検索装置。

技術分野

0001

本発明は、コンピュータを用いた大規模データベースにおけるデータ検索方法プログラム及び装置に関し、特に、複数の検索値を用いた検索高速化に関する。

背景技術

0002

大規模なデータベースには、多数のデータを表形式で管理し、複数の表を関連付けて運用するリレーショナルデータベース(RDB)が従来から用いられている。RDBはトランザクション処理に向いているため、各種の基幹システムに用いられているが、全件のソート更新、検索といった処理には時間がかかる。

0003

このようなRDBの弱点を克服するため、特許文献1には、成分分解法によるFAST(Filter Array Structure)構造が開示されている。FAST構造では、表形式のレコードの配列であるデータを順序、位置、値の成分に分解して管理することにより、全件を対象とした処理の高速化を可能としている。

0004

特許第3581831号公報

発明が解決しようとする課題

0005

しかしながら、上記のFAST構造を採用したデータベースにおいても、SQL構文のIN検索の実行には時間がかかるという問題がある。IN検索は、複数の検索値をパラメータとして、いずれかの検索値に該当するレコードを結果集合として出力する処理である。例えば検索値がValu1, Value2, Value3の3つであると仮定すると、従来の処理では、以下のような手順で処理が実行される。
1) 全件を対象に検索対象項目の値が検索値Value1に一致するレコードを抽出して第1の検索結果サブセットを生成する。
2) 全件を対象に検索対象項目の値が検索値Value2に一致するレコードを抽出して第2の検索結果サブセットを生成する。
3) 第1、第2の検索結果サブセットをOR演算して第1のORサブセットを生成する。
4) 全件を対象に検索対象項目の値が検索値Value3に一致するレコードを抽出して第3の検索結果サブセットを生成する。
5) 第1のORサブセットと第3の検索結果サブセットとをOR演算して第2のORサブセットを生成する。

0006

上記の方法では、全件検索が検索値の数と同回数、OR演算がそれより1回少ない回数必要になり、演算量が莫大となるため時間がかかり、かつ、検索毎、OR演算毎にサブセットが作成されるため、オンメモリ処理の場合にはメモリ消費量が多く、ディスク上で処理される場合にはディスク容量を消費しアクセスのための時間がかかるという問題がある。

0007

本発明は、上述した従来技術の問題点に鑑みてなされたものであり、例えばSQL構文のIN検索のような複数の検索値を持つ検索を短時間で実行することができるデータ検索方法、プログラム及び装置を提供することを目的(課題)とする。

課題を解決するための手段

0008

本発明にかかるデータ検索方法は、複数の項目について各項目に対応する項目値を有するレコードの配列を、項目毎に、ユニークな項目値をソートした配列である項目値テーブルと、レコードの配列順に当該レコードの項目値が格納されている項目値テーブル内の位置を記録した配列であるインデックス値テーブルとに分解して管理するデータ構造前提として、コンピュータが、検索対象項目について、項目値テーブルの各項目値に対応したフラグ配列を確保するフラグ配列確保手順、検索値をソートする検索値ソート手順、ソートされた検索値を先頭から取り出し、項目値テーブルの先頭の項目値から順に比較し、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する比較手順、インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合を出力する検索結果出力手順を実行することを特徴とする。

0009

フラグ配列確保手順から検索結果出力手順までの各手順は、具体的には、複数の検索値をパラメータとして、いずれかの検索値に該当するレコードを結果集合として出力するSQL構文のIN検索に対する処理として実行される。

0010

なお、本発明のデータ検索プログラムは、上記の方法の各手順に相当する手段としてコンピュータを機能させることを特徴とし、本発明のデータ検索装置は、そのように機能するコンピュータと等価である。

発明の効果

0011

本発明によれば、検索値と項目値とを共に事前にソートすることにより、検索値と項目値との比較は項目値テーブルに対して1回実行すればよく、かつ、比較の結果をフラグとして記録することにより、全件に対するスキャンも1回で終了するため、複数の検索値を用いた検索を短時間で実行することができる。また、検索結果集合のサブセットも1組のみで足りるため、メモリやディスクの消費量を小さく抑えることができる。

発明を実施するための最良の形態

0012

以下、本発明にかかるデータ検索方法の実施形態を説明する。最初に、図1に基づいて本実施形態のデータ検索方法が適用されるシステム概要を説明する。このシステム1は、単独のコンピュータ10と、周辺機器とから構成されている。コンピュータ10は、CPU11、並びにこのCPU11に接続されたハードディスク(HD)20、メモリ(RAM)12及びインターフェイス13を備えている。

0013

なお、コンピュータ10のCPU11には、周辺機器としてディスプレイ30、プリンタ31、キーボード32がインターフェイス13を介して接続されている。

0014

HD20には、図示せぬオペレーティングシステムの他、データ検索プログラム21がインストールされると共に、検索対象データベース(DB)22が構築されている。CPU11は、起動するとHD20からオペレーティングシステムをRAM13上に読み出して実行し、このオペレーティングシステム上でデータ検索プログラム21を実行する。

0015

検索対象DB22は、複数の項目について各項目に対応する項目値を有するレコードの配列を、項目毎に、ユニークな項目値をソートした配列である項目値テーブル22aと、レコードの配列順に当該レコードの項目値が格納されている項目値テーブル22a内の位置を記録した配列であるインデックス値テーブル22bとに分解して管理するデータ構造、すなわち、前記の特許文献1に記載されたFAST構造を備える。データ検索プログラム21は、検索対象DB22のデータをRAM13上に展開し、オンメモリ処理によりデータ検索を実行するが、以下の説明では、メモリ上に展開されたデータについても、HD上と同一の符号で説明する。

0016

なお、図1には、システムが単独のコンピュータにより構成される例を示したが、このコンピュータをサーバとしてネットワークを介して複数の端末を接続し、各端末から入力、閲覧ができるようにしてもよい。また、検索対象DBには、一組の項目値テーブルとインデックス値テーブルとのみを示しているが、実際には複数の項目値について、それぞれ項目値テーブルとインデックス値テーブルとが設けられている。

0017

HD20にインストールされたデータ検索プログラム21は、複数の検索値をパラメータとして、いずれかの検索値に該当するレコードを結果集合として出力するSQL構文のIN検索が指示された際に機能するフラグ配列確保機能21a、検索値ソート機能21b、比較機能21c、検索結果出力機能21dを備えている。以下、各機能について説明する。

0018

フラグ配列確保機能21aは、検索対象項目について、項目値テーブルの各項目値に対応した同数のフラグ配列を確保する。検索値ソート機能21bは、検索キーとして与えられた複数の検索値を昇順にソートする。比較機能21cは、ソートされた検索値を先頭から順に取り出し、項目値テーブルの先頭の項目値から順に比較する。そして、項目値が検索値に一致する場合には当該項目値に対応するフラグを立てて次の検索値と次の項目値とを比較し、一致しない場合には当該検索値と次の項目値とを比較する。検索結果出力機能21dは、インデックス値テーブルを順にスキャンし、各インデックス値毎に対応する項目値のフラグを確認してフラグが立っている場合に当該インデックス値が格納されたレコードの情報を検索結果集合に追加し、全件スキャン後に検索結果集合をサブセットとして出力する。

0019

次に、上記のデータ検索システム1において実行されるデータ検索処理の内容を、図2及び図3に示すフローチャートに基づいて説明する。所定のデータ構造に対して複数の検索値が検索キーとして与えられることにより、検索処理が開始する。ここでは、データ構造として、商品在庫管理データベースを例にする。このデータベースは、項目として商品識別するための記号である「商品ID」、「商品名」、商品を販売する店舗名を示す「店舗」、その店舗における当該商品の在庫量を示す「数量」を有する。

0020

SQL構文として、以下のような命令が与えられた場合を例にして説明する。
「SELECT商品ID, 商品名,店舗, 数量 FROM TBL-A WHERE 商品ID IN (Z99, A01, A05, B03, … A02);」
この命令は、商品IDが、Z99、A01、A05、B03、・・・A02のいずれかのものの、商品ID,商品名、店舗、数量を抽出することを要求している。

0021

図2に示すように、検索処理が開始すると、CPU11は、ステップS001において検索対象項目値テーブル内の検索対象項目値VLの数mと同数のフラグ配列領域をRAM13上に確保する。図4は、商品管理データベース中の商品ID項目に関するデータ構造を示す。ユニークな項目値(この例では2600種類の商品ID)をソートした配列である項目値テーブル(VL)と、1億個の商品を個々に規定するレコードの配列順に当該レコードの商品IDが格納されている項目値テーブル(VL)内の位置を記録した配列であるインデックス値テーブル(VN)とを備え、そこに、項目値テーブルの各項目値に一対一で対応するようにフラグ配列が定義される。フラグ配列内の各フラグは、全て0に初期化されている。

0022

次に、CPU11は、ステップS002において、検索キーに含まれる検索値を昇順にソートする。例えば、図5(A)に示すような配列として検索キーが与えられた場合、これをソートして図5(B)に示すような順序の配列に変更する。

0023

続いて、CPU11は、ステップS003において:検索キーと検索対象項目の比較のサブルーチンを呼び出して実行する。ここでの処理は図3に示されるとおりである。すなわち、図3の最初のステップS101では、CPU11は検索キー及び検索対象項目値の配列序数m,nをそれぞれ−1,0に初期化する。

0024

そして、CPU11は、ステップS102において検索キーのn番目の検索値を取り出し、この検索値と項目値との比較を行う。ステップS103で序数mを1カウント加算し、ステップS104でmが最後+1(この例では2601)に達したか否かを判断し、ステップS105で検索値と検索対象項目値とを比較する。ステップS106で検索値が検索対象項目値(VN)に一致すると判断されれば、ステップS107で該当する項目値に対応する位置のフラグを立て(フラグ配列に1をセットし)、一致しないと判断されればステップS103に戻って次の項目値を対象に比較が行われる。一致と判定されないうちに項目値が最後に達した場合には、ステップS104から図2のステップS004に戻る。

0025

検索値と項目値とが一致してフラグが立てられると、CPU11はステップS108で検索値が検索キーの最後であるか否かを判断し、最後でなければ序数nを1カウント加算し、ステップS102に戻って検索キーの次の検索値について上記と同様の比較がなされる。

0026

比較の際には、「検索キー」も「検索対象項目値(VL)」も昇順にソートされているため、比較によるフラグの設定時には、検索キーの1つ1つの検索値に対して、項目値全体を検索する必要は無く、1つの検索値で項目値を昇順に取り出して比較し、一致した場合には、次の検索値については、一致した項目値の次の項目値から検索すればよい。上記のように、検索値が「A01,A02,A05,B03」で、項目値が「A00,A01,A02,A03,A04,A05、…」である場合、まず、「A01」がみつかるまで項目値を昇順に検索し、「A01」がみつかるとフラグを立て、次の検索値「A02」により、検索値「A01」による検索が終了した項目値の次の項目値「A02」から検索を続行する。同様に、次の検索値「A05」については、項目値「A03」から検索を続行する。

0027

なお、検索対象の項目値が検索値を超えた場合には、その検索値による検索は終了し、フラグを立てずに次の検索値による検索を続行する。項目値が検索値を超えず、かつ、一致することなく検索項目値の最後まで比較が終了した場合には、検索自体を終了する。

0028

比較処理によるフラグの設定の様子を図6に示す。図6(A)はソート後の検索キー、(B)は検索対象の項目値テーブル(VL)とこれに対応するフラグ配列とを示す。検索値に一致する項目値「A01,A02,Z99」に対応するフラグが「1」にセットされ、他のフラグは「0」のままである。

0029

比較処理が終了すると、CPU11は図2のステップS004に戻って処理を続行する。ステップS004〜S009では、CPU11はインデックス値テーブル(VN)を一回だけレコード順に全件スキャンして項目値に対応するフラグが1にセットされているレコードを抽出する。すなわち、ステップS004ではインデックス値テーブルの値の順番を示すための序数pを0に初期化し、ステップS005では、当該インデックス値により指し示される項目値にフラグが立てられているか否かを判断し、フラグが1である場合には(S006, YES)、ステップS007で当該レコードを検索結果集合(サブセット)に追加た後にステップS008に進み、フラグが1でない場合には(S006, NO)、ステップS007の処理をスキップしてステップS008に進む。

0030

CPU11は、ステップS008では序数pの値を1カウント加算し、ステップS009で最後のインデックス値でないか否かを確認し、最後でなければステップS005に処理を戻す。このようにして、1レコードずつインデックス値テーブルをスキャンしながらフラグをチェックし、最後のインデックス値が検出されると(S009, YES)、ステップS010で検索結果集合(サブセット)を出力してデータ検索処理を終了する。

0031

図7は、上記のステップS005〜S010に相当する処理を示す。すなわち、インデックス値テーブル(VN)の1億件を順にスキャンし、示されるインデックス値「1,2,…,2600」により示される項目値テーブル(VL)内の項目値「A01,A02,…,Z99」に対応するフラグ配列内のフラグをチェックし、それが「1」であるインデックス値を持つレコード(レコード番号1,2,7,10…)を結果集合のサブセットとして抽出する。

0032

上記のフローチャートは結果集合の出力までを規定しているが、前記のSQL文の命令を完了するため、CPU11は、検索結果集合のインデックス値で示される商品IDと、抽出されたインデックス値テーブルのレコード番号に基づいて他の項目値テーブルから読み出した商品名、店舗、数量の各データとを組み合わせて図7下段に示すような検索結果を出力する。

0033

レコード件数1億件、対象項目データ種類108種類、IN構文で指定する検索値数108個としてベンチマークテストを行った結果、従来の検査口毎に全件検索する場合にはIN構文の処理にかかる所要時間が292秒であったのに対し、本発明の方式では所要時間は約2秒であり、150倍近く性能を向上させることができた。

0034

なお、入力パラメータの渡し方を工夫すれば、IN構文のみでなく、様々なパターンの検索に対して高速化を図ることができる。パラメータとしては、一致検索のみでなく、「以上」、「以下」、「大きい」、「小さい」等を用いた範囲を指定してもよい。

図面の簡単な説明

0035

本発明の実施形態に係るデータ検索装置を含むコンピュータシステムを示すブロック図である。
図1のデータ検索装置による検索処理の内容を示すフローチャートである。
図2から呼び出されて実行される比較処理の内容を示すフローチャートである。
図1のデータ検索装置の検索対象データの一例を示す説明図である。
図1のデータ検索装置で用いられる検索キーのソート前後の配列を示す説明図である。
図1のデータ検索装置による検索手順におけるフラグの設定処理を示す説明図である。
図1のデータ検索装置による検索手順における結果集合の生成処理を示す説明図である。

符号の説明

0036

1 システム
10コンピュータ
11 CPU
12 RAM
20 HD
21データ検索プログラム
21aフラグ配列確保機能
21b検索値ソート機能
21d検索結果出力機能
22検索対象DB
22a項目値テーブル
22b インデックス値テーブル

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • グーグルエルエルシーの「 ビデオマッチングシステムのサービス品質向上のための画像マッチングシステムの使用」が 公開されました。( 2019/05/30)

    【課題・解決手段】システムは、対象のビデオを受信する。システムは、対象のビデオ内の動的セグメントと準静的セグメントとを識別する。システムは、対象のビデオの動的セグメントと参照ビデオの参照動的セグメント... 詳細

  • 尾和剛一の「 特許文献集合の分析方法」が 公開されました。( 2019/05/23)

    【課題】特定のコア技術や、特定の出願人の特定の分野の全特許文献集合の文献件数時系列動向とは異なる動向を示す文献項目を抽出する方法を提供する。【解決手段】特定文献集合分折方法は、特定の文献集合の特許文献... 詳細

  • 株式会社大塚商会の「 画像解析システム」が 公開されました。( 2019/05/23)

    【課題】 画像解析システムを提供することを目的とする。【解決手段】 画像解析システムであって,対象物と対象物関連情報とを対応づけて記憶する対象物情報記憶部と,第1の画像情報と,少なくとも一以上の第... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ