0Pricing
SQL Interview Prep · レッスン

無限再帰を避ける

面接官が必ず確認する、循環検出、深さ制限、再帰ガードを学びます。

「無限再帰を避ける」はCoddyKit上の無料SQL Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはSQL Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 SQL Interview Prepコースには全4レッスンが含まれています。

質問の裏にある問い

再帰CTEを書いた後、鋭い面接官は「データにサイクルがあったらどうなりますか？」と尋ねます。これは、再帰が永遠に実行される可能性を理解しているか、そしてそれを防ぐ方法を知っているかを確認する質問です。

サイクルとは、階層が自分自身に戻ることです。たとえば、AがBに、BがAにレポートする状態です。素朴な再帰メンバーでは、この2人の間を無限に行き来してしまいます。

サイクルが発生する仕組み

ツリーは本来、非巡回であるはずですが、実際のデータは複雑です。誤った更新によって、社員が自分自身の間接的なマネージャーになることがあります。また、「ユーザーがユーザーをフォローする」のようなグラフは、本質的に巡回する可能性があります。

再帰メンバーがすでに訪問したノードに再び到達すると、そのノードをもう一度生成します。すると、その子ノードが再び起点となり、行がなくなることはありません。再帰は、あるステップが行を返さなくなったときにだけ停止するため、サイクルがあると常に行を返し続けます。

ガード1：深さの上限

最も簡単な安全策は、深さカウンターに上限を設け、再帰メンバーで制限することです。サイクルが存在していても、上限に達すれば再帰は停止します。

これは、正当な深いツリーまで制限してしまう大まかな方法ですが、すぐに使えて面接でも説明しやすい対策です。

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.depth < 50
)
SELECT * FROM org;

ガード2：訪問済みパス

より正確なガードでは、訪問済みノードのパスを記録し、そのパス上にすでに存在するノードには再び入らないようにします。IDを文字列（または配列）に蓄積し、再帰する前に含まれているかを確認します。

これにより、正当なツリーでは深さを制限せずに、サイクルだけを正確に停止できます。

WITH RECURSIVE org AS (
    SELECT id, name, manager_id,
           CAST(',' || id || ',' AS VARCHAR(2000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.path || e.id || ','
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.path NOT LIKE '%,' || e.id || ',%'
)
SELECT id, name, path FROM org;

パスチェックが機能する理由

条件path NOT LIKE '%,' || e.id || ',%'は、「子ノードのIDがパスにまだ含まれていない場合にだけ、このエッジをたどる」という意味です。カンマを区切り文字にすることで、ID 1がID 15の一部に含まれていると誤って一致することを防ぎます。

サイクルによってノードを再訪しようとすると、WHEREがその行を除外します。その結果、再帰メンバーは最終的に何も返さなくなり、再帰が正常に終了します。

ガード3：ネイティブのCYCLE句

最新のPostgres（14以降）とSQL標準には、パスチェックを自動化し、サイクルを検出してくれる組み込みのCYCLE句があります。エンジンが対応している場合、これが最もすっきりした解答です。

WITH RECURSIVE org AS (
    SELECT id, name, manager_id FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e JOIN org o ON e.manager_id = o.id
)
CYCLE id SET is_cycle USING cycle_path
SELECT id, name, is_cycle FROM org;

SQL ServerのMAXRECURSION

SQL Serverでは、再帰レベルのデフォルト上限が100に設定されています。サイクルや深いツリーがこの上限を超えると、クエリは無限に実行されるのではなく、エラーになります。これは暗黙の安全弁として機能します。

OPTION (MAXRECURSION n)で上限を引き上げたり解除したりできます。0は無制限を意味します。ただし、パスガードなしで上限を解除すると、サイクルのあるデータで無限ループが発生する危険が再び生じます。

-- Cap recursion at 200 levels in SQL Server
SELECT * FROM org
OPTION (MAXRECURSION 200);

サイクルの検出と防止

面接官は、次の2つの目的を区別することがあります。

  • 防止 — サイクルになっているエッジを暗黙にスキップして、クエリを完了させます（パスチェックのWHERE）。
  • 検出して報告 — サイクルの一部になっている行を明らかにし、データチームが不正なデータを修正できるようにします（CYCLE句のis_cycleフラグ）。

両方を理解し、それぞれを使うべき場面を判断できることが、シニアレベルの違いです。

パフォーマンス上の考慮事項

サイクルがなくても、再帰は高コストになることがあります。面接官が評価するポイントは次のとおりです。

  • 各反復の結合を高速にするため、結合列（たとえばmanager_id）にインデックスを作成します。
  • アンカーで早い段階に絞り込み、テーブル全体ではなく必要なサブツリーだけを起点にします。
  • SELECT *は避け、再帰に必要な列とdepth/pathだけを引き継ぎます。

安全なテンプレート

ガードを組み合わせて、プレッシャーのかかる状況でも再現できるテンプレートにします。深さの列を保険として使い、パスチェックを正確なガードとして使います。きれいなデータにはどちらかが過剰であっても、両方を示すことで厳密さを伝えられます。

WITH RECURSIVE walk AS (
    SELECT id, parent_id, 1 AS depth,
           CAST(',' || id || ',' AS VARCHAR(4000)) AS path
    FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, w.depth + 1,
           w.path || n.id || ','
    FROM nodes n JOIN walk w ON n.parent_id = w.id
    WHERE w.depth < 100
      AND w.path NOT LIKE '%,' || n.id || ',%'
)
SELECT id, depth FROM walk;

面接でよくある落とし穴

最後に、次の落とし穴を避けてください。

  • SQL Serverで他のガードなしにMAXRECURSIONを解除すると、無限ループの危険が再び生じます。
  • パス文字列の列を短く宣言すると、値が切り捨てられ、ガードが気づかないうちに壊れます。
  • カンマ区切りを使わずにIDを照合すると、ID 1がID 21の一部に含まれていると誤って一致します。
  • データは「そうあるはずだから」非巡回だと思い込まないでください。必ず確認しましょう。

確認問題

正当な深さを制限せずに、サイクルを正確に停止できるガードを選んでください。

まとめ

再帰CTEの解答では、必ず安全性にも触れる必要があります。

  • サイクルがあると再帰メンバーは空にならないため、再帰が停止しません。
  • 深さの上限は簡単な保険、訪問済みパスのチェックは正確なサイクル防止、CYCLE句は最新のエンジンで使えるネイティブな検出機能です。
  • SQL ServerのMAXRECURSION 100は暗黙の安全弁です。別のガードなしに解除しないでください。
  • パフォーマンスのため、結合列にインデックスを作成し、起点を狭く絞ります。

これで、再帰CTEの作成、走査、生成、安全対策を一通り実行できるようになりました。

よくある質問

「無限再帰を避ける」レッスンは無料ですか？

はい。「無限再帰を避ける」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、SQL Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 SQL Interview Prepコースには全4レッスンが含まれています。

「無限再帰を避ける」で何を学びますか？

面接官が必ず確認する、循環検出、深さ制限、再帰ガードを学びます。 ブラウザで直接実行するハンズオンコードでSQL Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

SQL Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのSQL Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「無限再帰を避ける」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このSQL Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのSQL Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. アンカー部と再帰部
  2. 組織図をたどる
  3. 数値系列と日付系列を生成する
  4. 無限再帰を避ける
← SQL Interview Prepに戻る