(57)【特許請求の範囲】
【請求項１】
ＫＶＳ（Key Value Store）を用いた分散データベース（ＤＢ）において、属性値を検索するためのhash関数を適用し、得られたhash値のhash空間上の位置に該当するサーバに、転置インデックスを格納するクラスタシステム、を構成する各前記サーバとしてのコンピュータを、
インデックス作成時には、
前記属性値を検索するためのhash関数に基づいて、前記属性値の属性種類分の属性のhash bit列を作成するhash bit列作成手段、
前記属性種類分の属性のhash bit列を所定の連結順序で結合する結合手段、として機能させるためのプログラム。
【請求項２】
前記結合手段は、
前記属性値の属性種類分のすべての属性が少なくとも一回、前記連結順序の先頭に配置して結合すること
を特徴とする請求項１に記載のプログラム。
【請求項３】
前記結合手段は、
前記属性値の属性種類を登場頻度の高い順に並び替え、並び替えた属性値から算出されたhash 値をbit列として結合すること
を特徴とする請求項１に記載のプログラム。
【請求項４】
前記結合手段は、
積条件の組合せ頻度が高い、前記属性値の属性種類のhash 値を上位にしてbit連結すること
を特徴とする請求項１に記載のプログラム。
【請求項５】
前記サーバは、
検索時には、積にされた検索条件の属性を先頭hash bit列にもつインデックスを選択し、該インデックスに対して範囲検索を実行すること
を特徴とする請求項１に記載のプログラム。
【請求項６】
ＫＶＳ（Key Value Store）を用いた分散データベース（ＤＢ）において、属性値を検索するためのhash関数を適用し、得られたhash値のhash空間上の位置に該当するサーバに、転置インデックスを格納するクラスタシステムであって、
前記サーバは、
インデックス作成時には、
前記属性値を検索するためのhash関数に基づいて、前記属性値の属性種類分の属性のhash bit列を作成するhash bit列作成手段と、
前記属性種類分の属性のhash bit列を所定の連結順序で結合する結合手段と、を備えること
を特徴とするクラスタシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムおよびクラスタシステムに関する。
【背景技術】
【０００２】
スケーラビリティの高い効果を得ることを最大目標としたデータベースの技術として、分散データベース（ＤＢ）が存在する。スケーラビリティを獲得するための方式としては、ＫＶＳ（Key Value Store）が代表的である。
現在広く利用されているデータベース（ＤＢ）として、ＲＤＢ（Relational Data Base）が存在する。このＲＤＢの技術は、Row（行）、Column（列）からなる２次元のテーブル構造でデータを表現し、ＳＱＬ（Structured Query Language）言語等によるクエリに応じて、JOIN（結合）や正規化を実行することで、検索等の処理を実現することができる。様々なアプリケーションは、ＲＤＢを用いて作成されることが多く、その理由は多岐に渡るが、特に重要な要素として、単純なkey検索だけでなく、データの属性値（value）でも検索できる機能を有するところが大きいと言える。但し、従来の分散システムでは、単純なkeyを用いたアプリケーションには適用できるが、valueを操作するアプリケーションには適用できないか、できてもスケール変更できない状況のものが多かった。しかも、データの構造を分散プラットフォーム（ＰＦ）用に大きく見直す必要もあった。
分散システムの研究分野でも、上記を鑑み、単純key検索用途のＮｏＳＱＬから、属性値検索を始めとしたＲＤＢ並みの操作能力を持つＮｅｗＳＱＬへの検討が多くされつつある。
【０００３】
分散システムにおいて属性値検索を可能とする代表的な手法として、Secondary Index等の転置インデックス手法があり、ＣａｓｓａｎｄｒａやＭｅｒｃｕｒｙ等の代表的な分散ＤＢが採用されてきている（非特許文献１，２参照）。但し、それらは、基本的に、複数のhash関数を用い、keyを主のhash関数に適用して得られた出力の場所にマスターデータを置き、検索したい属性値を別のhash関数に適用して得られた出力の場所にレプリカデータを置く仕組みである。
また、レプリカデータをリンクとして、データ容量の効率性を高めたＭｅｒＤｙという手法も存在する。
【０００４】
図１３は、ＭｅｒＤｙを説明する図である。
ＭｅｒＤｙは、転置インデックス（属性検索用）を用いて、属性値による検索を可能にする分散ＤＢにおいて、データの場所を示す識別子（hash値）を付与する。分散ＤＢにおけるデータ配置のサーバへの配置の決定方法としては、データの属性タグや属性値等にhash値をかけて識別子とする。一方、サーバ毎に担当する識別子領域を割り当ててある。
【０００５】
図１３に示すように、h0(key)を主のhash関数に適用して得られた出力のサーバ（このサーバは、ストレージとしての機能）にマスターデータ（ｖ０，ｖ１，ｖ２）を置き、検索したい属性値を別のhash関数に適用して得られた出力の場所にレプリカデータ（ｖ０，ｖ１，ｖ２）と（ｖ０，ｖ１，ｖ２）とを置く。なお、２つのレプリカデータを置くのは一例であって、冗長化数に従って決定される。
【０００６】
上記主のhash関数は、keyで検索されるh0(key)であり、ＭＤ５（Message Digest Algorithm 5）などの不連続hash関数である。このh0(key)にマスターデータ（ｖ０，ｖ１，ｖ２）を置く。
上記別のhash関数は、「属性値を検索するためのhash関数」であり、検索したい属性値に対して適用される上記主のhash関数とは別の、属性値で検索されるh1(v0),h2(v1),h3(v2)である。例えば、h1(v0)は、文字コード変換などの連続hash関数、h2(v1)は、文字数などの連続hash関数、h3(v2)は、ＳＨＡ１（Secure Hash Algorithm 1）などの不連続なhash関数である。なお、転置インデックス（属性検索用）のkeyをk1,k2,…で表すことがある。
前記した非特許文献１，２に記載のＭｅｒｃｕｒｙやＭｅｒＤｙでは、属性値に対して、keyと同様にhash関数を適用し、そのhash値のコンシステントハッシュ（Consistent Hashing）等の空間上の位置に該当するサーバに、転置インデックスを格納する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】川上 大輔, 他: “範囲検索と複数属性のデータの処理に適応した分散データストア” , 情報処理学会研究報告[システムソフトウェアとオペレーティング・システム] 2010-OS-113(10), 1-8, 2010-01-20.
【非特許文献２】Cassandra secondary index，［online］、［平成２６年7月21日検索］、インターネット<URL:http://books.google.co.jp/books?hl=ja&lr=&id=MKGSbCbEdg0C&oi=fnd&pg=PR7&dq=Cassandra+secondary+index&ots=XpPC2yy91A&sig=oCxd9a_Gvrp4cbfpidKEEVVMW6Y#v=onepage&q=Cassandra%20secondary%20index&f=false>
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ＫＶＳに基づいて分散配置されたデータに対してキー値でなく属性値(Value)で検索する場合において、条件を積にして検索する方法はいくつか存在する。例えば、単一の属性条件に適合するインデックスを集めてそれらを突き合わせる突合方式や論理式も含めた文字列でkeyを作成してhash値を算出する条件hash方式である。しかしながら、前者の突合方式では検索時の計算量が大きいという問題がある。また、後者の条件hash方式では、インデックス作成時にあらゆる論理式の組合せに対してhash値を検索する必要があるため、属性数が多くなると、インデックスの量が膨大化し、インデクシングの負荷が大きくなるという問題があった。さらに、後者は、属性値が変更された際に、その属性値を含む全ての論理式のインデックスに影響する等、インデックスの一貫性の観点でも問題があった。
【０００９】
このような背景を鑑みて本発明がなされたのであり、本発明は、検索時の負荷とインデクシングの負荷を小さくできるプログラムおよびクラスタシステムを提供することを課題とする。
【課題を解決するための手段】
【００１０】
前記した課題を解決するため、請求項１に記載の発明は、ＫＶＳ（Key Value Store）を用いた分散データベース（ＤＢ）において、属性値を検索するためのhash関数を適用し、得られたhash値のhash空間上の位置に該当するサーバに、転置インデックスを格納するクラスタシステム、を構成する各前記サーバとしてのコンピュータを、インデックス作成時には、前記属性値を検索するためのhash関数に基づいて、前記属性値の属性種類分の属性のhash bit列を作成するhash bit列作成手段、前記属性種類分の属性のhash bit列を所定の連結順序で結合する結合手段、として機能させるためのプログラムとした。
【００１１】
また、請求項６記載の発明は、ＫＶＳ（Key Value Store）を用いた分散データベース（ＤＢ）において、属性値を検索するためのhash関数を適用し、得られたhash値のhash空間上の位置に該当するサーバに、転置インデックスを格納するクラスタシステムであって、前記サーバは、インデックス作成時には、前記属性値を検索するためのhash関数に基づいて、前記属性値の属性種類分の属性のhash bit列を作成するhash bit列作成手段と、前記属性種類分の属性のhash bit列を所定の連結順序で結合する結合手段と、を備えることを特徴とするクラスタシステムとした。
【００１２】
このように、属性値の属性種類分の属性のhash bit列を結合した値を用いることで、検索時の負荷とインデクシングの負荷を小さくすることができる。すなわち、積条件の組合せ数に依存しないのでインデクシング負荷等は小さい。また、データ容量を節約できる上、一貫性も確保でき、データ設計時に何をkeyにするかを気にする必要もなく、柔軟な条件検索を実行することができる。
【００１３】
また、請求項２に記載の発明は、前記結合手段が、前記属性値の属性種類分のすべての属性が少なくとも一回、前記連結順序の先頭に配置して結合することを特徴とする請求項１に記載のプログラムとした。
【００１４】
このようにすることで、登場頻度が高い属性がより先頭にくるので、積条件検索全体の検索速度が向上する。
【００１５】
また、請求項３に記載の発明は、前記結合手段が、前記属性値の属性種類を登場頻度の高い順に並び替え、並び替えた属性値から算出されたhash 値をbit列として結合することを特徴とする請求項１に記載のプログラムとした。
【００１６】
このようにすることで、よく出現する属性タグを条件式に含む場合の検索速度が向上する。
【００１７】
また、請求項４に記載の発明は、前記結合手段が、積条件の組合せ頻度が高い、前記属性値の属性種類のhash 値を上位にしてbit連結することを特徴とする請求項１に記載のプログラムとした。
【００１８】
このようにすることで、よく出現する属性タグの組合せの条件積における検索速度が向上する。
【００１９】
また、請求項５に記載の発明は、前記サーバが、検索時には、積にされた検索条件の属性を先頭hash bit列にもつインデックスを選択し、該インデックスに対して範囲検索を実行することを特徴とする請求項１に記載のプログラムとした。
【００２０】
このようにすることで、検索時には、条件属性の１つを先頭bitに持つインデックスを選択し、それに対して範囲検索を実行することで実現するので、どのような積条件でも、領域が小さな範囲検索となる。膨大なインデックスの突合せがないため検索の負荷は小さいという効果がある。
【発明の効果】
【００２１】
本発明によれば、検索時の負荷とインデクシングの負荷を小さくできるプログラムおよびクラスタシステムを提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態に係るクラスタシステムを含む全体構成を示す図である。
【図２】本実施形態に係るクラスタシステムを構成するサーバの構成を示す機能ブロック図である。
【図３】（ａ）は本実施形態に係るクラスタシステムの属性タグ情報格納手段が格納する属性タグ情報の一例を示す図である。（ｂ）は本実施形態に係るクラスタシステムの属性タグ情報格納手段が格納するhash関数の出力bit長の一例を示す図である。
【図４】本実施形態に係るクラスタシステムの属性値を検索するためのhash関数のbit列の構成を説明する図である。
【図５】本実施形態に係るクラスタシステムの属性のhash値のbit連結インデクシング方法を説明する図である。
【図６】本実施形態に係るクラスタシステムの検索時のbit連結インデクシング方法を説明する図である。
【図７】本実施形態に係るクラスタシステムの検索時のbit連結インデクシング方法を説明する図である。
【図８】本実施形態に係るクラスタシステムの検索における積条件の登場頻度に従って結合するHash値の結合例を示す図である。
【図９】本実施形態に係るクラスタシステムの検索における積条件の登場頻度に従って結合するHash値の結合例を示す図である。
【図１０】本実施形態に係るクラスタシステムの検索における積条件の組合せ頻度に従って結合するHash値の結合例を示す図である。
【図１１】本実施形態に係るクラスタシステムのHash値の結合例を示す図である。
【図１２】本実施形態に係るクラスタシステムのHash値の結合例を示す図である。
【図１３】ＭｅｒＤｙを説明する図である。
【発明を実施するための形態】
【００２３】
次に、本発明を実施するための形態（以下、「本実施形態」という）におけるクラスタシステム１等について説明する。
【００２４】
（本実施形態のシステム構成）
本実施形態に係るクラスタシステム１について具体的に説明する。
図１は、本実施形態に係るクラスタシステムを含む全体構成を示す図である。
本実施形態に係るクラスタシステム１は、図１に示すように、ネットワークを介して、外部システムであるクライアント２等と接続される。そして、クライアント２からの入力データを受け取り、クラスタシステム１内でデータの保存、更新、検索等を行い、その結果を出力データとして、クライアント２に送信する。
【００２５】
図２は、本実施形態に係るクラスタシステム１を構成するサーバ１１の構成を示す機能ブロック図である。
図２に示すように、サーバ１１は、制御手段１１０、入出力手段２０は、メモリ手段３０、および記憶手段４０を含んで構成される。
【００２６】
入出力手段２０は、クライアント２や、各サーバ１１との間の情報の入出力を行う。この入出力手段２０は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００２７】
メモリ手段３０は、ＲＡＭ（Random Access Memory）等の一次記憶装置からなり、制御手段１１０によるデータ処理に必要な情報を一時的に記憶する。
【００２８】
記憶手段４０は、ハードディスクやフラッシュメモリ等の記憶装置からなり、クラスタシステム１内の各サーバ１１のＩＤ（ＩＰアドレス）等を記憶する。
【００２９】
制御手段１１０は、サーバ１１全体の制御を司り、情報受信手段１１１、構文解析手段１１２、属性タグ情報格納手段１１３、hash bit列作成手段１１４、結合手段１１５、検索手段１１６、および情報送信手段１１７を含んで構成される。なお、この制御手段１１０は、例えば、記憶手段４０に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ手段３０であるＲＡＭに展開し実行することで実現される。
【００３０】
情報受信手段１１１は、入出力手段２０を介して、クライアント２からの入力データ、他のサーバ１１等からの出力データを取得する。
【００３１】
構文解析手段１１２は、情報受信手段１１１から入力データを受け取り、その入力データの内容を構文解析する。例えば、構文解析手段１１２は、その入力データが、（ａ）keyの完全一致検索、（ｂ）keyの範囲検索、（ｃ）属性値（value）の完全一致検索、（ｄ）valueの範囲検索（部分文字列検索を含む）のいずれであるかを解析する。そして、構文解析手段１１２は、その解析結果をhash bit列作成手段１１４に引き渡す。
【００３２】
属性タグ情報格納手段１１３は、属性タグ毎に、属性タグに適用するhash関数、属性値に適用するhash関数、およびkeyに適用するhash関数を記憶手段４０に属性タグ情報として格納する（図３（ａ）参照）。また、各hash関数は、それぞれ何bitのhash値を算出するかを個別に記憶しているものとする。例えば、属性タグ「Location」や「Boolean」毎に、あらかじめ出力bit長が決まったhash関数のセットを格納している（図３（ｂ）参照）。
【００３３】
hash bit列作成手段１１４は、記憶手段４０に記憶された属性タグ情報から取得した属性タグ毎のhash関数及びbit長に基づいて、「属性値から得られたhash bit列」（図４の符号（Ａ）参照）と、「属性タグから得られた不連続hash bit列」（図４の符号（Ｂ）参照）と、「keyから得られた連続hash bit列」（図４の符号（Ｃ）参照）とを作成する。ここでhash値を２値でみる（２進数で表す）と、hash bit列となる。
hash bit列作成手段１１４は、インデックス作成時には、属性値を検索するためのhash関数に基づいて、属性値の属性種類分の属性のhash bit列を作成する。
【００３４】
結合手段１１５は、hash bit列を結合する。具体的には、結合手段１１５は、属性種類分の属性のhash bit列を所定の連結順序で結合する。結合手段１１５は、属性値の属性種類分のすべての属性が少なくとも一回、前記連結順序の先頭に配置して結合する。この場合、結合手段１１５は、属性の連結順序をサイクリックに入れ替える。
【００３５】
検索手段１１６は、検索時、積にされた検索条件の属性を先頭hash bit列にもつインデックスを選択し、該インデックスに対して範囲検索を実行する。
【００３６】
情報送信手段１１７は、入出力手段２０を介して、クライアント２や他のサーバ１１に出力データを送信する。
【００３７】
本実施形態は、「属性値を検索するためのhash関数」を、複数のhash bit列の組み合わせにより構成することを特徴とする。例えば、不連続関数（１つの属性値に対して不連続なhash関数(ＭＤ５など)を使うこと）、連続関数（文字コード変換で用いる数値化関数連続なhash関数を使うこと）といった排他的（二者択一的）な使用の仕方ではなく、bit列で結合したhash値を使うようにし、転置インデックス（属性検索用）を作成する。
【００３８】
以下、「属性値を検索するためのhash関数」の各bit列の構成について説明し、次に各bit列の結合手法について説明する。
図４は、「属性値を検索するためのhash関数」のbit列の構成を説明する図である。
図４に示すように、「属性値を検索するためのhash関数」のbit列は、「属性値から得られた連続hash bit列」（図４の符号（Ａ）参照）と、「属性タグから得られた不連続hash bit列」（図４の符号（Ｂ）参照）と、「keyから得られた連続hash bit列」（図４の符号（Ｃ）参照）と、から構成される。
なお、図４の符号（Ａ）に示す属性値から得られたhash bit列は、不連続hash bit列であってもよい。また、各hash bit列のビット長については、図５により後記する。
【００３９】
<属性値から得られたhash bit列>（図４の符号（Ａ）参照）
図４の符号（Ａ）に示すように、属性値から得られたhash bit列「00000101101101」は、転置インデックス（属性検索用）のhash値である。なお、図４の符号（Ａ）に示す属性値から得られた連続hash bit列は、従来例と同様の転置インデックスのhash値でもある。具体的には、本実施形態では、属性値に対して、keyと同様にhash関数を適用し、そのhash値（図４の符号（Ａ）に示すhash bit列）のコンシステントハッシュ等の空間上の位置に該当するサーバに、転置インデックス（属性検索用）を格納する。
【００４０】
<属性タグから得られた不連続hash bit列>（図４の符号（Ｂ）参照）
図４の符号（Ｂ）に示すように、属性タグから得られた不連続hash bit列「01001100101101」は、属性タグを不連続なＭＤ５等のhash関数に適用して得られたhash値である。一例を挙げる。「居住地」が「東京」であるとすると、属性値は「東京」、属性タグは「居住地」となる。なお、「居住地」が「東京」であることは「属性」となる。この「属性」とは、key に紐付いたデータの中身である。前記図１２を参照して説明すると、図１２のマスターデータｖ０について、ｖ０は属性値（属性）であり、属性値ｖ０がどこのデータかということはkey により関係が紐付けられている。属性値（属性）とkey とは、例えば一対一で関係が紐付けられている。
【００４１】
<keyから得られた連続hash bit列>（図４の符号（Ｃ）参照）
図４の符号（Ｃ）に示すように、keyから得られた連続hash bit列「111010101101000」は、keyを連続なhash関数に適用して得られたhash値である。
【００４２】
ここで、一般的には、転置インデックスを作成する場合、属性値は属性値で、keyはkeyで使用し、本実施形態のように、属性値にkeyを組み合わせてhash値とすることはない。当然のことながら、属性値から得られた連続hash bit列と属性タグから得られた不連続hash bit列とを結合させるものもなく、属性値から得られた連続hash bit列とkeyから得られた連続hash bit列とを結合させるものもない。
【００４３】
次に、bit連結インデクシング方法について説明する。
［概要］
<インデックス作成時>
本bit連結インデクシング方法におけるbit列は、図４の符号（Ａ）の部分に適用される。
本実施形態では、属性タグ、属性値、およびkeyに、コンシステントハッシュ等の空間で位置を決めるためのhash関数をそれぞれ適用した値を結合する。
特に、インデックスを作成する際に、全ての属性値のhash値を算出し、それをbit連結する。
（１）インデックス作成時には、各bit列間において、先頭は、異なる属性種類のhash値を配置するようにする。
（２）各bit列間においては、属性の連結順序をサイクリックに入れ替わるようにbit列の値をセットする。すなわち、bit連結する順序をサイクリックに入れ替え、どの属性も均等に各bit領域に割り当てられるようにする。
【００４４】
<検索時>
検索時には、積にされた検索条件の一つの属性を先頭bitにもつインデックスを選択し、それに対して範囲検索を実行する。どのような積条件でも、領域が小さな範囲検索となるので、膨大なインデックスの突合せがなく、検索の負荷は小さいという効果がある。
【００４５】
以下、具体的に説明する。
［インデックス作成時］
図５は、属性のhash値のbit連結インデクシング方法を説明する図である。
図５に示すように、データ５０は、key に紐付いたマスターデータ（例えば、前記図１２のマスターデータｖ０）である。図５では、keyは「１２３４」、その属性値は「山田」（属性タグは「姓」）、「太郎」（属性タグは「名」）、「男」（属性タグは「性別」）、および「東京」（属性タグは「居住地」）の各属性値を有するものとする。
【００４６】
<hash bit列作成>
インデックスを作成する際に、全ての属性値のhash値を算出する。
各属性値「山田」、「太郎」、「男」、および「東京」を、この順に属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）と記述する。属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）の下の矩形の中の数値が属性値から得られたhash bit列である。ここでは、８bitで表したがbit数はどのようなものでもよい。例えば、属性０（姓）のhash bit列「11010111」、属性１（名）のhash bit列「01110001」、属性２（性別）のhash bit列「00010100」、および属性３（居住地）のhash bit列「01011000」である。
【００４７】
<hash bit列のbit連結>
図５の符号ａに示すように、各属性値のhash値をbit連結したhash値を作成する。図５（ａ）の場合、「11010111」「01110001」「00010100」「01011000」がbit連結される。
そして、複数の属性値から算出されたhash値をbit列として結合した値に基づき、転置インデックスをクラスタ内のサーバ１１に格納するようにする。
【００４８】
<bit連結する順序入れ替え>
bit連結する順序をサイクリックに入れ替えることで、各bit列間において、先頭は、異なる属性種類のhash値を配置するようにする。
例えば、図５（ｂ）に示すように、次の順序では、属性１（名）のhash bit列「01110001」を先頭にくるようにbit連結する順序を入れ替える。この例では、この入れ替えに伴い、いままで先頭であった属性０（姓）のhash bit列「11010111」が最後尾となる。なお、一般的な前方一致の場合、先頭のみが重視される。
bit連結する順序をサイクリックに入れ替えることで、図５（ｃ）に示すように、次の順序では、属性２（性別）のhash bit列「00010100」を先頭にしたhash bit列が連結され、さらにその次の順序では、図５（ｄ）に示すように、属性３（居住地）のhash bit列「01011000」を先頭にしたhash bit列が連結される。
このように、インデックスを作成する際に、bit連結する順序をサイクリックに入れ替え、どの属性も均等に各bit領域に割り当てられるようにする。積条件の組合せ数に依存しないのでインデクシング負荷等は小さいという効果がある。
【００４９】
［検索時］
図６および図７は、検索時のbit連結インデクシング方法を説明する図である。
検索時には、検索条件の一つの属性を先頭bitにもつインデックスを選択し、それに対して範囲検索を実行する。
<例１>
図６は、クラスタ内のサーバ１１された転置インデックスに対して、属性２（性別）が男で、属性３（居住地）が東京を検索する場合の例である。属性０（姓）および属性１（名）は、検索対象外であるため「＊」（ワイルドカード）となっている。
条件式は、下記で示される。
属性２（性別）＝男 ∧ 属性３（居住地）＝東京
∧は、積の記号である。なお、∧（積）が実現できれば、∨(和)、¬(否定)、⇒(ならば)などを用いて全てを実現できることが知られている。
【００５０】
この例１の場合、hash bit列の先頭の８bitが「男」のhash値に、次のhash bit列の８bitが「東京」のhash値で決まる。したがって、図６の符号ａに示すように、hash空間上の当該hash領域を担当するインデックスを全て取得する。この例では、key「９８７６」「５４３２」「１２３４」「５６７８」を有するクラスタ内のサーバ１１からインデックスを取得する。そして、下位１６bitが全て「00000000」「00000000」から全て「11111111」「11111111」の領域に存在するインデックスを取得する。図６の符号ｂに示す「00010100」「01011000」「00000000」「00000000」から図６の符号ｃに示す「00010100」「01011000」「11111111」「11111111」の領域に存在するインデックスを取得することで、「男」∧「東京」の検索が実現される。
【００５１】
<例２>
図７は、クラスタ内のサーバ１１された転置インデックスに対して、属性０（姓）が山田で、属性２（性別）が男を検索する場合の例である。属性１（名）および属性３（居住地）は、検索対象外であるため「＊」（ワイルドカード）となっている。
条件式は、下記で示される。
属性０（姓）＝山田 ∧属性２（性別）＝男
この例２の場合、hash bit列の先頭の８bitが「山田」のhash値に、次のhash bit列の８bitが「男」のhash値で決まる。したがって、図７の符号ａに示すように、hash空間上の当該hash領域を担当するインデックスを全て取得する。この例では、key「９８７６」「５４３２」「１２３４」「５６７８」を有するクラスタ内のサーバ１１からインデックスを取得する。そして、「＊」（ワイルドカード）の対象８bitが全て「11010111」「00000000」「000010100」「00000000」から「11010111」「11111111」「00010100」「11111111」までの領域に存在するインデックスを取得する。図６の符号ｂ，ｃと符号ｄ，ｅに示すhash bit列の領域に存在するインデックスを取得することで、「山田」∧「男」の検索が実現される。
【００５２】
次に、Hash値の結合のバリエーションについて説明する。
<結合例１>
図８は、Hash値の結合例を示す図である。図８は、検索における積条件の登場頻度に従って結合する例１である。
属性値の属性種類として、前記図５に示す属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）があるものとする。また、これら属性種類の登場頻度は、属性２（性別）＞属性０（姓）＞属性３（居住地）＞属性１（名）であることが分かっているとする。
図８（ａ）に示すように、登場頻度の高い順に、属性種類を並び替え、並び替えた属性値から算出されたhash 値をbit列として結合する。
また、図８（ｂ）〜（ｄ）に示すように、登場頻度順にサイクリックに入れ替えて、bit連結する。登場頻度が高い属性がより先頭にくるので、積条件検索全体の検索速度が向上する。
【００５３】
<結合例２>
図９は、Hash値の結合例を示す図である。図９は、検索における積条件の登場頻度に従って結合する例２である。
属性値の属性種類として、前記図５に示す属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）があるものとする。また、これら属性種類の登場頻度は、属性２（性別）＞属性０（姓）＞属性３（居住地）＞属性１（名）の順に多く、かつ登場確率ＰがＰ(性別)＝０．５，Ｐ(姓)＝０．４，Ｐ(居住地)＝０．３，Ｐ(名)＝０．２であるとする。
図９の符号ａに示すように、それぞれの属性が必ず１回は先頭に来て、かつ、図９の符号ｂに示すように、結合するbit位置に応じて確率の重みづけ和をとるとともに、図９の符号ｃに示すように、この確率の重みづけ和が最大となる結合順序を決める。このようにすることで、よく出現する属性タグを条件式に含む場合の検索速度が向上する効果がある。
【００５４】
<結合例３>
図１０は、Hash値の結合例を示す図である。図１０は、検索における積条件の組合せ頻度に従って結合する例である。
属性値の属性種類として、前記図５に示す属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）があるものとする。また、積条件の組合せ頻度が分かっているとする。
例えば、属性２（性別）∧属性３（居住地）、属性０（姓）∧属性３（居住地）、属性０（姓）∧属性２（性別）、および属性０（姓）∧属性１（名）∧属性３（居住地）の積条件の組合せ頻度が高いものとする。
図１０（ａ）に示すように、積条件の組合せ頻度が高い、属性０（姓）および属性２（性別）のhash 値を上位にしてbit連結する。
【００５５】
同様に、図１０（ｂ）に示すように、積条件の組合せ頻度が高い、属性０（姓）および属性３（居住地）を上位にしてbit連結する。また、図８（ｃ）に示すように、積条件の組合せ頻度が高い、属性２（性別）および属性０（姓）のhash 値を上位にしてbit連結する。また、図１０（ｄ）に示すように、積条件の組合せ頻度が高い、属性３（居住地）と属性０（姓）と属性１（名）を上位にしてbit連結する。
ここで、積条件の組合せ頻度の検索が多い場合は、上記サイクリックな入れ替えはしないようにする。
なお、上記登場頻度（図９参照）、および上記組合せ頻度（図１０参照）に関して、それを利用するために、検索の際に検索条件に含まれる属性種類を検索履歴として記録しておくようにする。このようにすることで、よく出現する属性タグの組合せの条件積における検索速度が向上する効果がある。
【００５６】
次に、インデックス数の増減について説明する。
これまでの例では、属性数分だけのインデックスを作成していたが、固定数であれば属性数以上のインデックスを作成してもよい。また、同様な理由で属性数以下のインデックスでもよい。
<結合例４>
図１１は、Hash値の結合例を示す図である。図１１は、インデックス数を増減させて結合する例である。
前記図５の場合、属性数は、属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）の４つであり、図５（ａ）〜（ｄ）に示すように属性数分だけのインデックスを作成していた。属性値が固定数であれば属性数以上のインデックスを作成してもよい。
例えば、図１１（ａ）〜（ｄ）に示すように、図５（ａ）〜（ｄ）の場合と同様に属性数は、属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）の４つである。なお、図１１（ａ）〜（ｄ）については、図１０（ａ）〜（ｄ）の場合と同様の例を準用した。
図１１（ａ）〜（ｄ）に示すように、元の属性数は、４つであり、属性１（名）から始まるものは出現しない。そこで、図１１（ｅ）の符号ａに示すように、属性１（名）から始まるものを追加する。
【００５７】
<結合例５>
図１２は、Hash値の結合例を示す図である。図１２は、積条件として用いない属性があるならば結合しない例である。
これまでの例１〜３では、属性数分だけのhash値を結合していた。積条件として用いない属性があるならばそれは結合しなくてもよいものとする。
前記図５の場合、属性数は、属性０（姓）、属性１（名）、属性２（性別）、および属性３（居住地）の４つであり、図５（ａ）〜（ｄ）に示すように属性数分だけのインデックスを作成していた。
仮に、属性１（名）が積条件として用いない属性であることが分かっている場合、属性１（名）は結合しなくてもよいものとする。
例えば、図１２（ａ）〜（ｃ）に示すように、属性１（名）が積条件として用いない属性である場合、属性１（名）を結合しない。属性数は３つとなる。その結果、この例では、重複を避けるためインデックスの数も３つとなる。
【００５８】
以上説明したように、本実施形態のサーバ１１は、インデックス作成時、属性値を検索するためのhash関数に基づいて、属性値の属性種類分の属性のhash bit列を作成するhash bit列作成手段１１４と、属性種類分の属性のhash bit列を所定の連結順序で結合する結合手段１１５と、検索時、積にされた検索条件の属性を先頭hash bit列にもつインデックスを選択し、該インデックスに対して範囲検索を実行する検索手段１１６と、を備える。
【００５９】
これにより、属性値の属性種類分の属性のhash bit列を結合した値を用いることで、検索時の負荷とインデクシングの負荷を小さくすることができる。すなわち、積条件の組合せ数に依存しないのでインデクシング負荷等は小さい。また、データ容量を節約できる上、一貫性も確保でき、データ設計時に何をkeyにするかを気にする必要もなく、柔軟な条件検索を実行することができる。
【符号の説明】
【００６０】
１  クラスタシステム
２  クライアント
１１  サーバ
２０  入出力手段
３０  メモリ手段
４０  記憶手段
１１０  制御手段
１１１  情報受信手段
１１２  構文解析手段
１１３  属性タグ情報格納手段
１１４  hash bit列作成手段
１１５  結合手段
１１６  検索手段
１１７  情報送信手段
【図１】
0006291435.tif 000002
【図２】
0006291435.tif 000003
【図３】
0006291435.tif 000004
【図４】
0006291435.tif 000005
【図５】
0006291435.tif 000006
【図６】
0006291435.tif 000007
【図７】
0006291435.tif 000008
【図８】
0006291435.tif 000009
【図９】
0006291435.tif 000010
【図１０】
0006291435.tif 000011
【図１１】
0006291435.tif 000012
【図１２】
0006291435.tif 000013
【図１３】
0006291435.tif 000014