インメモリXMLデータベースの開発

全文

(1)2003−DD−40 (2) 2003／7／25. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report. インメモリ XML データベースの開発川口浩司. 沼崎慎吾. 株式会社セック. 柳下精一郎土井憲雄マーケティング本部. 本稿では、XML をメモリ上に効率的に格納し、高速に検索や集計を行うインメモリ XML データベース「Karearea」の機構について紹介する。XML データの RDB への格納方式には万能のものはなく、ネイティブ XML データベースではパフォーマンスやメモリ消費の面で不十分という評価がされることが多い。筆者らはメモリベースの高速処理エンジンを核に、高速な検索や多次元集計の可能な XML データベースを開発した。また、メモリ上に XML データを格納した際のメモリ使用量や、検索や集計を行った場合の処理時間を計測し、その効果を確認した。. A Development of In-Memory XML Database Koji Kawaguchi. Shingo Numazaki. Seiichiro Yagishita. Norio Doi Systems Engineering Consultants Co.,LTD In this paper, we introduce the mechanism of an in-memory XML database “Karearea.” We developed the in-memory XML database, which stores XML efficiently in memory and performs searching and multi-dimensional summarizing at high speed, applying a high-speed processing engine of memory base in the core. We confirmed the effects of Karearea by measuring memory usage and processing time for searching or summarizing.. 方式として例えば次のものが知られている. 1 はじめに. が、いずれも一長一短で、あらゆる用途に万. XML データは階層構造を持ち、繰り返し. 能ではない。. や構造が一定でないといった「半構造」を表現できる特徴がある。このため、XML デー. •. タを RDB に格納する場合、二次元の表で表. XML データ全体を単なる 1 つの文字列として格納する。. すためには何らかの工夫が必要になる。この－1－ −9−.

(2) •. 要素の種類ごとにテーブルを作成し、1 要素ごとに 1 レコードとして格納する。属性やテキスト値はテーブルのカラム. •. (1) 検索性能が悪い格納方式や検索アルゴリズムにもよるが、. として表現する。要素間の関係はレコー. データ量が増えると極端に性能が悪くなる. ド間のリンクによって表現する。. 場合がある。ツリーを順番にたどりながら検. XML データを DOM 形式で表現し、要. 索する方式の場合、検索条件の指定方法によ. 素や属性といったノードの種類ごとの. って大きな性能差が出る。そのため、たどる. テーブルに、1 ノードごとに 1 レコード. ノード数をなるべく少なくするように条件. として格納する。ノード間の関係はレコ. 指定を工夫する必要がある。また、親子関係. ード間のリンクによって表現する。. を処理するために Join を利用する方式では、 Join が性能上のネックになってしまう。. 最近では、商用の RDB 製品でも「ネイテ. 検索性能を改善するため、RDB と同じよ. ィブ XML 対応」が謳われている。これらの. うにインデックスを設定できる製品が大半. 製品では、例えば「XPath[1]と、それに対応. である。XPath により、XML 構造の特定の. するレコード位置をインデックス情報とし. ノードを指定してインデックスを作成する. て持っておくことにより、ノードへのアクセ. 製品が多いが、XML では構造が一定とは限. スを高速化する」というような工夫が追加さ. らないため、インデックスの設定が困難なケ. れているようである。. ースも少なくない。このため、製品によって. 一方、XML データを RDB のテーブルにマッピングするのではなく、XML データをそ. は自動的にすべてのノードについてインデックスが作成される。. のままの形で取り扱うことが可能な「ネイテ. 「XML データベースは遅くて使いものに. ィブ XML データベース（NXDB）」がいくつ. ならない」という評価結果を聞くことも少な. か製品化されている。しかし、RDB と比較. くないが、多量の XML から高速に検索がし. して歴史が浅く、まだ普及しているとは言い. たいというニーズは今後ますます大きくな. 難い。RDB に比べて機能や実績が不足して. ると思われる。. いたり、メモリ消費が多くパフォーマンスが (2) メモリを大量に要求する製品が多い. 不十分という評価がされることも多い。筆者らは、多量の XML からの高速な検索. 動作環境には「必要メモリ 256MB」と記. や集計を行うことが可能なインメモリ XML. 述されていても、メーカーから「快適な動作. データベース「Karearea[2]」を開発した。. には 2GB のメモリを搭載してください」と. 本稿では、従来の XML データベースを利用. 言われたという話も多い。データ本体はディ. した場合のいくつかの問題点について述べ. スクに格納されるものの、検索のためのイン. た後、「Karearea」によってこれらをどのよ. デックス等をメモリ上に置くために、大量の. うに解決したかを紹介する。. メモリが必要だと考えられる。また、最近では製品自体に Web サーバや Java に対応したアプリケーションサーバが組み込まれてい. 2 解決しようとする問題点従来の XML データベースでの問題点として、今回「Karearea」で解決しようとするのは以下のものである。. るものが多いのも一因と考えられる。 (3) Java 用 API の使い勝手がよくない大半の XML データベース製品では、サー. −10− －2－.

