PostgreSQL IN句とEXISTS句(semi-join)のプッシュダウン

## PostgreSQL IN句とEXISTS句(semi-join)のプッシュダウン

### はじめに
PostgreSQL17が2024年9月26日にリリースされました。
この中で、ForeignDataWrapper(FDW)のIN句とEXISTS句(semi-join)のプッシュダウンができるようになりました。

ForeignDataWrapper(FDW)とは外部のデータベースをPostgreSQLで扱えるようにする機能で、詳細は下記をご参照ください。
https://www.postgresql.jp/document/16/html/postgres-fdw.html


### semi-joinとは
semi-joinとは何ぞや、というのを簡単に説明していきます。

下図に２つのあるサービスのユーザーテーブルと、サービスの利用をロギングしたログテーブルと、そのsemi-joinの例を示します。
![qiita_semi_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597157/3afc0194-9b48-a837-f5af-9d20aae96f52.png)


この例ではログテーブルにレコードがあるユーザ(サービスを利用したユーザ)から、そのユーザ情報をユーザテーブルから抽出する例です。
ログテーブルのuseridを取得し、ユーザーテーブルのidと合致するものがあればそのユーザテーブルのレコードを表示する、という形です。
    結果として、ログテーブルには3,4のユーザしかないので、ユーザテーブルの3,4のユーザの情報が取得されるという形です。
まとめると、semi-joinはあるテーブルの要素をフィルタリングなどの条件として使いたい場合(条件の抽出側を結果には出さない)に使用されます。

### 今までの動きと17からの動き
FDWでは外部のデータベースと接続して親のPostgreSQLにSQLを実行すると、子のデータベースのデータを取得することができます。
もっとも単純に動く場合、どのようなSQLでも親のPostgreSQLは指定されたテーブルのデータを全件取得し、親側でデータを処理して返却するという動作です。
最もこのような動きは非常に重くなる可能性が高いです。このため、WHERE句やLIMITなどのプッシュダウン機能がPostgreSQLには実装されています。

以前までのケースでは下図のようにサブクエリを実行した中身と、もう片方のテーブルを取得し親のPostgreSQL上で実行する、という動きでした。
![qiita_semi_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597157/feca983d-8654-6987-886e-f08dcba38523.png)



PostgreSQL17からは、下図のようにそのまま下のデータベースにSQLを実行させ、その結果を得るようになっています。
![qiita_semi_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597157/ada1ca28-955b-42cd-e8aa-c9639cdea244.png)



## 実際にやってみた

### 実験環境
比較のために、PostgreSQL16.6とPostgreSQL17.2を用意しました。
1つの仮想マシンの上でPostgreSQL16,17の親子の組を作成、合計4つのPostgreSQLをポートを変えて作り、FDWで16,17それぞれを接続しています。
![qiita_semi_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/597157/c2d1d6f5-3ec4-6447-1ddf-a9a995a35400.png)



また、データとしては以下のような2つのユーザテーブルとログテーブルを作成しました。
細かいスキーマとデータのサイズは今回割愛しますが、16,17ともに同一データで実行しています。

スキーマを簡単に説明すると、ユーザテーブルには名前や性別、年齢が入ったユーザの情報が、
ログテーブルにはどのユーザがアクセスするたびに1レコード作成される情報が入るイメージです。
(ユーザテーブルのidが主キー、ログテーブルのuser_idが外部キー)

これを子のPostgreSQLにテーブルとして作成します。

### 実行結果
#### 実行プランの比較
それではまずPostgreSQL16から実行していきましょう。親側にSELECTを実行します。
SQLの内容としては、ある期間のアクセスした男性ユーザの情報を表示する内容です。
##### PostgreSQL16の場合
```
                                                      QUERY PLAN                                
----------------------------------------------------------------------------------------------------------------------
 Hash Join
   Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
   Inner Unique: true
   Hash Cond: (user_data.id = log_data.user_id)
   ->  Foreign Scan on public.user_data
         Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
         Remote SQL: SELECT id, name, age, reg_date, login_date, sex FROM public.user_data WHERE ((sex = 0))
   ->  Hash
         Output: log_data.user_id
         ->  HashAggregate
               Output: log_data.user_id
               Group Key: log_data.user_id
               ->  Foreign Scan on public.log_data
                     Output: log_data.user_id
                     Remote SQL: SELECT user_id FROM public.log_data
```
慣れていないと少々わかりにくいですが2つのRemote SQLという部分に注目するとわかりやすいです。
RemoteSQLとはつまり、子に実行させて結果を親が取得したSQLとなっています。
```
Remote SQL: SELECT id, name, age, reg_date, login_date, sex FROM public.user_data WHERE ((sex = 0))
Remote SQL: SELECT user_id FROM public.log_data
```
これはユーザテーブルを性別でフィルタリングした結果とログテーブルとを親のPostgreSQLが取得し、id(ログテーブル側はuser_id)でHashJoinするという形です。
つまりsemi-joinがプッシュダウンできず、親側で結合をしてしまっています。

