PostgreSQL の無限再帰 WITH 句で思うこと

お世話になっております、サイオス 那賀です。

PostgreSQL の再帰 WITH 句で、無限長のフィボナッチ数列を作ってみます。

template1=# WITH RECURSIVE
              f(a, b) AS (VALUES(0, 1) UNION SELECT b, a + b FROM f)
            SELECT a FROM f OFFSET 0 LIMIT 20;
  a
------
    0
    1
    1
    2
    3
    5
    8
   13
   21
   34
   55
   89
  144
  233
  377
  610
  987
 1597
 2584
 4181
(20 rows)

template1=# 

この "LIMIT" の用法は、下記の通り可搬性が低いので推奨はできないようですが、ちょっと面白いので。

これが動作するのは、PostgreSQLの実装が、実際に親問い合わせで取り出されるのと同じ数のWITH問い合わせの行のみを評価するからです。 この秘訣を実稼動環境で使用することは勧められません。 他のシステムでは異なった動作をする可能性があるからです。（「WITH問い合わせ（共通テーブル式）」 - PostgreSQL 文書）

「必要な部分しか持ってこないので、データ元が無限でも OK」というところが、ちょっと Haskell 等の遅延評価型言語における無限長リストを思い起こさせます。

無限長のフィボナッチ数列。

module Fib where
  f = 0:1:zipWith (+) f (tail f)

その頭 20 個を取得。

*Fib> take 20 f
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]
*Fib>

RDBMS で、複雑な結合の実行計画を賢く最適化して、実際に必要なデータだけをストレージからフェッチしてくれる機能というのは、どこか遅延評価の考え方に似ているように思われます。

CREATE TABLE foo (k integer PRIMARY KEY, v text);
TRUNCATE TABLE foo;
INSERT INTO foo VALUES(1, '1st foo');
INSERT INTO foo VALUES(2, '2nd foo');
INSERT INTO foo VALUES(3, '3rd foo');
INSERT INTO foo VALUES(5, '5th foo');
INSERT INTO foo VALUES(7, '7th foo');

CREATE TABLE bar (k integer PRIMARY KEY, v text);
TRUNCATE TABLE bar;
INSERT INTO bar VALUES(1, '1st bar');
INSERT INTO bar VALUES(2, '2nd bar');
INSERT INTO bar VALUES(4, '4th bar');
INSERT INTO bar VALUES(6, '6th bar');
INSERT INTO bar VALUES(8, '8th bar');

当たり前ですが、直積をとってから絞り込むような、手続き型処理的なアホなことはしていませんね。

template1=# EXPLAIN SELECT * FROM foo CROSS JOIN bar;
                             QUERY PLAN
--------------------------------------------------------------------
 Nested Loop  (cost=23.53..30303.83 rows=1512900 width=72)
   ->  Seq Scan on foo  (cost=0.00..22.30 rows=1230 width=36)
   ->  Materialize  (cost=23.53..35.83 rows=1230 width=36)
         ->  Seq Scan on bar  (cost=0.00..22.30 rows=1230 width=36)
(4 rows)

template1=# EXPLAIN SELECT * FROM foo CROSS JOIN bar WHERE foo.k = bar.k;
                             QUERY PLAN
--------------------------------------------------------------------
 Merge Join  (cost=170.85..290.46 rows=7564 width=72)
   Merge Cond: (foo.k = bar.k)
   ->  Sort  (cost=85.43..88.50 rows=1230 width=36)
         Sort Key: foo.k
         ->  Seq Scan on foo  (cost=0.00..22.30 rows=1230 width=36)
   ->  Sort  (cost=85.43..88.50 rows=1230 width=36)
         Sort Key: bar.k
         ->  Seq Scan on bar  (cost=0.00..22.30 rows=1230 width=36)
(8 rows)

template1=#

PostgreSQL、賢いですねぇ。実行計画の最適化こそがデータベースの真髄ですな。

ではまた。