(3) バは C/C++言語で実装されており、クライア. 計用にデータを抽出するなど二度手間とな. ント側の API は Windows の COM、C/C++、. り、アプリケーションでの処理が複雑になる。. Java 等に対応している。サーバプロセスと. XML のまま、直接集計が出来るのが理想. クライアント間の通信でソケット、CORBA、. 的であると言える。. HTTP などが使用されているが、プログラム言語やプラットフォームに依存しないために XML 文字列形式でのレスポンスが採用されているものが多い。この場合、検索結果全体が単一の XML 文字列として返されるため、クライアント側でそれを再度 parse する必要が生じることになる。 Java 標準の RDB アクセスインタフェースである JDBC では、カーソルを移動したり様々なデータ型として取得するための多様なメソッドが用意されている。一方、ほとんどの XML データベースでは、結果の取得方法としては単純な iteration しか用意されておらず、貧弱と言える。 XML データをハンドリングするための Java 用 API として、DOM と JDOM[3]がある。DOM はプログラム言語に依存しない形で W3C で制定されたものであるが、Java の標準的な API とは異なるスタイルのために使いづらい点も多い。その点、JDOM は Java 専用に設計されたものなので、XML を快適に扱うことができる。 Java での利用に特化し、効率よく XML を扱えるデータベースがあってもよいのではないだろうか。. 3 Karearea での実現方法 3.1 LFM 技術 Karearea では、XML データの高速な検索、集計などを実現するにあたって、株式会社ターボデータラボラトリーが開発した LFM 技術[4]を基盤としている。LFM は、全てのデータをメインメモリ上で管理することが前提になっている。 LFM のデータベースは複数のテーブルから構成される。各テーブルはフィルタ（カラム）とレコード、さらにレコードの選択／非選択状態の集合を表す「セット」を合わせた 3 次元の形式で表される。 LFM では、検索の高速化のために特定のカラムにインデックスを作成するという概念はなく、どのフィルタに対しても高速な検索が可能である。その仕組みは、各フィルタが値情報と位置情報との 2 つのデータ構造によって管理されているためで、これを FAST （Filter Array STructure）と呼んでいる。値情報は重複のない集合として管理されており、常に昇順にソートされる。このため、フィルタにおける値検索は 2 分探索によって実現される。一方、位置情報はレコードごとに値情報のポインタを持つものである。デー. (4) 高速な集計が困難多量に蓄積された XML データを活用するための、データマイニング的な利用を考えたい。例えば、データベース中の XML データに対する集計を行うためには、一般的にはアプリケーションで XML データを一つずつ取得して処理することになり、膨大な時間がかかってしまう。集計のために RDB やデーターウェアハウスツールを適用することが考えられるが、集－3－ −11−. タ型に係わらず、常に整数のポインタとして表されるので、高速処理が可能なのである。 LFM では、巨大なテーブル同士の Join であっても非常に高速という特長もある。テーブルを Join すると、Join 結果のテーブルそのものがメモリ上に作成されるのではなく、 Join 元のテーブルを参照した、仮想的なテーブルが作成される。このため、Join テーブルが存在している間は元のテーブルの編集は.

