PostgreSQLでXML(5): ORDER BYとB-treeインデックス

さて、PostgreSQLでXMLを使うシリーズ、第5回です。

なお、今回も引き続き次のようなテーブルを前提とします。

CREATE TABLE testxml (
  id SERIAL PRIMARY KEY,
  xmldoc XML
);

コンテンツも引き続き、本サイトのXMLデータ(約1500件)を、 xmldocに突っ込んであります。idは連番です。

B-treeインデックス復習

前回の内容で、一般的にXMLに対して利用されるGINインデックスではなく、次のような形のB-treeインデックスを作成することで、XMLの内容に対するインデックスを利用した高速な前方一致検索ができるということを紹介しました(ただしここで、//title/text()がもし文書中で複数回出現する場合は、最初の1回のみが対象となる)。

CREATE INDEX testxml_title_btree2_idx ON testxml
USING BTREE
(array_first(xpath(E'//title/text()'::text, xmldoc)::text[]))

ここで、array_first()は次のような定義となります。

CREATE FUNCTION array_first(text[]) RETURNS text
    LANGUAGE sql 
    IMMUTABLE STRICT
    AS $$ 
        SELECT $1[1]
    $$;

B-treeインデックスとORDER BY

さて、PostgreSQLにおけるB-treeインデックスは、 大小の比較に使えるという特徴を持っており、 この特徴からWHERE条件だけではなく、ORDER BYのソートにも利用することができます。 PostgreSQLのドキュメントにも次のように記述されています。

PostgreSQLが現在サポートするインデックスの種類の中で、B-Treeのみがソート出力を行うことができます。 他の種類のインデックスでは指定なし、または、実装固有の順序で一致した行を返します。(PostgreSQL 9.0.3文書: 11.4. インデックスとORDER BY)

従って、XMLにB-treeインデックスを設定すれば、ORDER BYにこのインデックスを用いることができるのでしょうか?

と思ったのですが、そううまくはいかないのです。 たとえば単純な例で、<title>の内容でソートしたいとして次のようなSQLを作ります。 array_first(xpath(E'//title/text()'::text, xmldoc)::text[])は上記のインデックスtestxml_title_btree2_idxが張られているので、 これを使ってソートしてくれることを期待するのですが…。

SELECT id,
array_first(xpath(E'//title/text()'::text, xmldoc)::text[]) AS title
FROM testxml
ORDER BY title

実際にEXPLAIN ANALYZEすると、Sortがシーケンシャルな検索をされて、800ms程度とかなり時間がかかっていることがわかります。

testxml=# SELECT id,
testxml-# array_first(xpath(E'//title/text()'::text, xmldoc)::text[]) AS title
testxml-# FROM testxml
testxml-# ORDER BY title;
  id  |                                                        title                                                         
------+----------------------------------------------------------------------------------------------------------------------
  632 | (ベタだけどやっぱり)ガンダム、台場に立つ!
 1398 | 10年以上経ったカップヌードル・タイムカンを開けてみた
...(略)...
(1558 行)
testxml=# EXPLAIN ANALYZE SELECT id,
testxml-# array_first(xpath(E'//title/text()'::text, xmldoc)::text[]) AS title
testxml-# FROM testxml
testxml-# ORDER BY title;
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Sort  (cost=322.09..325.99 rows=1558 width=36) (actual time=799.861..803.396 rows=1558 loops=1)
   Sort Key: (((xpath('//title/text()'::text, xmldoc, '{}'::text[]))::text[])[1])
   Sort Method:  quicksort  Memory: 171kB
   ->  Seq Scan on testxml  (cost=0.00..239.48 rows=1558 width=36) (actual time=0.418..786.624 rows=1558 loops=1)
 Total runtime: 806.736 ms
(5 行)

いろいろ苦労したのですが、少なくとも全件検索時には、インデックスが使われることはないようです。

おそらく、PostgreSQLのプランナのアルゴリズムが、 xpath()のような、 コストが非常に高くなる関数の想定をしておらず、 よほどインデックスの効用が明確でない限り、 インデックスを用いないようになっているのかも知れません。 先程のPostgreSQLのドキュメンテーションでも、次のように書かれています。

テーブルの大部分のスキャンが必要な問い合わせでは、後に発生するシーケンシャルなアクセスパターンのために要求されるディスクI/Oが少ないため、インデックスを使用するよりも、明示的なソートの方が高速です。 数行を取り出す必要がある場合のみ、インデックスの方が有用になります。 ORDER BYとLIMIT nが組み合わされた場合が、重要かつ特別です。(PostgreSQL 9.0.3文書: 11.4. インデックスとORDER BY)

LIMITを用いることで、条件によりますがインデックスが利用出来るようになります。 しかし、LIMITの値が大きいとインデックスを利用しなくなります。

上記の例では、LIMITが510と511の間に閾値が存在するようで、 LIMITが511の場合は、510の場合のなんと3倍近くの時間がかかってしまうようです。 この差は、個々のXMLのデータが大きくなればなるほど激しくなるでしょう。 メガバイト単位のXMLデータがあった場合などは目も当てられない性能差となります。

testxml=# EXPLAIN ANALYZE SELECT id,
testxml-# array_first(xpath(E'//title/text()'::text, xmldoc)::text[]) AS title
testxml-# FROM testxml
testxml-# ORDER BY title
testxml-# LIMIT 510 OFFSET 0;
                                                                    QUERY PLAN                                                                    
--------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..315.40 rows=510 width=36) (actual time=1.240..246.099 rows=510 loops=1)
   ->  Index Scan using testxml_title_btree2_idx on testxml  (cost=0.00..963.52 rows=1558 width=36) (actual time=1.233..243.436 rows=510 loops=1)
 Total runtime: 247.494 ms
