(57)【要約】【課題】検索処理時間を短縮することができる検索装置、プログラム、データベースシステム、および検索方法を提供することである。【解決手段】実施形態の検索装置は、クエリ受付部と、データ取得部と、判定部と、決定部とを持つ。クエリ受付部は、対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付ける。データ取得部は、前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得する。判定部は、前記データ取得部により取得されたｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定する。決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する。【選択図】図１
2019061486.tif 000002
【特許請求の範囲】
【請求項１】
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けるクエリ受付部と、
前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得するデータ取得部と、
前記データ取得部により取得されたｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定する判定部と、
前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する決定部と、
を備える、検索装置。
【請求項２】
前記データ取得部は、前記判定部により前記上位Ｎ件のデータが確定できると判定されるまでの間、前記決定部により決定されるノードから、前記決定部により決定されるデータ数のデータを取得する処理を繰り返す、
請求項１に記載の検索装置。
【請求項３】
前記決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、当該回で取得したデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定する、
請求項１または２に記載の検索装置。
【請求項４】
前記決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる、
請求項１から３のうち何れか１項に記載の検索装置。
【請求項５】
前記決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記データ取得部により取得されたデータ数、クエリ結果として出力されるデータ数、および前記複数のノードの数に基づいて、次にデータを取得するノードから取得するデータ数ｎを決定する、
請求項１から４のうち何れか１項に記載の検索装置。
【請求項６】
前記決定部は、前記クエリの実行履歴に基づいて、複数回のデータの取得が実行された確率を算出し、算出した確率に基づいて、前記ノードから取得するデータ数ｎを決定する、
請求項１から５のうち何れか１項に記載の検索装置。
【請求項７】
前記決定部は、予め決められた繰り返し回数に基づいてデータを取得すると仮定した場合に、取得するデータ数が最小になる係数を算出し、算出した係数に基づいてデータ数を決定する、
請求項１から６のうち何れか１項に記載の検索装置。
【請求項８】
前記データ取得部は、予め前記複数のノードから上位Ｎ件のデータを取得するまでの処理時間を取得し、取得した処理時間に基づいて算出された評価値が、閾値以下である場合に、前記複数のノードの全てから上位Ｎ件のデータを取得する、
請求項１から７のうち何れか１項に記載の検索装置。
【請求項９】
前記データ取得部は、前記クエリ受付部により前記クエリを最初に受け付けた場合に、前記上位Ｎ件のデータを取得するまでの処理時間を取得し、取得した処理時間に基づいて算出された評価値が閾値以下である場合に、前記複数のノードの全てから上位Ｎ件のデータを取得する、
請求項１から７のうち何れか１項に記載の検索装置。
【請求項１０】
検索装置のコンピュータに、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けさせ、
受け付けられた前記クエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得させ、
取得された前記ｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定させ、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定させる、
プログラム。
【請求項１１】
検索装置と、複数のノードとを備えるデータベースシステムであって、
前記検索装置は、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けるクエリ受付部と、
前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する前記複数のノードからｎ（ｎはＮ以下の自然数）ずつ件のデータを取得するデータ取得部と、
前記データ取得部により取得されたｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定する判定部と、
前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する決定部と、を備え、
前記ノードは、
前記対象となるデータを記憶する記憶部と、
前記検索装置から受信したクエリを実行して、前記記憶部に記憶された前記対象となるデータからｎ件のデータを取得し、取得したデータを前記検索装置に送信するクエリ実行部と、を備える、
データベースシステム。
【請求項１２】
検索装置のコンピュータが、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付け、
受け付けられた前記クエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得し、
取得された前記ｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定し、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する、
検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、検索装置、プログラム、データベースシステム、および検索方法に関する。
【背景技術】
【０００２】
従来、複数の下位ノードに接続された検索装置から、上位Ｎ（Ｎは自然数）件のデータを取得するためのクエリ（以下、Ｔｏｐ−Ｎクエリと称する）を実行し、複数の下位ノードに記憶されたデータから上位Ｎ件のデータを抽出するデータベースシステムが知られている。このデータベースシステムでは、Ｍ（Ｍは自然数）台の下位ノードのそれぞれから上位Ｎ件のデータを取得し、取得したデータをマージして最終的な上位Ｎ件のデータを抽出する。そのため、下位ノードと検索装置との間でＮ＊Ｍ件分のデータ転送が発生し、そのうちＮ件分のデータしかクエリ結果に反映されないため、Ｎ＊（Ｍ−１）分のデータ転送が無駄になり、結果として、検索処理時間が大きくなる可能性があった。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Clement Yu，George Philip，Weiyi Meng、“Distributed top-N query processing with possibly uncooperative local systems”、VLDB '03 Proceedings of the 29th international conference on Very large data bases - Volume 29 Pages 117-128、September 09 - 12, 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、検索処理時間を短縮することができる検索装置、プログラム、データベースシステム、および検索方法を提供することである。
【課題を解決するための手段】
【０００５】
実施形態の検索装置は、クエリ受付部と、データ取得部と、判定部と、決定部とを持つ。クエリ受付部は、対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付ける。データ取得部は、前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得する。判定部は、前記データ取得部により取得されたｎ件ずつのデータから前記上位Ｎ件のデータが確定できるか否かを判定する。決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する。
【図面の簡単な説明】
【０００６】
【図１】実施形態のデータベースシステム１の機能構成例を示す図。
【図２】第１のデータ取得手法によるクエリ処理部２２０の第１の処理内容を説明するための図。
【図３】第１のデータ取得手法によるクエリ処理部２２０の第２の処理内容を説明するための図。
【図４】第１のデータ取得手法によるクエリ処理部２２０の第３の処理内容を説明するための図。
【図５】第４のデータ数決定手法における決定部２２４の処理を説明するための図。
【図６】コスト算出結果の第１の例を示す図。
【図７】コスト算出結果の第２の例を示す図。
【図８】検索装置２００のクエリ処理部２２０で実行される処理内容の一例を示すフローチャート。
【図９】コスト算出部２２５における処理内容の一例を示すフローチャート。
【図１０】検索装置２００が複数階層に構成されたデータベースシステム２の機能構成例を示す図。
【発明を実施するための形態】
【０００７】
以下、実施形態の検索装置、プログラム、データベースシステム、および検索方法を、図面を参照して説明する。
【０００８】
図１は、実施形態のデータベースシステム１の機能構成例を示す図である。図１に示すデータベースシステム１は、例えば、クライアント端末１００と、検索装置２００と、一以上のデータベース装置（ノードの一例）３００−１〜３００−Ｍ（Ｍは自然数）とを備える。クライアント端末１００と、検索装置２００と、データベース装置３００とは、インターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等を含むネットワークＮＷを介して通信する。なお、以下の説明において、データベース装置３００−１〜３００−Ｍは、それぞれ同様の構成とし、何れのデータベース装置であるかを区別しないときは、何れのデータベース装置であるかを示すハイフン以降の符号を省略し、「データベース装置３００」と称して説明する。
【０００９】
まず、クライアント端末１００の機能構成について説明する。クライアント端末１００は、例えば、クエリ生成部１１０と、クエリ送信部１２０と、クエリ結果受信部１３０とを備える。これらの構成要素のうち一部または全部は、ＬＳＩ（Large Scale Integration）やＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）、ＧＰＵ（Graphics Processing Unit）等のハードウェア（回路部；circuitryを含む）によって実現されてもよいし、ソフトウェアとハードウェアの協働によって実現されてもよい。
【００１０】
クエリ生成部１１０は、データベース装置３００−１〜３００−Ｍに保持されているデータから上位または下位Ｎ（Ｎは自然数）件のデータを取得するためのＴｏｐ−Ｎクエリを生成する。クエリとは、例えば、データベース装置３００に保持されているデータに対する操作を表す命令である。クエリは、例えば、ＳＱＬ（Standard Query Language）で記述されたコマンドである。以下では、Ｔｏｐ−Ｎクエリは、対象のデータの中から降順に上位Ｎ件のデータを取得するクエリであるものとして説明する。
【００１１】
クエリ送信部１２０は、クエリ生成部１１０により生成されたＴｏｐ−Ｎクエリを検索装置２００に送信する。
【００１２】
クエリ結果受信部１３０は、クエリ送信部１２０により送信されたＴｏｐ−Ｎクエリによって得られるクエリ結果として、上位Ｎ件のデータを検索装置２００から受信する。
【００１３】
次に、検索装置２００の機能構成について説明する。検索装置２００は、例えば、送受信部２１０と、クエリ処理部２２０と、記憶部２３０とを備える。クエリ処理部２２０は、ＬＳＩ、ＡＳＩＣ、ＦＰＧＡ、ＧＰＵ等のハードウェアによって実現されてもよいし、ソフトウェアとハードウェアとの協働によって実現されてもよい。また、送受信部２１０は、「クエリ受付部」の一例である。
【００１４】
送受信部２１０は、クライアント端末１００により送信されたＴｏｐ−Ｎクエリを受信する。また、送受信部２１０は、Ｔｏｐ−Ｎクエリに対するクエリ結果を、クライアント端末１００に送信する。また、送受信部２１０は、データ取得部２２１が生成したクエリをデータベース装置３００に送信し、送信したデータベース装置３００からクエリ結果を受信する。
【００１５】
クエリ処理部２２０は、送受信部２１０が受信したＴｏｐ−Ｎクエリに基づいて、データベース装置３００からデータを取得し、取得したデータから上位Ｎ件のデータを取得する。クエリ処理部２２０は、例えば、データ取得部２２１と、ソート処理部２２２と、判定部２２３と、決定部２２４と、コスト算出部２２５とを備える。
【００１６】
データ取得部２２１は、コスト算出部２２５により決定された第１のデータ取得手法または第２のデータ取得手法に基づいて、データベース装置３００−１〜３００−Ｍのそれぞれに分散して保持された対象のデータのうち、ｎ（ｎはＮ以下の自然数）件ずつのデータを取得するクエリを生成する。
【００１７】
第１のデータ取得手法とは、ｎをＮより小さい値に設定して、データベース装置３００に保持された対象のデータのうち、ｎ件ずつのデータを取得し、これを一または複数回繰り返すことで、最終的に出力する上位Ｎ件のデータを取得する手法である。データ取得部２２１は、第１のデータ取得手法で上位Ｎ件のデータを取得する場合には、一又は複数のクエリを生成する。また、データ取得部２２１により２回目以降にデータを取得するクエリを生成する場合に、決定部２２４により決定された対象のデータベース装置３００と、取得するデータ数とに基づいてクエリを生成する。
【００１８】
第２のデータ取得手法とは、ｎをＮと同じ値に設定して、データベース装置３００に保持された対象のデータのうち、ｎ件ずつのデータを取得し、これを一回行うことで、最終的な上位Ｎ件のデータを取得する手法である。データ取得部２２１は、第２のデータ取得手法で上位Ｎ件のデータを取得する場合には、一回のクエリを生成する。
【００１９】
そして、データ取得部２２１は、生成したクエリをデータベース装置３００−１〜３００−Ｍに送信し、送信したデータベース装置３００−１〜３００−Ｍに保持された対象のデータからｎ件ずつのデータを取得する。
【００２０】
ソート処理部２２２は、データを取得する対象のデータベース装置３００のそれぞれで取得したデータをデータベース装置３００ごとに降順にソートする。また、ソート処理部２２２は、データベース装置３００ごとにソートしたデータをマージする。また、ソート処理部２２２は、取得したデータを昇順にソートしてもよい。
【００２１】
判定部２２３は、ソート処理部２２２によりソートされたデータに基づいて、最終的に出力する上位Ｎ件のデータが確定できるか否かを判定する。判定部２２３の機能の詳細については、後述する。
【００２２】
決定部２２４は、判定部２２３により上位Ｎ件のデータが確定できないと判定された場合に、次フェーズでデータを取得するデータベース装置３００を決定する。また、決定部２２４は、決定されたデータベース装置３００ごとに取得するデータ数を決定する。決定部２２４の機能の詳細については、後述する。
【００２３】
コスト算出部２２５は、データ取得部２２１が実行する第１のデータ取得手法および第２のデータ取得手法のそれぞれのコストを算出し、算出したコスト結果に基づいて、データ取得部２２１で実行するデータ取得手法を決定する。コストは、例えば、検索装置２００が、Ｔｏｐ−Ｎクエリに基づいて、データベース装置３００にクエリを送信してから、最終的に出力する上位Ｎ件のデータが確定できると判定されるまでの処理時間である。コスト算出部２２５の機能の詳細については、後述する。
【００２４】
記憶部２３０は、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等により実現される。記憶部２３０には、例えば、判定用データ２３２、コスト算出データ２３４、およびその他の情報が格納される。判定用データ２３２およびコスト算出データ２３４の内容については、後述する。
【００２５】
次に、データベース装置３００の機能構成について説明する。データベース装置３００は、例えば、送受信部３１０と、クエリ実行部３２０と、記憶部３３０とを備える。クエリ実行部３２０は、ＬＳＩ、ＡＳＩＣ、ＦＰＧＡ、ＧＰＵ等のハードウェアによって実現されてもよいし、ソフトウェアとハードウェアとの協働によって実現されてもよい。
【００２６】
送受信部３１０は、検索装置２００により送信されたクエリを受信する。また、送受信部３１０は、クエリ実行部３２０で実行されたクエリ結果を検索装置２００に送信する。
【００２７】
クエリ実行部３２０は、送受信部３１０により受信されたクエリを実行する。例えば、クエリ実行部３２０は、記憶部３３０に記憶されたデータ３３２のうち、クエリに対応するデータを取得する。データ３３２には、例えば、数値が含まれる。数値は、例えば、消費電力、ガス使用量、水道使用量、温度、湿度、金額等である。データ３３２は、上述した数値に、データベース装置３００の識別情報やユーザ情報、時間情報、位置情報等が対応付けられたレコードデータであってもよい。クエリ実行部３２０は、例えば、データ３３２に含まれる数値の高い順に、上位ｎ件のデータまたはクエリにより指定された順位からｎ件のデータを取得する。
【００２８】
記憶部３３０は、ＲＡＭやＲＯＭ、ＨＤＤ、フラッシュメモリ等により実現される。記憶部３３０には、例えば、データ３３２、およびその他の情報が格納される。
【００２９】
次に、検索装置２００のクエリ処理部２２０の処理内容について説明する。以下では、ノードＡ〜Ｅは、データベース装置３００−１〜３００−５に相当するものとする。また、図２〜図４に示すＡ１〜Ａ１０、Ｂ１〜Ｂ１０、Ｃ１〜Ｃ１０、Ｄ１〜Ｄ１０、およびＥ１〜Ｅ１０は、ノードＡ〜Ｅで分散して保持される１０個のデータを表すものとする。また、各ノードＡ〜Ｅが保持するデータは、Ａ１＞Ａ２＞…＞Ａ１０、Ｂ１＞Ｂ２＞…＞Ｂ１０、Ｃ１＞Ｃ２＞…＞Ｃ１０、Ｄ１＞Ｄ２＞…＞Ｄ１０、Ｅ１＞Ｅ２＞…＞Ｅ１０の関係が成り立っているものとする。
【００３０】
図２は、第１のデータ取得手法によるクエリ処理部２２０の第１の処理内容を説明するための図である。第１の処理内容は、Ｔｏｐ−Ｎクエリに基づいて、上位Ｎ件のデータを取得する際に、対象のデータが保持されるデータベース装置３００の数Ｍが、Ｎより大きい場合（Ｎ＜Ｍ）の処理内容である。図２の例では、Ｎ＝４、Ｍ＝５の場合を示している。
【００３１】
第１の処理内容において、まず第１フェーズとして、データ取得部２２１は、ノードＡ〜Ｅのそれぞれから最上位のデータを１件ずつ取得する（図２のＰ１）。ソート処理部２２２は、ノードＡ〜Ｅから取得した最上位の５件のデータをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータに基づいて、最終的に出力する候補となる上位４件のデータ（以下、候補データと称する）を抽出する。また、判定部２２３は、一つのノードからこれまでに取得した全てのデータが候補データに含まれずに、上位４件の候補データが抽出できた場合、最終的に出力する上位４件のデータが確定できると判定する。また、判定部２２３は、一つのノードから当該回までに取得した全てのデータが候補データに含まれる場合に、最終的に出力する上位４件のデータが確定できないと判定する。
【００３２】
図２の例では、ノードＡ〜Ｄから第１フェーズで取得した全てのデータが候補データに含まれているため、判定部２２３は、最終的に出力する上位４件のデータが確定できないと判定する。この場合、決定部２２４は、判定部２２３の判定結果に基づいて、データの全てが候補データとして抽出されているノードＡ〜Ｄを次フェーズでデータを抽出するノードとして決定する。また、決定部２２４は、決定したノードＡ〜Ｄに対して、例えば、第１フェーズで取得したデータ数を２倍した２件のデータを取得することを決定する。
【００３３】
次に、第２フェーズとして、データ取得部２２１は、ノードＡ〜Ｄのそれぞれから、まだ取得していないデータのうち上位２件のデータを取得する（図２のＰ２）。ソート処理部２２２は、候補データと、今回取得したデータとをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータの中から上位４件の候補データを抽出する。そして、判定部２２３は、一つのノードからこれまでに取得した全てのデータが候補データに含まれずに、上位４件の候補データが抽出できた場合、最終的に出力する上位４件のデータが確定できると判定する。また、判定部２２３は、一つのノードからこれまでに取得した全てのデータが候補データに含まれる場合に、最終的に出力する上位４件のデータが確定できないと判定する。
【００３４】
図２の例では、ノードＡから第２フェーズで取得した全てのデータＡ２、Ａ３が候補データに含まれているため、判定部２２３は、最終的に出力する上位４件のデータが確定できないと判定する。この場合、決定部２２４は、判定部２２３の判定結果に基づいて、次フェーズでノードＡからデータを取得することを決定する。また、決定部２２４は、残りの未確定件数が１件であるため、次フェーズでは、１件のデータを取得することを決定する。
【００３５】
次に、第３フェーズとして、データ取得部２２１は、ノードＡからまだ取得していないデータから上位１件のデータを取得する（図２のＰ３）。ソート処理部２２２は、候補データと、今回取得したデータとをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータから上位４件を取得する。図２の例では、データ取得部２２１は、最終的に出力する上位４件のデータとしてデータＡ１〜Ａ４を取得する。
【００３６】
図３は、第１のデータ取得手法によるクエリ処理部２２０の第２の処理内容を説明するための図である。第２の処理内容は、Ｔｏｐ−Ｎクエリに基づいて、上位Ｎ件のデータを取得する際に、対象のデータが保持されるデータベース装置３００の数Ｍが、Ｎより小さい場合（Ｎ＞Ｍ）の処理内容である。図３の例では、Ｎ＝１０、Ｍ＝５の場合を示している。
【００３７】
第２の処理内容において、まず第１フェーズとして、データ取得部２２１は、所定の関数で得られるデータ数のデータを取得する。所定の関数は、例えば、２＊（Ｎ／Ｍ）である。したがって、データ取得部２２１は、ノードＡ〜Ｅから、上位４件（＝２＊（１０／５）件）ずつのデータを取得する（図３のＰ１）。ソート処理部２２２は、各ノードからから取得した計２０件のデータをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータから上位１０件の候補データを抽出する。また、判定部２２３は、ノードＡ〜Ｅのそれぞれから取得した４件のデータの全てが候補データに含まれずに、上位１０件の候補データが抽出できた場合、最終的に出力する上位１０件が確定できると判定する。また、判定部２２３は、一つのノードから取得した４件のデータが、候補データに含まれる場合、最終的に出力する上位１０件のデータが確定できないと判定する。
【００３８】
図３の例では、ノードＡおよびノードＢから第１フェーズで取得した４件のデータが候補データに含まれている。そのため、判定部２２３は、最終的に出力する上位１０件のデータが確定できないと判定する。この場合、決定部２２４は、判定部２２３の判定結果に基づいて、次フェーズでノードＡおよびノードＢからデータを取得することを決定する。また、決定部２２４は、次フェーズで４件の２倍の８件のデータを取得することを決定する。なお、ノードＡおよびノードＢのそれぞれの残りのデータ数は６件であるため、結果として、ノードＡおよびノードＢからそれぞれ６件のデータが取得される。
【００３９】
次に、第２フェーズとして、データ取得部２２１は、ノードＡおよびノードＢからまだ取得していないＡ５〜Ａ１０、Ｂ５〜Ｂ１０のデータを取得する（図３のＰ２）。ソート処理部２２２は、候補データと、今回取得したデータとをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータから上位１０件の候補データを抽出する。図３の例では、データ取得部２２１は、データＡ１〜Ａ４、Ｂ１〜Ｂ４、およびＣ１〜Ｃ２を最終的に出力する上位１０件として取得する。
【００４０】
図４は、第１のデータ取得手法によるクエリ処理部２２０の第３の処理内容を説明するための図である。第３の処理内容は、Ｔｏｐ−Ｎクエリに基づいて、上位Ｎ件のデータを取得する際に、対象のデータが保持されるデータベース装置３００の数Ｍが、Ｎと同じである場合の処理内容である。図４の例では、Ｎ＝５、Ｍ＝５の場合を示している。
【００４１】
第３の処理内容において、まず第１フェーズとして、データ取得部２２１は、所定の関数に基づいて、ノードＡ〜Ｅの最上位から２件（＝２＊（５／５）件）ずつのデータを取得する（図４のＰ１）。ソート処理部２２２は、それぞれから取得した計１０件のデータをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータから上位５件の候補データを抽出する。また、判定部２２３は、ノードＡ〜Ｅのそれぞれから取得した２件のデータの全てが候補データに含まれていない場合に、最終的に出力する上位５件のデータが確定できると判定する。また、判定部２２３は、一つのノードから取得した全データが候補データに含まれる場合に、最終的に出力する上位５件のデータが確定できないと判定する。図４の例では、ノードＡおよびノードＢから取得した２件のデータの全てが候補データに含まれている。そのため、判定部２２３は、最終的に出力する上位１０件のデータが確定できないと判定する。この場合、決定部２２４は、判定部２２３の判定結果に基づいて、次フェーズでノードＡおよびノードＢからデータを取得することを決定する。また、決定部２２４は、次フェーズで上位５件のうち２件を除く３件のデータを取得することを決定する。
【００４２】
次に、第２フェーズとして、データ取得部２２１は、ノードＡおよびノードＢからまだ取得していない上位３件のデータＡ３〜Ａ５、Ｂ３〜Ｂ５を取得する（図４のＰ２）。ソート処理部２２２は、候補データと、今回のフェーズで取得したＡ３〜Ａ５およびＢ３〜Ｂ５とをマージし、マージしたデータをソートして、判定用データ２３２として記憶部２３０に格納する。判定部２２３は、マージされたデータから最終的に出力する上位５件のデータを取得する。
【００４３】
上述した処理内容により、対象のデータから上位Ｎ件のデータを取得することで、下位ノードとのデータ転送量や転送時間を十分に短くすることができる。また、上述の処理内容により、データをマージしたり、ソートする時間も短縮されるため、結果として、検索処理時間を短縮させることができる。
【００４４】
次に、決定部２２４におけるデータ数の決定手法について説明する。例えば、決定部２２４は、フェーズ数ｋにおいて、以下に示す第１〜第４のデータ数決定手法を用いてデータ数ｎ（ｋ）を決定する。
【００４５】
第１のデータ数決定手法は、フェーズ数ｋに応じて定数倍にデータ数を増加させる手法である。この場合、決定部２２４は、例えば、次フェーズで取得するデータ数ｎ（ｋ）を、前回のフェーズで取得したデータ数の２倍とし、ｎ（ｋ−１）＊２として算出する。
【００４６】
第２のデータ数決定手法は、フェーズ数ｋに応じて定数Ｘを加算する手法である。この場合、決定部２２４は、次フェーズで取得するデータ数ｎ（ｋ）を、ｎ（ｋ−１）＋Ｘとして算出する。上述した第１および第２のデータ数決定手法では、決定部２２４は、フェーズ数ｋに応じて取得するデータ数を、Ｎを越えない範囲内で徐々に増加させている。
【００４７】
第３のデータ数決定手法は、今までに実行された同種のＴｏｐ−Ｎクエリにおける実行履歴に基づいて、２回目以降のフェーズに入った確率を算出し、算出した確率に基づいてデータ数ｎ（ｋ）を決定する手法である。同種のＴｏｐ−Ｎクエリとは、例えば、取得するデータの種類やデータ数、データベース装置３００の数Ｍが同一である条件において、実行されるＴｏｐ−Ｎクエリである。この場合、決定部２２４は、次フェーズで取得するデータ数ｎ（ｋ）を、確率変数ｐを含む所定の関数「ｐ＊ｎ（ｋ−１）」を用いて算出する。
【００４８】
ここで、確率変数ｐについて説明する。まず、決定部２２４は、確率変数ｐの初期値をｐ０に設定し、Ｔｏｐ−Ｎクエリをｋ回実行する。実行結果は、履歴情報として記憶部２３０に記憶されてもよい。そして、決定部２２４は、実行結果に基づき、第２フェーズ以降の処理を一度も実行しなかった場合に、決定部２２４は、ｐ＝ｐｏｌｄ＊Ａ１（Ａ１＜１）として、確率変数ｐの値を減少させる。Ｐｏｌｄは、前回のＴｏｐ−Ｎクエリで用いられた確率変数ｐの値である。また、決定部２２４は、ｔｏｐ−Ｎクエリをｋ回実行して、第２フェーズに入る確率が基準確率ＰΦ２より大きい場合、ｐ＝ｐｏｌｄ＊Ａ２（Ａ２＞１）として変数ｐの値を増加させる。
【００４９】
例えば、初期値ｐ０＝２，実行回数ｋ＝１０，Ａ１＝０．９，Ａ２＝１．２，基準確率ＰΦ２＝０．２が設定されているものとする。決定部２２４は、Ｔｏｐ−Ｎクエリを１０回実行して第２フェーズが実行されなかった場合に、確率変数ｐ＝２＊０．９＝１．８とし、データ数ｎ（ｋ）＝ｐ＊ｎ（ｋ−１）に代入してデータ数を決定する。また、決定部２２４は、Ｔｏｐ−Ｎクエリを１０回実行して第２フェーズが２回実行された場合、確率変数ｐ＝２＊１．２＝２．４とし、ｎ（ｋ）＝ｐ＊ｎ（ｋ−１）に代入してデータ数を決定する。このように、第３のデータ数決定手法を用いることで、Ｔｏｐ−Ｎクエリの実行履歴に基づいて、取得するデータ数を調整できるため、無駄なデータの転送を抑制することができる。
【００５０】
第４のデータ数決定手法は、予め決められた繰り返し回数に基づいてデータを取得すると仮定した場合に、取得するデータ数の総和が最小になる係数ｒを算出し、算出した係数ｒに基づいて、実際にＴｏｐ−Ｎクエリを実行する際のデータ数を決定する手法である。この場合、決定部２２４は、例えば、等比数列の和の公式「ａ（１−ｒｎ）／（１−ｒ）＞Ｎ（ａは第１フェーズにおけるデータ数）」を用いて、最小の係数ｒを求める。また、決定部２２４は、ニュートン法等による数値解析で近似することで係数ｒを求めてもよい。
【００５１】
図５は、第４のデータ数決定手法における決定部２２４の処理を説明するための図である。図５の例では、上位１００件のデータを取得するデータベース装置３００の数を１００とし、繰り返し回数を６回とした場合に、係数ｒ＝２および１．８９としてデータ取得を実行したときのフェーズごとのクエリ内容、ノード数ｘ（ｋ）、データ数ｎ（ｋ）、およびデータ数ｎ（ｋ）の総和Σｎ（ｋ）を示している。
【００５２】
例えば、図５の上図に示すように、係数ｒ＝２である場合には、第６フェーズまでに取得するデータ数の総和が１２６であり、無駄なデータが２６となるのに対し、図５の下図に示す係数ｐ＝１．８９の場合には、第６フェーズまでに取得するデータ数の総和が１０３であり、無駄なデータ数が３となる。この二つのデータを比較すると、係数ｒが１．８９の場合には、係数２の場合に比して無駄なデータ数が小さくなる。このように、第４のデータ数決定手法では、複数の係数値を用いて仮のデータ取得を実行し、実行により取得されるデータ数を比較することで、適切な係数ｒを設定することができる。また、設定した係数ｒを用いて実際のデータ数を決定することで、無駄なデータの取得を抑制することができる。
【００５３】
次に、コスト算出部２２５の機能について説明する。コスト算出部２２５は、上述した第１のデータ取得手法と、第２のデータ取得手法のそれぞれのコストを算出する。コスト算出部２２５は、算出したそれぞれのコストに基づいて、データ取得部２２１におけるデータ取得手法を決定する。
【００５４】
例えば、コスト算出部２２５は、送受信部２１０によりＴｏｐ−Ｎクエリを最初に受け付けて、クエリ処理部２２０によるＴｏｐ−Ｎクエリの初回処理の実行時に、第２のデータ取得手法で全てのデータベース装置３００より上位Ｎ件のデータを取得し、取得したデータをマージおよびソートして、最終的に出力する上位Ｎ件のデータを取得するまでの処理時間を算出する。また、コスト算出部２２５は、Ｔｏｐ−Ｎクエリの初回処理の実行時に限定されずに、所定のタイミングで上述した処理時間を予め算出してもよい。また、コスト算出部２２５は、算出した処理時間を、第２のデータ取得手法のコストとする。そして、コスト算出部２２５は、第２のデータ取得手法のコストを、コスト算出データ２３４として記憶部２３０に格納する。
【００５５】
また、コスト算出部２２５は、コスト算出データ２３４により算出された処理時間に基づいて、第１のデータ取得手法におけるコストを見積もる。そして、コスト算出部２２５は、第１のデータ取得手法によるコストと、第２のデータ取得手法によるコストとを比較し、コストの小さいデータ取得手法で、データ取得部２２１にデータを取得させる。
【００５６】
ここで、具体的なコスト算出手法について説明する。まず前提として、データベース装置３００におけるクエリ実行処理時間は、第１のデータ取得手法と第２のデータ取得手法とで同一であるものとする。コスト算出部２２５は、Ｔｏｐ−Ｎクエリの初回処理時に第２のデータ取得手法を用いて、「ソート処理部２２２におけるデータのソート時間Ｓ」、「データベース装置３００へのデータ取得命令転送時間Ｑ」、および「データ総転送時間Ｔ」を算出する。ソート時間Ｓは、ソート機能の起動させる時間等の固定時間Ｓｆｉｘと、データ量に依存する時間Ｓｆ（ｎ）とを加算した値である。また、コスト算出部２２５は、ソート時間Ｓとデータ取得命令転送時間Ｑとを加算した値を評価値とし、閾値の一例であるデータ総転送時間Ｔと比較した結果に基づいて、第１および第２のデータ取得手法のうち一方のデータ取得手法を決定する。
【００５７】
例えば、コスト算出部２２５は、Ｔｏｐ−Ｎクエリによるデータ取得において、最大でｋフェーズを要するものと仮定して、「第ｉフェーズにおいてデータベース装置３００が転送するデータ数ｎ（ｉ）」と、「第ｉフェーズにおいて転送したデータの全てが候補データに含まれるノード数の最大値ｘ（ｉ）」とを用いて、ｘ（ｉ＋１）＝ｆｌｏｏｒ（Ｎ／（ｎ（ｉ）＊ｘ（ｉ）））を算出する。ｆｌｏｏｒは、小数点以下を切り捨てる関数である。
【００５８】
また、コスト算出部２２５は、Ｓｆｉｘと、Ｓｆ（ｎ）とを用いて、第１のデータ取得手法におけるソート時間の差分△Ｓ＝（ｋ−１）＊Ｓｆｉｘ＋Ｓｆ（Σ｛ｉ∈｛１〜ｋ｝｝（ｘ（ｉ）＊ｎ（ｉ））／（Ｎ＊Ｍ））を算出する。また、コスト算出部２２５は、第１のデータ取得手法におけるデータ取得命令転送時間の増加分△Ｑ＝（ｋ−１）＊Ｑを算出する。また、コスト算出部２２５は、第１のデータ取得手法におけるデータ総転送時間の差分△Ｔ＝Ｔ−Σ｛ｉ∈｛１〜ｋ｝｝（ｘ（ｉ）＊ｎ（ｉ）＊Ｔ／（Ｎ＊Ｍ）））を算出する。コスト算出部２２５は、これらの算出結果で得られた△Ｓと△Ｑとの和と、△Ｔとを比較し、△Ｓと△Ｑとの和が△Ｔより小さい場合には、第１のデータ取得手法を用いることを決定し、△Ｓと△Ｑとの和が△Ｔ以上である場合には、第２のデータ取得手法を用いることを決定する。
【００５９】
図６は、コスト算出結果の第１の例を示す図である。図６の例では、フェーズｋごとに、クエリ内容、ｘ（ｋ）、ｎ（ｋ）、および転送データ数が対応付けられている。例えば、Ｎ＝１０，Ｍ＝１００，Ｓｆｉｘ＝１［ｍｓ］，Ｓｆ（ｎ）＝９［ｍｓ］，Ｑ＝１０［ｍｓ］，Ｔ＝１０００［ｍｓ］と設定したものとして第４フェーズまで実行したときの転送データ数は１４５であったとする。この場合、コスト算出部２２５は、
△Ｓ＝（４−１）＊１＋１４５／１０００＊９＝４．３［ｍｓ］
△Ｑ＝（４−１）＊１０＝３０［ｍｓ］
△Ｔ＝１０００−（１４５／１０００）＊１０００＝８５５［ｍｓ］
を算出する。この結果、△Ｓ、△Ｑ、および△Ｔには、「△Ｓ＋△Ｑ＜△Ｔ」の関係が成り立つ。したがって、コスト算出部２２５は、データ取得部２２１におけるデータ取得に第１のデータ取得手法を用いることを決定する。
【００６０】
図７は、コスト算出結果の第２の例を示す図である。図７の例では、フェーズごとに、クエリ内容、ｘ（ｋ）、ｎ（ｋ）、および転送データ数が対応付けられている。例えば、Ｎ＝１００，Ｍ＝５，Ｓｆｉｘ＝１０［ｍｓ］，Ｓｆ（ｎ）＝９９０［ｍｓ］，Ｑ＝１０［ｍｓ］，Ｔ＝１００［ｍｓ］と設定したものとして第２フェーズまで実行したときの転送データ数は３２０件であったとする。この場合、コスト算出部２２５は、
△Ｓ＝（２−１）＊１０＋３２０／５００＊９９０−１０００＝４１４［ｍｓ］
△Ｑ＝（２−１）＊１０＝１０［ｍｓ］
△Ｔ＝１００−（３２０／５００）＊１００＝３６０［ｍｓ］
を算出する。この結果、△Ｓ、△Ｑ、および△Ｔには、「△Ｓ＋△Ｑ≧△Ｔ」の関係が成り立つ。したがって、コスト算出部２２５は、データ取得部２２１におけるデータ取得に第２のデータ取得手法を用いることを決定する。
【００６１】
上述したようにコスト算出部２２５により算出されたコストに基づいて、データ取得手法を切り替えることにより、データ転送時間を短縮することができ、結果として、検索処理時間を短縮することができる。
【００６２】
次に、実施形態の検索装置２００で実行される各種処理内容についてフローチャートを用いて説明する。以下のフローにおいて、下位ノードとは、データベース装置３００である。図８は、検索装置２００のクエリ処理部２２０で実行される処理内容の一例を示すフローチャートである。図８の例では、第１のデータ取得手法を用いて下位データに分散して保持される対象データのうち上位Ｎ件のデータを取得する処理を示している。
【００６３】
まず、データ取得部２２１は、初期値として、下位ノードを識別する変数ｉに０を設定し、およびフェーズ数を識別する変数ｋに１を設定する（ステップＳ１００）。次に、データ取得部２２１は、取得するデータ数ｎ（ｋ）を算出する（ステップＳ１０２）。次に、データ取得部２２１は、変数ｉに１を加算し（ステップＳ１０４）、ｉ番目の下位ノードから上位ｎ（ｋ）のデータを取得し、取得したデータを集合Ａ［ｉ］とする（ステップＳ１０６）。
【００６４】
次に、データ取得部２２１は、変数ｉの値が下位ノード数と同一であるか否かを判定する（ステップＳ１０８）。変数ｉの値が下位ノード数と同一でないと判定された場合、ステップＳ１０４の処理に戻る。また、変数ｉが下位ノード数と同一であると判定された場合、ソート処理部２２２は、全てのＡ［ｉ］をマージして、上位Ｎ件の候補データを集合Ｒとする（ステップＳ１１０）。
【００６５】
次に、判定部２２３は、変数ｉに０を設定し、フェーズ数ｋに１を加算する（ステップＳ１１２）。次に、決定部２２４は、次フェーズで下位ノードから取得するデータ数ｎ（ｋ）を算出する（ステップＳ１１４）。次に、判定部２２３は、変数ｉに１を加算し（ステップＳ１１６）、候補データの集合Ｒに集合Ａ［ｉ］の全データが含まれるか否かを判定する（ステップＳ１１８）。集合Ｒに集合Ａ［ｉ］の全データが含まれていると判定された場合、ｉ番目の下位ノードから次のｎ（ｋ）件のデータを取得して集合Ａ［ｉ］とし、集合Ａ［ｉ］を候補データの集合Ｒに追加する（ステップＳ１２０）。ステップＳ１２０の処理を、以下、処理Ａと称する。
【００６６】
ステップＳ１２０の処理後、またはステップＳ１１８の処理において、集合Ｒに集合Ａ［ｉ］の全データが含まれないと判定された場合、変数ｉの値が下位ノード数と同一であるか否かを判定する（ステップＳ１２２）。変数ｉの値が下位ノード数と同一でないと判定された場合、ステップＳ１１６の処理に戻る。また、変数ｉが下位ノード数と同一であると判定された場合、ソート処理部２２２は、集合Ｒに含まれるデータをソートし、上位Ｎ件以外のデータを集合Ｒから除去する（ステップＳ１２４）。
【００６７】
次に、決定部２２４は、上述したステップＳ１２０における処理Ａが一回以上発生したか否かを判定する（ステップＳ１２６）。一回以上発生したと判定された場合、ステップＳ１１２の処理に戻る。ステップＳ１１２の処理に戻った場合に、処理Ａの実行回数は、０回に初期化されステップＳ１１２以降の処理が実行される。また、処理Ａが一回以上発生していない場合、判定部２２３は、集合Ｒを最終的なＴｏｐ−Ｎクエリのクエリ結果として出力する（ステップＳ１２８）。これにより、本フローチャートの処理は、終了する。
【００６８】
図９は、コスト算出部２２５における処理内容の一例を示すフローチャートである。なお、図９の例では、既に第２のデータ取得手法におけるコスト計算が実施され、図９の例において、コスト算出部２２５は、コスト算出部２２５は、第１のデータ取得手法によるデータ取得のコストＣ１を算出し（ステップＳ２００）、第２のデータ取得手法によるデータ取得のコストＣ２を算出する（ステップＳ２０２）。
【００６９】
次に、コスト算出部２２５は、取得したコストＣ１が、コストＣ２より小さいか否かを判定する（ステップＳ２０４）。コストＣ１がコストＣ２より小さいと判定された場合、コスト算出部２２５は、データ取得部２２１によるデータ取得に第１のデータ取得手法を用いることを決定する（ステップＳ２０６）。また、コストＣ１がコストＣ２以上であると判定された場合、コスト算出部２２５は、データ取得に第２のデータ取得手法を用いることを決定する（ステップＳ２０８）。
【００７０】
また、実施形態のデータベースシステム１は、クライアント端末１００を複数備えてもよく、検索装置２００を複数備えてもよい。また、実施形態のデータベースシステムは、検索装置２００が複数階層に構成されてもよい。図１０は、検索装置２００が複数階層に構成されたデータベースシステム２の機能構成例を示す図である。図１０に示すデータベースシステム２は、図１に示すデータベースシステム１と比較して、複数の検索装置２００−１〜２００−Ｊ（Ｊは２以上の自然数）を備えており、検索装置２００−２〜２００−Ｊは、検索装置２００−１の下位の装置としてネットワークＮＷを介して接続されている。
【００７１】
図１０に示すデータベースシステム２において、検索装置２００−１は、クライアント端末１００からＴｏｐ−Ｎクエリを受け付けた場合に、下位の検索装置２００−２〜２００−ＪのそれぞれにＴｏｐ−Ｎクエリを送信する。下位の検索装置２００−２〜２００−２は、上述した第１のデータ取得手法および第２のデータ取得手法を用いて、それぞれが上位Ｎ件のデータを抽出し、抽出したデータを検索装置２００−１に送信する。上位Ｎ件の検索結果を受信したそれぞれの検索結果に基づいて、最終的に出力される上位Ｎ件のデータを取得し、取得したデータをクライアント端末１００に送信する。なお、図１０に示すデータベースシステム２では、検索装置２００が２段階層に構成されているが、３段以上の階層に構成されてもよい。
【００７２】
以上説明した少なくとも一つの実施形態によれば、検索装置２００が対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付ける送受信部２１０と、送受信部２１０により受け付けられたクエリに基づいて、対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得するデータ取得部２２１と、データ取得部２２１により取得されたｎ件ずつのデータから上位Ｎ件のデータが確定できるか否かを判定する判定部２２３と、判定部２２３により上位Ｎ件のデータが確定できないと判定された場合に、複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する決定部２２４と、を持つことにより、複数のデータベース装置３００−１〜３００Ｍに分散された対象のデータのうち、Ｔｏｐ−Ｎのデータを効率よく検索することができ、検索処理時間を短縮することができる。
【００７３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００７４】
１、２…データベースシステム、１００…クライアント端末、１１０…クエリ生成部、１２０…クエリ送信部、１３０…クエリ結果受信部、２００…検索装置、２１０、３１０…送受信部、２２０…クエリ処理部、２２１…データ取得部、２２２…ソート処理部、２２３…判定部、２２４…決定部、２２５…コスト算出部、２３０、３３０…記憶部、３００…データベース装置、３２０…クエリ実行部
【図１】
2019061486.tif 000003
【図２】
2019061486.tif 000004
【図３】
2019061486.tif 000005
【図４】
2019061486.tif 000006
【図５】
2019061486.tif 000007
【図６】
2019061486.tif 000008
【図７】
2019061486.tif 000009
【図８】
2019061486.tif 000010
【図９】
2019061486.tif 000011
【図１０】
2019061486.tif 000012
【手続補正書】
【提出日】平成31年1月18日(2019.1.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けるクエリ受付部と、
前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得するデータ取得部と、
前記データ取得部により取得されたｎ件ずつのデータをマージして最終的に出力する上位Ｎ件の候補となる候補データを抽出し、抽出した前記候補データに基づいて前記上位Ｎ件のデータが確定できるか否かを判定する判定部と、
前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する決定部と、を備え、
前記判定部は、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれる場合に前記上位Ｎ件のデータが確定できないと判定し、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれない場合に前記上位Ｎ件のデータが確定できると判定し、
前記決定部は、前記複数のノードのうち、取得したｎ件のデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定し、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる、
検索装置。
【請求項２】
前記データ取得部は、前記判定部により前記上位Ｎ件のデータが確定できると判定されるまでの間、前記決定部により決定されるノードから、前記決定部により決定されるデータ数のデータを取得する処理を繰り返す、
請求項１に記載の検索装置。
【請求項３】
前記決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記データ取得部により取得されたデータ数、クエリ結果として出力されるデータ数、および前記複数のノードの数に基づいて、次にデータを取得するノードから取得するデータ数ｎを決定する、
請求項１または２に記載の検索装置。
【請求項４】
前記決定部は、前記クエリの実行履歴に基づいて、複数回のデータの取得が実行された確率を算出し、算出した確率に基づいて、前記ノードから取得するデータ数ｎを決定する、
請求項１から３のうち何れか１項に記載の検索装置。
【請求項５】
前記決定部は、予め決められた繰り返し回数に基づいてデータを取得すると仮定した場合に、取得するデータ数が最小になる係数を算出し、算出した係数に基づいてデータ数を決定する、
請求項１から４のうち何れか１項に記載の検索装置。
【請求項６】
前記データ取得部は、予め前記複数のノードから上位Ｎ件のデータを取得するまでの処理時間を取得し、取得した処理時間に基づいて算出された評価値が、閾値以下である場合に、前記複数のノードの全てから上位Ｎ件のデータを取得する、
請求項１から５のうち何れか１項に記載の検索装置。
【請求項７】
前記データ取得部は、前記クエリ受付部により前記クエリを最初に受け付けた場合に、前記上位Ｎ件のデータを取得するまでの処理時間を取得し、取得した処理時間に基づいて算出された評価値が閾値以下である場合に、前記複数のノードの全てから上位Ｎ件のデータを取得する、
請求項１から５のうち何れか１項に記載の検索装置。
【請求項８】
検索装置のコンピュータに、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けさせ、
受け付けられた前記クエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得させ、
取得された前記ｎ件ずつのデータをマージして最終的に出力する上位Ｎ件の候補となる候補データを抽出し、抽出した前記候補データに基づいて前記上位Ｎ件のデータが確定できるか否かを判定させ、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定させ、
更に、前記上位Ｎ件のデータが確定できるか否かを判定させる際、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれる場合に前記上位Ｎ件のデータが確定できないと判定させ、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれない場合に前記上位Ｎ件のデータが確定できると判定させ、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、取得したｎ件のデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定し、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる、
プログラム。
【請求項９】
検索装置と、複数のノードとを備えるデータベースシステムであって、
前記検索装置は、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付けるクエリ受付部と、
前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する前記複数のノードからｎ（ｎはＮ以下の自然数）ずつ件のデータを取得するデータ取得部と、
前記データ取得部により取得されたｎ件ずつのデータをマージして最終的に出力する上位Ｎ件の候補となる候補データを抽出し、抽出した前記候補データに基づいて前記上位Ｎ件のデータが確定できるか否かを判定する判定部と、
前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する決定部と、を備え、
前記ノードは、
前記対象となるデータを記憶する記憶部と、
前記検索装置から受信したクエリを実行して、前記記憶部に記憶された前記対象となるデータからｎ件のデータを取得し、取得したデータを前記検索装置に送信するクエリ実行部と、を備え、
前記判定部は、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれる場合に前記上位Ｎ件のデータが確定できないと判定し、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれない場合に前記上位Ｎ件のデータが確定できると判定し、
前記決定部は、前記複数のノードのうち、取得したｎ件のデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定し、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる、
データベースシステム。
【請求項１０】
検索装置のコンピュータが、
対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付け、
受け付けられた前記クエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得し、
取得された前記ｎ件ずつのデータをマージして最終的に出力する上位Ｎ件の候補となる候補データを抽出し、抽出した前記候補データに基づいて前記上位Ｎ件のデータが確定できるか否かを判定し、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定し、
更に、前記上位Ｎ件のデータが確定できるか否かを判定する際、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれる場合に前記上位Ｎ件のデータが確定できないと判定し、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれない場合に前記上位Ｎ件のデータが確定できると判定し、
前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、取得したｎ件のデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定し、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる、
検索方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
実施形態の検索装置は、クエリ受付部と、データ取得部と、判定部と、決定部とを持つ。クエリ受付部は、対象となるデータのうち、上位Ｎ（Ｎは自然数）件のデータを検索するクエリを受け付ける。データ取得部は、前記クエリ受付部により受け付けられたクエリに基づいて、前記対象となるデータを分散して保持する複数のノードからｎ（ｎはＮ以下の自然数）件ずつのデータを取得する。判定部は、前記データ取得部により取得されたｎ件ずつのデータをマージして最終的に出力する上位Ｎ件の候補となる候補データを抽出し、抽出した前記候補データに基づいて前記上位Ｎ件のデータが確定できるか否かを判定する。また、判定部は、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれる場合に前記上位Ｎ件のデータが確定できないと判定し、一つのノードから取得したｎ件のデータの全てが前記候補データに含まれない場合に前記上位Ｎ件のデータが確定できると判定する。決定部は、前記判定部により前記上位Ｎ件のデータが確定できないと判定された場合に、前記複数のノードのうち、次にデータを取得するノードと、取得するデータ数とを決定する。また、決定部は、前記複数のノードのうち、取得したｎ件のデータの全てが前記上位Ｎ件に含まれているノードを、次にデータを取得するノードとして決定し、取得するデータ数ｎを、Ｎを越えない範囲内で徐々に増加させる。