SAP SQL Anywhere で再帰クエリーを使用する (過去のブログ記事より)

このページは、以下の英語ページの抄訳です。最新の情報については、英語ページを参照してください。

（この記事では英語版のSQL Anywhere が使用されていますが、SQL Anywhere は日本語にローカライズされています。）

この記事のオリジナルは、Glenn Paulley が sybase.com に2009年4月に掲載したものです。Glenn はこの中で再帰クエリーが一般にはどのように機能し、さらにSQL Anywhere ではどのように機能するのか説明しています。

再帰 SQL クエリー (あるいは bill-of-materials、transitive closure queries) は、SQL Anywhere ではversion 9 よりサポートされています。再帰 SQL に関しては、下の[1] を含め、オンラインや書籍の形で様々なリソースが提供されていますが、特にここでお伝えしたいのは、下のものです。

• SQL Anywhere の実装と、ANSI/ISO SQL: 2008 標準の再帰クエリーシンタックスの間の（マイナーな）違い;
• 再帰クエリーをアプリケーションで活用する場合に考慮すべき 3つの接続オプション設定；　そして
• 再帰クエリーのグラフィカルなプランの簡単な説明

再帰クエリーを Hibernate でどのように使用するかは後で説明します。というのは、Hibernate の HQL 言語は再帰は直接サポートしていないからです。

例

下は、シンプルですが、再帰クエリーを説明するのに良い例です。SQL Anywhere のサンプルデータベース、demo.dl に対して、全 manager のリストと、それぞれの manager　によって管理されている employee の数を作成します。

demo.db の employee テーブルを見ると、bill-of-materials の性質の問題を示しているのがわかります。それぞれの employee が、自分の manager に対して自己参照する外部キーになっており、全てではありませんが、ほとんどの manager に managerが存在します。Employee テーブルから直接的に直属 manager をリストすると下のようになります。

問題は、このシンプルな結果セット – 冗長な ManagerID はとりあえず無視します – では、employee 501 と 1293 には manager が存在せず （彼らは、「自分自身をmanage します」）、902 が1293 の部下で、703 と 1576 は 902 の部下であることを示していないということです。つまり、それぞれのカウントは、彼らの manager のものとの総計になっていなければなりません。

求める結果セットは、以下になります。

問題は、再帰クエリーにどのように計算させるか、です。

標準再帰 SQLの基本

SQL における再帰は、再帰のとても特別な形です; Jim Melton 氏と Alan Simon 氏が、標準SQL の実装についてとても役に立つ説明を[1] (section 9.13) でしています。要約すると、以下で再帰 SQL クエリーを形成します。

1. 最初の結果セットを seed クエリー とともに構成する。それから
2. そのSELECT 文内のテーブル参照の1つとして再帰中間結果を使用して、二番目のクエリースペックでその結果セットに追加のローをUNION する。

再帰の実行は、fixpoint に到達すると停止します。Semmle’s .QL query language　のベースになっている Datalog などの関数型プログラミング言語では Fixpoint セマンティクスがより共通的に使用されています。ANSI SQL 標準 [1]では、fixpoint セマンティクスは、以下のような状況では緩く定義されています。

…..結果にインサートするより多くのローを特定する努力の過程でそのような追加ローがないことがわかる場合

ANSI SQL 標準では、再帰クエリーは WITH RECURSIVE 句を含む共通テーブル表現を使用して形成されています。下は、修正された再帰クエリーに関連する SQL 文法のサブセットです。

再帰クエリーは、以下のように制限されています。

• SQL 標準では、再帰クエリー表現は、UNION ALLに制限されています。さらに、各仮想再帰テーブルは、そのテーブルの定義において多くとも1度しか参照される可能性はありません。
• ANSI SQL 標準では、単調進行（monotonic progressions）しか許していません。つまり、再帰が継続すると、（仮想）再帰テーブルはサイズの拡大しか許されません。
• 単調性の結果、（仮想）再帰テーブルからのローは（例えばSELECT DISTINCT 経由で）取り除くことも、（仮想）再帰テーブル内の既存ローを on-the-fly で修正することもできません。

標準 SQL には、(1) サーチオーダー経由のトラバーサルがDEPTH FIRST か BREADTH FIRST かを特定する追加のシンタックス、そして(2) 暴走クエリーを防ぐために再帰計算の制限を特定するシンタックスが含まれます。

このSQL 標準からの追加のシンタックスは、下のとおりです。

将来のリリースでの対応の可能性はありますが、SEARCH も CYCLE 句も SQL Anywhere ではサポートしていません。

また、再帰クエリーは、bill-of-material の問題である non-procedural 計算を許していることに注意してください。例えば、結果セットがそれ以上は大きくならないところまで、結果セットにローを追加し続け、永遠にループするストアドプロシージャーを使用するなど、再帰結果セットを呼び起こすことを妨げるものはありません。

実際、まさにこれが、初期のバージョンのSemmle’s .QL 言語での、Microsoft SQL Server データベースをバックエンドとした再帰クエリーの処理方法です。しかしながら、再帰 UNION クエリーをとおして結果を計算する方が、ずっとシンプルで効率的です。

