(57)【要約】【課題】排他制御の競合を最小化させ、負荷の偏りの発生時において低コストで負荷を平均化させる。【解決手段】複数のスレッドを処理するプロセッサと、メモリと、を備えてデータベースを提供する計算機で、前記データベースのインデクスツリーを探索するインデクスツリーの探索方法であって、前記計算機が、前記複数のスレッドに対して前記インデクスツリーの探索範囲を割り当てる第１のステップと、前記計算機が、探索キーを受け付ける第２のステップと、前記計算機が、前記受け付けた探索キーに対応するスレッドを選択する第３のステップと、前記計算機が、選択されたスレッドで、前記受け付けた探索キーで前記インデクスツリーを探索する第４のステップと、を含む。【選択図】図９
2015170239.tif 000002
【特許請求の範囲】
【請求項１】
複数のスレッドを処理するプロセッサと、メモリと、を備えてデータベースを提供する計算機で、前記データベースのインデクスツリーを探索するインデクスツリーの探索方法であって、
前記計算機が、前記複数のスレッドに対して前記インデクスツリーの探索範囲を割り当てる第１のステップと、
前記計算機が、探索キーを受け付ける第２のステップと、
前記計算機が、前記受け付けた探索キーに対応するスレッドを選択する第３のステップと、
前記計算機が、選択されたスレッドで、前記受け付けた探索キーで前記インデクスツリーを探索する第４のステップと、
を含むことを特徴とするインデクスツリーの探索方法。
【請求項２】
請求項１に記載のインデクスツリーの探索方法であって、
前記第１のステップは、
前記インデクスツリーを複数の探索範囲に分割し、前記分割した探索範囲を前記スレッドに割り当てることを特徴とするインデクスツリーの探索方法。
【請求項３】
請求項１に記載のインデクスツリーの探索方法であって、
前記第４のステップは、
前記インデクスツリーを構成するノードを参照または更新する際に、当該ノードが複数のスレッドから参照または更新されるか否かを判定するステップと、
前記判定の結果が真である場合に前記ノードに対して排他制御を行うステップと、
前記判定の結果が偽である場合に前記ノードに対して排他制御を禁止するステップと、
を含むことを特徴とするインデクスツリーの探索方法。
【請求項４】
請求項３に記載のインデクスツリーの探索方法であって、
前記第４のステップは、
前記判定の結果が偽となったノードより下位のノードについては、前記参照または更新されるか否かの判定を禁止して、かつ、前記下位のノードに対して排他制御を禁止することを特徴とするインデクスツリーの探索方法。
【請求項５】
請求項１に記載のインデクスツリーの探索方法であって、
前記計算機が、前記スレッドの負荷を検出し、前記スレッド間の負荷の偏りを検出する第５のステップと、
前記計算機が、前記スレッド間の負荷の偏りを検出すると、移動元のスレッドから負荷を移動させる移動先のスレッドを決定する第６のステップと、
前記計算機が、移動させる前記負荷の量を決定する第７のステップと、
前記計算機が、移動元のスレッドから前記決定された量の負荷を前記移動先のスレッドへ移動させる第８のステップと、
をさらに含むことを特徴とするインデクスツリーの探索方法。
【請求項６】
請求項５に記載のインデクスツリーの探索方法であって、
前記第６のステップは、
前記負荷の移動元のスレッドを実行しているプロセッサと同一のプロセッサ上で実行されているスレッドを優先的に選択することを特徴とするインデクスツリーの探索方法。
【請求項７】
請求項５に記載のインデクスツリーの探索方法であって、
前記第４のステップは、
前記インデクスツリーを構成するノードを参照または更新する際に、当該ノードの使用回数を負荷量として記録するステップをさらに有し、
前記第７のステップは、
前記移動元のスレッドと移動先のスレッドの負荷量が等しくなるように移動させる負荷量を決定するステップと、
前記ノードの負荷量が所定の閾値を超えたか否かを判定するステップと、
前記ノードの負荷量が所定の閾値を超えたか否かを判定するステップを最下位のノードから上位ノードへ向けて実行し、前記判定の結果が真になるまで行うステップと、
前記判定の結果が真となったノードを移動先のスレッドの新たな探索範囲とするステップと、
を含むことを特徴とするインデクスツリーの探索方法。
【請求項８】
請求項５に記載のインデクスツリーの探索方法であって、
前記第８のステップは、
前記負荷の移動元のスレッドが移動先のスレッドへ探索範囲の変更を要求するステップと、
前記移動先のスレッドが移動先のスレッドの探索範囲の変更を行うステップと、
前記移動先のスレッドが移動元のスレッドへ探索範囲の変更完了を通知するステップと、
前記移動元のスレッドが移動元のスレッドの探索範囲の変更を行うステップと、
を含むことを特徴とするインデクスツリーの探索方法。
【請求項９】
請求項２に記載のインデクスツリーの探索方法であって、
前記第１のステップは、
前記インデクスツリーを複数の探索範囲に分割し、前記分割した探索範囲の最小値と最大値とを前記スレッドに割り当てることを特徴とするインデクスツリーの探索方法。
【請求項１０】
複数のスレッドを処理するプロセッサと、メモリと、を備えてデータベースのインデクスツリーを探索する計算機であって、
前記複数のスレッドに対して前記インデクスツリーの探索範囲を割り当てるインデクス管理部と、
探索キーを受け付けて、前記探索キーに対応するスレッドを選択するリクエスト処理部と、を有し、
前記インデクス管理部は、
前記リクエスト処理部が選択したスレッドで、前記受け付けた探索キーで前記インデクスツリーを探索することを特徴とする計算機。
【請求項１１】
請求項１０に記載の計算機であって、
前記インデクス管理部は、
前記インデクスツリーを複数の探索範囲に分割し、前記分割した探索範囲を前記スレッドに割り当てることを特徴とする計算機。
【請求項１２】
請求項１０に記載の計算機であって、
前記インデクス管理部は、
前記インデクスツリーを構成するノードを参照または更新する際に、当該ノードが複数のスレッドから参照または更新されるか否かを判定し、前記判定の結果が真である場合に前記ノードに対して排他制御を行い、前記判定の結果が偽である場合には前記ノードに対して排他制御を禁止することを特徴とする計算機。
【請求項１３】
請求項１２に記載の計算機であって、
前記インデクス管理部は、
前記判定の結果が偽となったノードより下位のノードについては、前記参照または更新されるか否かの判定を禁止して、かつ、前記下位のノードに対して排他制御を禁止することを特徴とする計算機。
【請求項１４】
請求項１０に記載の計算機であって、
前記インデクス管理部は、
前記スレッドの負荷を検出し、前記スレッド間の負荷の偏りを検出し、前記スレッド間の負荷の偏りを検出すると、移動元のスレッドから負荷を移動させる移動先のスレッドを決定し、移動させる前記負荷の量を決定し、移動元のスレッドから前記決定された量の負荷を前記移動先のスレッドへ移動させることを特徴とする計算機。
【請求項１５】
請求項１４に記載の計算機であって、
前記インデクス管理部は、
前記負荷の移動元のスレッドを実行しているプロセッサと同一のプロセッサ上で実行されているスレッドを優先的に選択することを特徴とする計算機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース管理システムにおけるインデクスアクセスの処理に関する。
【背景技術】
【０００２】
近年の計算機ハードウェアの進化により、計算機は、多数のＣＰＵコアを含むマルチコアＣＰＵ、および大容量のメモリを備えることが可能になってきている。これに対し、データベース管理システム（ＤＢＭＳ）では、メモリ上に全てのデータを格納し処理する、インメモリＤＢがより一般的になってきている。データを永続記録媒体（HDDやSSD）に記憶する従来のＤＢＭＳ（ディスクＤＢ）では、記録媒体に対する入出力が性能上のボトルネックとなるが、インメモリＤＢにおいては、多数のＣＰＵコア上で実行されるスレッドがメモリ上で同時に処理を行うため、スレッド間の排他制御における競合がボトルネックとなる。そのため、スレッド間の排他競合を最小限にし、多数のスレッドが並列してデータベース処理を行うことが、データベース管理システムの性能向上において必要となっている。
【０００３】
従来のデータベース処理において排他競合が発生しやすい処理として、インデクスアクセス処理がある。インデクスアクセス処理では、多数のスレッドが並列に同一のデータ構造にアクセスするため、データ構造に対する排他制御が必要となり、スレッド間の同時実行性能が低下する問題がある。また、排他制御の競合を回避し同時実行性能を向上させるために複雑な排他制御処理を行うと、排他制御処理自体がオーバヘッドとなり、性能のボトルネックになるという問題があった。
【０００４】
前記の問題に対し、特許文献１では、インデクスツリーの探索時には、探索条件に該当する中間ノードまでを排他制御の対象とし、当該中間ノード以下のノードに対する排他制御は行わないことによる、排他制御処理の削減手法が開示されている。
【０００５】
また、非特許文献１では、インデクスツリーをスレッド単位に分割し、分割された各々のインデクスサブツリーには、単一のスレッドのみがアクセスする手法が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−３２３１５３号公報
【非特許文献】
【０００７】
【非特許文献１】PLP: page latch-free shared-everything OLTP (Proceedings of the VLDB Endowment, Volume 4 Issue 10, July 2011)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、上記特許文献１の手法では、探索条件に該当する中間ノード以下を一括して排他制御処理を行うため、排他制御の粒度が大きく、もし探索範囲が重複した場合には排他制御の競合が発生するという問題がある。
【０００９】
また、非特許文献１の手法では、インデクスアクセス処理における排他処理を不要とすることが可能である。しかし、スレッド間に負荷の偏りが生じた場合には、システム全体のスループットが低下するという問題がある。負荷を平均化して偏りを解消するためには、インデクスサブツリー間でデータを移動する必要があるが、その際にインデクスサブツリー間の排他制御が必要となり、また、データ構造の変更を伴うため、処理負荷が大きいという問題があった。
【００１０】
以上の従来技術に対して、排他処理および排他制御の競合を最小化させること、および、負荷の偏りの発生時において小さい処理コストで負荷を平均化させることの両立が課題となる。
【課題を解決するための手段】
【００１１】
本発明は、複数のスレッドを処理するプロセッサと、メモリと、を備えてデータベースを提供する計算機で、前記データベースのインデクスツリーを探索するインデクスツリーの探索方法であって、前記計算機が、前記複数のスレッドに対して前記インデクスツリーの探索範囲を割り当てる第１のステップと、前記計算機が、探索キーを受け付ける第２のステップと、前記計算機が、前記受け付けた探索キーに対応するスレッドを選択する第３のステップと、前記計算機が、選択されたスレッドで、前記受け付けた探索キーで前記インデクスツリーを探索する第４のステップと、を含む。
【発明の効果】
【００１２】
したがって、本発明は、スレッド間で同時にアクセスされる可能性があるノードに対してのみ排他制御を行い、同時にアクセスされる可能性がないノードに対しては排他制御を行わないことにより、排他制御の実行回数を低減することが可能となる。また、排他制御が必要なノードにおいても、スレッドの探索範囲割当てにより当該ノードにアクセスするスレッドが減少するため、排他制御の競合が発生する頻度を低減することが可能となる。さらに、スレッドの探索範囲割当てを変更することにより、スレッド間で負荷の偏りが生じた場合でも、インデクスツリー構造を変更することなく負荷の平均化を行うことが可能となる。以上の効果により、データベース処理におけるインデクスアクセス速度を向上させることが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施例を示し、計算機システムの構成の一例を示すブロック図である。
【図２】本発明の実施例を示し、インデクスの論理的な構成の一例を表す模式図である。
【図３Ａ】本発明の実施例を示し、インデクスノードの内部構造の一例を表すブロック図である。
【図３Ｂ】本発明の実施例を示し、リーフノードの内部構造の一例を表すブロック図である。
【図４】本発明の実施例を示し、インデクスノードおよびリーフノードがメモリ上で物理的に配置される例を表すブロック図である。
【図５】本発明の実施例を示し、ＳＱＬ処理部およびインデクス管理部で行われる処理の概要を表すブロック図である。
【図６】本発明の実施例を示し、スレッド割当てテーブルの一例を示す図である。
【図７】本発明の実施例を示し、インデクス管理部がインデクス処理リクエストに基づいてエントリ探索処理を行う場合のフローチャートである。
【図８】本発明の実施例を示し、エントリ探索処理における排他取得処理で用いる排他可否決定テーブルである。
【図９】本発明の実施例を示し、排他処理回数削減の効果の例を示す図である。
【図１０】本発明の実施例を示し、負荷平均化処理の全体の流れを表すフローチャートである。
【図１１】本発明の実施例を示し、負荷平均化パラメタテーブルの例である。
【図１２】本発明の実施例を示し、負荷偏り検出処理の流れを表すフローチャートである。
【図１３】本発明の実施例を示し、スレッド−コア対応テーブルの例である。
【図１４Ａ】本発明の実施例を示し、負荷の移動先スレッドを決定するための移動方向決定テーブルの例である。
【図１４Ｂ】本発明の実施例を示し、負荷の移動先スレッドを決定するための移動方向決定テーブルの例である。
【図１５】本発明の実施例を示し、負荷移動量算出処理の流れを表すフローチャートである。
【図１６】本発明の実施例を示し、負荷移動処理の流れを表すフローチャートである。
【図１７】本発明の実施例を示し、スレッド負荷記録テーブルの一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態を添付図面に基づいて説明する。図１は、本発明の実施例を示し、本発明を適用する計算機システムの構成の一例を示すブロック図である。
【００１５】
図１において、ネットワーク１０１にはデータベース管理システム（ＤＢＭＳ）が稼働するＤＢサーバ１１０と、アプリケーションプログラム（以下、ＡＰ）１５１が稼働するＡＰサーバ１５０が接続されている。
【００１６】
ＡＰサーバ１５０のハードウェア構成の詳細は省略するが、内部でアプリケーションプログラム１５１が稼働している。アプリケーションプログラム１５１は、その処理の過程において、ネットワーク１０１を経由してＤＢサーバ１１０にデータベース処理要求を発行し、その処理結果を受信することによりアプリケーション処理を行う。データベース処理要求は一般的にはＳＱＬ言語（Structured Query Language）により記述される。
【００１７】
ＤＢサーバ１１０は、複数のプロセッサ１１１−１（Ｐ１）、１１１−２（Ｐ２）とメモリ１１５−１〜１１５−４を備える。なお、プロセッサの総称を符号１１１で表し、メモリの総称を符号１１５で表す。
【００１８】
プロセッサ１１１は、演算処理を行うＣＰＵコア（またはプロセッサコア）１１２を複数備え、複数のＣＰＵコア１１２（Ｃ１、Ｃ２）で共有アクセスされる共有キャッシュメモリ１１３と、メモリ１１５へのアクセスを制御するメモリコントローラ１１４を備える。
【００１９】
ＣＰＵコア１１２は後述のスレッド４０２（図５参照）を実行する。スレッド４０２は、ＤＢＭＳプログラム１２０がＣＰＵコア１１２毎に発行する処理の単位である。プロセッサ１１１とメモリ１１５は、２チャンネルのメモリコントローラ１１４を介して接続されている。あるプロセッサ１１１内のＣＰＵコア１１２が、他のプロセッサ１１１に接続されているメモリ１１５へアクセスを行う場合には、メモリコントローラ１１４間でデータを転送することによりメモリアクセスを行う。
【００２０】
この処理はメモリコントローラ１１４により透過的に行われるため、ＣＰＵコア１１２が処理を実行する際には、アクセス先のメモリ１１５がいずれのプロセッサ１１１に接続されているメモリであるかを区別する必要はない。
【００２１】
ただし、同一プロセッサ１１１に接続されたメモリ１１５にアクセスする場合と、他のプロセッサ１１１に接続されたメモリ１１５にアクセスする場合では、アクセス速度（またはレイテンシ）には差が生じ、後者の場合の方が低速である。
【００２２】
メモリ１１５には、データベース処理を行うデータベース管理システム（ＤＢＭＳ）プログラム１２０がロードされ、プロセッサ１１１によって実行される。ＤＢＭＳプログラム１２０は、アプリケーションプログラム１５１からのデータベース処理要求を受信して、データベース処理要求（ＳＱＬ）に基づいてテーブルデータ１２９に対する操作を行うＳＱＬ処理部（リクエスト処理部）１２１と、インデクス１２８に関する処理を行うインデクス管理部１２２と、操作対象データであるテーブルデータ１２９と、テーブルデータ１２９に対応するインデクスであるインデクス１２８を備える。
【００２３】
インデクス管理部１２２は、排他制御を行う排他管理部１２３と、スレッドに対する探索範囲を格納するスレッド割当てテーブル１２４と、スレッド間の負荷の平均化処理を行う負荷平均化管理部１２５と、負荷平均化処理に用いるパラメタを格納する負荷平均化パラメタテーブル１２６と、各スレッドが実行されているプロセッサやＣＰＵコアが記録されているスレッド−コア対応テーブル１２７を備える。なお、排他管理部１２３は、図８に示す排他可否決定テーブル８００を保持する。
【００２４】
なお、本実施例ではスレッドによって様々な処理が実行される例を示すが、必ずしもスレッドである必要はなく、プロセス間で共有可能なメモリと、複数のプロセスにより実現することも可能である。この場合、プロセスは、ＤＢＭＳプログラム１２０がＣＰＵコア１１２毎に発行する処理の単位とすることができる。
【００２５】
ＤＢＭＳプログラム１２０のＳＱＬ処理部１２１とインデクス管理部１２２の各機能部はプログラムとしてメモリ１１５にロードされる。
【００２６】
プロセッサ１１１の各ＣＰＵコア１１２は、各機能部のプログラムに従って処理することによって、所定の機能を提供する機能部として稼働する。例えば、ＣＰＵコア１１２は、ＳＱＬ処理プログラムに従って処理することでＳＱＬ処理部１２１として機能する。他のプログラムについても同様である。さらに、ＣＰＵコア１１２は、各プログラムが実行する複数の処理のそれぞれの機能を提供する機能部としても稼働する。計算機及び計算機システムは、これらの機能部を含む装置及びシステムである。
【００２７】
ＤＢＭＳプログラム１２０の各機能を実現するプログラム、テーブル等の情報は、ストレージサブシステム（図示省略）や不揮発性半導体メモリ、ハードディスクドライブ、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の記憶デバイス、または、ＩＣカード、ＳＤカード、ＤＶＤ等の計算機読み取り可能な非一時的データ記憶媒体に格納することができる。
【００２８】
次に、図２から図４を用いて、インデクス１２８の構成について説明する。
【００２９】
図２は、インデクス１２８の論理的な構成を表す模式図である。ここでは、ＤＢＭＳにおいて一般的に用いられているＢ＋ツリーインデクスを例にとり説明する。
【００３０】
Ｂ＋ツリーインデクスは、インデクスノード２０１ａ〜２０１ｄおよびリーフノード２０２ａ〜２０２ｈがポインタによってツリー状に接続されるデータ構造である。なお、インデクスノードの総称を符号２０１で示し、リーフノードの総称を符号２０２で示す。インデクスノード２０１およびリーフノード２０２を合わせて、ノードと呼ぶ。リーフノード２０２は、インデクスキーと、テーブルデータ１２９のレコードへのポインタ（図中丸印）の組を格納する。この組をエントリと呼ぶ。
【００３１】
インデクスツリーの頂点に位置するノードを、ルートノードと呼ぶ。ルートノードポインタ２０３は、ルートノードへのポインタを格納する。
【００３２】
インデクスノード２０１は、下位のインデクスノード２０１またはリーフノード２０２へのポインタ（図中丸印）を格納する。インデクスノード２０１に格納されるポインタの間にはインデクスキーが格納され、当該インデクスキーより左側のポインタの下位のリーフノード２０２には、当該インデクスキーより小さいインデクスキーのエントリが格納され、当該インデクスキーより右側のポインタの下位のリーフノード２０２には、当該インデクスキーより大きいインデクスキーのエントリが格納される。
【００３３】
インデクスツリーに対する代表的な操作として、エントリ挿入、エントリ削除、エントリ検索がある。いずれの操作においても、指定された探索キーに基づいてルートノードからインデクスツリーを探索し、当該探索キーに対応するリーフノード２０２やその内部のエントリを決定する、エントリ探索処理を行う。
【００３４】
複数のスレッド４０２がインデクスツリーの参照や更新を同時に行う場合、ノードの排他処理が必要となる。例えば、エントリの挿入処理や削除処理の際には、ノードに対して変更処理を行っている際に当該ノードを他のスレッドからアクセスを禁止して排他制御を行う必要がある。またエントリ探索処理においても、参照しているノードが他のスレッドから変更されないように、他のスレッドからアクセスを禁止して排他制御を行う必要がある。
【００３５】
Ｂ＋ツリーインデクスの特徴として、ルートノードからリーフノード２０２までに経由するノード数が、全てのリーフノードについて等しいという特徴を有する。以下、本実施例ではＢ＋ツリーインデクスを用いて処理の例を説明するが、本発明は必ずしもＢ＋ツリーインデクスに限るものではなく、要素に順序関係（大小関係）を持つ任意のツリー構造に対して適用可能である。
【００３６】
図３Ａおよび図３Ｂは、それぞれインデクスノード２０１およびリーフノード２０２の内部構造の例を表す図である。なお、図３Ａはインデクスノードの内部構造の一例を表すブロック図である。また、図３Ｂは、リーフノードの内部構造の一例を表すブロック図である。
【００３７】
インデクスノード２０１は、下位ノードへのポインタ３０２をＮ個、インデクスキー３０１をＮ−１個持つ。探索キーに基づくエントリ探索では、探索キーがインデクスキーＸ（ただしＸは１〜Ｎ−１）より小さい場合はポインタＸを、大きい場合はポインタＸ＋１を辿る。
【００３８】
また、当該インデクスノード２０１が複数のスレッドから同時にアクセスされる場合に排他制御を行うために、排他制御管理情報３０３を持つ。なお、排他制御管理情報３０３は、図８に示した排他可否決定テーブル８００に従って管理され、当該ノードの排他状態が格納される。
【００３９】
さらに、当該インデクスノード２０１が参照される頻度を記録するために、ノード参照回数３０４およびノード参照回数３０４の記録を開始した時刻を格納するカウント開始時刻３０５を持つ。
【００４０】
図３Ｂのリーフノード２０２は、インデクスキー３０１とテーブルデータ１２９のレコードへのポインタ３０２の組をＮ個持つ。またインデクスノード２０１と同様に、排他制御管理情報３０３、ノード参照回数３０４、カウント開始時刻３０５を持つ。さらに、左側のリーフノードへのポインタ３０６および右側のリーフノードへのポインタ３０７を持つ。
【００４１】
ここで、右リーフポインタ３０７は、インデクスのキーの値が増大するリーフノードへのポインタが格納される。左リーフポインタ３０６は、インデクスのキーの値が減少するリーフノードへのポインタが格納される。
【００４２】
図４は、インデクスノード２０１およびリーフノード２０２がメモリ１１５上で物理的に配置される例を表す図である。図４に示すように、複数のプロセッサ１１１およびメモリ１１５を備えるＤＢサーバ１１０の場合、インデクスノード２０１およびリーフノード２０２は、複数のメモリ１１５に分散して配置される。
【００４３】
リーフノード２０２は、隣接するリーフノードを可能な限りまとめて同一のメモリ１１５に配置する。インデクスノード２０１は、下位のノードが全て同一のメモリ１１５に配置されている場合は、下位ノードと同一のメモリ１１５に配置し、下位のノードが複数のメモリ１１５に跨がっている場合には、任意のメモリ１１５に配置してよい。
【００４４】
上記のようにインデクスノード２０１およびリーフノード２０２を複数のメモリ１１５に跨がって配置した場合でも、メモリコントローラ１１４が透過的にアクセス処理を行うため、任意のＣＰＵコア１１２から任意のインデクスノード２０１およびリーフノード２０２へアクセスすることが可能である。
【００４５】
図５は、本実施例におけるＳＱＬ処理部１２１およびインデクス管理部１２２の処理の概要を表す図である。ＳＱＬ処理部１２１は、アプリケーションプログラム１５１からのデータベース処理要求を受け付けると、当該処理要求の実行に必要なインデクス処理リクエスト４０１をインデクス管理部１２２に対して発行する。
【００４６】
インデクス処理リクエスト４０１は、エントリ挿入や削除といったインデクス操作種別、および、探索キーを含む。インデクス管理部１２２は複数のスレッド４０２により実行され、スレッド４０２の各々について、インデクス操作リクエストを受け付けるためのリクエストキュー４０３を持つ。
【００４７】
ＳＱＬ処理部１２１がインデクス管理部１２２にインデクス処理リクエスト４０１を発行する際には、後述するスレッド割当てテーブル１２４を参照して、インデクス処理リクエスト４０１が持つ探索キーに対応するスレッド４０２を決定し、当該スレッドに対応するリクエストキュー４０３に対してインデクス処理リクエスト４０１を発行する。
【００４８】
図示の例では、ＤＢサーバ１１０が２つのＣＰＵコア１１２を有するプロセッサ１１１を２つ備えた２ソケットの構成で、合計４つのＣＰＵコア１１２で並列的に処理を実行することができる。このため、ＳＱＬ処理部１２１が４つのリクエストキュー４０３を有して、４つのスレッドＴ１〜Ｔ４を発行する例を示す。
【００４９】
図６は、スレッド４０２がインデクスツリーを探索する際に、探索キーに対していずれのスレッド４０２がインデクス探索処理を実行すべきかを表す、スレッド割当てテーブル１２４の例である。
【００５０】
スレッド割当てテーブル１２４は、スレッドの識別子を格納するスレッド６０１と、当該スレッドの探索範囲６０２、および、そのスレッドを優先的に使用すべきか否かを表す優先使用フラグ６０５をひとつのエントリに持つ。
【００５１】
探索範囲６０２は、当該スレッドに割り当てられた探索範囲の左端キー６０３および右端キー６０４によって表される。あるスレッドの探索範囲は、他のスレッドの探索範囲と重複する場合もあれば、重複しない場合もある。ただし、任意の探索キーを探索範囲に含むスレッドが１つ以上存在するものとする。
【００５２】
スレッド割当てテーブル１２４において設定される各スレッドの探索範囲の左端キー６０３および右端キー６０４の初期値は、各スレッドのリーフページ数やエントリ数が均等になるように設定してもよい。あるいは、図４に示すメモリ１１５上のノード配置を考慮して、各スレッドを実行するＣＰＵコア１１２がローカルにアクセス可能なメモリ上に配置されているリーフノードの範囲としてもよい。
【００５３】
ある探索キーに対して、当該探索キーが複数のスレッドの探索範囲に含まれる場合、ＳＱＬ処理部１２１は、優先使用フラグ６０５が“Ｏｎ”であるスレッドを優先的に選択して、当該スレッドに対応するリクエストキュー４０３に対してインデクス処理リクエスト４０１を発行する。
【００５４】
図示の例では、Ａ〜Ｚ等の探索キーをスレッドＴ１〜スレッドＴ４に割り当てた例を示す。図中スレッドＴ１の左端キー６０３の「＊」は、右端キー６０４のインデクスのキーが「Ｆ」以下の最小値を示す。一方、スレッドＴ４の右端キー６０４の「＊」は、左端キー６０３のインデクスのキーが「Ｒ」より大きい最大値を指す。そして、スレッドＴ２の左端キー６０３〜右端キー６０４では、インデクスのキーが「Ｆ」より大きく、「Ｌ」以下の値が割り当てられる。スレッドＴ３では、左端キー６０３〜右端キー６０４では、インデクスのキーが「Ｌ」より大きく、「Ｒ」以下の値が割り当てられる。
【００５５】
図１７は、各スレッドＴ１〜スレッドＴ４の負荷を管理するスレッド負荷記録テーブル１３０の一例を示す図である。スレッド負荷記録テーブル１３０は、スレッドＴ１〜Ｔ４の識別子を格納するスレッド１７０１と、当該スレッドがインデクスを操作した回数を格納するインデクス操作回数１７０２と、当該スレッドのインデクス操作回数１７０２の計数を開始した日時をカウント開始時刻として格納するカウント開始時刻１７０３とをひとつのエントリに含む。
【００５６】
インデクス管理部１２２は、インデクス１２８の探索処理を行ったときには、処理の終了時にインデクスの操作回数を更新し、後述するようにスレッド毎の負荷、換言すれば、ＣＰＵコア１１２ごとの負荷を記録する。
【００５７】
ここで、スレッドの負荷は、スレッドのスループットと近似する。このため、本実施例では、
負荷≒スループット＝インデクス操作回数／（現在時刻−カウント開始時刻）  …（１）
としてスレッドＴｓ毎の負荷を算出することができる。
【００５８】
図７は、インデクス管理部１２２がインデクス処理リクエスト４０１に基づいてエントリ探索処理の一例を示すフローチャートである。以下の説明において、エントリ探索処理をスレッドＴｓが行うものとする。このインデクス管理部１２２の処理は、探索キーに応じて選択されたスレッド４０２を処理するＣＰＵコア１１２で実行される。
【００５９】
この処理を開始する以前に、ＳＱＬ処理部１２１がＡＰサーバ１５０から探索キー（または検索キー）を含むデータベース処理要求を受け付ける。ＳＱＬ処理部１２１は、スレッド割当てテーブル１２４を参照して、受け付けた探索キーが探索範囲６０２に含まれるスレッド４０２を選択する。ＳＱＬ処理部１２１は、選択したスレッド４０２のキュー４０３へインデクス処理リクエスト４０１を投入する。
【００６０】
そして、選択されたスレッド４０２が、キュー４０３からインデクス処理リクエスト４０１を取得すると、図７の処理が開始される。
【００６１】
初めに、インデクス管理部１２２は排他要否フラグ（変数）を“Ｙ”で初期化し（Ｓ７０１）、図２示したルートノードポインタ２０３からインデクスノード２０１のアドレスを取得する（Ｓ７０２）。
【００６２】
次に、インデクス管理部１２２は排他要否フラグが“Ｙ”であるか否かを判定し（Ｓ７０３）、“Ｙ”ならば、現在探索しているインデクスノード２０１またはリーフノード２０２（以下、単にノードとする）が複数スレッドからアクセスされ得るか否かを判定する（Ｓ７０４）。一方、ステップＳ７０３の判定の結果、排他要否フラグが“Ｎ”であれば後述のステップＳ７０７に進む。
【００６３】
ステップＳ７０４の判定処理は、当該スレッドＴｓに割り当てられたノードの最小キーをＫ＿Ｎ＿ｍｉｎとし、当該ノードの最大キーをＫ＿Ｎ＿ｍａｘ、スレッドＴｎの探索範囲の最小値をＫ＿Ｔｎ＿ｍｉｎ、スレッドＴｎの探索範囲の最大値をＫ＿Ｔｎ＿ｍａｘとしたとき、Ｋ＿Ｎ＿ｍｉｎまたはＫ＿Ｎ＿ｍａｘをＫ＿Ｔｎ＿ｍｉｎ〜Ｋ＿Ｔｎ＿ｍａｘの範囲に含むスレッドＴｎが自スレッドＴｓ以外に存在するか否か、によって判定する。
【００６４】
ステップＳ７０４の判定がＹｅｓの場合、インデクス管理部１２２は当該ノードに対して後述の排他取得処理を行う（Ｓ７０５）。一方、ステップＳ７０４の判定結果がＮｏであった場合、インデクス管理部１２２は排他要否フラグに“Ｎ”を設定する（Ｓ７０６）。これにより、判定の結果がＮＯである場合には当該ノードに対して排他制御を禁止する。
【００６５】
次に、インデクス管理部１２２は探索対象のノード内の参照回数３０４をインクリメントする（Ｓ７０７）。
【００６６】
次に、インデクス管理部１２２は現在の探索対象のノードがリーフノードであるか否かを判定し（Ｓ７０８）、インデクスノード２０１である場合は、インデクスノード２０１内のインデクスキー３０１を探索キーによりスキャンし、下位ノードのアドレスをポインタ３０２から取得して（Ｓ７０９）、Ｓ７０３に戻る。
【００６７】
当該ノードがリーフノードである場合、インデクス管理部１２２はリーフノード２０２内のインデクスキー３０１をスキャンし、探索キーに対応するエントリ（ポインタ３０２）を取得し（Ｓ７１０）、インデクス処理リクエスト４０１に基づく処理を行う。
【００６８】
その後、インデクス管理部１２２は、当該スレッドがＳ７０５において取得した排他を全て解除する（Ｓ７１１）。そして、インデクス管理部１２２は、当該スレッドＴｓの負荷を管理するため、スレッド負荷記録テーブル１３０の、スレッドＴｓに対応するインデクス操作回数１７０２をインクリメントする。なお、インデクス操作回数１７０２が初期値“０”の場合は、現在の日時をカウント開始時刻１７０３に設定する。
【００６９】
上記ステップＳ７０４によってインデクス管理部１２２が、スレッドＴ１〜スレッドＴ４に割り当てられたノードの排他要否を判定することにより、複数のスレッドからアクセスされ得るノードに対してのみ排他制御を行い、単一スレッドからのみアクセスされるノードに対しては排他制御を不要とすることができる。
【００７０】
また、ステップＳ７０３において排他要否フラグが“Ｙ”であるか否かを判定することにより、一旦ノードが排他不要と判定されると、当該ノードより下位のノードにおいてはステップＳ７０４による当該ノードの排他要否判定処理が不要となる。
【００７１】
以上のように、同時にアクセスされる可能性がないノードに対しては排他制御を行わない（禁止する）ことにより、排他制御の実行回数を低減することが可能となる。また、排他制御が必要なノードにおいても、スレッドの探索範囲の割当てにより当該ノードにアクセスするスレッドが減少するため、排他制御の競合が発生する頻度を低減することが可能となる。さらに、ステップ７０３でノードが排他不要と判定されると、当該ノードより下位のノードについてはステップＳ７０４による排他要否判定処理を禁止し、かつ、排他制御を禁止することで処理の高速化を図ることができる。
【００７２】
図８は、上記図７のステップＳ７０５における排他取得処理で用いる排他可否決定テーブル８００の一例を表す図である。
【００７３】
排他可否決定テーブル８００は、他のスレッド（先行スレッドと呼ぶ）が既に取得している排他種別に対し（８０１）、自スレッド（後続スレッドと呼ぶ）が排他を取得しようとした場合（８０５）の処理について記述している。
【００７４】
排他の種類としては「参照排他」と「更新排他」があり、ノード内のキーやポインタを参照するのみである場合は「参照排他」であり、ノード内のキーやポインタを変更する場合は「更新排他」が必要となる。ノードの排他の状態および排他の種類は、排他制御管理情報３０３に格納される。
【００７５】
後続スレッドが参照排他（８０６）を取得しようとした際に、排他を取得している先行スレッドが存在しない場合（８０２）、または、先行スレッドが当該ノードに対し参照排他（８０３）を取得していた場合は、即時に参照排他の取得が可能である。しかし、先行スレッドが当該ノードに対し更新排他（８０４）を取得していた場合は、先行スレッドが排他を解放するまで後続スレッドは待ち状態となる。
【００７６】
後続スレッドが更新排他（８０７）を取得しようとした際に、排他を取得している先行スレッドが存在しない場合（８０２）、即時に更新排他の取得が可能である。しかし、先行スレッドが当該ノードに対し参照排他（８０３）または更新排他（８０４）を既に取得していた場合は、先行スレッドが排他を解放するまで後続スレッドは待ち状態となる。
【００７７】
上記の処理により、ノード内のインデクスキー３０１やポインタ３０２の変更を行わない操作については、参照排他により複数のスレッドが同時に実行することが可能となる。
【００７８】
上記の例では、参照排他および更新排他の２種類の排他種別を使用した排他処理を示したが、複数粒度ロック等のより高度なロック処理技法を使用してもよい。
【００７９】
図９は、本発明における排他処理回数削減の効果の例を示す図である。図９に示すインデクスツリーにおいて、図６に示したスレッド割当てテーブルに基づいてスレッドＴ１〜Ｔ４がそれぞれアクセスする可能性があるノードの範囲を破線で示している。
【００８０】
例えば、インデクスノード２０１ｄは、スレッドＴ１〜Ｔ３がアクセスする可能性は無く、スレッドＴ４のみがアクセスすることが分かる。これによりインデクスノード２０１ｄにアクセスする際の排他制御処理が不要となる。
【００８１】
また、他のインデクスノード２０１ｂや２０１ｃについても、アクセスする可能性があるスレッドが少なくなることにより、排他制御において競合（図８における排他解放待ち）が発生する可能性が減少する。
【００８２】
また、各スレッドが任意のノードにアクセスすることなく、アクセスするノードの範囲がスレッド毎に限定されることにより、プロセッサ１１１の共有キャッシュメモリ１１３におけるキャッシュヒット率の向上が期待できる。
【００８３】
次に、図１０から図１７を用いて、スレッド間で負荷の偏りが発生した場合に負荷を平均化する処理の一例について説明する。
【００８４】
インデクス処理において特定のインデクスキー（またはノード）に処理要求が偏った場合、スレッド間で負荷の偏りが生じ、ＤＢＭＳ１２０全体としてのスループットが低下する。そのため、スレッドＴ１〜スレッドＴ４間で負荷を移動させ、スレッドの負荷を平均化する必要がある。
【００８５】
図１０は、負荷平均化管理部１２５における負荷平均化処理の全体の流れを表すフローチャートである。初めに負荷平均化管理部１２５がスレッドＴｓの負荷（スループット）の偏りを検出する処理を行い（Ｓ１００１）、負荷の偏りが発生しているか否かを判定する（Ｓ１００２）。スレッドＴｓ間で負荷の偏りが発生している場合は、負荷平均化管理部１２５が、負荷移動先スレッドの決定処理（Ｓ１００３）と、負荷移動量の決定処理（Ｓ１００４）を順に行い、その結果に基づいて負荷の移動を実行する（Ｓ１００５）。最後に、負荷平均化管理部１２５は、スレッド負荷記録テーブル１３０において、移動元スレッドおよび移動先スレッドの、インデクス操作回数に０を設定し、カウント開始時刻に現在時刻を設定してリセットする（Ｓ１００６）。ステップＳ１００１およびＳ１００３からＳ１００５の詳細については図１２以降で後述する。
【００８６】
負荷平均化処理の実行は任意のタイミングで行うことが可能であり、例えば、一定時間毎や、インデクス操作リクエストを一定件数処理する度に実行してもよい。また、スレッド４０２が実行してもよいし、負荷の平均化処理を行う専用のスレッドが実行してもよい。以下、スレッドＴ１〜Ｔ４のうち１つが負荷平均化処理を実行するものとして説明する。
【００８７】
図１１は、負荷平均化処理におけるパラメタを設定する負荷平均化パラメタテーブル１２６の例である。
【００８８】
負荷平均化パラメタテーブル１２６は、負荷偏りの発生を検出するための閾値ＴHである偏り検出閾値１１０１、および、負荷の移動先を選択する際に使用される閾値ＴLである低負荷判定閾値１１０２をひとつのエントリに含む。これらの閾値や後述の負荷はスループット値であり、例えば、単位時間当たりのインデクス操作リクエスト件数である。ここでは、偏り検出閾値１１０１の設定値をＴH、低負荷判定閾値１１０２の設定値をＴLとする。なお、負荷平均化パラメタテーブル１２６は負荷平均化管理部１２５が参照する。
【００８９】
図１２は、図１０の負荷偏り検出処理のＳ１００１で行われる処理の詳細を表すフローチャートである。
【００９０】
はじめに、負荷平均化管理部１２５は、スレッド負荷記録テーブル１３０を参照して、自スレッドのインデクス操作回数１７０２と、カウント開始時刻１７０３とを取得し、上記（１）式より負荷を算出する。
【００９１】
負荷平均化管理部１２５は、自スレッドの負荷が偏り検出閾値ＴHより大きいか否かを判定する（Ｓ１２０１）。自スレッドの負荷が偏り検出閾値ＴHより大きい場合は、自スレッドより左側のインデクスキーを探索範囲に持つスレッド（以降、左スレッドと呼ぶ）の負荷、又は、自スレッドより右側のインデクスキーを探索範囲に持つスレッド（以降、右スレッドと呼ぶ）の負荷のいずれかが、偏り検出閾値ＴHより小さいか否かを判定する（Ｓ１２０２）。なお、図９において、自スレッドがスレッドＴ２の場合、左スレッドはインデクスキーがＡ〜ＦのスレッドＴ１でスレッドの識別子が自スレッドよりも小さい。また、右スレッドはインデクスキーがＭ〜ＲのスレッドＴ３でスレッドの識別子が自スレッドよりも大きい。
【００９２】
ここで、負荷平均化管理部１２５は、スレッド負荷記録テーブル１３０を参照して、左スレッドと右スレッドのインデクス操作回数１７０２と、カウント開始時刻１７０３とをそれぞれ取得して、上記（１）式より負荷をそれぞれ算出する。
【００９３】
次に、負荷平均化管理部１２５は、左スレッドの負荷と右スレッドの負荷の少なくとも一方が偏り検出閾値ＴHより小さい場合は、負荷の偏りありとして負荷偏り検出処理を終了する（Ｓ１２０３）。一方、ステップＳ１２０１又はＳ１２０２の判定結果がＮｏである場合は、負荷の偏りなしとして負荷偏り検出処理を終了する（Ｓ１２０４）。
【００９４】
上記の処理によって、自スレッドの負荷が閾値ＴHより大きく、かつ、左右のスレッドのいずれかの負荷が閾値ＴH未満の場合に、負荷の偏りを検出することができる。
【００９５】
図１３は、図１０の負荷移動先スレッド決定処理Ｓ１００３において使用される、スレッドおよび当該スレッドがいずれのプロセッサ１１１やＣＰＵコア１１２において実行されているかを管理するスレッド−コア対応テーブル１２７の例である。
【００９６】
スレッド−コア対応テーブル１２７は、スレッドのＩＤ（１３０１）に対して、当該スレッドが実行されているプロセッサＩＤ（１３０２）とＣＰＵコアＩＤ（１３０３）がひとつのエントリに含まれている。
【００９７】
負荷平均化管理部１２５は、このスレッド−コア対応テーブル１２７テーブルを参照することにより、処理対象のスレッドと、別のスレッドが、同一のプロセッサ上で実行されているか否かを判定することができる。
【００９８】
図１４Ａおよび図１４Ｂは、図１０の負荷移動先スレッド決定処理Ｓ１００３において、負荷の移動先スレッドを決定するために参照する移動方向決定テーブル１４００、１４１０の例である。
【００９９】
負荷移動先スレッド決定処理Ｓ１００３においては、図１４Ａに示す通り、負荷平均化管理部１２５は、左スレッドの負荷（１４０１）および右スレッドの負荷（１４０２）と、偏り検出閾値ＴHおよび低負荷判定閾値ＴLの値をそれぞれ比較し、移動方向決定テーブル１４００で該当する方向（左右のスレッド）への移動を決定する。
【０１００】
左スレッドの負荷１４０１および右スレッドの負荷１４０２が、いずれも低負荷判定閾値ＴLより小さい場合、または、いずれの負荷も低負荷判定閾値ＴLから偏り検出閾値ＴHの範囲に含まれる場合、負荷平均化管理部１２５は、図１４Ｂの移動方向決定テーブル１４１０によって移動方向を決定する。
【０１０１】
図１４Ｂの移動方向決定テーブル１４１０においては、左スレッドおよび右スレッドを実行しているプロセッサ１１１の識別子が、移動元スレッドを実行しているプロセッサ１１１の識別子とそれぞれ同一であるか否かを判定し、移動先スレッドを決定する。
【０１０２】
図１４Ａによって移動先スレッドが決定された場合は、左右のスレッドの負荷の差が大きかったため、負荷の小さい方のスレッドを移動先スレッドとして選択する結果となる。
【０１０３】
一方、図１４Ｂによって移動先スレッド決定された場合は、左右のスレッドの負荷の差が小さかったため、メモリ１１５上の物理的な配置を考慮して、負荷の移動を可能な限り同一プロセッサ１１１内で実施することを優先した結果となる。
【０１０４】
以上により、負荷平均化管理部１２５は、左右のスレッドの負荷に基づいて、自スレッドから負荷（インデクスキー）を移動させるスレッドを決定することができる。なお、図９で示したように、インデクスキー３０１の最小値を含むスレッドＴ１は移動先の左スレッドは存在せず、同様にインデクスキー３０１の最大値を含むスレッドＴ４は移動先の右スレッドは存在しない。
【０１０５】
図１５は、図１０の負荷移動量算出処理Ｓ１００４の処理の一例を表すフローチャートである。負荷移動量算出処理Ｓ１００４では、負荷移動先スレッド決定処理Ｓ１００３において決定した移動先のスレッドへ、新たに割り当てるインデクスキー３０１の探索範囲を算出する。ここでは、負荷移動先のスレッドが右スレッドであるとして説明する。なお、図１５において括弧内の（最小）、（右側）、（最大）は、負荷移動先のスレッドが左スレッドの場合を示す。また、現在のスレッドから移動先のスレッドへ新たに割り当てるインデクスキー３０１の探索範囲を、移動すべき負荷量ＬMとする。
【０１０６】
はじめに、負荷平均化管理部１２５は、移動すべき負荷量ＬMを算出する（Ｓ１５０１）。ここでは移動元スレッドの負荷をＬS、移動先スレッドの負荷をＬTとした場合に、移動負荷量ＬMは、
ＬM  ＝（ＬS＋ＬT）／２−ＬS    …（２）
として算出する。
【０１０７】
次に、負荷平均化管理部１２５は、スレッド割当てテーブル１２４から移動元スレッドの右端キー６０４を取得し（Ｓ１５０２）、当該キーによってエントリ探索処理を実行してリーフノード２０２を特定し、当該リーフノードをカレントノードとする（Ｓ１５０３）。
【０１０８】
負荷平均化管理部１２５は、カレントノードの負荷ＬNと移動負荷量ＬMを比較し（Ｓ１５０４）、カレントノードの負荷ＬNが小さい場合は、カレントノードの上位ノードをカレントノードとしてＳ１５０４に戻る（Ｓ１５０５）。
【０１０９】
一方、カレントノードの負荷ＬNが移動負荷量ＬMより大きい場合は、カレントノードの上位ノードを取得し、カレントノードへのポインタの左側キーを取得する（Ｓ１５０６）。そして、Ｓ１５０６で取得したキーを移動先スレッドの新たな左端キー６０３とする（Ｓ１５０７）。
【０１１０】
上記の処理により、負荷平均化管理部１２５は、自ノードの右スレッド（または左スレッド）へ移動させる負荷量として、あるインデクスノード以下のエントリを一括して移動させることが可能となり、迅速な負荷平均化が可能となる。さらに、負荷平均化管理部１２５は、インデクスノード単位でスレッドへの割当てを変更することにより、インデクスノードが複数のスレッドからアクセスされる可能性を低減することが可能となる。
【０１１１】
なお、上記では自ノードの右スレッドへ移動負荷量ＬMを移動させる例を示したが、図中括弧内の記載に基づいて処理を行うことで、自ノードの左スレッドへ移動負荷量ＬMを移動させることができる。
【０１１２】
図１６は、図１０の負荷移動処理Ｓ１００５で行われる処理の一例を表すフローチャートである。同図中、破線左側が移動元スレッドにおける処理を示し、破線右側が移動先スレッドにおける処理となる。
【０１１３】
はじめに移動元スレッドが、スレッド割当てテーブル１２４の変更要求を移動先スレッドのリクエストキュー４０３へ登録する（Ｓ１６０１）。
【０１１４】
移動先スレッドは、リクエストキュー４０３からスレッド割当てテーブル１２４の変更要求を取り出すと、スレッド割当てテーブル１２４の移動先スレッドの左端キー６０３を負荷移動量算出処理Ｓ１００４によって決定された左端キーに変更する。また、移動先スレッドは、自身が該当するスレッド６０１の優先使用フラグ６０５を“Ｏｎ”に変更する（Ｓ１６０３）。その後、移動先スレッドは、スレッド割当てテーブル１２４の変更完了通知を移動元スレッドのリクエストキュー４０３へ登録する（Ｓ１６０３）。
【０１１５】
移動元スレッドは、リクエストキュー４０３からスレッド割当てテーブル１２４の変更完了通知を取り出すと、スレッド割当てテーブル１２４の移動元スレッドの右端キー６０４を、負荷移動量算出処理Ｓ１００４によって決定された左端キーに変更する。さらに、移動元スレッドは、移動先スレッドの優先使用フラグ６０５を“Ｏｆｆ”に変更する（Ｓ１６０４）。
【０１１６】
以上の負荷移動の手順により、移動元スレッドにおいては、ステップＳ１６０１からＳ１６０４の間においても、リクエストキュー４０３内のインデクス操作要求の処理が可能であり、処理を停止することなく各スレッドの探索範囲を切り替えることが可能となる。
【０１１７】
以上の負荷平均化処理により、スレッド間で負荷の偏りが生じた場合でも、小さい処理コストで負荷の平均化を行うことが可能となる。さらに、スレッドの探索範囲割当てを変更することによってスレッド間で負荷の移動を行っているため、インデクスツリー構造を変更することなく負荷の平均化を行うことが可能である。これにより、負荷移動処理を高速かつ低負荷で実行することができる。
【０１１８】
上記実施例では、インデクス１２８及びテーブルデータ１２９をメモリ１１５に格納するインメモリ型のデータベースの例を示したが、ディスク型のデータベースに適用することができる。この場合、各メモリ１１５のインデクス１２８に代わって、各スレッド毎のＤＢキャッシュを図示しないディスクに設け、これらのＤＢキャッシュにインデクスを上述したように割り当てることができる。
【０１１９】
また、上記実施例では、プロセッサ１１１の１つのＣＰＵコア１１２が１つのスレッドを処理する例を示したが、これに限定されるものではなく、１つの物理ＣＰＵコアが複数の論理ＣＰＵコアを提供し、１つの論理ＣＰＵコアが１つのスレッドを処理するようにしてもよい。
【０１２０】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることが可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の非一時的な記録媒体に置くことができる。
【０１２１】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【０１２２】
また、本発明において説明した計算機等の構成、処理部及び処理手段等は、それらの一部又は全部を、専用のハードウェアによって実現してもよい。
【０１２３】
また、本実施例で例示した種々のソフトウェアは、電磁的、電子的及び光学式等の種々の記録媒体（例えば、非一時的な記憶媒体）に格納可能であり、インターネット等の通信網を通じて、コンピュータにダウンロード可能である。
【０１２４】
＜補足＞
１６．請求項１４に記載の計算機であって、
前記インデクス管理部は、
前記インデクスツリーを構成するノードを参照または更新する際に、当該ノードの使用回数を負荷量として記録し、
前記移動元のスレッドと移動先のスレッドの負荷量が等しくなるように移動させる負荷量を決定し、前記ノードの負荷量が所定の閾値を超えたか否かを判定し、前記ノードの負荷量が所定の閾値を超えたか否かを判定する処理を最下位のノードから上位ノードへ向けて実行し、前記判定結果が真になるまで行って、前記判定の結果が真となったノードを移動先のスレッドの新たな探索範囲とすることを特徴とする計算機。
【０１２５】
１７．請求項１４に記載の計算機であって、
前記インデクス管理部は、
前記負荷の移動元のスレッドが移動先のスレッドへ探索範囲の変更を要求し、前記移動先のスレッドが移動先のスレッドの探索範囲の変更を行って、前記移動先のスレッドが移動元のスレッドへ探索範囲の変更完了を通知し、前記移動元のスレッドが移動元のスレッドの探索範囲の変更を行うことを特徴とする計算機。
【０１２６】
１８．請求項１１に記載の計算機であって、
前記インデクス管理部は、
前記インデクスツリーを複数の探索範囲に分割し、前記分割した探索範囲の最小値と最大値とを前記スレッドに割り当てることを特徴とする計算機。
【符号の説明】
【０１２７】
１１０  ＤＢサーバ
１１１  プロセッサ
１１２  ＣＰＵコア
１１５  メモリ
１２０  データベース管理プログラム
１２１  ＳＱＬ処理部
１２２  インデクス管理部
１２３  排他管理部
１２４  スレッド割当てテーブル
１２５  負荷平均化管理部
１２６  負荷平均化パラメタテーブル
１２７  スレッド−コア対応テーブル
１２８  インデクス
１２９  テーブルデータ
１３０  スレッド負荷記録テーブル
２０１  インデクスノード
２０２  リーフノード
４０２  スレッド
４０３  リクエストキュー
【図１】
2015170239.tif 000003
【図２】
2015170239.tif 000004
【図３Ａ】
2015170239.tif 000005
【図３Ｂ】
2015170239.tif 000006
【図４】
2015170239.tif 000007
【図５】
2015170239.tif 000008
【図６】
2015170239.tif 000009
【図７】
2015170239.tif 000010
【図８】
2015170239.tif 000011
【図９】
2015170239.tif 000012
【図１０】
2015170239.tif 000013
【図１１】
2015170239.tif 000014
【図１２】
2015170239.tif 000015
【図１３】
2015170239.tif 000016
【図１４Ａ】
2015170239.tif 000017
【図１４Ｂ】
2015170239.tif 000018
【図１５】
2015170239.tif 000019
【図１６】
2015170239.tif 000020
【図１７】
2015170239.tif 000021