【次世代高速RDB 劔"Tsurugi"】Tsurugi におけるサブクエリーの実現

SQL では、サブクエリー (副問い合わせ) を利用することで、複雑な問い合わせを簡潔に表現することができます。

サブクエリーとは、SQL の問い合わせの中に、入れ子になった問い合わせを含める機能です。
例えば、以下のように「平均値を算出するサブクエリー」を使って、外側の「平均値以上の行を抽出するメインクエリー (主問い合わせ)」が記述できます:

SELECT *
FROM member
WHERE point >= (
    SELECT AVG(point)
    FROM member
)

この例は「スカラーサブクエリー」の節でもう一度出現し、そちらで説明します。

なお、Tsurugi ではそれぞれ以下のバージョンでサブクエリーの機能を実現しています。

・Tsurugi 1.0 ：テーブルサブクエリー
・Tsurugi 1.9 ：共通テーブル式
・Tsurugi 1.10 ：スカラーサブクエリー、IN述語、EXISTS述語
・Tsurugi 1.11 ：相関サブクエリー

今回は、Tsurugi では上記のサブクエリーをどのような形で処理しているのか、実行に適した「データフロー」の形式に変換する過程を紹介します。

SQL とデータフロー処理

Tsurugi では、SQL を内部的に「テーブルデータを処理するデータフロー」へと変換し、それをもとに処理を実現しています。

例えば、以下のような SQL について考えます:

SELECT m.name, o.amount * m.price AS total
FROM orders AS o
JOIN item_master AS m
  ON o.item_id = m.id
WHERE o.order_date = DATE '2026-01-01'

上記は、おおよそ以下の処理を行っています:

• orders テーブルと item_master テーブルを結合

• order_date が 2026-01-01 の行のみを抽出

• name と amount * price の列を抽出

• その結果をクライアントに返す

これをデータフローとして表現すると、下図のような処理の流れになります:

データフローのそれぞれのノードは、Tsurugi では「演算子」とよびます。
上記に出現する演算子は、おおよそ以下のような処理を行うものです。

Tsurugi では、上図のようなデータフローをもとに、データフロー上の演算子を書き換えることで SQL の最適化を行ったり、より実行に適した形式に変換したりして、最終的にクエリーに対する実行計画を作成します。

サブクエリーの種類

Tsurugi ではテーブルサブクエリー、スカラーサブクエリー、EXISTS 述語など、様々な種類のサブクエリーを利用可能です。

今回紹介するサブクエリーはいずれも、先に説明したようなデータフローで表現することができます。
以降では、それぞれのサブクエリーについて順に見ていきます。

テーブルサブクエリー

テーブルサブクエリーは、本来テーブルを指定する場所にサブクエリーを指定することで、サブクエリーの結果をテーブルの代わりとして利用する仕組みです。

以下はテーブルサブクエリーの例です:

SELECT *
FROM (
    SELECT category, AVG(price) AS avg_price
    FROM item_master
    GROUP BY category
) AS summary
WHERE avg_price >= 1000

上記は item_master テーブルの category ごとの平均価格を算出するサブクエリーを仮想的なテーブルとして利用し、メインクエリー側でその平均価格が 1000 以上の行を抽出しています。
この例であれば HAVING 句を使って同じ処理を書くこともできますが、複雑な SQL ではテーブルサブクエリーを用いて処理を分割することで、全体の見通しを改善できます。

さて、これをデータフローで表現すると、下図のようになります:

図のように、サブクエリー内のデータフロー (破線部分) とメインクエリーのデータフローを、1つのデータフローとして連結することでテーブルサブクエリーを実現しています。

今回新しく出現した演算子は以下の通りです:

共通テーブル式

共通テーブル式 (Common Table Expression, CTE) は、前項のテーブルサブクエリーに名前を付け、メインクエリーからテーブルとして参照できるようにしたものです。

以下は共通テーブル式の例です:

WITH summary AS (
    SELECT category, AVG(price) AS avg_price
    FROM item_master
    GROUP BY category
)
SELECT *
FROM summary
WHERE avg_price >= 1000

上記は、前項のテーブルサブクエリーの例と同じ処理を、共通テーブル式を用いて書き換えたものです。
これに対するデータフローも前項と同様なので、ここでは省略します。

スカラーサブクエリー

スカラーサブクエリーは、1行1列の結果を返すサブクエリーを外側のクエリーでスカラー値として扱う仕組みです。

以下は、冒頭でも挙げたスカラーサブクエリーの例です:

SELECT *
FROM member
WHERE point >= (
    SELECT AVG(point)
    FROM member
)

スカラーサブクエリーは様々な実現方法がありますが、Tsurugi では「スカラーサブクエリーの結果を結合処理によってメインクエリーに取り込む」という手法で実現しています。
この手法の利点は、既存のデータフローの枠組みを保ったまま、スカラーサブクエリーの評価を全体で1回に収めることができる点です。

Tsurugi の手法で先ほどの SQL をデータフローで表現すると、下図のようになります:

データフロー中の join 演算子では、左表 (図中の (L)) に member テーブル全体を、右表 (図中の (R)) にスカラーサブクエリーの結果である1行1列の値をとります。
この結合結果は、 member テーブルの各行に、スカラーサブクエリーの結果である平均値の列を追加したものです。

なお、スカラーサブクエリー特有の処理として、join 演算子には type: left_outer_at_most_one という結合タイプを指定しています。
これは、スカラーサブクエリーの結果が1行以下である場合には LEFT OUTER JOIN のように振る舞い、2行以上の場合には SQL 全体をエラーで終了させます。
結果が0行である場合、追加される列は NULL となります。

IN 述語

IN 述語は、サブクエリーの結果に特定の値が含まれているかどうかを判定するための仕組みです。

以下は IN 述語の例です:

SELECT *
FROM member
WHERE id IN (
    SELECT member_id
    FROM orders
    WHERE order_date = DATE '2026-01-01'
)

上記は、 orders テーブルから 2026-01-01 に注文した会員の ID を抽出し、その ID を持つ member テーブルの行を抽出する処理です。
おおまかには「2026-01-01 に注文した会員を抽出する」と読めます。

IN 述語をデータフローで表す際には、半結合 (semi join) という特殊な結合を利用します。
これは、左表と右表を比較した際に、左表の各行に対して条件を満たす右表の行が存在するかどうかを判定し、存在する場合に左表の行を出力する (右表の列は含まない) という結合です。

これを利用してデータフローを表現すると、下図のようになります:

図中のデータフローで注目すべきなのは、join 演算子に半結合を表す type: semi が指定され、その結合条件として左右の列を比較する on: L.id = R.member_id が与えられている点です。
なお、 L. は左表 (図中の (L)) の列を、 R. は右表 (図中の (R)) の列を表す疑似的な接頭辞で、データフローの説明のために挿入しています。

これは、左表の列 L.id に対応する右表の R.member_id が存在する場合に、その左表の行を出力するという動作です。
これはまさに IN 述語の動作を表しています。

EXISTS 述語

EXISTS 述語は、サブクエリーの結果が1行以上存在するかどうかを判定するための仕組みです。
まずは以下の簡単な EXISTS 述語の例を見てみましょう:

SELECT *
FROM member
WHERE EXISTS (
    SELECT *
    FROM campaign
    WHERE CURRENT_DATE BETWEEN start_date AND end_date
)

上記は、開催中のキャンペーンが存在する場合に、member テーブルの全行を返す処理です。
サブクエリーがメインクエリーの列を参照していないため、member テーブルのどの行に対しても判定結果は変わりません。

この EXISTS 述語も、 IN 述語と似たような形式で、半結合を利用したデータフローで表現できます。
ただし、「いずれかの行が存在するかどうか」という条件を判定するという点が、IN 述語と異なります。

これを利用してデータフローを表現すると、下図のようになります:

図中のサブクエリー側のデータフローは、前項の IN 述語の例と同じ形をしています。
IN 述語との差異は、半結合の結合条件が左右の列の比較ではなく、常に真 (on: TRUE) となっている点です。
これにより、「左表 (図中の (L)) の各行に対して、右表 (図中の (R)) が1行でも存在するかどうか」を判定することができます。

つまり、「右表が1行でもあれば左表の全行を出力し、右表が0行であれば左表を1行も出力しない」という動作です。
これは EXISTS 述語の動作そのものです。

相関サブクエリー

ここまでの説明では、すべてのサブクエリーは「非相関サブクエリー」と呼ばれるものでした。

Tsurugi では、サブクエリーの中から外側のクエリーの列を参照するような、「相関サブクエリー」も利用可能です。

例えば、以下のような SQL が書けます:

SELECT *
FROM member AS m
WHERE EXISTS (
    SELECT *
    FROM campaign AS c
    WHERE CURRENT_DATE BETWEEN c.start_date AND c.end_date
      AND m.point >= c.min_point
)

上記は前項の EXISTS 述語の例をもとに、サブクエリー内に m.point >= c.min_point という抽出条件を追加したものです。
サブクエリー内の m.point はメインクエリーの member テーブルの列を参照しているため、これは相関サブクエリーに分類できます。
SQL 全体としては「開催中のキャンペーンが存在し、かつ会員がそのキャンペーンの規定ポイントを満たしている場合に、その会員の情報を抽出する」と読めます。

前項までの非相関の例と異なり、相関サブクエリーの例ではメインクエリーの行ごとに m.point が異なる値をとりえるため、サブクエリーはその値によって結果が変化します。

相関サブクエリーに対する考え方

非相関サブクエリーと同様に、相関サブクエリーも様々な実現方法があります。

最も単純な方法としては、メインクエリーの各行に対して、毎回サブクエリーを実行する、という方式です。

これはメインクエリーの行数が非常に少ない場合には有効ですが、メインクエリーが数億行もあるような場合には、サブクエリーもその回数だけ実行されることになり、あまり効率がよくありません。

そこで、Tsurugi では、相関サブクエリーを「非相関化 (de-correlation)」という方式で非相関サブクエリーへと変換し、そのうえで処理を行っています。

相関サブクエリーの変換

Tsurugi では、相関サブクエリーを「パラメーター化された非相関サブクエリー」として取り扱います。
ここでいうパラメーターとは、サブクエリー内で参照される外側のクエリーの列 (相関列) を指します。

このような考え方のもと、以下の手順で相関サブクエリーをデータフローで表現します:

1. メインクエリーからサブクエリーに対して、パラメーターの集合を渡す

2. サブクエリー内で、パラメーターを結合によって取り込む

3. 上記のパラメーターを取り込んだ状態でサブクエリーの処理を行う

4. メインクエリーに、サブクエリーの結果をパラメーターごとに結合する

文章だけでは伝わりにくいので、実際にデータフローを見てみましょう。

データフローに変換する対象の SQL は、「相関サブクエリー」の項で紹介した以下の SQL です:

SELECT *
FROM member AS m
WHERE EXISTS (
    SELECT *
    FROM campaign AS c
    WHERE CURRENT_DATE BETWEEN c.start_date AND c.end_date
      AND m.point >= c.min_point
)

これに対し、Tsurugi では下図のようなデータフローを生成します:

先に新規の演算子について紹介します:

相関サブクエリーであっても、サブクエリーの結果をメインクエリーと半結合する点は、非相関の EXISTS 述語と同様です。
以下の箇所で非相関の場合と異なります:

• メインクエリー側の m.point 列を、サブクエリー側に「パラメーター」として注入している

  • サブクエリー側では、そのパラメーターを join 演算子で結合し、以降の演算子で参照できるようにしている (図中 [a])

  • このとき、事前にパラメーターの重複を distinct 演算子で排除することで、結合結果を必要最小限に抑えている (図中 [b])

  • 後段の filter 演算子では、注入した m.point を利用している (図中 [c])