##### PostgreSQL17の場合
次にPostgreSQL17の場合です
```
                                        QUERY PLAN                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Foreign Scan
   Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
   Relations: (public.user_data) SEMI JOIN (public.log_data)
   Remote SQL: SELECT r1.id, r1.name, r1.age, r1.reg_date, r1.login_date, r1.sex FROM public.user_data r1 WHERE ((r1.sex = 0)) AND EXISTS (SE
LECT NULL FROM public.log_data r2 WHERE ((r1.id = r2.user_id)))
```
非常に簡素になっています。Remote SQLが1つのみ、EXISTSを伴ったSQLになっており、それを実行する(させる)だけで終わりです。


#### 実行時間の比較
次に実行時間を確認してみましょう。explain analyseで確認します。

##### PostgreSQL16の場合
```
postgres=# explain (verbose, costs off, analyze) SELECT * FROM user_data WHERE sex=0 and EXISTS (SELECT NULL FROM log_data WHERE user_data.id=log_data.user_id);
 Hash Join (actual time=20056.029..22433.544 rows=56 loops=1)
（省略...）
 Planning Time: 0.225 ms
 Execution Time: 22434.076 ms
```

###### PostgreSQL17の場合
```
postgres=# explain (verbose, costs off, analyze) SELECT * FROM user_data WHERE sex=0 and EXISTS (SELECT NULL FROM log_data WHERE user_data.id=log_data.user_id);
 Foreign Scan (actual time=1935.064..1935.067 rows=49 loops=1)
（省略...）
 Planning Time: 0.207 ms
 Execution Time: 1935.442 ms
```

実行時間が1/10以下で、非常に高速な結果となっています。
場合によってはプッシュダウンしてしまうと遅くなってしまうケースなどもありますが、そのあたりは最適化の話になるので、また別の機会にしたいと思います。


## semi-joinがプッシュダウンできないケース

NOT INやNOT EXISTSなどのanti semi-joinのケースはどうやら対応していないようです。
下記のように、プッシュダウンせずに動いてしまっています。

```
postgres=# explain (verbose, costs off) SELECT * FROM user_data WHERE sex=0 and NOT EXISTS (SELECT NULL FROM log_data WHERE user_data.id=log_data.user_id);
                                                         QUERY PLAN                                                         
----------------------------------------------------------------------------------------------------------------------------
 Hash Right Anti Join
   Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
   Hash Cond: (log_data.user_id = user_data.id)
   ->  Foreign Scan on public.log_data
         Output: log_data.id, log_data.user_id, log_data.log, log_data.date
         Remote SQL: SELECT user_id FROM public.log_data
   ->  Hash
         Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
         ->  Foreign Scan on public.user_data
               Output: user_data.id, user_data.name, user_data.age, user_data.reg_date, user_data.login_date, user_data.sex
               Remote SQL: SELECT id, name, age, reg_date, login_date, sex FROM public.user_data WHERE ((sex = 0))
```


今回の変更はコード的にはpostgres_fdwのJOINプッシュダウンの部分を修正した追加のようなので、
ANTIの場合はまた別のパスになってしまって捕まえられないのではないかと思います。

## おわりに
PostgreSQL17からsemi-joinがプッシュダウンできるようになり、効果を確認しました。
前述の通り、今回のコードはPostgreSQLのFDWのコードであり、
ほかのデータソースでsemi-joinのプッシュダウンが行うには、それぞれのデータソースのFDWで追加を行う必要があります。

なお、PostgreSQLでは取り込まれる機能に関して、CommitFestと呼ばれるレビューを通過したものだけが取り込まれます。
このレビューはすべてオンライン上で扱われており、今回の機能の詳細は以下のチケットとなります。
https://commitfest.postgresql.org/46/3838/

この機能が取り込まれるまでのレビューやパッチの詳細、FDWの実装に興味がある方はぜひ読んでみてください。