PostgreSQL 14で追加されたmultirange型(多重範囲型)を試してみた

エンジニアの吉田です。
今回はPostgreSQL(以降postgresと表記) 14から新しく追加されたmultirange型について紹介し、簡単な性能検証をしようと思います。

multirange型とは

従来よりpostgresではrange型（範囲型）と呼ばれるデータ型が用意されていました。これは文字通り範囲を保持するためのデータ型です。例えば整数であれば以下のように宣言できます。

select int4range(1,10);
 int4range 
-----------
 [1,10)
(1 row)

引数でも指定できますが、デフォルトでは左閉右開区間となります（今回の例であれば[1,10)）^[1]。

また値と範囲や範囲同士の比較、演算が可能な組み込み関数も提供されています。以下はその一例です。

-- 左辺が右辺に包含されるか（左辺にスカラも取れます）
select 1 <@ int4range(1,10);
 ?column? 
----------
 t
(1 row)

select int4range(2,8) <@ int4range(1,10);
 ?column? 
----------
 t
(1 row)

-- 左辺と右辺に共通部分があるか
select int4range(5,15) && int4range(10,20);
 ?column? 
----------
 t
(1 row)

今回紹介する multirange型（多重範囲型） はrange型の集合を保持するデータ型です。対応するrange型から生成できます。

-- 複数のint4rangeからint4multirangeを生成
-- 重複する範囲はそれらの和を保持する
select int4multirange(int4range(1,10),int4range(5,15), int4range(20,30));
  int4multirange  
------------------
 {[1,15),[20,30)}
(1 row)

range型との違いは値が連続でなくても良いという点で、これにより非常に柔軟なパターンの範囲を格納できます。
また、range型で利用可能だった多くの組み込み関数はmultirange型でも利用可能で、関数によってはスカラやrange型との比較もサポートしています。

-- 左辺が右辺に包含されるか（左辺にスカラやrangeも取れます）
select 1 <@ int4multirange(int4range(1,15), int4range(20,30));
 ?column? 
----------
 t
(1 row)

select int4range(2,8) <@ int4multirange(int4range(1,15), int4range(20,30));
 ?column? 
----------
 t
(1 row)

select int4multirange(int4range(25,40),int4range(50,60)) <@ int4multirange(int4ran
ge(1,15), int4range(20,30));
 ?column? 
----------
 f
(1 row)

-- 左辺と右辺に共通部分があるか（左辺にrangeも取れます）
select int4range(2,8) && int4multirange(int4range(1,15), int4range(20,30));
 ?column? 
----------
 t
(1 row)

select int4multirange(int4range(25,40),int4range(50,60)) && int4multirange(int4ran
ge(1,15), int4range(20,30));
 ?column? 
----------
 t
(1 row)

range_agg という集約関数も用意されており、range型またはmultirange型をmultirange型へと集約可能です。

-- スカラを直接range_aggでmultirangeにすることはできず、ひと工夫が必要
select range_agg(int4range(val, val+1)) from (select generate_series(1,10) as val) s;
 range_agg 
-----------
 {[1,11)}
(1 row)

multirange型の使い時を考える

まずmultirange型で注目すべきは、単なる範囲の集合というだけではなく一対多の対応関係を1行1列で表現できる点にあると考えています。
一般的にRDBでは交差テーブルを用いて表現すべきものですが、multirange型を使って値ごとの関係を1行にまとめることで、場合によってはデータ量の削減や検索性能の向上が期待できそうです。

また、range型は範囲同士の高速な比較が可能ですが、multirange型も（当然ながら）同じ特性を持っており、範囲検索を頻繁に実施する場合は検討の余地があるかもしれません。

考慮すべき特徴としては、内部ではrange型の集合として表現されるため、含まれる範囲の数が少ない（飛び飛びが少ない）方が効率的にデータを格納できるという点です。
含まれる要素数自体はいくら大きくてもよいため、取りうる値の集合が非常に巨大で、対応関係も列挙すると膨大になってしまうケースも有効に働くかもしれません。