例に戻ると

そのため、ANSI SQL モデルが強いる再帰における制限 —  モノトニシティ と non-negation（否定）— を考えると、意図した結果（集約された employee 数）をse 毎の単一の再帰クエリで生成するのは、直接的にはできないことが明らかです。我々がしなければならないことは、構成されたら、再帰を使用して中間結果を構成することです。

必要なことは、一度構成されれば必要な結果を生成することができる別のクエリへのインプットとして使用することが可能な中間結果を再帰を使用して構成することです。

上記のANSI 再帰 SQL クエリの説明において、seed を展開し、そのローと（仮想）再帰中間結果を UNION し、再帰クエリ表現を呼び出すことが必要だと述べました。我々のケースでは、seed クエリーは、上で説明したシンプルな GROUP BY クエリーで、直属の manager の employeeの数を計算します。

しかし、我々ができることは、management ヒエラルキーを反映する追加の中間結果ローを生成することです。つまり仮想再帰結果セットにおいて、2つの属性（EmployeeID と ManagerID）が必要だということです。

これらの直属の manager でスタートすることで、同じ employee のカウント数を含む追加ローを追加することができますが、これは管理者チェーンの次の manager のためです。

完全なクエリーと生成された結果セットは下のとおりです。

この中間結果について、いくつか特別なポイントがあります。

• テーブル表現 FROM Employees e JOIN EmpsByManager em ON (e.EmployeeID = em.ManagerID)は、Employees テーブルと manager の (仮想) テーブルを join し、より上層の manager にレポートする employee をドキュメントする追加ローを作成します。
• 制限条件である WHERE e.ManagerID <> e.EmployeeID は、自身を管理するmanager のローが再度含まれるのを防ぎます。デモデータベースでは、自身を管理する manager は外部キー値（ManagerID）を同じローに使用して特定することができます。反対に、トップレベルの manager を表しているローで NULL 値を使用しているのであれば、この追加句は必要ありません。

この中間結果が計算されたので、求める最終結果の作成は直接的に、シンプルに下のラインを

下のラインでリプレースします。

SQL Anywhere における条件

SQL Anywhere では、再帰クエリーに関連するものとして注目に値する接続オプションが 3 種類あります。

• SQL Anywhere では、CYCLE 句はサポートしていませんが、再帰クエリーのインタラクションが超過した場合に　(デフォルトは 100です)、暴走再帰クエリーを SQLerror で停止する MAX_RECURSIVE_ITERATIONS の接続オプションを提供しています。ある特定のクエリーで必要な再帰の数は、再帰のヒエラルキーの深さに等しくなければなりません。多くの状況では、これは、ほぼ間違いなく、100よりかなり少なくなります。この接続オプションを小さな値に設定すると、暴走クエリーの異常なリソース消費を防ぐことができます。
• SQL Anywhere には、さらに2つの追加接続オプションが用意されています。MAX_TEMP_SPACE と TEMP_SPACE_LIMIT_CHECK です。これらは、再帰クエリーが間違っている場合のカタストロフィックサーバー問題を避けるのに役立ちます。最初のオプションは、サーバーがTEMPファイルに無制限のスペースを使用するのを防ぎ、次のオプション TEMP_SPACE_LIMIT_CHECK は、テンポラリスペースの使用を接続毎に制限するサーバーガバナーのパラメーターです。

SQL Anywhere では、2つの特別なクエリー実行オペレーター Recursive Hash [Outer] Join と Recursive Nested-Loop [Outer] Join を使用して再帰クエリーを計算します。上記の再帰クエリーのグラフィカルなプランは下のようになります。

このプランでは、”seed” クエリーは再帰 UNION ALL オペレーター (RU) の左側にあります。RT は、再帰中間結果　”EmpsByManager”　を含む（仮想）再帰テーブルを意味します。JHR は、再帰ハッシュジョインオペレーターを意味します。

SQL Anywhere サーバー内のその他全てのメモリー集中型のオペレーターのように、JHR はクエリー実行時間にメモリーがとても少なくなるか、または JHR オペレーターがこの join instance のための入力の カーディナリティ が cheapで、nested-loop な実行戦略を保証すると決定した場合に選択できる低メモリー代替戦略 — 再帰 [outer] nested-loop join — を持っています。

join 実行戦略におけるこの変更は、on-the-flyで実行されます。

理解する

再帰 SQL クエリーの呼び出しに苦労しているのであれば、便利なテクニックとして、最初の再帰のインタラクションをハンドコードし、そこから、何の属性と結果が（仮想）再帰中間結果に追加される必要があるかを決定する方法があります。上の例では、最初のインタラクションは以下のようになります。

join する3つのローから、Employee テーブルとの join によって特定されるような 上層部の manager の（直属の managersのための）seed クエリーで以前に生成されたローの数のカウントを含む追加のローを UNION できるということがわかります。

再帰クエリーのさらなる例については、SQL Anywhere サーバー マニュアル　または　オンラインマニュアル DocCommentXchange をご参照ください。

過去のブログ記事より