(4) <A id="apple"> white </A> <A id="pear"> blue green </A> <A/>. A. B up-grip. 図 1. down-grip. attr-id. up-grip. down-grip. text. 1. 11 apple. 11. 12 white. 1. 13 pear. 13. 14 blue. 1. 16. 13. 15 green. XML データの例と、テーブルに格納されるデータ. 出来ないが、高速かつ少ないメモリでの Join. )>. が実現されている。. <!ATTLIST issue-category code CDA. LFM では、上記の FAST によって高速な. TA #REQUIRED>. 集計も実現されている。四次元までの多次元集計に対応しており、次元ごとのカテゴライ. 全てのテーブルには、各要素間の親子関係. ズ機能も備えている。集計の種類は、カウン. を表すための、up-grip、down-grip というカ. ト、最大値、最小値、合計、平均である。. ラムが作成される。down-grip はフォルダ内全テーブルのレコードでユニークな値を表し、要素の出現順に番号が振られる。up-grip. 3.2 データの格納方法 Karearea のデータベースは複数のフォル. は親要素へのリンクを表す。ある要素 A の. ダから構成される。フォルダ作成時にスキー. down-grip の値と別の要素 B の up-grip の値. マ情報を指定し、そのスキーマ情報に従った. が等しい場合、2 つの要素は親子関係にある。. XML をフォルダに格納できる。スキーマ情. 要素 B が複数存在する場合は子が複数存在. 報としては、DTD または XML Schema が指. することを表し、子の出現順は down-grip の. 定できる。. 若いものからとなる。なお、要素 A の. フォルダを作成すると、スキーマ情報に従. down-grip の値と等しい up-grip の値を持つ. って、LFM データベースに複数のテーブル. ような要素 B が存在しない場合は、要素 B. が作成される。テーブルは、スキーマ情報で. には子がないことを表す。（図 1）. 定義された要素の種類ごとに 1 つずつ作成さ. XML では、同じ要素の同じ属性やテキス. れる。そして、XML データの各要素ごとに、. トに、複数の XML データで同じ値を持つこ. 要素に対応するテーブルに 1 レコードずつ格. とも多い。LFM では、この場合は値情報と. 納される。. して 1 つの値しか保持しないため、圧縮効果. 要素に属性やテキストが指定されている. が期待できることになる。このため、. 場合は、該当する値を格納するためのカラム. down-grip や up-grip といった付加情報を差. がそのテーブルに作成される。例えば、スキ. し引いても、XML データの格納に必要なメ. ーマ情報に以下の DTD が指定された場合は、. モリは、元の XML 文字列形式でのバイト数. issue-category テーブルに text と attr-code. とだいたい同じとなった。 Karearea はインメモリデータベースのた. という 2 つのカラムが作成される。. め、すべてのデータがメモリ上に格納されることになる。しかし、圧縮効果やインデック. <!ELEMENT issue-category (#PCDATA －4－ −12−.

(5) し、Join 可能な issue-data テーブルのレ. <stock-price> <trading-date year="2003" month="07" day="24"/> <issue-data> <issue-category code='65'>通信</issue-category> <stock-index nikkei='0' topix='0'/> <issue-code>1001</issue-code> <issue-name>カレアレア</issue-name> <todays-start-price>1350</todays-start-price> <todays-high-price>1500</todays-high-price> <todays-low-price>1350</todays-low-price> <todays-end-price>1480</todays-end-price> <todays-output>45000</todays-output> </issue-data> </stock-price> 図 2. コードを選択する。 (3) (2)の結果を stock-price テーブルと Join して、同様に stock-price テーブルのレコードを選択する。 (4) (3)で得られたレコードで表されるのが、上記の XPath に該当する stock-price 要素である。このように、XML の階層構造をたどっていくのに Join を多用しているにもかかわらず、LFM 技術における高速な Join が可能という特性により、十分実用的な性能が実現し. 株価情報の XML. た。また、同じく LFM 技術のインデックススが不要という LFM 技術の特性を活かすこ. が不要という特性により、検索指定によらず. とによって、コンパクトなデータベースを実. に高速な検索を実現した。. 現できた。. 3.4 Java ベースのアプリケーションに特化. 3.3 検索方法現在のほとんど全ての XML データベース. Karearea では、Java ベースのアプリケー. では、XML データの検索（絞り込み）に. ションでの利用をターゲットとした。筆者ら. XPath 式を使用する。したがって、Karearea. の会社では Web アプリケーションシステム. でも検索条件の指定に XPath を採用した。. を開発することが多いが、Java で実装する. 例えば、図 2 のような株価情報を表す XML. ことが一般的である。また、XML の操作を. データが格納されている場合に、銘柄コード. 行うための豊富な API やライブラリも Java. が 1001 であるような XML データを検索す. 用に多く提供されており、Java をターゲッ. るには次の XPath を指定する。. トとするのが最適だと考えた。 Java では、RDB にアクセスするための. /root/stock-price[issue-data/issue-code = 10. JDBC という標準 API が用意されている。. 01]. XML データベースについても、XML:DB Initiative にて XML:DB API[5]が検討されて. Karearea では、この XPath が指定される. いる。この API は一部の製品で採用されてい. と、3.2 章で述べた形式で格納されている. るものの、まだ普及しているとは言い難い。. XML データに対して、次の手順によって検. このため、Karearea では JDBC を参考に. 索を行う。. 独自の API を採用した。例えば、フォルダから XPath による検索を行い、結果を DOM 形. (1) issue-code テーブルについて、text カラ. 式で取得するには、図 3 のように記述する。. ムが 1001 であるようなレコードを選択. Java に特化した形式とすることにより、ユ. する。. ーザに習得しやすく、利用しやすい API とす. (2) (1)の結果を issue-data テーブルと Join −13− －5－.