一方で更新を頻繁にするカラムの場合には注意が必要です。値の一部ではなくカラム全体を更新する必要があるため縦持ちと比較するとコストがかかりますし、値が変動した結果内部で保持するrangeの数が変わる場合はより時間がかかることが予想できます。
また、共通部分のある複数範囲を登録した場合は共通部分がマージされて１つの範囲となるため、後から一方のみを取り除くことはできません。

検証してみた

実際に、multirangeを既存の仕組みと比較してデータ量や検索性能にどういった特徴があるか軽く検証してみます。

postgresで多対多を表現する手段としては、multirangeの他に縦持ちか配列^[2]が考えられますので、今回はこれら3パターンの検証をします。

• 格納するデータの状態は以下のようなイメージです。

 id | val 
----+-----
  1 |   1
  1 |   2
  1 |   4
  1 |   5
 ...
  2 |   1
  2 |   2
 ...

 id |        val 
----+-------------------
  1 |   {1, 2, 4, 5, ...}
  2 |   {1, 2, 4, 5, ...}
  3 |   {1, 2, 4, 5, ...}
 ...

 id |          val 
----+-----------------------
  1 |   {[1,3),[4,6), ...}
  2 |   {[1,3),[4,6), ...}
  3 |   {[1,3),[4,6), ...}
 ...

データセットは以下のようなものを用意しました。

• set A: 1, 2, 3, ..., 100 (連続する整数100個) * 10万レコード
  • 全ての値が同一範囲に収まっている、multirangeが一番有利な分布です。
• set B: 1, 3, 5, ...,199 (連続する奇数100個) * 10万レコード
  • 全ての値が異なる範囲に収まっている、multirangeが一番不利な分布です。
• set C: 1, 2, 4, 5, ..., 148, 149 (連続する3n±1の数100個) * 10万レコード
  • AとBの中間くらいの分布です。
• set D: 1 (値1つのみ) * 1000万レコード
  • 1対1の関係です。（かなり極端ですが）最低性能を確認するために用意しました。データ量を揃えたら検証に時間がかかって後悔しています。

テーブル作成後のページ数比較

	set A	set B	set C	set D
縦持ち	44248	44248	44248	44248
配列	5883	5883	5883	73530
multirange	736	16667	9091	73530

要素の数を一定にしているため、縦持ちの場合は全て全く同じページ数となります。

配列はid当たりの要素数に依存します。縦持ちと比較すると、完全に一対一の場合こそ負けていますが1レコードあたりの要素数が多いと非常に効率の良い持ち方になります。
1要素あたりに必要な領域は一定のため、配列長が同じであれば値の分布によってサイズが変わることもありません。

multirangeは包含するrangeの個数に依存し、最悪（全ての値が飛び飛び）の場合配列の3倍程度になりました。
一方で最高（全ての値が連続）の場合は配列と比較しても非常に高効率でデータを保持できます。

絞り込み性能比較

次はそれぞれのテーブルに対し、検索対象の要素が全体の半分程度になるような絞り込み検索を実施します。
それぞれ件数表示（select count(*)）と、対象内の最小、最大値を取得するクエリそれぞれを実行して比較します。

最小、最大値を取得する検証に使用したSQLは以下のようなイメージです。

select
    max(val),
    min(val)
from
    value_pattern_1
where
    val between 25 and 74
group by
    id
;

値で絞り込み、group byして最小値、最大値を取得します。

select
    array_lower(array_val & array[25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74], 1),
    array_upper(array_val & array[25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74], 1)
from
    value_pattern_array_1
where
    array_val && array[25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74];

配列の場合、範囲との積集合を取ろうとすると範囲を配列で宣言せざるを得ないような気がします（もっと良いやり方があるかもしれない）。
高々数十件なので列挙していますが、もっと膨大になってくると構文解析時間も無視できなくなってくるため、工夫は必要そうです。
where句はselect句と表記を揃えましたが、左端と右端、右端と左端をそれぞれ比較するような書き方で短縮できます。

select
    range_merge(multirange_val * int4multirange(int4range(25,75)))
from
    value_pattern_multirange_1
where
    multirange_val && int4multirange(int4range(25,75))
;

