Использование EXCEPT в рекурсивном общем табличном выражении

Question

Почему следующий запрос возвращает бесконечные строки?Я бы ожидал EXCEPT предложение о прекращении рекурсии..

with cte as (
    select *
    from (
        values(1),(2),(3),(4),(5)
    ) v (a)
)
,r as (
    select a
    from cte
    where a in (1,2,3)
    union all
    select a
    from (
        select a
        from cte
        except
        select a
        from r
    ) x
)
select a
from r

Я столкнулся с этим, пытаясь ответить на вопрос о переполнении стека.

Answer 1

Видеть Ответ Мартина Смита Для получения информации о текущем статусе EXCEPT в рекурсивном CTE.

Чтобы объяснить, что вы видели и почему:

Я использую переменную таблицы здесь, чтобы прояснить различие между якорными значениями и рекурсивным элементом (она не меняет семантику).

DECLARE @V TABLE (a INTEGER NOT NULL)
INSERT  @V (a) VALUES (1),(2)
;
WITH rCTE AS 
(
    -- Anchor
    SELECT
        v.a
    FROM @V AS v

    UNION ALL

    -- Recursive
    SELECT
        x.a
    FROM
    (
        SELECT
            v2.a
        FROM @V AS v2

        EXCEPT

        SELECT
            r.a
        FROM rCTE AS r
    ) AS x
)
SELECT
    r2.a
FROM rCTE AS r2
OPTION (MAXRECURSION 0)

План запросов:

Выполнение начинается в корне плана (SELECT), а управление передает дерево в индексную катушку, конкатенацию, а затем на сканирование таблицы верхнего уровня.

Первый ряд от сканирования пропускает дерево и (а) хранится в катушке стека, и (б) возвращается клиенту. Какая строка сначала не определен, но, давайте предположим, что это строка со значением {1}, ради аргумента. Поэтому первая строка, чтобы появиться {1}.

Управление снова переходит к сканированию таблицы (оператор конкатенации потребляет все ряды от своего самого внешнего ввода перед открытием следующего). Сканирование излучает вторую строку (значение {2}), и это снова пропускает дерево, которое будет сохранено в стеке, и выводится с клиента. Клиент теперь получил последовательность {1}, {2}.

Приняв соглашение, где верхняя часть стека LIFO находится слева, стек теперь содержит {2, 1}. По мере того, как контроль снова переходит к сканированию таблицы, он не сообщает больше о строках, а управление возвращается обратно к оператору конкатенации, который открывает свой второй вход (ему нужна строка, чтобы передать катушку стека), и управление проходит во внутреннее соединение в первый раз.

Внутреннее соединение вызывает катушку таблицы на его внешнем входе, который считывает верхнюю строку из стека {2} и удаляет ее из рабочего стола. Стек теперь содержит {1}.

Получив строку на своем внешнем входе, внутреннее соединение передает управление своим внутренним входом в левое анти-семи-соединение (LASJ). Это запрашивает строку с его внешнего входа, передавая управление видом. Сортировка - это блокирующий итератор, поэтому он считывает все ряды из переменной таблицы и сортирует их восходящими (как это происходит).

Первая строка, излучаемая видом, является поэтому значение {1}. Внутренняя сторона LASJ возвращает текущее значение рекурсивного элемента (значение только что выскочило из стека), которое составляет {2}. Значения в LASJ являются {1} и {2}, так что {1} испускается, поскольку значения не совпадают.

Эта строка {1} протекает в дерево плана запросов на катушку индекса (стек), где он добавляется в стек, который теперь содержит {1, 1} и излучается клиенту. Клиент теперь получил последовательность {1}, {2}, {1}.

Контроль теперь возвращается к конкатенации, обратно вниз по внутренней стороне (он вернул ряд в прошлый раз, мог бы снова сделать), вниз через внутреннее соединение, к LASJ. Он снова читает свой внутренний ввод, получая значение {2} из сорта.

Рекурсивный член по -прежнему {2}, поэтому на этот раз LASJ находит {2} и {2}, что приводит к тому, что ни одна строка не испускается. Найдя больше строк на своем внутреннем входе (сортировка теперь вне рядов), управление переходит обратно в внутреннее соединение.

Внутреннее соединение считывает свой внешний вход, что приводит к тому, что значение {1} выскочило из стека {1, 1}, оставляя стек с помощью {1}. Процесс теперь повторяется со значением {2} из нового вызова табличного сканирования и сортировки, проходя тест LASJ и добавляется в стек, и передается клиенту, который теперь получил {1}, {2}, {1}, {2} ... и вокруг мы идем.

Мой любимый объяснение Степень, используемая в рекурсивных планах CTE, - это Крейг Фридман.

Answer 2

