Hatena::Grouppostgresql

PostgreSQL 雑記 このページをアンテナに追加 RSSフィード

2012-04-17SQLでランレングス圧縮 このエントリーを含むブックマーク このエントリーのブックマークコメント

範囲型 (range types) ⇔ 普通のテーブル構成の相互変換は、いわゆるランレングス圧縮 (RLE) になりますね。とりあえずサンプルデータを作成。

=# CREATE TABLE flat (seq serial, v integer);
=# INSERT INTO flat (v) SELECT v FROM (
  SELECT v, generate_series(1, 1 + floor(random() * 10)::integer) FROM (
    SELECT floor(random() * 10)::integer AS v FROM generate_series(1, 1000)
  ) T
) T;
INSERT 0 5594

最初はウィンドウ関数を使えば良いかと思っていたんですが、いまいち上手くいかない……。increment_if() みたいなエッジを検出するようなウィンドウ関数があれば可能かも? 再帰クエリならば簡単ですが、効率は悪い気がします:

=# CREATE TABLE rle AS
WITH RECURSIVE r AS (
  SELECT seq, v, seq AS seq_first FROM flat
UNION ALL
  SELECT flat.*, r.seq_first FROM flat, r WHERE flat.v = r.v AND flat.seq = r.seq + 1
)
SELECT int4range(min(seq), max(seq) + 1) AS seq_range, v FROM (
  SELECT seq, v, min(seq_first) AS seq_first FROM r GROUP BY seq, v
) T
GROUP BY seq_first, v
ORDER BY seq_range;

=# SELECT * FROM rle;
  seq_range  | v
-------------+---
 [1,10)      | 5
 [10,16)     | 0
 [16,23)     | 6
...
(900 rows)

逆に、展開するのは generate_series() を使えば簡単です:

=# SELECT generate_series(lower(seq_range), upper(seq_range) - 1) AS seq, v FROM rle;
 seq  | v
------+---
    1 | 5
    2 | 5
    3 | 5
...
(5594 rows)