(6) Folder folder;. また、フォルダへの格納処理をまとめて行. ElementResultSet ers = folder.. うバッチモードを用意した。LFM 処理エン. createPathQuery("/root/stock-p. ジンでは、テーブルデータの追加・更新時に. rice[issue-data/issue-code = 10. 「コンパイル」という処理が行われる。この. 01]").execute();. 時、フィルタごとにデータを位置情報と値情. while (ers.next()) {. 報に分解したり、値情報のソートなどが行われる。XML ファイル 1 件ごとにコンパイル. Element element = ers.getEl ement();. が行われるとパフォーマンスが悪くなるが、. }. バッチモードでは登録する XML ファイル全図 3. 体で 1 回のコンパイルとなる。. API の利用例. データベースレジューム機能は、フォルダ全体をメモリイメージとしてファイルに保. ることが出来た。 Karearea では、エンジン自体も Java で実. 存する。Karearea はインメモリデータベー. 装を行った。ただし、LFM 処理エンジンは. スであり、データベースをシャットダウンす. ネイティブコードであるため、Karearea か. ると全データが消えてしまう。しかし、デー. らは JNI（Java Native Interface）により利. タベース再起動後にメモリイメージから高. 用する形態を取っている。Java で実装した. 速にフォルダを復元し、直前の処理を継続す. ことにより、あらかじめサーバを起動してク. ることが可能である。. ライアントから接続して通信を行うのでは. 3.6 集計機能. なく、データベースそのものを単なる Java のライブラリのように利用することも可能. XPath には sum や count といった集約関. である。ただし、この場合はプロセスを終了. 数が用意されており、一般の XML データベ. するとデータベースも解放される。. ースでも格納された XML に対して合計等を. 一方、Karearea Server を別途起動し、ク. 求めることが可能である。複雑な集計であれ. ライアントから接続して使用する「リモート. ば XSLT スタイルシートを用意することにな. 接続」も可能である。この場合は、通信に. るが、すべてのドキュメントを順番に処理し. RMI（Java Remote Method Invocation）プ. ていくことになり、膨大な時間がかかってし. ロトコルを利用する。通信のためのオーバー. まう。. ヘッドがあるものの、複数クライアントから. Karearea では、フォルダ内の XML データ. 同じデータベースを利用できるというメリ. に対する高速集計が可能で、簡単なデータウ. ットがある。. ェアハウス的用途に利用できる。LFM 技術では 4 次元までの高速な集計が可能であり、 Karearea ではこれを XML に適用した。集計. 3.5 入出力の高速化フォルダに大量の XML ファイルを登録す. では、どの要素のどの属性やテキストを集計. る場合、ZIP ファイルを指定してアーカイブ. 対象とするかを指定し、Karearea から集計. 中の全ファイルをまとめて登録することも. 結果が返される。. 可能にした。XML ファイルを 1 つずつ指定した場合と比べてディスク I/O が削減され、処理の高速化が期待できる。. 4 評価 Karearea の高速な処理とコンパクトなメ. −14− －6－.