Описание рекурсивных CTE в BOL описывает семантику рекурсивного выполнения следующим образом:

1. Разделите выражение CTE на привязку и рекурсивные члены.
2. Запустите элементы привязки, создав первый вызов или базовый набор результатов (T0).
3. Запустите рекурсивный элемент(ы) с Ti в качестве входных данных и Ti+1 в качестве выходных данных.
4. Повторяйте шаг 3, пока не будет возвращен пустой набор.
5. Вернуть набор результатов.Это ОБЪЕДИНЕНИЕ ВСЕХ от T0 до Tn.

Обратите внимание, что вышеизложенное является логичный описание. Физический порядок операций может несколько отличаться, как показано здесь.

Применяя это к вашему CTE, я ожидаю бесконечного цикла со следующим шаблоном

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       4 | 5 |   |   |
|         3 |       1 | 2 | 3 |   |
|         4 |       4 | 5 |   |   |
|         5 |       1 | 2 | 3 |   |
+-----------+---------+---+---+---+ 

Потому что

select a
from cte
where a in (1,2,3)

является выражением привязки.Это явно возвращает 1,2,3 как T0

После этого рекурсивное выражение выполняется

select a
from cte
except
select a
from r

С 1,2,3 в качестве входных данных, которые дадут результат 4,5 как T1 затем подключив его обратно для следующего раунда рекурсии, вы вернетесь 1,2,3 и так до бесконечности.

Однако на самом деле это не то, что происходит.Это результаты первых 5 вызовов

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       1 | 2 | 4 | 5 |
|         3 |       1 | 2 | 3 | 4 |
|         4 |       1 | 2 | 3 | 5 |
|         5 |       1 | 2 | 3 | 4 |
+-----------+---------+---+---+---+

От использования OPTION (MAXRECURSION 1) и корректировка вверх с шагом 1 видно, что он входит в цикл, в котором каждый последующий уровень будет постоянно переключаться между выводом 1,2,3,4 и 1,2,3,5.

Как обсуждал @Quassnoi в этот пост в блоге.Картина наблюдаемых результатов такова, как если бы каждый вызов выполнял (1),(2),(3),(4),(5) EXCEPT (X) где X это последняя строка предыдущего вызова.

Редактировать: После прочтения Отличный ответ SQL Kiwi ясно и то, почему это происходит, и то, что это еще не вся история: в стеке все еще остается масса данных, которые никогда не могут быть обработаны.

Якорь излучает 1,2,3 клиенту Содержимое стека 3,2,1

3 выскочили из стопки, Содержимое стопки 2,1

LASJ возвращается 1,2,4,5, Содержимое стека 5,4,2,1,2,1

5 вырванных из стопки, Содержимое стопки 4,2,1,2,1

LASJ возвращается 1,2,3,4 Содержимое стека 4,3,2,1,5,4,2,1,2,1

4 выскочили из стопки, Содержимое стопки 3,2,1,5,4,2,1,2,1

LASJ возвращается 1,2,3,5 Содержимое стека 5,3,2,1,3,2,1,5,4,2,1,2,1

5 вырванных из стопки, Содержимое стопки 3,2,1,3,2,1,5,4,2,1,2,1

LASJ возвращается 1,2,3,4 Содержимое стека 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

Если вы попытаетесь заменить рекурсивный член логически эквивалентным (при отсутствии дубликатов/NULL) выражением

select a
from (
    select a
    from cte
    where a not in 
    (select a
    from r)
) x

Это недопустимо и приводит к ошибке «Рекурсивные ссылки не разрешены в подзапросах», так что, возможно, это упущение, которое EXCEPT в этом случае даже разрешено.

Добавление:Microsoft уже ответила на мое Подключить обратную связь как показано ниже

Джекпредположение верно:это должна была быть синтаксическая ошибка;рекурсивные ссылки действительно не должны быть разрешены в EXCEPT статьи.Мы планируем исправить эту ошибку в следующем выпуске службы.В В то же время, я бы посоветовал избегать рекурсивных ссылок в EXCEPTстатьи.

Ограничивая рекурсию EXCEPT мы следуем стандарту ANSI SQL, который включал в себя это ограничение с тех пор, как рекурсия была введен (кажется, в 1999 году).По этому вопросу нет единого мнения какой должна быть семантика для рекурсии EXCEPT (также называется "нестратифицированное отрицание") в декларативных языках, таких как SQL.В Кроме того, общеизвестно, что реализовать такие семантика эффективно (для баз данных разумного размера) в реляционной СУБД система.

И похоже, что окончательная реализация для баз данных была сделана в 2014 году. с уровнем совместимости 120 или выше.

Рекурсивные ссылки в предложении EXCEPT создают ошибку в соответствии со стандартом ANSI SQL.