(57)【要約】【課題】ヒストグラムを高速に生成する技術を提供する。【解決手段】ヒストグラム生成装置は、ヒストグラム生成のための対象データに基づいて、ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定する決定手段と、当該各分割候補点における上記対象データの頻度の変化値をそれぞれ計算する変化値計算手段と、この変化値計算手段で計算された各変化値に基づいて上記複数の分割候補点をサンプリングすることにより、上記決定手段により決定された分割候補点の数よりも少ない数の分割候補点を選択する選択手段と、この選択手段により選択された分割候補点を用いて上記対象データのヒストグラムを生成するヒストグラム生成手段と、を備える。【選択図】図１
2012133608.tif 000002
【特許請求の範囲】
【請求項１】
ヒストグラム生成のための対象データに基づいて、該ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定する決定手段と、
前記各分割候補点における前記対象データの頻度の変化値をそれぞれ計算する変化値計算手段と、
前記変化値計算手段で計算された各変化値に基づいて前記複数の分割候補点をサンプリングすることにより、前記決定手段により決定された分割候補点の数よりも少ない数の分割候補点を選択する選択手段と、
前記選択手段により選択された分割候補点を用いて前記対象データのヒストグラムを生成するヒストグラム生成手段と、
を備えることを特徴とするヒストグラム生成装置。
【請求項２】
前記変化値計算手段に前記変化値の計算対象とするデータ範囲を示すパラメータを送るパラメータ指定手段、
を更に備え、
前記変化値計算手段は、前記パラメータ指定手段から取得した前記パラメータの示すデータ範囲で、前記各分割候補点における前記対象データの頻度の変化値をそれぞれ計算する、
ことを特徴とする請求項１に記載のヒストグラム生成装置。
【請求項３】
前記パラメータ指定手段は、前記選択手段で利用されるサンプリング数の上限値を前記選択手段に送り、
前記選択手段は、前記パラメータ指定手段から取得した前記上限値を超えない範囲で、前記決定手段により決定された分割候補点の数よりも少ない数の分割候補点を選択する、
ことを特徴とする請求項２に記載のヒストグラム生成装置。
【請求項４】
前記選択手段によるサンプリングのためのサンプリング数と該サンプリング数で選択された分割候補点を用いた前記ヒストグラム生成手段によるヒストグラム生成の処理時間との複数の組み合わせを格納する処理時間格納手段、
を更に備え、
前記パラメータ指定手段は、ヒストグラム生成希望時間を前記選択手段に送り、
前記選択手段は、前記処理時間格納手段に格納された複数の組み合わせを分析することにより、前記パラメータ指定手段から送られたヒストグラム生成希望時間に対応するサンプリング数を算出し、算出されたサンプリング数の分割候補点が選択されるようにサンプリングを行う、
ことを特徴とする請求項２又は３に記載のヒストグラム生成装置。
【請求項５】
前記選択手段は、前記分割候補点の数よりも少ない数の分割候補点をそれぞれ含む複数タイプの分割候補点集合を選択し、
前記ヒストグラム生成手段は、前記選択手段により選択された複数の分割候補点集合の各々を用いて複数のヒストグラムを生成し、生成された複数のヒストグラムのいずれか１つを出力する、
ことを特徴とする請求項１から４のいずれか１項に記載のヒストグラム生成装置。
【請求項６】
コンピュータが、
ヒストグラム生成のための対象データに基づいて、該ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定し、
前記各分割候補点における前記対象データの頻度の変化値をそれぞれ計算し、
前記計算された各変化値に基づいて前記複数の分割候補点をサンプリングすることにより、前記分割候補点の数よりも少ない数の分割候補点を選択し、
前記選択された分割候補点を用いて前記対象データのヒストグラムを生成する、
ことを含むヒストグラム生成方法。
【請求項７】
コンピュータを、
ヒストグラム生成のための対象データに基づいて、該ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定する決定手段と、
前記各分割候補点における前記対象データの頻度の変化値をそれぞれ計算する変化値計算手段と、
前記変化値計算手段で計算された各変化値に基づいて前記複数の分割候補点をサンプリングすることにより、前記決定手段により決定された分割候補点の数よりも少ない数の分割候補点を選択する選択手段と、
前記選択手段により選択された分割候補点を用いて前記対象データのヒストグラムを生成するヒストグラム生成手段、
として機能させることを特徴とするヒストグラム生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ヒストグラム生成技術に関する。
【背景技術】
【０００２】
ヒストグラムは、縦軸に頻度（度数）、横軸に階級を持つ統計グラフの一種であり、データの分布状況を表現する。与えられたデータに関し生成されるヒストグラムにより、データの分布が視覚的に把握される。ヒストグラムは、このような点に加えて、産業上の様々な技術に応用される。
【０００３】
ヒストグラムの応用事例の一つとして、データベースのクエリ最適化が挙げられる。クエリ最適化では、クエリを実行するための複数のクエリプランの中から最も効率のよいクエリプランが選択される。クエリ最適化処理では、クエリは複数の小さなサブクエリに分解され、それらの適用順序によりいくつかの実行プランが生成される。
【０００４】
データベースは、統計情報としてデータの属性の値に対応する頻度（データ数）のヒストグラムを保持しているため、実際にクエリを実行しなくてもそれぞれのサブクエリの結果の件数はヒストグラムから推定することができる。そのため、クエリ最適化処理では、この推定値を用いてそれぞれの実行プランの計算コストが見積られ、最もコストの低いものが最適な実行プランとして選択される。
【０００５】
このようなデータベースのクエリ最適化の例では、ヒストグラムの精度が実行プランの良し悪しを決める。例えば、ヒストグラムの精度が悪い場合、適切な実行プランが選ばれず、結果として、クエリの処理に、本来の時間よりも長い時間が費やされる可能性がある。そのため、精度の高いヒストグラムを生成することは、高速にクエリを処理するために重要である。
【０００６】
このようなヒストグラムを生成する手法としては、パーティションルールに基づく方法（非特許文献１参照）、ＭＤＬ（Minimum Description Length）原理に基づくモデル選択により生成する方法（非特許文献２及び３参照）等が存在する。
【０００７】
前者は、パーティションルールに従ってデータをユーザが所望するビン数に分割する。ここで、ビンとは、ヒストグラムにおける、値を持つ集合が区切られる任意の各区間を意味する。
【０００８】
非特許文献１で示されるように、当該パーティションルールとして、複数のルールが提案されている。例えば、ＥＱＵＩ−ＷＩＤＴＨ、ＥＱＵＩ−ＤＥＰＴＨ、ＭＡＸ−ＤＩＦＦ、ＣＯＭＰＲＥＳＳＥＤ等のルールがある。ＥＱＵＩ−ＷＩＤＴＨの手法は、データの値の範囲を均一に分割してヒストグラムを生成する。ＥＱＵＩ−ＤＥＰＴＨの手法は、値の頻度がそれぞれのビンで等しくなるようにヒストグラムを生成する。ＭＡＸ−ＤＩＦＦの手法は、連続するユニークなデータ値の頻度の差が大きい場所から順に分割する。ＣＯＭＰＲＥＳＳＥＤの手法は、頻度の高い値に個別のビンを与えて、残りはＥＱＵＩ−ＷＩＤＴＨやＥＱＵＩ−ＤＥＰＴＨの手法を使う。但し、これらいずれのパーティションルールにおいても、ユーザは、ビン数を指定する必要がある。
【０００９】
一方、後者は、データからそのデータを発生させている確率密度分布の推定を行うことでヒストグラムの生成を行う。そのなかで、ＭＤＬ原理によりモデル選択を行い、最もデータをよく表現する複雑さのモデルが選択される。このため、後者は、前者のようにユーザがビン数を指定しなくても自動的に適切なビン数を選択することができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Viswanath Poosala; Yannis E. Ioannidis; Peter J. Haas; Eugene J. Shekita, "Improved Histograms for Selectivity Estimation of Range Predicates", the 1996 ACM SIGMOD international conference
【非特許文献２】Petri Kontkanen; Petri Myllymaki, "MDL Histogram Density Estimation", Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS 2007), 21-24 Mar 2007
【非特許文献３】Rissanen J; Speed T.P; Yu B, "Density estimation by stochastic complexity", IEEE Transactions on Information Theory, Vol.38, March 1992.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上述のようなモデル選択に基づくヒストグラム生成手法では、パーティションルールに基づく方法に比べて計算量が大きくなる。これは、各ビン数についての、全てのビンの分割の仕方に対してそれぞれ分割の良し悪しを測るための記述長の計算を行うからである。
【００１２】
通常、複数の分割候補点から分割点を選ぶ各選択パターンの数分の計算が必要となる。上述の提案手法では、動的プログラミングによりこの計算量の削減が行われている。しかしながら、そのような提案手法であっても、依然として分割候補点の数が大きくなるにつれ計算量は大きくなる。
【００１３】
本発明の目的は、ヒストグラムを高速に生成する技術を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の各態様では、上述した課題を解決するために、それぞれ以下の構成を採用する。
【００１５】
第１の態様は、ヒストグラム生成装置に関する。第１の態様に係るヒストグラム生成装置は、ヒストグラム生成のための対象データに基づいて、ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定する決定手段と、当該各分割候補点における上記対象データの頻度の変化値をそれぞれ計算する変化値計算手段と、この変化値計算手段で計算された各変化値に基づいて上記複数の分割候補点をサンプリングすることにより、上記決定手段により決定された分割候補点の数よりも少ない数の分割候補点を選択する選択手段と、この選択手段により選択された分割候補点を用いて上記対象データのヒストグラムを生成するヒストグラム生成手段と、を備える。
【００１６】
第２の態様は、ヒストグラム生成方法に関する。第２の態様に係るヒストグラム生成方法は、コンピュータが、ヒストグラム生成のための対象データに基づいて、ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定し、上記各分割候補点における上記対象データの頻度の変化値をそれぞれ計算し、この計算された各変化値に基づいて上記複数の分割候補点をサンプリングすることにより、上記決定された分割候補点の数よりも少ない数の分割候補点を選択し、この選択された分割候補点を用いて上記対象データのヒストグラムを生成する。
【００１７】
なお、他の態様として、以上の何れかの構成をコンピュータに実現させるヒストグラム生成プログラムであってもよいし、このようなプログラムを記録したコンピュータが読み取り可能な記憶媒体であってもよい。
【発明の効果】
【００１８】
上記各態様によれば、ヒストグラムを高速に生成する技術を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】第１実施形態における関係データベースシステムの構成例を示す概念図。
【図２】データ格納部の一例としての購買テーブルを示す図。
【図３】データ格納部の一例としての商品テーブルを示す図。
【図４】ヒストグラムの例を示す図。
【図５】ヒストグラム格納テーブルの例を示す図。
【図６】第１実施形態における関係データベースシステムのヒストグラム生成時の動作例を示すフローチャート。
【図７】分割候補点の変化値の計算方法の例を概念的に示す図。
【図８】分割候補点に対する変化値の算出例を概念的に示す図。
【図９Ａ】実行プランの例を示す図。
【図９Ｂ】実行プランの例を示す図。
【図１０】ヒストグラム格納テーブルの第２例を示す図。
【図１１】データ問合せ処理の結果、抽出されたレコードの例を示す図。
【図１２】第２実施形態における関係データベースシステムの構成例を示す概念図。
【図１３】処理時間格納部に格納される処理時間データの例を示す図。
【図１４】第２実施形態におけるＤＢシステムのヒストグラム生成時の動作例を示すフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態について説明する。なお、以下に挙げる実施形態は例示であり、本発明は以下の実施形態の構成に限定されない。
【００２１】
本実施形態に係るヒストグラム生成装置は、ヒストグラム生成のための対象データに基づいて、該ヒストグラムの各区間を決めるための分割点の候補となる複数の分割候補点を決定する決定部と、当該各分割候補点における対象データの頻度の変化値をそれぞれ計算する変化値計算部と、この変化値計算部で計算された各変化値に基づいて上記複数の分割候補点をサンプリングすることにより、上記決定部により決定された分割候補点の数よりも少ない数の分割候補点を選択する選択部と、この選択部により選択された分割候補点を用いて対象データのヒストグラムを生成する生成部と、を備える。
【００２２】
上記ヒストグラム生成装置では、ヒストグラムの各区間を決めるための各分割候補点において、対象データの頻度の変化値がそれぞれ計算され、この変化値に基づいて複数の分割候補点がサンプリングされ絞られた分割候補点が利用されることで対象データのヒストグラムが生成される。つまり、最終的にヒストグラムが生成される際に利用される分割候補点は、対象データに基づいて決められた分割候補点の数よりも少ない数に設定される。
【００２３】
従って、上記ヒストグラム生成装置によれば、計算量が分割候補点の数に依存して大きくなるモデル選択に基づくヒストグラム生成方法等が採られた場合であっても、高速にヒストグラムを生成することができる。
【００２４】
以下、上述の実施形態について更に詳細を説明する。以下の各実施形態は、上述のヒストグラム生成装置の構成を関係データベースシステムに適用した場合の例である。なお、上述のヒストグラム生成装置の構成は、関係データベースシステムへの適用に限定されるものではなく、ヒストグラムを生成する様々な態様に適用可能である。例えば、分散データベースシステムに当該ヒストグラム生成装置の構成を適用することが可能である。このシステムでは、各データベース間でのデータ負荷の均一化を図るために、データの分布に基づいて負荷が均一化される。そのデータの分布の予測に利用されるヒストグラムの生成を当該ヒストグラム生成装置の構成で実現してもよい。
【００２５】
［第１実施形態］
〔システム構成〕
図１は、第１実施形態における関係データベースシステム（以降、単にＤＢシステムと表記する）１０の構成例を示す概念図である。第１実施形態におけるＤＢシステム１０は、データ格納部１００、ヒストグラム生成系２００、パラメータ指定部３００、ヒストグラム格納部４００、データ問合せ部５００等を有する。
【００２６】
ＤＢシステム１０は、例えば、ＣＰＵ（Central Processing Unit）、メモリ（ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等）、入出力インタフェース等を有し、ＣＰＵによりメモリに記憶されるプログラムが実行されることで上記各処理部を実現する。データ格納部１００及びヒストグラム格納部４００は、メモリ上で実現される。なお、本実施形態は、ＤＢシステム１０のハードウェア構成を限定しない。
【００２７】
データ格納部１００は、任意のデータを格納する関係データベースである。図２及び図３は、データ格納部１００の例を示す図である。図２には、購入者による商品購入の履歴を格納する購買テーブル（購買Ｔ）が示されている。購買テーブルの各レコードには、購入された商品を特定するための商品ＩＤ、購入者を特定するための購入者ＩＤ、購入時を特定するための日時情報がそれぞれ格納される。
【００２８】
図３には、商品情報を格納する商品テーブル（商品Ｔ）が示されている。商品テーブルの各レコードには、上記商品ＩＤ、商品名、価格がそれぞれ格納される。商品テーブルに格納される商品ＩＤは、購買テーブルに格納される商品ＩＤと対応する。
【００２９】
ヒストグラム生成系２００は、ヒストグラムを生成する処理系統であり、上述のヒストグラム生成装置の構成に対応する。ヒストグラム生成系２００は、分割候補点決定部（以降、単に決定部と表記する）２１０、変化値計算部２２０、分割候補点選択部（以降、単に選択部と表記する）２３０、ヒストグラム生成部２４０等を含む。ヒストグラム生成系２００に含まれるこれら各処理部についても、ＣＰＵによりメモリに記憶されるプログラムが実行されることでそれぞれ実現される。
【００３０】
決定部２１０は、データ格納部１００からヒストグラムを生成したいデータ（対象データ）を取得して、この対象データに基づいて複数の分割候補点を決定する。ここで、分割候補点とは、生成されるヒストグラムのビンとビンとの境界となり得る候補点を意味する。
【００３１】
変化値計算部２２０は、決定部２１０により決定された各分割候補点に対し分割され易さを示す値をそれぞれ計算する。本実施形態では、この分割され易さを示す値として、当該各分割候補点における対象データの頻度の変化値をそれぞれ計算する。この変化値は、分割候補点の前後で対象データの頻度がどれくらい急激に変化しているかを示す。ヒストグラムは、長方形（棒グラフ）のビンで密度分布を示すため、ヒストグラムを実際の密度分布に近似させるためには、急激に頻度が変化する部分に分割点を多く置き（ビンを多く割り当て）、変化が小さい部分に分割点を少なく置く又は分割点を置かないことが好ましい。これにより、本実施形態は、分割され易さを分割点での頻度の変化値と捉える。
【００３２】
変化値計算部２２０は、当該変化値の計算において、各分割候補点を中心としたデータ精度の範囲のデータを計算対象としてもよい。しかしながら、対象データが少なくデータの抜けが存在するような場合に、分割候補点の近傍のみで変化値を計算すると、そのデータの抜けにより変化値が大きくなり、本来の密度分布と異なる結果となる可能性がある。そこで、本実施形態では、変化値計算部２２０は、パラメータ指定部３００により指定されるパラメータを用いて変化値を計算する。このパラメータには、例えば、変化値の計算において対象とするデータ範囲を示す値等を含む。変化値計算で利用されるパラメータについては動作例の項において詳述する。
【００３３】
選択部２３０は、変化値計算部２２０で計算された各分割候補点における対象データの頻度の変化値に基づいて決定部２１０により決定された複数の分割候補点をサンプリングする。このサンプリングでは、頻度の変化の大きい分割候補点が重視され選択される。サンプリング数は、頻度の変化の大きい分割候補点が重視され、かつ、決定部２１０により決定された分割候補点の数よりも小さい数であれば、後述のパラメータ指定部３００で指定される数に設定されてもよいし、その指定される数を上限値とした乱数で決定されてもよい。
【００３４】
具体的なサンプリング手法としては、例えば、以下の例が挙げられる。第１の例は、変化値の閾値をパラメータ指定部３００から取得し、この閾値以上の変化値を持つ分割候補点を選択する手法である。第２の例は、この閾値以上の変化値を持つ分割候補点の中から更にランダムにサンプリングする手法である。第３の例は、変化値に比例した値で頻度の変化の大きい分割候補点を重点的に選択する手法である。なお、この第３の例については、動作例の項において詳述する。
【００３５】
選択部２３０は、このサンプリングにより、決定部２１０により決定された分割候補点の数よりも少ない数の点を最終的な分割候補点として選択する。
【００３６】
ヒストグラム生成部２４０は、サンプリングされた分割候補点を使いヒストグラムを生成する。このとき、ヒストグラム生成部２４０は、選択部２３０により選択された分割候補点（サンプリングされた分割候補点）の中から最終的にヒストグラムを作成するのに利用する分割点を選択するようにしてもよいし、当該分割候補点をそのまま分割点として用いてもよい。図４は、ヒストグラムの例を示す図である。例えば、ヒストグラム生成部２４０は、図３の商品テーブルの価格に関し図４に示すようなヒストグラムを生成する。このヒストグラム生成手法には、上述したような周知の様々な方法が利用される。本実施形態は、このヒストグラム生成手法自体を限定するものではないため、ここでは説明を省略する。
【００３７】
パラメータ指定部３００は、ヒストグラム生成系２００で使用される各種パラメータを指定する。例えば、変化値計算部２２０で使用されるパラメータ、選択部２３０で使用されるサンプル上限数、ヒストグラム生成部２４０で使用されるパラメータ等が指定される。なお、ヒストグラム生成部２４０で使用されるパラメータは、ヒストグラム生成手法に応じて決まる。
【００３８】
例えば、パラメータ指定部３００は、調整可能に設定されているユーザ設定ファイルから所望のパラメータを読み込んでもよいし、図示しないユーザインタフェースを通じて入力されたパラメータを取得してもよい。本実施形態は、パラメータ指定部３００の具体的パラメータ指定方法を限定するものではない。
【００３９】
ヒストグラム格納部４００は、ヒストグラム生成系２００で生成されたヒストグラムを格納する。図５は、ヒストグラム格納テーブルの例を示す図である。例えば、ヒストグラム格納部４００は、図４に示すようなヒストグラムを図５の例のような表形式で格納する。図５のヒストグラム格納テーブルの各レコードは、ヒストグラムの各ビンにそれぞれ対応し、左の分割点を開始値カラムに格納し、右の分割点を終了値カラムに格納し、その範囲のデータ数を出現数カラムにそれぞれ格納する。なお、本実施形態は、ヒストグラムの格納方式を限定しない。
【００４０】
データ問合せ部５００は、ユーザからのデータの問合せ（ＳＱＬ（Structured Query Language））を受け付け、その問合せに適合するデータをデータ格納部１００から抽出して、抽出されたデータをユーザへ返す。データ問合せ部５００は、問合せに適合するデータを抽出するにあたり、その問合せを最適化する。具体的には、データ問合せ部５００は、ユーザから発行されたＳＱＬからいくつかの実行プランを生成し、各実行プランに対してヒストグラムを参照しながら実行コストをそれぞれ算出する。データ問合せ部５００は、算出された実行コストが最も小さい実行プランを選択して実行する。
【００４１】
〔動作例〕
以下、第１実施形態におけるＤＢシステム１０の動作例について説明する。
まず、図６を用いて、ヒストグラム生成時におけるＤＢシステム１０の動作例を説明する。図６は、第１実施形態におけるＤＢシステム１０のヒストグラム生成時の動作例を示すフローチャートである。
【００４２】
パラメータ指定部３００は、ヒストグラム生成系２００で使用される各種パラメータを取得し、取得された各種パラメータをヒストグラム生成系２００へ送る（Ｓ１００）。この各種パラメータは、例えば、設定ファイルから読み出される。また、パラメータ指定部３００は、予め決められた既定のパラメータ値を利用してもよい。
【００４３】
決定部２１０は、データ格納部１００からヒストグラムを生成したい対象データを取得する（Ｓ１１０）。例えば、決定部２１０は、図３の商品テーブルの価格データに関してヒストグラムを作る場合には、以下のようなデータＸを得る。
Ｘ＝｛６９８０、８６００、１９８０、１０００００、１９８０、...｝
【００４４】
次に、決定部２１０は、上記処理（Ｓ１１０）で得られたデータから複数の分割候補点を決定する（Ｓ１２０）。この分割候補点の決定方法には複数の方法が考えられるが、ここでは、２種類の決定方法について例を挙げる。
【００４５】
第１の決定方法は、対象データが取り得る全ての値の前後にそれぞれ分割候補点を配置する方法である。例えば、第１の方法で決定される分割候補点の集合は、以下のＣ１で示すことができる。
Ｃ１＝｛ｘ＿ｍｉｎ＋ｅ／２＋ｔ×ｅ  ｜  ｔ＝０、１、．．．、（ｘ＿ｍａｘ−ｘ＿ｍｉｎ）／ｅ−１｝
【００４６】
ここで、ｘ＿ｍｉｎは、対象データの最小値を示し、ｘ＿ｍａｘは、対象データの最大値を示し、ｅは、対象データの精度を示す。図３の商品テーブルの価格データの例において、対象データの精度が１０に設定されたと仮定すると、各分割候補点は、１０円単位にそれぞれ設定される。
【００４７】
第２の決定方法は、対象データの全てのデータ点の前後にそれぞれ分割候補点を配置する方法である。例えば、第２の方法で決定される分割候補点の集合は、以下のＣ２で示すことができる。
Ｃ２＝｛ｘ＿ｊ−ｅ／２  ｜  ｘ＿ｊ∈Ｘ｝∪｛ｘ＿ｊ＋ｅ／２  ｜ｘ＿ｊ∈Ｘ｝
【００４８】
ここで、Ｘは対象データの集合を示し、ｘ＿ｊは各対象データを示し、ｅは対象データの精度を示す。
【００４９】
上記第１の決定方法によれば、分割候補点の集合Ｃ１は、対象データから最大値と最小値とを取得すれば自動的に決定することができる。一方、第２の決定方法によれば、分割候補点の集合Ｃ２は、全ての対象データに関して前後に分割候補点を設けることにより決定することができる。なお、本実施形態は、このような２種類の分割候補点の決定方法に限定するものではない。
【００５０】
次に、変化値計算部２２０は、処理（Ｓ１２０）で決定された複数の分割候補点に対して変化値をそれぞれ計算する（Ｓ１３０）。図７は、分割候補点の変化値の計算方法の例を概念的に示す図である。図７の例では、当該変化値の計算において、パラメータ指定部３００から指定される２つのパラメータε及びｄｘが利用される。パラメータｄｘは変化値を求める上でのデータ範囲を示す。パラメータｄｘの値がデータ精度に設定された場合には、分割候補点に隣接するデータ範囲のみを対象に変化値が計算され、データ精度よりも大きく設定された場合には、分割候補点を中心により広い範囲のデータ傾向が反映された変化値が計算される。
【００５１】
また、図７において、関数ｆ（ｘ）は、パラメータεを用いて、［ｘ−ε／２、ｘ＋ε／２］（開区間）の値がデータに出現する頻度を示す。この場合、変化値計算部２２０は、変化値Ｐ〜（ｘ）を以下の式により算出する。
Ｐ〜（ｘ）＝｜ｆ（ｘ１−ｄｘ／２）−ｆ（ｘ１＋ｄｘ／２）｜／ｄｘ
【００５２】
結果、算出される変化値は、図７における矢印の傾きを表す。図８は、分割候補点に対する変化値の算出例を概念的に示す図である。パラメータｄｘ及びεは、データの精度に設定されてもよい。また、データの精度に対して対象データが少なくデータの抜けが存在する場合には、パラメータｄｘ及びεは、データ精度より大きい値に設定されてもよい。
【００５３】
次に、選択部２３０は、各分割候補点における変化値（Ｐ〜（ｘ））が確率分布となるように各変化値を正規化する。各分割候補点における変化値（Ｐ〜（ｘ））が正規化された値をＰ（ｘ）とすると、例えば、その正規化は以下の式で示すことができる。
Ｐ（ｘ）＝Ｐ〜（ｘ）／ΣＰ〜（ｘ）
【００５４】
選択部２３０は、このように正規化された変化値の確率分布（Ｐ（ｘ））に基づいて、処理（Ｓ１２０）で決定された複数の分割候補点のうちのＮ個を分割候補点として選択する（Ｓ１４０）。サンプリング数Ｎは、例えば、パラメータ指定部３００から取得される。例えば、選択部２３０は、確率分布（Ｐ（ｘ））に従いランダムにパラメータ指定部３００から指定されたサンプリング数Ｎを上限として分割候補点を選択する。
【００５５】
ヒストグラム生成部２４０は、上記処理（Ｓ１４０）でサンプリングされた分割候補点を用いてヒストグラムを生成する（Ｓ１５０）。このヒストグラム生成方法には、例えば、分割候補点の数に計算量が依存するヒストグラム生成方法（例えば、非特許文献２、非特許文献３で提案されている方法等）が利用される。なお、ヒストグラム生成方法毎にパラメータが必要な場合には、パラメータ指定部３００から各種パラメータが取得される。
【００５６】
ヒストグラム生成部２４０は、上記処理（Ｓ１５０）で生成されたヒストグラムをヒストグラム格納部４００に格納する（Ｓ１６０）。
【００５７】
次に、上述のように生成されたヒストグラムを用いてデータ問合せに対する処理をする際におけるＤＢシステム１０の動作例について説明する。
【００５８】
データ問合せ部５００は、ユーザからの問い合わせＳＱＬを構文解析した後に、いくつかのＳＱＬの実行プランを生成する。例えば、データ格納部１００に図２及び図３に示すようなデータが格納されている場合に、そのデータに対して、次のようなＳＱＬ問い合わせがあったと仮定する。
ＳＥＬＥＣＴ  ＊  ＦＲＯＭ  購買Ｔ、商品Ｔ  ＷＨＥＲＥ  日時＞０８／１０  ＡＮＤ  価格＞５０００  ＡＮＤ  購買Ｔ．商品ＩＤ＝商品Ｔ．商品ＩＤ；
【００５９】
このとき、データ問合せ部５００は、例えば、図９Ａ及び図９Ｂに示す２つの実行プランを生成する。図９Ａ及び図９Ｂは、実行プランの例を示す図である。この２つの実行プランは、２つのテーブルの結合を含んでいる。データ問合せ部５００は、２つのテーブルを入れ子ループ結合（Nested loop join）する場合のコストとして、例えば、次式を用いて各実行プランのコストをそれぞれ計算する。
Ｐ１＋Ｃｅｉｌ（Ｐ１／（Ｍ−１））×Ｐ２
【００６０】
ここで、Ｐ１は、外側ループテーブルのページ数を示し、Ｐ２は、内側ループテーブルのページ数を示し、Ｍは、作業バッファサイズを示す。また、Ｃｅｉｌ（ｎ）は、ｎに指定した値以上で最も小さな整数値を求める関数である。なお、このようなコストの計算手法は、周知な手法が利用されればよく（北川博之著のデータベースシステム等参照）、本実施形態ではその計算手法を限定しないため、ここでは説明を簡略化する。
【００６１】
データ問合せ部５００は、上述のコストを算出するために、外側ループテーブル及び内側ループテーブルの各ページ数（Ｐ１及びＰ２）を各テーブルの選択率から求める。データ問合せ部５００は、上述のように生成されヒストグラム格納部４００に格納されているヒストグラムを用いて、当該選択率を取得する。この選択率とは、抽出されたレコード数の全体レコード数に対する割合を意味する。
【００６２】
ここで、図９Ａの実行プランのコストを算出する場合、結合の外側ループに、購買テーブルから「日時＞０８／１０」で抽出したレコードが使われ、内側ループに、商品テーブルから「価格＞５０００」で抽出したレコードが使われる。データ問合せ部５００は、各ページ数を得るために、ヒストグラム格納部４００に格納されているヒストグラムを用いて各選択率をそれぞれ求める。
【００６３】
例えば、図３の商品テーブルの価格データに関し、ヒストグラム格納部４００に図１０に示すヒストグラムが格納されていると仮定する。図１０は、ヒストグラム格納テーブルの第２例を示す図である。このとき、データ問合せ部５００は、「価格＞５０００」で抽出されるレコード数を、開始値が５０００より大きい範囲の出現数（３００＝１００＋１００＋２０＋８０）により取得し、この出現数の、全体の出現数（５００）に対する割合（６０％）を商品テーブルから「価格＞５０００」で抽出する場合の選択率として求める。
【００６４】
同様にして、データ問合せ部５００は、購買テーブルから「日時＞０８／１０」で抽出する場合の選択率をヒストグラム格納部４００に格納されているヒストグラムに基づいて求める。ここでは、その選択率が１０％として取得されたものと仮定する。更に、購買テーブルのページ数が５００、商品テーブルのページ数が３０、作業バッファサイズＭが５であると仮定すると、図９Ａ及び図９Ｂの各実行プランのコストはそれぞれ以下のように算出される。
【００６５】
図９Ａの実行プランのコスト＝５００×０．１＋Ｃｅｉｌ（５００×０．１／４）×３０×０．６＝２８４
図９Ｂの実行プランのコスト＝３０×０．６＋Ｃｅｉｌ（３０×０．６／４）×５００×０．１＝２６８
【００６６】
この例によれば、図９Ｂの実行プランの方が図９Ａよりもコストが小さい。従って、データ問合せ部５００は、図９Ｂの実行プランを実行して結果を得る。図１１は、データ問合せ処理の結果、抽出されたレコードの例を示す図である。
【００６７】
〔第１実施形態の作用及び効果〕
上述の第１実施形態におけるＤＢシステム１０では、決定部２１０が、ヒストグラム生成の対象となるデータから、ヒストグラムの各区間を決めるための複数の分割候補点を決定する。続いて、変化値計算部２２０が、各分割候補点における対象データの頻度の変化値をそれぞれ計算し、選択部２３０が、各変化値に基づいて、頻度の変化の大きい分割候補点が重視され選択されるように複数の分割候補点をサンプリングする。結果、ヒストグラム生成部２４０が、サンプリングされることにより、対象データに基づいて決められた分割候補点の数よりも少ない数に設定された分割候補点を用いて対象データのヒストグラムを生成する。
【００６８】
このように、選択部２３０により、対象データに基づいて決定された分割候補点が一定数以下でサンプリングされるため、分割候補点の数に計算量が依存するヒストグラム生成方法が採用されたとしても、高速にヒストグラムを生成することができる。
【００６９】
更に、第１実施形態では、対象データに基づいて決定された複数の分割候補点の中から、分割に不要な点が省かれ、分割に重要な点が重点的に分割候補点として選択される。ヒストグラムの各区間を決めるための分割点は、上述したように、急激に頻度が変化する部分に多く置かれることが好ましい。第１実施形態では、この分割の重要性が変化値により評価される。
【００７０】
従って、第１実施形態によれば、分割候補点を削減したとしても、分割に重要な点を重点的に選択しているため、ヒストグラムの精度の低下を抑えることができる。
【００７１】
［第２実施形態］
上述の第１実施形態では、パラメータ指定部３００においてサンプリング数の上限値が指定されていたが、第２実施形態は、ヒストグラム生成時間を指定可能に実現される。以下、第２実施形態におけるＤＢシステム１０について第１実施形態と異なる内容を中心に説明し、同一の内容については説明を適宜省略する。
【００７２】
〔システム構成〕
図１２は、第２実施形態におけるＤＢシステム１０の構成例を示す概念図である。図１２に示すように、第２実施形態におけるＤＢシステム１０は、第１実施形態の構成に加えて、処理時間格納部６００を更に有する。処理時間格納部６００は、ＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）などのようなメモリ上に実現される。
【００７３】
パラメータ指定部３００は、分割候補点のサンプリング数の上限値に加え、ヒストグラム生成希望時間を選択部２３０に送る。このヒストグラム生成希望時間とは、ヒストグラム生成に費やす時間長であってユーザ等により希望される時間長である。このヒストグラム生成希望時間は、サンプリング数の上限値等と共に、設定ファイルに格納されていてもよいし、ユーザインタフェース等を介して取得されてもよい。
【００７４】
図１３は、処理時間格納部６００に格納される処理時間データの例を示す図である。図１３の例に示すように、処理時間格納部６００は、分割候補点のサンプリング数に対して、実際にヒストグラムを生成するのに費やされた時間を格納する。
【００７５】
選択部２３０は、パラメータ指定部３００から取得されたサンプリング数の上限値及びヒストグラム生成希望時間、並びに、処理時間格納部６００に格納される処理時間データに基づいて、分割候補点のサンプリング数を決定する。具体的には、処理時間格納部６００に所定レコード数の処理時間データが格納されている場合には、選択部２３０は、処理時間格納部６００から抽出された処理時間データから、サンプリング数の上限値を超えない範囲で、ヒストグラム生成希望時間に相当するサンプリング数を決定する。
【００７６】
ヒストグラム生成部２４０は、ヒストグラムの生成に要した時間を測り、計測された生成時間及びそのときのサンプリング数を処理時間格納部６００に格納する。
【００７７】
〔動作例〕
図１４は、第２実施形態におけるＤＢシステム１０のヒストグラム生成時の動作例を示すフローチャートである。
【００７８】
パラメータ指定部３００は、第１実施形態で利用される各種パラメータ（例えば、サンプリング数の上限値）に加えて、ヒストグラム生成希望時間をヒストグラム生成系２００へ送る（Ｓ１０１）。以降、（Ｓ１１０）、（Ｓ１２０）及び（Ｓ１３０）の各処理については第１実施形態と同様である（図６参照）。
【００７９】
選択部２３０は、分割候補点のサンプリングを実行する前に、サンプリング数を計算し、決定する（Ｓ１４１）。具体的には、選択部２３０は、処理時間格納部６００に所定レコード数以上のデータが格納されている場合には、サンプリング数及び処理時間を含むレコードを抽出し、抽出されたサンプリング数及び処理時間の複数の組み合わせを用いて回帰分析を行う。選択部２３０は、得られた回帰曲線から、ヒストグラム生成希望時間に対応する値を算出し、算出された値をサンプリング数に決定する。なお、処理時間格納部６００に所定レコード数以上のデータがない場合には、第１実施形態と同様の手法によりサンプリング数が決定されればよい。
【００８０】
以降、選択部２３０は、この決定されたサンプリング数により分割候補点のサンプリングを行う（Ｓ１４０）。その後の処理（Ｓ１５０）及び（Ｓ１６０）は第１実施形態と同様である。
【００８１】
ヒストグラム格納部４００にヒストグラムを格納すると、ヒストグラム生成部２４０は、そのヒストグラムの生成にかかった処理時間と、そのときの分割候補点のサンプリング数とを処理時間格納部６００に格納する（Ｓ１６１）。
【００８２】
〔第２実施形態の作用及び効果〕
このように第２実施形態では、ヒストグラム生成部２４０によりヒストグラムが生成されると、その処理時間とサンプリング数（分割候補点数）とが処理時間格納部６００に格納される。ヒストグラム生成に利用される分割候補点の数となるサンプリング数は、処理時間格納部６００に格納される処理時間とサンプリング数との履歴データに基づいて、ユーザ等により望まれるヒストグラム生成希望時間に対応する値に決定される。
【００８３】
このように、第２実施形態によれば、例えば、複数のサンプリング数の各々で前もって複数のヒストグラムを生成し、処理時間格納部６００に履歴データを格納しておくことにより、ユーザ等が希望する生成時間に近似する時間でヒストグラムの生成を行うことができる。これは、処理時間格納部６００に格納される履歴データの回帰分析により所望される時間に対応するサンプリング数を計算することができるからである。
【００８４】
ユーザは、ヒストグラム生成に費やされる時間として許容する時間の感覚を認識することはできるが、その許容する時間でヒストグラムを生成させるためのサンプリング数を認識することは困難である。そのため、ユーザにとってサンプリング数を指定できるよりもヒストグラム生成希望時間を指定できる方が有益な場合が多い。よって、第２実施形態によれば、ユーザフレンドリーなシステムを提供することができる。
【００８５】
［変形例］
上述の各実施形態では、選択部２３０は、決定部２１０により決定された複数の分割候補点をサンプリングすることにより１つの分割候補点の集合を決定していた。しかしながら、選択部２３０は、複数タイプの分割候補点の集合を決定するようにしてもよい。つまり、選択部２３０は、サンプリング数の上限値を超えない範囲又はヒストグラム生成希望時間に対応して決定されたサンプリング数の集合であって、各集合に含まれる少なくとも１つの分割候補点がそれぞれ異なる分割候補点の集合を決定する。
【００８６】
この場合、選択部２３０は、決定された複数タイプの分割候補点の集合をヒストグラム生成部２４０に提供する。ヒストグラム生成部２４０は、各集合についてそれぞれヒストグラムを生成し、生成されたヒストグラムのうち最も評価の高いヒストグラムをヒストグラム格納部４００に格納する。なお、ヒストグラムの評価手法は、周知技術が利用されればよいため（例えば、非特許文献２及び非特許文献３参照）、ここでは説明を省略する。
【００８７】
このような変形例によれば、ヒストグラム生成の高速化を実現することができると共に、安定的にヒストグラムの精度の低下を抑えることができる。
【００８８】
なお、上記実施形態の説明には、複数のフローチャートを用いており、それぞれに複数のステップを順番に記載してあるが、その複数のステップの順番は内容的に支障しない範囲で変更することができる。また、上述した実施の形態および複数の変形例は、その内容が相反しない範囲で組み合わせることができる。
【符号の説明】
【００８９】
１０  関係データベースシステム（ＤＢシステム）
１００  データ格納部
２００  ヒストグラム生成系
２１０  分割候補点決定部（決定部）
２２０  変化値計算部
２３０  分割候補点選択部（選択部）
２４０  ヒストグラム生成部
３００  パラメータ指定部
４００  ヒストグラム格納部
５００  データ問合せ部
６００  処理時間格納部
【図１】
2012133608.tif 000003
【図２】
2012133608.tif 000004
【図３】
2012133608.tif 000005
【図４】
2012133608.tif 000006
【図５】
2012133608.tif 000007
【図６】
2012133608.tif 000008
【図７】
2012133608.tif 000009
【図８】
2012133608.tif 000010
【図９Ａ】
2012133608.tif 000011
【図９Ｂ】
2012133608.tif 000012
【図１０】
2012133608.tif 000013
【図１１】
2012133608.tif 000014
【図１２】
2012133608.tif 000015
【図１３】
2012133608.tif 000016
【図１４】
2012133608.tif 000017