• サブクエリーの結果をメインクエリーに結合する際に、注入したパラメーターによる比較を行っている

  • メインクエリー (図中の (L)) が持つ m.point と、サブクエリー (図中の (R)) に注入した m.point を結合条件に利用している (図中 [d])

  • この操作によって、「現在のパラメーターに対して処理したサブクエリーの結果」のみをメインクエリーに結合することができる

上図のようなデータフローを組むことで、相関サブクエリーであってもサブクエリー内の campaign テーブルへのアクセスを全体で1回に限定しています。

このような非相関化のもう1つの利点として、「通常のデータフロー最適化が適用可能である」という点が挙げられます。
実際に、Tsurugi では最適化の段階において、サブクエリーはフラットなデータフローに変換済みであり、メインクエリーとサブクエリーを1本のデータフロー上でまとめて最適化を行っています。

相関サブクエリーの基礎技術

Tsurugi の非相関化の実装は "Magic De-correlation" という手法を基礎にしています。
以下はその参考文献です:

• "Magic sets and other strange ways to implement logic programs"

  • Francois Bancilhon et al.

  • PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p1-15

  • DOI: 10.1145/6012.15399

• "Magic is relevant"

  • I. S. Mumick et al.

  • ACM SIGMOD Record, Volume 19, Issue 2, p247-258

  • DOI: 10.1145/93605.98734

今回紹介しきれなかった他の複雑なケースについても、Tsurugi では同様の手法でデータフローの変換を行い、SQL を処理しています。
手法について詳しくは上記の文献を参照してください。

サブクエリー関連の現在の制限

サブクエリーには、現状で以下の表に挙げる機能の制限があります。
これらの制限は将来のバージョンで対応することを検討しています。

ここでいう「分離可能なフィルター条件」とは、 WHERE や HAVING などのフィルター条件として単独で利用されているか、あるいはそこに直接現れる AND または NOT の直接のオペランドであることを指します。

まとめ

以上が Tsurugi におけるサブクエリーの実現方法の概要です。

紹介したように、Tsurugi ではサブクエリーとメインクエリーを1つのデータフローに統合することで、SQL 全体を大きなデータフローとして処理しています。

非相関のサブクエリーでは、サブクエリーの結果をメインクエリーに join 演算子を用いて取り込みました。

相関のサブクエリーでは、メインクエリーの列をパラメーターとしてサブクエリー内に注入し、サブクエリー内では join 演算子を用いてパラメーターを取り込みました。

サブクエリーの種類ごとの取り込み方は、下記の表のようにまとめられます:

Tsurugi では、すべての処理をフラットなデータフロー上で行っています。
サブクエリーという特殊な構造であっても、上記の表のように結合 ( join 演算子) 等を利用することで、メインクエリーとサブクエリーをつなぎ、データフロー上で自然に処理を表現できることがわかります。
そして、これらのデータフローは「SQL とデータフロー処理」で述べた通り、最適化を経て実行計画に変換されます。

ただし、この方法には問題もあります。
特に相関サブクエリーでは、非相関化の際にメインクエリーからパラメーター (相関列) をサブクエリーに注入しています。
このとき、注入するパラメーターの種類数と、サブクエリーが処理するテーブルの行数との直積 (掛け算) が、一時的にメモリー上に展開されます (多くのケースでは、最適化によってそれよりはずっと少ない件数にはなります)。

このため、一部のケースについては、「メインクエリーの1行ずつで、サブクエリーを評価する」という単純な方法 (demanding evaluation) のほうがうまく動く場合があります。
このメモリー使用量を実行前に推定し、実行計画を切り替える方式などを検討しています。

その他の劔"Tsurugi"を使う際に役立つTips集はコ

次世代高速RDB劔"Tsurugi"は、オープンソースで公開中です。
ぜひダウンロードしてみて、触ってみてください。

劔"Tsurugi"のダウンロードはコチラから

https://www.tsurugidb.com/