Как рекурсивное коррелированное выражение ускоряет различные запросы?

Я нашел этот пост об ускорении отдельных запросов:

Сверхбыстрый DISTINCT с использованием рекурсивного CTE:

USE     tempdb;
GO
DROP    TABLE dbo.Test;
GO
CREATE  TABLE 
        dbo.Test 
        (
        data            INTEGER NOT NULL,
        );
GO
CREATE  CLUSTERED INDEX c ON dbo.Test (data);
GO
-- Lots of duplicated values
INSERT  dbo.Test WITH (TABLOCK)
        (data)
SELECT  TOP (5000000)
        ROW_NUMBER() OVER (ORDER BY (SELECT 0)) / 117329
FROM    master.sys.columns C1,
        master.sys.columns C2,
        master.sys.columns C3;
GO



SET     STATISTICS TIME ON;

-- 1591ms CPU
SELECT  DISTINCT 
        data
FROM    dbo.Test;

- 15 мс ЦП

WITH    RecursiveCTE
AS      (
        SELECT  data = MIN(T.data)
        FROM    dbo.Test T
        UNION   ALL
        SELECT  R.data
        FROM    (
                -- A cunning way to use TOP in the recursive part of a CTE Smile
                SELECT  T.data,
                        rn = ROW_NUMBER() OVER (ORDER BY T.data)
                FROM    dbo.Test T
                JOIN    RecursiveCTE R
                        ON  R.data < T.data
                ) R
        WHERE   R.rn = 1
        )
SELECT  *
FROM    RecursiveCTE
OPTION  (MAXRECURSION 0);

SET     STATISTICS TIME OFF;
GO
DROP    TABLE dbo.Test;

Рекурсивный CTE в 100 раз эффективнее :-) Этот тип ускорения был бы чрезвычайно полезен для моего текущего проекта, но я не уверен, в каких случаях этот подход выгоден.

Если честно: я не понимаю, почему это так сильно ускоряет запрос и почему база данных не может выполнить эту оптимизацию сама. Можете ли вы объяснить, как это работает и почему это так эффективно?

Редактировать: я вижу аналогичный эффект на sybase, поэтому этот подход не подходит только для sql-сервера.

Подвопрос: полезна ли рекурсивная CTE для других систем баз данных?

Ответы

Ответ 1

Пол Уайт подробно объяснил этот "трюк" в своем посте "Настройка производительности всего плана запросов" в разделе Поиск отличительных значений.

Почему база данных не может сама выполнить эту оптимизацию?

Является ли рекурсивный CTE полезным для других систем баз данных?

Оптимизатор не идеален и не реализует все возможные методы. Люди попросили Microsoft ее реализовать. См. Этот пункт Connect Внедрение индекса Skip Scan. Он был закрыт, так как Will not Fix, но это не значит, что в будущем он не будет рассмотрен. Другие СУБД могут это реализовать (элемент Connect указывает, что Oracle реализует эту оптимизацию). Если такая оптимизация реализована в СУБД, то этот "трюк" не нужен, и оптимизатор выбирает оптимальный метод вычисления результата на основе доступных статистических данных.

Я не понимаю, почему это ускоряет запрос.

Я не уверен, в каких случаях этот подход выгоден

Простой DISTINCT запрос сканирует весь индекс. "Сканирование" означает, что он считывает каждую страницу индекса с диска и агрегирует значения в памяти (или tempdb), чтобы получить список различных значений.

Если вы знаете, что в таблице много строк, но только несколько разных различных значений, то чтение всех этих повторяющихся значений является пустой тратой времени. Рекурсивный CTE заставляет сервер искать индекс для первого отдельного значения, затем искать индекс для второго значения и так далее. "Ищите" означает, что сервер использует двоичный поиск в индексе для поиска значения. Обычно для поиска требуется чтение только нескольких страниц с диска. "Индекс" - это сбалансированное дерево.

Если таблица имеет только несколько отдельных значений, она быстрее ищет несколько раз, чем чтение всех страниц индекса. С другой стороны, если есть много разных значений, тогда было бы быстрее читать все страницы последовательно, чем искать для каждого последовательного значения. Это должно дать вам представление о том, в каких случаях этот подход выгоден.

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

Есть вопрос, связанный с dba.se: Можно ли получить параллельный план поиска для отдельной/группы на?

Ответ 2

Заметная точка, когда выше script выполняется на моей машине.

Disctinct query = clustered scan - 94%

Рекурсивный запрос = кластерное сканирование - 14%

Это основная причина

Неактивный запрос

Время процессора = 920 мс, прошедшее время = 211 мс.

Рекурсивный запрос

Время процессора = 0 мс, прошедшее время = 64 мс.

В этом примере может быть рекурсивный вариант, кажется хорошим.

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

Поэтому вы не можете сказать: " Super-fast DISTINCT с использованием рекурсивного CTE:"