(57)【特許請求の範囲】
【請求項１】
データベースと、該データベースのデータをキャッシュしたデータ・キャッシュと、データ・キャッシュのデータにアクセスするための無効化用インデックスをもつシステムにおいて、コンピュータの処理によって、無効化用インデックスを制御する方法であって、  参照クエリの検索条件を用いて作成される検索キーのフィールドと、前記検索条件に合致する前記データベースのレコードのＩＤのリストのフィールドと、カウント値のフィールドをもつ無効化用インデックスを、前記システムのメモリに用意するステップと、
参照クエリで取得したデータに基づき、検索キー作成に必要な検索条件を抽出して、前記無効化用インデックスの検索キーを作成するステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行を検索するステップと、  前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、前記カウント値を減少させるステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つからなかったことに応答して、新たな前記無効化用インデックスの行を作成して、その検索キーのフィールドに、前記作成された検索キーを格納し、ＩＤのリストのフィールドに、対応する前記検索条件に合致する前記データベースのレコードのＩＤを格納するステップと、
所定の時期に、前記カウント値が最小である、前記作成された検索キーをもつ前記無効化用インデックスの行を、前記データベースのレコードの値に関連する条件に基づき分割し、分割した各々の行のＩＤのリストのフィールドには、前記レコードの値に関連する条件に従い元の行のＩＤのリストに格納されていたＩＤの値を振り分けて格納し、分割した各々の行の検索キーのフィールドには、振り分けて格納されたＩＤの値に基づいて計算された異なる検索キーの値をそれぞれ格納する処理を、可能なインデックス・サイズ内で繰り返すステップを有する、
無効化用インデックスを制御する方法。
【請求項２】
更新クエリの検索条件部分に基づき、前記無効化用インデックスの検索キーを作成するステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、その行のＩＤのリストのフィールドに格納されているＩＤに対応するデータ・キャッシュのデータを無効化し、その行のカウント値を増加させるステップをさらに有する、  請求項１に記載の方法。
【請求項３】
所定の時期に、前記カウント値が所定の閾値より大きい前記無効化用インデックスの行をまとめて、まとめられた行のＩＤのリストのフィールドのＩＤの値を合弁し、合弁されたＩＤの値に対応する検索キーを計算して、まとめられた行の検索キーのフィールドに格納するステップをさらに有する、請求項２に記載の方法。
【請求項４】
前記カウント値を増加させるステップが、前記カウント値を１だけ増分させる、請求項２に記載の方法。
【請求項５】
前記カウント値を増加または減少させるステップが、前記無効化用インデックスの各行のデータ更新と参照クエリの数を基に重みをつけた値を導出して、前記カウント値に格納する、請求項２に記載の方法。
【請求項６】
データベースと、該データベースのデータをキャッシュしたデータ・キャッシュと、データ・キャッシュのデータにアクセスするための無効化用インデックスをもつシステムにおいて、コンピュータの処理によって、無効化用インデックスを制御するプログラムであって、
前記コンピュータに、
参照クエリの検索条件を用いて作成される検索キーのフィールドと、前記検索条件に合致する前記データベースのレコードのＩＤのリストのフィールドと、カウント値のフィールドをもつ無効化用インデックスを、前記システムのメモリに用意するステップと、
参照クエリで取得したデータに基づき、検索キー作成に必要な検索条件を抽出して、前記無効化用インデックスの検索キーを作成するステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行を検索するステップと、  前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、前記カウント値を減少させるステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つからなかったことに応答して、新たな前記無効化用インデックスの行を作成して、その検索キーのフィールドに、前記作成された検索キーを格納し、ＩＤのリストのフィールドに、対応する前記検索条件に合致する前記データベースのレコードのＩＤを格納するステップと、
所定の時期に、前記カウント値が最小である、前記作成された検索キーをもつ前記無効化用インデックスの行を、前記データベースのレコードの値に関連する条件に基づき分割し、分割した各々の行のＩＤのリストのフィールドには、前記レコードの値に関連する条件に従い元の行のＩＤのリストに格納されていたＩＤの値を振り分けて格納し、分割した各々の行の検索キーのフィールドには、振り分けて格納されたＩＤの値に基づいて計算された異なる検索キーの値をそれぞれ格納する処理を、可能なインデックス・サイズ内で繰り返すステップを実行させる、
無効化用インデックスを制御するプログラム。
【請求項７】
更新クエリの検索条件部分に基づき、前記無効化用インデックスの検索キーを作成するステップと、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、その行のＩＤのリストのフィールドに格納されているＩＤに対応するデータ・キャッシュのデータを無効化し、その行のカウント値を増加させるステップをさらに有する、  請求項６に記載のプログラム。
【請求項８】
所定の時期に、前記カウント値が所定の閾値より大きい前記無効化用インデックスの行をまとめて、まとめられた行のＩＤのリストのフィールドのＩＤの値を合弁し、合弁されたＩＤの値に対応する検索キーを計算して、まとめられた行の検索キーのフィールドに格納するステップをさらに有する、請求項７に記載のプログラム。
【請求項９】
前記カウント値を増加させるステップが、前記カウント値を１だけ増分させる、請求項７に記載のプログラム。
【請求項１０】
前記カウント値を増加または減少させるステップが、前記無効化用インデックスの各行のデータ更新と参照クエリの数を基に重みをつけた値を導出して、前記カウント値に格納する、請求項７に記載のプログラム。
【請求項１１】
データベースと、該データベースのデータをキャッシュしたデータ・キャッシュと、データ・キャッシュのデータにアクセスするための無効化用インデックスをもつシステムにおいて、
メモリと、
参照クエリの検索条件を用いて作成される検索キーのフィールドと、前記検索条件に合致する前記データベースのレコードのＩＤのリストのフィールドと、カウント値のフィールドをもつ無効化用インデックスを、前記メモリに作成する手段と、
参照クエリで取得したデータに基づき、検索キー作成に必要な検索条件を抽出して、前記無効化用インデックスの検索キーを作成する手段と、
前記作成された検索キーをもつ前記無効化用インデックスの行を検索する手段と、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、前記カウント値を減少させる手段と、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つからなかったことに応答して、新たな前記無効化用インデックスの行を作成して、その検索キーのフィールドに、前記作成された検索キーを格納し、ＩＤのリストのフィールドに、対応する前記検索条件に合致する前記データベースのレコードのＩＤを格納する手段と、
所定の時期に、前記カウント値が最小である、前記作成された検索キーをもつ前記無効化用インデックスの行を、前記データベースのレコードの値に関連する条件に基づき分割し、分割した各々の行のＩＤのリストのフィールドには、前記レコードの値に関連する条件に従い元の行のＩＤのリストに格納されていたＩＤの値を振り分けて格納し、分割した各々の行の検索キーのフィールドには、振り分けて格納されたＩＤの値に基づいて計算された異なる検索キーの値をそれぞれ格納する処理を、可能なインデックス・サイズ内で繰り返す手段を有する、
システム。
【請求項１２】
更新クエリの検索条件部分に基づき、前記無効化用インデックスの検索キーを作成する手段と、
前記作成された検索キーをもつ前記無効化用インデックスの行が見つかったことに応答して、その行のＩＤのリストのフィールドに格納されているＩＤに対応するデータ・キャッシュのデータを無効化し、その行のカウント値を増加させる手段をさらに有する、
請求項１１に記載のシステム。
【請求項１３】
所定の時期に、前記カウント値が所定の閾値より大きい前記無効化用インデックスの行をまとめて、まとめられた行のＩＤのリストのフィールドのＩＤの値を合弁し、合弁されたＩＤの値に対応する検索キーを計算して、まとめられた行の検索キーのフィールドに格納する手段をさらに有する、請求項１２に記載のシステム。
【請求項１４】
前記カウント値を増加させる手段が、前記カウント値を１だけ増分させる、請求項１２に記載のシステム。
【請求項１５】
前記カウント値を増加または減少させる手段が、前記無効化用インデックスの各行のデータ更新と参照クエリの数を基に重みをつけた値を導出して、前記カウント値に格納する、請求項１２に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータ・システムにおけるデータベース処理に関し、特に、データベースのデータをキャッシュすることにより、データ・アクセスを高速化する技法に関するものである。
【背景技術】
【０００２】
従来より、データベースの検索を高速化するために、データをキャッシュすることが行われているが、データ更新によりキャッシュされたデータが最新でなくなる場合、キャッシュの無効化が必要となる。
【０００３】
その際、キャッシュ無効化の影響範囲を減らすために、インデックスを用いて無効化するキャッシュを特定する技術が知られている。しかし、その場合、インデックス用にメモリが必要になり、キャッシュのメモリサイズを圧迫してしまう、という問題があった。
【０００４】
それを軽減するために、インデックスに載せるデータを制限したり、ハッシュ分割したりすると、キャッシュ無効化の範囲が大きくなり、キャッシュ・ヒット率が低下してしまう。
【０００５】
データベースにアクセスするインデックスに載せるデータを制限する手法は、
http://db.cs.berkeley.edu/papers/ERL-M89-17.pdfあるいは、
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5740などの文献に記述されている。
【０００６】
また、データ更新時のキャッシュメンテナンス手法で似たものとして、具体化ビュー（materialized view）のメンテナンスの技術がある。例えば、
http://pages.cs.wisc.edu/~gangluo/partial_full.pdfに記述された技術がある。
【０００７】
さらに、特許文献として、特開２０００−３５９１２号公報は、ディレクトリ情報を記憶するデータベースを備えたディレクトリ・サーバにおいて、高キャッシュ効率を確保することを目的とするものであり、開示されている技術によれば、まずデータベースのキャッシュの空間が、アクセスパターン別に分割される。そして、分割したそれぞれの空間でＬＲＵをつかってキャッシュのeviction(キャッシュが指定したサイズからあふれた時にキャッシュデータを削除すること)を管理することにより、分割せず１つの空間でＬＲＵ管理するよりも高いキャッシュヒット率を維持できることが示されている。すなわち、上記アクセスパターンで分割したときに、各アクセスで必要とされない属性はキャッシュには載せないようにすることで、全属性を載せるのにくらべて無駄にキャッシュ空間を消費しない、という効果を与える。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０００−３５９１２号公報
【非特許文献】
【０００９】
【非特許文献１】http://db.cs.berkeley.edu/papers/ERL-M89-17.pdf
【非特許文献２】http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.5740
【非特許文献３】http://pages.cs.wisc.edu/~gangluo/partial_full.pdf
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記従来技術において、データ更新時のキャッシュ無効化の影響範囲を減らすために、インデックスを用いて無効化するキャッシュを特定する手法が提示される。ところが、一般的に、リソースの制限により、インデックスとして確保するメモリ領域のサイズは限度がある。しかし、インデックスのサイズを制限するためにインデックスに載せるデータを制限したり、ハッシュ分割した場合には、キャッシュ無効化の範囲が大きくなり、キャッシュ・ヒット率が低下してしまうという問題がある。
【００１１】
従って、本発明の目的は、限られたメモリ空間内で、データベースのキャッシュにアクセスするための無効化用インデックスを効率的に生成することにある。
【００１２】
本発明の別の目的は、ハッシュ分割された無効化用インデックスにおいて、キャッシュ無効化の影響を減らすことにある。
【課題を解決するための手段】
【００１３】
この発明は、上記問題を解決するためになされたものであり、限られたサイズ内の無効化用インデックスでキャシュヒット率を維持するため、ハッシュ分割された各分割領域に対する更新頻度と参照頻度の情報をもとに、更新の割合が高い分割領域をまとめ、参照の割合が高い分割領域はさらに細かく分割して無効化の影響をうけにくくすることにより、k個に均等に分割（ハッシュ分割）するよりもキャッシュヒット率が向上することを見込むものである。
【００１４】
本発明に従うシステムは先ず、例えば、INDEX_U1_HashMapと呼ぶ無効化用インデックスのテーブルをメモリ上に作成する。INDEX_U1_HashMapは、検索式の検索条件をハッシュしたフィールドと、その検索条件にヒットしたレコードのＩＤを含むフィールドと、カウントのフィールドを含む。
【００１５】
ある検索条件には一般的に複数のレコードがヒットするので、レコードのＩＤを含むフィールドは、複数のＩＤを含むことができる。
【００１６】
カウントのフィールドは、対応する検索条件でデータが更新、すなわち、その検索条件に該当するレコードのキャッシュが無効化されることに応答して増分され、対応する検索条件でデータが参照されることで減分される。これには限定されないが、典型的には増分とは１増やすことであり、減分とは１減らすことである。
【００１７】
所定期間経過後、本発明に従うシステムは、INDEX_U1_HashMapのカウントのフィールドを調べて、ここの値が所定の閾値よりも大きいことに応答してテーブルの行を統合し、統合によって空いた行数分、カウント値が最小の行から順に分割する。
【００１８】
カウントのフィールドが所定の閾値よりも大きいということは、更新の頻度が高いということであり、すると、行を統合することによって、INDEX_U1_HashMapの行の数を減らす。このことは、メモリ制約の下で、無効化用インデックスのテーブルの行の数を妥当に維持することを意味する。なお、更新に従って、対応するＩＤのフィールドのエントリは、フラッシュされる。
【００１９】
一方、カウントのフィールドが小さいということは、典型的には参照の頻度が高いということであり、すると、行を分割することによって、無効化用インデックスの行の無効化の影響を受けにくくする。すなわち、行を分割しておくと、ある検索条件に対してデータ更新が行われたとき、それにより影響を受ける行に含まれるＩＤが減り、キャッシュ・ヒット率が高まる。
【００２０】
このようにINDEX_U1_HashMapにおいて、カウントのフィールドの値に応じて統合され、あるいは分割されたテーブルは、以下では、INDEX_U1_WeightedHashMapとも呼ばれる。
【発明の効果】
【００２１】
この発明によれば、無効化用インデックスのテーブルにカウントのフィールドを設け、各行のデータ更新と参照クエリの数をもとに各行の重みを計算し、カウントのフィールドが所定の閾値よりも大きいことに応答して無効化用インデックスの行を統合し、統合により空いた行数分、カウント値が最小の行から順に無効化用インデックスの行を分割することによって重み付無効化用インデックスを生成することにより、サイズを妥当に保つとともに、参照アクセスに対してキャッシュ・ヒット率を高めるという効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】アプリケーション・サーバに、インターネットを介して、クライアント・コンピュータが接続されることを示す図である。
【図２】クライアント・コンピュータのハードウェア構成を示す図である。
【図３】アプリケーション・サーバ・サーバのハードウェア構成を示す図である。
【図４】本発明の実施例の機能ブロック図である。
【図５】データベースのレコードの例を示す図である。
【図６】データ・キャッシュのエントリの例を示す図である。
【図７】無効化用インデックスのエントリの例を示す図である。
【図８】Index_U1_WeightHashMapを作成する処理の概要フローチャートを示す図である。
【図９】更新クエリが発行された際の処理のフローチャートを示す図である。
【図１０】参照クエリが発行された際の処理のフローチャートを示す図である。
【図１１】無効化用インデックスのエントリ分割処理のフローチャートを示す図である。
【図１２】無効化用インデックスのエントリ分割処理の様子を示す図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことに留意されたい。
【００２４】
図１において、データベース・サーバの機能を併せ持つアプリケーション・サーバ１０２には、インターネット１０４を介して、複数のクライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚから、ＨＴＴＰなどのプロトコルにより、リクエストを受け取る。図１のシステムにおいては、クライアント・コンピュータのユーザは、Ｗｅｂブラウザを通じて、インターネット１０４の回線を介して、アプリケーション・サーバ１０２に、ログインする。具体的には、所定のＵＲＬをＷｅｂブラウザに打ち込んで、所定のページを表示する。なお、Ｗｅｂブラウザではなく、所定の専用クライアント・アプリケーション・プログラムを使ってログインするようにしてもよい。
【００２５】
次に、図２を参照して、図１で参照番号１０６ａ、１０６ｂ・・・１０６ｚのように示されているクライアント・コンピュータのハードウェア・ブロック図について、説明する。図２において、クライアント・コンピュータは、主記憶２０６、ＣＰＵ２０４、ＩＤＥコントローラ２０８をもち、これらは、バス２０２に接続されている。バス２０２には更に、ディスプレイ・コントローラ２１４と、通信インターフェース２１８と、ＵＳＢインターフェース２２０と、オーディオ・インターフェース２２２と、キーボード・マウス・コントローラ２２８が接続されている。ＩＤＥコントローラ２０８には、ハードディスク・ドライブ（ＨＤＤ）２１０と、ＤＶＤドライブ２１２が接続されている。ＤＶＤドライブ２１２は、必要に応じて、ＣＤ−ＲＯＭやＤＶＤから、プログラムを導入するために使用する。ディスプレイ・コントローラ２１４には、好適には、ＬＣＤ画面をもつディスプレイ装置２１６が接続されている。ディスプレイ装置２１６には、Ｗｅｂブラウザを通じて、アプリケーションの画面が表示される。
【００２６】
ＵＳＢインターフェース２２０には、必要に応じて、拡張ハードディスクなどのデバイスを接続をすることができる。
【００２７】
キーボード・マウス・コントローラ２２８には、キーボード２３０と、マウス２３２が接続されている。キーボード２３０は、検索のためのキーデータや、パスワードなどを打ち込むために使用される。
【００２８】
ＣＰＵ２０４は、例えば、３２ビット・アーキテクチャまたは６４ビット・アーキテクチャに基づく任意のものでよく、インテル社のＰｅｎｔｉｕｍ（インテル・コーポレーションの商標）４、Ｃｏｒｅ（商標）２  Ｄｕｏ、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。
【００２９】
ハードディスク・ドライブ２１０には、少なくとも、オペレーティング・システムと、オペレーティング・システム上で動作するＷｅｂブラウザ（図示しない）が格納されており、システムの起動時に、オペレーティング・システムは、メインメモリ２０６にロードされる。オペレーティング・システムは、Ｗｉｎｄｏｗｓ  ＸＰ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ  Ｖｉｓｔａ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ（マイクロソフト・コーポレーションの商標）  ７、Ｌｉｎｕｘ（Linus Torvaldsの商標）などを使用することができる。また、Ｗｅｂブラウザは、マイクロソフト・コーポレーションのInternet Explorer、Mozilla FoundationのMizilla FireFoxなど、任意のものを使用することができる。
【００３０】
通信インターフェース２１８は、オペレーティング・システムが提供するＴＣＰ／ＩＰ通信機能を利用して、イーサネット（商標）・プロトコルなどにより、アプリケーション・サーバ１０２と、通信する。
【００３１】
図３は、アプリケーション・サーバ１０２のハードウェア構成の概要ブロック図である。図３に示すように、クライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚは、インターネット１０４を経由して、アプリケーション・サーバ１０２の通信インターフェース３０２に接続される。通信インターフェース３０２はさらに、バス３０４に接続され、バス３０４には、ＣＰＵ３０６、主記憶（ＲＡＭ）３０８、及びハードディスク・ドライブ（ＨＤＤ）３１０が接続されている。
【００３２】
図示しないが、アプリケーション・サーバ１０２にはさらに、キーボード、マウス、及びディスプレイが接続され、これらによって、保守担当者が、アプリケーション・サーバ１０２全体の管理やメンテナンス作業を行うようにしてもよい。
【００３３】
アプリケーション・サーバ１０２のハードディスク・ドライブ３１０には、オペレーティング・システム、クライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚのログイン管理のための、ユーザＩＤとパスワードの対応テーブルが保存されている。ハードディスク・ドライブ３１０にはさらに、アプリケーション・サーバ１０２をＷｅｂサーバとして機能させるためのＡｐａｃｈｅなどのソフトウェア、及びＪａｖａ仮想環境を実現するＪａｖａ  ＥＥ、及びＪａｖａ仮想環境上で動作する本発明に係る後述するアプリケーション・プログラム４０２が保存され、アプリケーション・サーバ１０２の立ち上げ時に、主記憶３０８にロードされて、動作する。これによって、クライアント・コンピュータ１０６ａ、１０６ｂ・・・１０６ｚが、ＴＣＰ／ＩＰのプロトコルで、アプリケーション・サーバ１０２にアクセスすることが可能となる。
【００３４】
アプリケーション・サーバ１０２のハードディスク・ドライブ３１０にはさらに、後述するデータベース管理システム４０４とデータベース４０６が保存されている。
【００３５】
尚、上記アプリケーション・サーバ１０２として、インターナョナル・ビジネス・マシーンズ・コーポレーションから購入可能な、ＩＢＭ（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）System X、System i、System pなどの機種のサーバを使うことができる。その際、使用可能なオペレーティング・システムは、AIX（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）、UNIX(The Open Groupの商標)、Linux(商標)、Windows(商標)2003 Serverなどがある。
【００３６】
次に、図４を参照して、本発明の機能構成を説明する。アプリケーション・プログラム４０２は、Java(R)で書かれたプログラムであり、Ｏ／Ｒマッピングのアプリケーションである。Ｏ／Ｒマッピングとは、Java(R)のようなオブジェクト指向言語で扱うオブジェクトとリレーショナル・データベースのレコードをマッピング（対応付け）する機能である。これには限定されないが、ここでは例えば、オンラインショッピングサイトを想定する。
【００３７】
アプリケーション・プログラム４０２は、データベース管理システム４０４に問い合わせを出す。データベース管理システム４０４は、好適にはリレーショナル・データベースであり、例えば、IBM(R) DB2である。
【００３８】
データベース管理システム４０４が管理するデータベース４０６は、ハードディスク・ドライブ３１０に保存され、図５に示すようなレコードをもつ。なお、図５は単なる例示であり、データベース４０６は、実際はより多くのレコードを含むことを理解されたい。
【００３９】
アプリケーション・プログラム４０２は、主記憶３０８中に、データ・キャッシュ４０８と、無効化用インデックス（以下では、単にインデックスとも呼ぶこともある）４１０をもち、データベース管理システム４０４を介してデータベース４０６から取得したデータを、データ・キャッシュ４０８に格納する。図６は、データ・キャッシュ４０８のエントリの例を示す図である。なお、図６は単なる例示であり、データ・キャッシュ４０８は、実際はより多くのエントリを含むことを理解されたい。
【００４０】
アプリケーション・プログラム４０２は、クライアント・コンピュータから、データベース４０６のデータの参照クエリまたは更新クエリを受け取る。アプリケーション・プログラム４０２は、参照クエリに対して、条件を満たすデータを返す。条件を満たすデータがデータ・キャッシュ４０８にあれば、データ・キャッシュ４０８のデータがクライアント・コンピュータに返される。条件を満たすデータがデータ・キャッシュ４０８に見つからなければ、アプリケーション・プログラム４０２は、データベース管理システム４０４に問い合わせを行う。
【００４１】
アプリケーション・プログラム４０２は、問い合わせに対して、無効化用インデックス４１０のエントリに格納されている、データ・キャッシュ４０８中のデータのＩＤを使用することで、データ・キャッシュ４０８のデータに高速アクセスする。
【００４２】
図７に、無効化用インデックス４１０の構造とエントリの例を示す。図示されているように、無効化用インデックス４１０は、検索条件のハッシュのフィールドAACC'と、データベース４０６のレコードのＩＤの番号を含むフィールドと、カウントを含むフィールドを有する。検索条件のハッシュのフィールドは、問い合わせのＳＱＬ文のwhere以下の検索条件から生成される。ＩＤの番号を含むフィールドは、検索条件に該当するデータベース４０６のレコードのＩＤの番号を複数含むことができる。カウントを含むフィールドは、更新アクセスに応答して１だけ増分され、参照アクセスに応答して１だけ減分するように、アプリケーション・プログラム４０２によって操作される。
【００４３】
アプリケーション・プログラム４０２は、クライアント・コンピュータから、データベース４０６の更新クエリを受け取った場合は、データベース管理システム４０４に更新の問い合わせを行うとともに、データ・キャッシュ４０８中の該当するデータを削除する。更新処理によって、データ・キャッシュ４０８中の該当するデータは無効になるからである。
【００４４】
データ・キャッシュ４０８と、無効化用インデックス４１０は、アプリケーション・プログラム毎に主記憶３０８内に確保され、すると、アプリケーション・プログラムが複数、アプリケーション・サーバ１０２に走っている場合、１つのアプリケーション・プログラムに割当て可能な主記憶３０８の容量が制限される。本発明は、このような限られたメモリ容量の範囲内で、無効化用インデックス４１０を有効に利用することを意図する。
【００４５】
次に、アプリケーション・プログラム４０２による無効化用インデックス４１０に対する処理を、図８以下の図面を参照して、より詳細に説明する。
【００４６】
図８のフローチャートにおいて、アプリケーション・プログラム４０２は、ステップ８０２で、INDEX_U1_HashMapを使用した状態で処理を実行する。INDEX_U1_HashMapとは、図７に示すテーブルの構造をもつ無効化用インデックス４１０であり、この実施例では特に、初期的に作成された無効化用インデックス４１０を、INDEX_U1_HashMapと呼ぶことにする。
【００４７】
ここでのアプリケーション・プログラム４０２の典型的な処理とは、クライアント・コンピュータからの、データベースに対する更新クエリあるいは参照クエリを受け取ることである。更新クエリあるいは参照クエリを受け取った際の処理の詳細は、図９及び図１０のフローチャートを参照して、後で説明する。
【００４８】
アプリケーション・プログラム４０２は、ステップ８０４で、一定期間、処理を実行することによって、更新頻度と参照頻度の情報を蓄積する。ここでいう一定期間とは、文字通り所定の時間であってもよいし、更新クエリあるいは参照クエリを所定の回数受け取ることであってもよい。
【００４９】
アプリケーション・プログラム４０２は、ステップ８０６で、更新頻度と参照頻度の情報をもとに、無効化用インデックスを再分割して、INDEX_U1_WeightedHashMapを生成する。このインデックス再分割処理は、図１１のフローチャートを参照して、後で説明する。
【００５０】
なお、好適には、INDEX_U1_WeightedHashMapは、INDEX_U1_HashMapとは別の実体ではなく、この実施例では、INDEX_U1_HashMapに対して無効化用インデックスを再分割する処理を施した時点で、INDEX_U1_HashMapをINDEX_U1_WeightedHashMapと呼び変えている。
【００５１】
図８に示すINDEX_U1_WeightedHashMapの作成処理は、定期的に、あるいは所定のイベントに応答して、繰り返してもよい。このとき、ステップ８０２におけるINDEX_U1_HashMapとは、実際は前に作成されたINDEX_U1_WeightedHashMapであることに留意されたい。
【００５２】
次に、図９のフローチャートを参照して、アプリケーション・プログラム４０２がクライアント・コンピュータから更新クエリを受け取った場合の処理を説明する。
【００５３】
ステップ９０２では、クライアント・コンピュータが更新クエリを発行し、アプリケーション・プログラム４０２がその更新クエリを受け取る。ここで更新クエリとは例えば、次のようなＳＱＬ文であらわされるものである。
UPDATE ITEM SET CC = 'S72' WHERE AA = 'css' AND CC = 'S71'
【００５４】
ステップ９０４では、アプリケーション・プログラム４０２は、WHERE句のパラメータを抽出する。上記の例では、「AA = 'css' AND CC = 'S71'」が、WHERE句のパラメータである。
【００５５】
ステップ９０６では、アプリケーション・プログラム４０２は、WHERE句のパラメータからハッシュ値を計算する。本発明はこれに限定されるものではないが、この実施例では次のようにしてハッシュ値が計算される。すなわち、'css'と'S71'をそれぞれアスキーの文字コードで数値に変換すると、それぞれ、css = 678383、S71 = 512317となる。それを連結して、678383512317に対してハッシュ関数を適用して、ハッシュ値を得る。ここでのハッシュ関数とは、最も簡単なものとして、適当な素数での法(modulo)を使うこともできる。
【００５６】
この実施例の場合、適当な関数F()を用いて、
W = F('css','S71')
X = F('sjd','S71')
W = F('gh','S72')
W = F('sjd','S72')
....
のようになることを、図７の無効化用インデックスの例は示している。
【００５７】
図７のAACC'のフィールドに格納されるのは、このようにして計算されたハッシュ値である。なお、この実施例では、where句として、AA = ?? AND CC = ??のような定型の検索条件を想定しているので、ハッシュ値の計算が容易である。オンラインショッピングのサイトなどでは、いくつかの定型のクエリを決めて限定し使用するので、このような想定が可能である。
【００５８】
ステップ９０８では、アプリケーション・プログラム４０２は、計算結果のハッシュ値をもつINDEX_U1_HashMapの行のＩＤリストのフィールドにあるＩＤに対応するデータを、データ・キャッシュ４０８から削除する。更新クエリによって、そのＩＤに対応するデータが更新されたので、データ・キャッシュ４０８にある対応するデータが無効になったからである。これにあわせて、INDEX_U1_HashMapの行のＩＤリストのフィールドにあるＩＤのデータは、フラッシュされる。
【００５９】
ステップ９１０では、アプリケーション・プログラム４０２は、計算結果のハッシュ値をもつINDEX_U1_HashMapの行のカウントのフィールドの値を１だけ増分して、処理を終る。尚、他の更新が無効化用インデックスに影響を与えることも考えられる。その場合には、影響を受けた行のエントリを削除するなどして、無効化用インデックスを、メンテナンスするなどしてもよい。
【００６０】
次に、図１０のフローチャートを参照して、アプリケーション・プログラム４０２がクライアント・コンピュータから参照クエリを受け取った場合の処理を説明する。
【００６１】
ステップ１００２では、クライアント・コンピュータが参照クエリを発行し、アプリケーション・プログラム４０２がその参照クエリを受け取る。ここで参照クエリとは例えば、次のようなＳＱＬ文であらわされるものである。
SELECT * FROM ITEM WHERE AA = 'css' AND CC = 'S71'
【００６２】
ステップ１００４では、アプリケーション・プログラム４０２は、参照クエリの検索条件で指定されたデータが、データ・キャッシュにあるかどうかを判断する。もしそうなら、アプリケーション・プログラム４０２は、ステップ１００６で、無効化用インデックスに必要なカラムの値を抽出する。これは、実際上、ステップ９０４に関連して説明したのと等価な処理で、参照クエリのWHERE句のパラメータを抽出するものである。
【００６３】
ステップ１００８では、アプリケーション・プログラム４０２は、カラムの値からハッシュ値を計算する。これは、実際上、ステップ９０６に関連して説明したのと等価な処理である。
【００６４】
ステップ１０１０では、アプリケーション・プログラム４０２は、ステップ１００６で計算されたハッシュ値を、ハッシュ値フィールドにもつ無効化用インデックス４１０(INDEX_U1_HashMap)の行のカウント値を１だけ減少させる。
【００６５】
ステップ１０１２では、アプリケーション・プログラム４０２は、参照クエリで指定されたＩＤの値のデータをデータ・キャッシュ４０８から求めて返し、処理を終了する。
【００６６】
ステップ１００４に戻って、アプリケーション・プログラム４０２が、参照クエリの検索条件で指定されたデータが、データ・キャッシュにないと判断すると、アプリケーション・プログラム４０２は、ステップ１０１４で、データベース管理システム４０４に問い合わせを出して、参照クエリの検索条件で指定されたデータをデータベース４０６から取得する。
【００６７】
ステップ１０１６で、アプリケーション・プログラム４０２は、データベース４０６から取得したデータを、データ・キャッシュ４０８に挿入する。
【００６８】
ステップ１０１８では、アプリケーション・プログラム４０２は、無効化用インデックスに必要なカラムの値を抽出する。これは、実際上、ステップ９０４に関連して説明したのと等価な処理で、参照クエリのWHERE句のパラメータを抽出するものである。
【００６９】
ステップ１０２０では、アプリケーション・プログラム４０２は、カラムの値からハッシュ値を計算する。これは、実際上、ステップ９０６に関連して説明したのと等価な処理である。
【００７０】
ステップ１０２２では、アプリケーション・プログラム４０２は、ステップ１０２０で生成したハッシュ値をもつ無効化用インデックス４１０の行があれば、そのＩＤリストのフィールドに、ステップ１０１６でデータ・キャッシュ４０８に挿入したデータのＩＤの値を格納する。もしステップ１０２０で生成したハッシュ値をもつ無効化用インデックス４１０の行がなければ、アプリケーション・プログラム４０２は、無効化用インデックス４１０に空の行を作成し、そのハッシュ値のフィールドに、ステップ１０２０で計算したハッシュ値を格納し、そのＩＤリストのフィールドに、ステップ１０１６でデータ・キャッシュ４０８に挿入したデータのＩＤの値を格納する。
【００７１】
ステップ１０２４では、アプリケーション・プログラム４０２は、ステップ１０２２で無効化用インデックス４１０(INDEX_U1_HashMap)の行のＩＤリストに追加されたＩＤの値に対応するデータをデータ・キャッシュ４０８から求めて返し、処理を終了する。
【００７２】
次に、図１１のフローチャートを参照して、アプリケーション・プログラム４０２が、無効化用インデックス４１０(INDEX_U1_HashMap)の行を条件に従い分割し、あるいは統合する場合の処理を説明する。
【００７３】
ステップ１１０２では、アプリケーション・プログラム４０２は、無効化用インデックス４１０(INDEX_U1_HashMap)の行において、カウント数が、ユーザーが設定した閾値を超えている領域、すなわち、更新頻度の高い領域を選択する。図１２のINDEX_U1_HashMapの例では、AACC'のハッシュ値がXの行とZの行がそれに該当する。
【００７４】
ステップ１１０４では、アプリケーション・プログラム４０２は、ステップ１１０２で選択した更新頻度の高い領域をまとめる処理を行う。それは具体的に、図１２において、AACC'のハッシュ値がXの行１２０２とZの行１２０４を、INDEX_U1_WeightedHashMapにおいて、行１２０６に統合する処理である。このとき、行１２０６のAACC'のフィールドは、XZと表記されているが、これは、ハッシュ値がXとZのどちらでもこの行に該当することを意味する。これを実現するために、
XZ = F1(AAのフィールドの値,CCのフィールドの値) for ＩＤ=2,7,6,9,12となるような関数F1()を用意して、行１２０６のハッシュ値のフィールドには、ハッシュ値の計算に、F()でなくF1()を使うことを指示する目印をつけておく。あるいは、ハッシュ値のフィールドに、ハッシュ値の計算に使用される関数を入れておいてもよい。
【００７５】
このように統合された行では、統合前の行のＩＤリストも統合され、カウント値は、統合前の行から引き継ぐ必要はなく、0と置いてよい。３行以上の行の統合も可能であるが、別の閾値を設定して、合計のカウント値がその閾値を超える場合は、それ以上の統合はしないで、新たな行との統合をはかるようにしてもよい。
【００７６】
ステップ１１０６では、無効化用インデックス４１０(INDEX_U1_HashMap)の行のサイズがK、すなわち、許容される無効化用インデックスの行数以上かどうかをアプリケーション・プログラム４０２が判断し、もしそうなら、これ以上無効化用インデックス４１０行を増やすことは許されないので、単に処理は終る。
【００７７】
ステップ１１０６で、無効化用インデックス４１０の行のサイズがKより小さいと判断されると、ステップ１１０８に進み、そこで、アプリケーション・プログラム４０２は、カウント数の最も小さい領域、すなわち、参照割合の最も高い領域をさらに２分割する処理を行う。それは、図１２では、行１２０８である。この分割は例えば、ステップ９０６でハッシュ関数として使われた素数の法(modulo)とは異なる素数の法を使って、INDEX_U1_HashMapの分割対象の行１２０８のＩＤリストにあるＩＤを振り分ける。すなわち、ステップ９０６で説明したデータを数値化した値に対して、元のハッシュ関数では、ＩＤ = 1,3,4に対応するデータが同一のハッシュ値をもっていたが、別の法に基づくハッシュ関数によって、INDEX_U1_HashMapの分割対象の行１２０８が、INDEX_U1_WeightedHashMapで、ＩＤ = 1に対応する行１２１０と、ＩＤ = 3,4に対応する行１２０１２振り分けられる。
【００７８】
すなわち、前述の関数F()を用いると、
W = F('css','S71')  // ＩＤ = 1
W = F('gh','S72')   // ＩＤ = 3
W = F('sjd','S72')  // ＩＤ = 4
のように、ＩＤ = 1,3,4で同じハッシュ値Wとなるが、別の関数F2()を用意して、
W1 = F2('css','S71')  // ＩＤ = 1
W2 = F2('gh','S72')   // ＩＤ = 3
W2 = F2('sjd','S72')  // ＩＤ = 4
のように、ＩＤ = 1のグループと、ＩＤ = 3,4のグループで分かれるようにする。
【００７９】
その際、行１２１０と行１２１２のハッシュ値のフィールドには、ハッシュ値の計算に、F()でなくF2()を使うことを指示する目印をつけておく。あるいは、ハッシュ値のフィールドに、ハッシュ値の計算に使用される関数を入れておいてもよい。このとき、分割した後の行１２１０、１２１２では、カウント値をもとの行１２０８から引き継ぐ必要はなく、分割した直後で0とおいてよい。
【００８０】
一般的に、INDEX_U1_HashMapからINDEX_U1_WeightedHashMapを生成する際に、カウント値のフィールドは、0にクリアして加算しなおしてよい。
【００８１】
ステップ１１０８の行の分割は、ステップ１１０６で、無効化用インデックスのサイズが限界のKに達したと判断されるまで反復される。
【００８２】
このように無効化用インデックス４１０の行を分割しておくと、更新問い合わせに応答して一度に無効化される無効化用インデックス４１０の行は１つだけなので、更新問い合わせに従って無効化されるデータ・キャッシュのデータ数を減らし、キャッシュ・ヒット率を向上させることにより、データベース問い合わせを高速化することができる。
【００８３】
無効化用インデックス４１０におけるハッシュ・フィールドの計算は、必ずしもハッシュ関数を用いる必要はなく、WHERE句以下の式を数字に変換した結果の値を、レンジの固定刻みで振り分けるようにしてもよい。
【００８４】
また、上記実施例では、カウント値のフィールドの数値を、更新クエリに応答して１増加させ、参照クエリに応答して１減少させるようにしていたが、これには限定されず、次のようなバリエーションを採用してもよい。すなわち、この計算結果をカウント値のフィールドに格納する。
(1) 参照数×(参照数 / 更新数)
この場合は、値が高いほうが参照の割合と頻度が高い。
(2) キャッシュヒット率×参照数×(参照数 / 更新数)
これは、アプリケーションのふるまいの差を考慮して、キャッシュヒット率の差を入れた計算方式である。
(3) (キャッシュヒット数)×Chit / {更新数 × Cupdate + (キャッシュミス数) ×Cmiss }
これは、キャッシュヒット、キャッシュ無効化などのコストを考慮した計算方式であり、Chitはキャッシュヒットのコスト、Cupdateはキャッシュ無効化のコスト、Cmissはキャッシュミスのコストである。
【００８５】
さらに、上記実施例では、アプリケーション・サーバ中にデータベースが配置されているが、アプリケーション・サーバとは別にデータベース・サーバを設置して、そちらにデータベースを配置し、アプリケーション・サーバからデータベース・サーバにアクセスするようにしてもよい。
【００８６】
以上、特定のハードウェア及びソフトウェアのプラットアフォームの上で本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを、この分野の当業者なら理解するであろう。
【符号の説明】
【００８７】
１０２  アプリケーション・サーバ
３０２  通信インターフェース
３０６  ＣＰＵ
３０８  主記憶
３１０  ハードディスク・ドライブ
４０２  アプリケーション・プログラム
４０４  データベース管理システム
４０６  データベース
４０８  データ・キャッシュ
４１０  無効化用インデックス
【図１】
0005567967.tif 000002
【図２】
0005567967.tif 000003
【図３】
0005567967.tif 000004
【図４】
0005567967.tif 000005
【図５】
0005567967.tif 000006
【図６】
0005567967.tif 000007
【図７】
0005567967.tif 000008
【図８】
0005567967.tif 000009
【図９】
0005567967.tif 000010
【図１０】
0005567967.tif 000011
【図１１】
0005567967.tif 000012
【図１２】
0005567967.tif 000013