(7) <merchandise id="1127" toppage="false"> <title>XML 入門</title> <price>2800</price> <category>XML</category> <discount>0.1</discount> <image>img/1127.jpg</image> <info name="発売日" value="2003/7/11" /> <info name="出版社" value="セック出版" /> </merchandise>. モリ消費について評価するために、以下の項目について測定を行った。 •. データの格納時のメモリ使用量. •. 検索時間. •. 集計時間また、メモリ上の XML データに対する処. 図 4. 理という観点から、Apache プロジェクトの XSLT プロセッサ「Xalan」での同様の処理. 商品データの XML. データが圧縮されるために若干の増加にと. と比較した。対象の XML データは DOM オ. とまっている。一方、DOM オブジェクトと. ブジェクトの形でメモリ上に展開し、XPath. 比較すると 1/193 となり、圧倒的に小さい。. の処理にかかる時間を使用した。測定に使用した PC 環境は以下の通りであ. 4.2 検索時間. る。. 4.1 と同じ商品データに対して、以下の CPU. Pentium III 933MHz × 1. XPath による検索を行った。この条件に該当. RAM. 512MHz. する商品は 1 件である。. OS. Windows XP Professional. /merchandise[info/@value = "ソフトガレージ"]. なお、他の XML データベース製品との比較は各製品のライセンス契約上困難である. Karearea で上記検索を行い、結果集合を. ために見送った。. 返すまでの時間は 12ms であった。これに該当する XML データの取得処理を含めると. 4.1 格納. 28ms である。一方、Xalan では同様の処理. 図 4 に示されるような商品データを表す. に 496ms かかったので、Karearea の方が約. XML データを 2,242 件用意し、Karearea の. 20 倍高速に処理できたことになる。. フォルダに格納してメモリ使用量を測定した。また、同じ XML データを parse して. 4.3 集計時間. DOM オブジェクトに展開した場合について. 4.1 と同じ商品データに対して、以下の条. も測定した。結果は以下の通り。. 件による集計（カウント）を行った。元 XML データ DOM Karearea 格納後. 970kB 次元 1（カテゴリー）. 217,088kB 1,099kB. XPath. /merchandise/category. カテゴライズ. なし. Karearea では、元の XML データに対して次元 2（値段）. 113%のメモリ消費となった。フォルダに格. XPath. 納する際に付加情報が追加されるが、冗長な. −15− －7－. /merchandise/price.

(8) カテゴライズ. v<1000、v>=1000. 今後の課題は以下の通りである。. Karearea の集計 API を使用すると、集計. (1) メモリデータベースであるために、すべ. 結果を得るのに 21ms かかった。なお、集計. てのデータをメモリに格納する必要があ. 結果は以下のような 2 次元の表となる。. るが、メモリに格納しきれないほどの大量のデータを扱いたいという要求も多い。. 1,000 円未満. 例えば、32 ビット Windows では 2GB と. 1000 円以上. J-POP. 0. 4. いう制約が存在する。Karearea の 64 ビ. SE. 0. 4. ット Solaris 版ではこうした制約は撤廃. SF. 24. 68. されるものの、ハードウェア費用が高額. ～. ～. となり、導入の敷居が高くなってしまう。. ～. 自伝. 22. 60. 野球. 0. 4. 風景. 0. 22. 現在、複数サーバによる分散を検討中である。 (2) メモリデータベースであるため、トランザクションの保証が困難である。そのた. (27 項目). め、現状 Karearea ではトランザクションをサポートしていない。OLTP 的なデ. 一方、比較のために Xalan の XPathAPI. ータについては RDBMS を利用し、両者. を使用して、カテゴリーを表す category 要素. を使い分けるような仕組みを検討中で. の値のすべてのバリエーションについて、順. ある。. に以下の XPath を実行してカウントを行う. (3) 現状はフォルダ作成時に指定したスキー. ような Java アプリケーションを作成した。. マに従った XML のみ格納可能である。しかし、運用中にスキーマを拡張してい. count(/root/merchandise[category = "カテゴ. くことも多い。スキーマを拡張できるよ. リー" and price < 1000]. うな仕組みを検討したい。. count(/root/merchandise[category = "カテゴ. リー" and price >= 1000]. 6 参考文献. 上記の集計には 18,692ms かかった。単純. [1] XML Path Language (XPath) Version. に Karearea での測定結果と比較すると 890. 1.0. 倍である。. [2] Karearea. http://www.w3.org/TR/xpath. http://www.sec.co.jp/products/karearea/ [3] JDOM. 5 終わりに. http://www.jdom.org/. [4]「LFM 技術概論」. 本稿では、従来の XML データベースを利. http://www.digo-tech.com/tech/lfm_techdl.p. 用した場合のいくつかの問題点を解決する. df. ために、インメモリ XML データベース. [5] Application Programming Interface for. 「Karearea」で採用した機構について紹介し. XML Databases. た。また、メモリ消費量や「Xalan」で XPath. http://www.xmldb.org/xapi/. 処理を行った場合との処理速度について比較を行い、その優位性を確認した。－8－ −16−.

(9)