select句では、検索範囲とカラムの積集合（*）を取った上で、その凸包（range_merge）を返却する、という処理を行っています。
これによって範囲内の最小値～最大値からなるrange型が取得でき、最小値と最大値が得られたことになります。

結果は以下のようになりました。
※自分のローカル環境で計測したもので、環境によっては異なる結果となる可能性があります。あくまで参考値として考えてください。
※縦持ちはseq scanだと比較にならないほど遅くなる可能性があったため、値にindexを貼っています。multirange(gist), array(gin or gist)にも貼ることができますが、今回はseq scanより良い実行計画にならなかったため割愛します。

	set A (list)	set A (count)	set B (list)	set B (count)	set C (list)	set C (count)	set D (list)	set D (count)
縦持ち	1858 ms	1760 ms	1827 ms	1716 ms	1784 ms	1683 ms	8133 ms	7982 ms
配列	175 ms	78 ms	176 ms	78 ms	175 ms	80 ms	5946 ms	2355 ms
multirange	82 ms	45 ms	1938 ms	95 ms	972 ms	71 ms	7498 ms	2275 ms

比較すると配列がかなり優秀であることがわかる一方、行数取得はmultirangeが非常に高速であることも見て取れます。

配列、multirangeともに1レコード当たりの演算に時間がかかるため、実際に行を取得するより行数のみ取得する方がselect句の評価がない分高速になります。
今回は全行評価しているため遅いですが、日常的に用いる絞り込んでlimit offsetをかけるような処理ではlimit後に評価されるため、そこまで気にならないかもしれません。

multirangeに関しては積集合を取る処理が大変重く、特に多くのrangeを内包するパターンの演算には時間がかかっています。
一方で共通部分の取得は非常に高速に動作し、また内部で保持するrangeの数が増えてもそこそこの速度を保っている点は特筆に値します。

更新性能比較

最後に更新性能を比較します。今回はset B(奇数のみ), set D(1のみ) の全idに2を追加する、という処理を実施しました。
結果は以下のようになりました。

	2 to set B	2 to set D
縦持ち	971 ms	31139 ms
配列	1044 ms	52292 ms
multirange	5937 ms	162603 ms

縦持ちの場合、1レコード追加すればよいため最も高速に動作する一方で、配列やmultirangeは値の集合自身を更新する必要があるため、相対的に遅くなります。
multirangeは顕著に遅く、内部で保持するrange型の数が増えるとより時間がかかるという結果になりました。

配列の更新は縦持ちと比較してもそこまで性能劣化はありませんでしたが、idに紐づく値の数が増えると速度関係に変化があるかもしれません。
今回は1:100と1:1の検証でしたが、これが1:100万などになってくるとmultirangeとの性能逆転が起きる可能性はあります。

まとめ

今回のmultirangeに関する検証結果をまとめると、

• データの分布によっては配列以上に高効率でデータを保持できる
• 範囲検索が非常に高速で、データの多くが飛び飛びであった場合でも有用
• 更新操作はかなり苦手

ということが言えそうでした。

条件付き最大値/最小値の取得にトリッキーな操作をしている部分など改善の余地はありますが、更新頻度が低く範囲検索の頻度が高い場合は単純に交差テーブルの互換としてかなり使えそうな印象を受けました。
配列操作の優秀さも同時に確認できましたが、データの整合性を保つ難度がかなり高いため、比較的容易に検索性能を高める手段として、multirangeは「できる子」なのではないかと思います。

この記事を書いた人

吉田　侑弥

今年のサマーインターン検索高速化コースでは、課題にmultirangeを使うと高速化できるようなボトルネックを仕込んでみました。なお、インターン生に提供したpostgresのバージョンは12です。

脚注

1. integerの場合、どの指定でも内部では左閉右開区間で保持されます。(1,10] は [2,11) となります。

2. 配列の構築や演算はかなりトリッキーで、一般的にはあまり利用されないと思いますが、postgresでは配列を活用することで性能が向上するケースがしばしばあります。
   intarrayというcontribモジュールを活用すると、一対多関係の構築や更新が比較的容易に実現できます。