Группирование связанных элементов в T-SQL. Часть II
Содержание:
1. Часть I;
2. Часть II (Вы читаете данный раздел);
3. Часть III.
Первое решение заключается в вычислении транзитивного закрытия нашего входного графа. При данном входном графе G (представленном таблицей T1) транзитивное закрытие G — новый направленный граф ТС, содержащий ребро для каждой пары узлов, между которыми находится цепь, прямая или транзитивная. На рисунке 2 показано транзитивное закрытие нашего тестового входного графа. Красные стрелки представляют направленные ребра транзитивного закрытия.
Рисунок 2. Транзитивное закрытие
Сначала будет представлено решение для подготовки транзитивного закрытия графа, хранимого в T1, а затем я покажу, как выполнить нашу задачу группирования связанных элементов на его основе. Приведенный в коде 5 программный код создает функцию TVF с несколькими инструкциями, именуемую T1TC, которая возвращает табличную переменную (@Т1ТС) с транзитивным закрытием T1.
Код 5. Создание функции T1TC
Сначала программный код записывает в @Т1ТС ребро для каждой прямой цепи между двумя узлами из Т1. Одна инструкция INSERT записывает все ребра, представляющие цепи id1->id2, а вторая инструкция INSERT записывает все ребра, представляющие цепи id2->id1. Затем начинается выполнение цикла, продолжающееся до тех пор, пока на последнем шаге не будет найдено по крайне мере одно новое ребро. На каждом проходе цикла используйте одну инструкцию INSERT, чтобы добавить к @Т1ТС новые ребра (х, z), где (х, у) присутствуют в @Т1ТС, а (у, z) присутствует в Т1, и другую инструкцию INSERT, чтобы добавить к @Т1ТС новые ребра (х, z), где (х, у) присутствует в @T1TC, a (z, у) присутствует в Т1. Эти две инструкции обеспечивают обход графа как в правом, так и в левом направлении для поиска новых транзитивных соединений: @T1TC.id1-> @T1TC.id2=T1.id1->T1.id2, поэтому @T1TC.id1->T1.id2, и @Т1TC.id1-> @T1TC.id2=T1.id2->T1.id1, поэтому @T1TC.id1->T1id1.
Выполните следующий программный код, чтобы протестировать функцию с малым набором тестовых данных:
Экран 3. Транзитивное закрытие графа в T1
Вы получите выходные данные как на экране 3, представляющие транзитивное закрытие графа в Т1.
Коде 6. Получение идентификатора группы
Для любого узла х транзитивное закрытие будет иметь ребро (х,) для любого другого узла, который является частью той же группы. К ней, конечно же, относится ребро (х,). Исключение — для х = транзитивное закрытие не имеет ребра (х, х). Поэтому чтобы получить идентификатор группы, нужно сгруппировать данные по id1 и возвратить id1 как идентификатор, а в качестве идентификатора группы — меньшее из значений id 1 и MIN (id2). Эта логика реализована в запросе в коде 6. Данный запрос формирует предпочтительные выходные данные, показанные на экране 4.
Экран 4. Вывод идентификатора группы
Рисунок 3. План для внутреннего запроса 1 Решения 1
Всегда приятно видеть, что ваше решение возвращает правильный результат. К сожалению, его производительность не очень высокая. При запуске решения после заполнения T1 одной группы со 100 строками (@minnumgroups = 1, @rowspergroup = 100) для его выполнения потребовалось 40 секунд на моем ноутбуке. Это крошечная таблица, почему же такая низкая производительность? Причиной неэффективности стало то обстоятельство, что программный код использует табличную переменную в функции TVF с несколькими инструкциями, и отсутствие векторов плотности и статистики распределения приводит к неудачным оценкам числа элементов и влечет за собой неоптимальные шаги. На рисунке 3 показано сравнение оценки с действительными планами (с использованием обозревателя планов SentryOne) на последней итерации внутреннего запроса 1 в теле цикла, а на рисунке 4 — для внутреннего запроса 2.
Рисунок 4. План для внутреннего запроса 2 Решения 1
Обратите внимание на неточности в оценке количества элементов в обоих случаях. Например, алгоритм вложенных циклов полезен как для соединения между @Т1ТС и Т1, так и для оператора anti-semi join, обрабатывающего предикат NOT EXISTS, только если задействовано очень малое количество строк. Это предполагается оценкой, но на практике дело обстоит иначе. Когда число строк довольно велико, алгоритм хеш-соединения оказывается гораздо более удачным в обоих случаях. Кроме того, обратите внимание, что во втором запросе цикл, выполняющий оператор anti-semi join, просматривает в целом десятки миллионов строк из @Т1ТС вследствие многочисленных повторных просмотров табличной переменной. Одним словом, решение на основе табличной переменной — неудачный вариант для этого алгоритма.
1. Часть I;
2.
3. Часть III.
Решение 1. Транзитивное закрытие с табличной переменной
Первое решение заключается в вычислении транзитивного закрытия нашего входного графа. При данном входном графе G (представленном таблицей T1) транзитивное закрытие G — новый направленный граф ТС, содержащий ребро для каждой пары узлов, между которыми находится цепь, прямая или транзитивная. На рисунке 2 показано транзитивное закрытие нашего тестового входного графа. Красные стрелки представляют направленные ребра транзитивного закрытия.
Рисунок 2. Транзитивное закрытие
Сначала будет представлено решение для подготовки транзитивного закрытия графа, хранимого в T1, а затем я покажу, как выполнить нашу задачу группирования связанных элементов на его основе. Приведенный в коде 5 программный код создает функцию TVF с несколькими инструкциями, именуемую T1TC, которая возвращает табличную переменную (@Т1ТС) с транзитивным закрытием T1.
Код 5. Создание функции T1TC
Сначала программный код записывает в @Т1ТС ребро для каждой прямой цепи между двумя узлами из Т1. Одна инструкция INSERT записывает все ребра, представляющие цепи id1->id2, а вторая инструкция INSERT записывает все ребра, представляющие цепи id2->id1. Затем начинается выполнение цикла, продолжающееся до тех пор, пока на последнем шаге не будет найдено по крайне мере одно новое ребро. На каждом проходе цикла используйте одну инструкцию INSERT, чтобы добавить к @Т1ТС новые ребра (х, z), где (х, у) присутствуют в @Т1ТС, а (у, z) присутствует в Т1, и другую инструкцию INSERT, чтобы добавить к @Т1ТС новые ребра (х, z), где (х, у) присутствует в @T1TC, a (z, у) присутствует в Т1. Эти две инструкции обеспечивают обход графа как в правом, так и в левом направлении для поиска новых транзитивных соединений: @T1TC.id1-> @T1TC.id2=T1.id1->T1.id2, поэтому @T1TC.id1->T1.id2, и @Т1TC.id1-> @T1TC.id2=T1.id2->T1.id1, поэтому @T1TC.id1->T1id1.
Выполните следующий программный код, чтобы протестировать функцию с малым набором тестовых данных:
SELECT id1, id2
FROM dbo.T1 TC ();Экран 3. Транзитивное закрытие графа в T1
Вы получите выходные данные как на экране 3, представляющие транзитивное закрытие графа в Т1.
Коде 6. Получение идентификатора группы
Для любого узла х транзитивное закрытие будет иметь ребро (х,) для любого другого узла, который является частью той же группы. К ней, конечно же, относится ребро (х,). Исключение — для х = транзитивное закрытие не имеет ребра (х, х). Поэтому чтобы получить идентификатор группы, нужно сгруппировать данные по id1 и возвратить id1 как идентификатор, а в качестве идентификатора группы — меньшее из значений id 1 и MIN (id2). Эта логика реализована в запросе в коде 6. Данный запрос формирует предпочтительные выходные данные, показанные на экране 4.
Экран 4. Вывод идентификатора группы
Рисунок 3. План для внутреннего запроса 1 Решения 1
Всегда приятно видеть, что ваше решение возвращает правильный результат. К сожалению, его производительность не очень высокая. При запуске решения после заполнения T1 одной группы со 100 строками (@minnumgroups = 1, @rowspergroup = 100) для его выполнения потребовалось 40 секунд на моем ноутбуке. Это крошечная таблица, почему же такая низкая производительность? Причиной неэффективности стало то обстоятельство, что программный код использует табличную переменную в функции TVF с несколькими инструкциями, и отсутствие векторов плотности и статистики распределения приводит к неудачным оценкам числа элементов и влечет за собой неоптимальные шаги. На рисунке 3 показано сравнение оценки с действительными планами (с использованием обозревателя планов SentryOne) на последней итерации внутреннего запроса 1 в теле цикла, а на рисунке 4 — для внутреннего запроса 2.
Рисунок 4. План для внутреннего запроса 2 Решения 1
Обратите внимание на неточности в оценке количества элементов в обоих случаях. Например, алгоритм вложенных циклов полезен как для соединения между @Т1ТС и Т1, так и для оператора anti-semi join, обрабатывающего предикат NOT EXISTS, только если задействовано очень малое количество строк. Это предполагается оценкой, но на практике дело обстоит иначе. Когда число строк довольно велико, алгоритм хеш-соединения оказывается гораздо более удачным в обоих случаях. Кроме того, обратите внимание, что во втором запросе цикл, выполняющий оператор anti-semi join, просматривает в целом десятки миллионов строк из @Т1ТС вследствие многочисленных повторных просмотров табличной переменной. Одним словом, решение на основе табличной переменной — неудачный вариант для этого алгоритма.