(3 行)

testxml=# EXPLAIN ANALYZE SELECT id,
testxml-# array_first(xpath(E'//title/text()'::text, xmldoc)::text[]) AS title
testxml-# FROM testxml
testxml-# ORDER BY title
testxml-# LIMIT 511 OFFSET 0;
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=317.35..318.63 rows=511 width=36) (actual time=713.741..716.986 rows=511 loops=1)
   ->  Sort  (cost=317.35..321.25 rows=1558 width=36) (actual time=713.735..714.891 rows=511 loops=1)
         Sort Key: (((xpath('//title/text()'::text, xmldoc, '{}'::text[]))::text[])[1])
         Sort Method:  top-N heapsort  Memory: 64kB
         ->  Seq Scan on testxml
  (cost=0.00..239.48 rows=1558 width=36) (actual time=0.416..700.424 rows=1558 loops=1)
 Total runtime: 718.152 ms
(6 行)

このあたりは、PostgreSQLのプランナの改善を待つしかないかも知れません。 B-treeインデックスの内部にxpath()があった場合は、 問答無用で全件検索のORDER BYにもインデックスを使ってもらいたい、と思いますね。

回避策

この問題は基本的に、 現状でのPostgreSQLのXMLサポートの範囲内で回避することを諦めました。 例えば次のようなテーブルを用意して、 何らかの仕組みで<title>の内容がこのテーブルに格納されることとします。

CREATE TABLE testxmltitle (
  id SERIAL PRIMARY KEY,
  testxmltitle INTEGER,
  title TEXT
);

そして、次のような感じでアクセスします。 インデックスは利用されませんが、 testxmltitle.titleへのシーケンシャルな検索はxpath()と異なり十分に高速なので、LIMITなしでも問題ない速度で検索されてきます (ただの「逃げ」ですが)。

SELECT testxml.id, testxml.title
FROM testxml INNER JOIN testxmltitle
  ON testxml.id = testxmltitle.id
WHERE (何かtestxml.xmlに関する条件があればここに)
ORDER BY testxmltitle.title

何かこんなひどい方法ではない、いい回避法をご存じの方、 タイトルのところの「ツイートする」ボタンでつぶやいて教えてくださいませ…。

関連記事