Теорема номер тринадцать

Программирование - Теория программирования

математическая индукция объединение полное соединение эквивалентные запросы

14
Использование математических методов для языка запросов.

Предисловие

Один из приемов оптимизации запросов - замена соединения на объединение. Например, в СУБД Postgres полное соединение может вызвать тормоза. Тем не менее, не будем обсуждать преимущества и недостатки такого приема - применение зависит от конкретной ситуации. Проблема в том, что не всегда очевидно, когда можно выполнить такое преобразование без изменения результата запроса. Работать на авось, заметать грязь под ковер - не наши методы )). Укажем условия, когда два запроса будут эквивалентны, то есть результаты запросов будут совпадать для всех наборов данных - замена будет возможна. Доказательство теоремы будет проведено методом математической индукции для множеств конечной меры. Алгоритмы полного соединения, объединения, группировки хотя и имеют машинную реализацию, но прозрачны для пользователя. Поэтому метод математической индукции вполне уместен. Думаю, аналогичный результат известен в курсе реляционной алгебры, но ссылку найти не могу. Буду благодарен, если кто покажет. Если найдете ошибку в доказательстве — буду благодарен вдвойне.

Определим переменные

ТаблицаА — источник данных (таблица), содержит колонки КлючА, ПолеА.

ТаблицаБ — источник данных (таблица), содержит колонки КлючБ, ПолеБ.

Запрос1 = Новый Запрос;
Запрос1.Текст =
"ВЫБРАТЬ
ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) КАК Ключ,
ТаблицаА.КлючА,
ТаблицаА.ПолеА,
ТаблицаБ.КлючБ,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА
ПОЛНОЕ СОЕДИНЕНИЕ ТаблицаБ КАК ТаблицаБ
ПО ТаблицаА.КлючА = ТаблицаБ.КлючБ";

////////////////////////////////////////////////////////////////////////

Запрос2 = Новый Запрос;
Запрос2.Текст =
"ВЫБРАТЬ
ВложеннаяТаблица2.Ключ,
МАКСИМУМ(ВложеннаяТаблица2.КлючА) КАК КлючА,
МАКСИМУМ(ВложеннаяТаблица2.ПолеА) КАК ПолеА,
МАКСИМУМ(ВложеннаяТаблица2.КлючБ) КАК КлючБ,
МАКСИМУМ(ВложеннаяТаблица2.ПолеБ) КАК ПолеБ
ИЗ
(ВЫБРАТЬ
ТаблицаА.КлючА КАК Ключ,
ТаблицаА.КлючА КАК КлючА,
NULL КАК КлючБ,
ТаблицаА.ПолеА КАК ПолеА,
NULL КАК ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаБ КАК ТаблицаБ) КАК ВложеннаяТаблица2

СГРУППИРОВАТЬ ПО
ВложеннаяТаблица2.Ключ";

Теорема

Пусть выполняются условия:

  • ТаблицаА не содержит повторений по полю КлючА
  • ТаблицаА не содержит в поле КлючА значений NULL
  • ТаблицаБ не содержит повторений по полю КлючБ
  • ТаблицаБ не содержит в поле КлючБ значений NULL

Тогда Запрос1 эквивалентен Запрос2. Результаты запросов совпадают для всех наборов данных.

Примечание 1

Колонки КлючА, ПолеА, КлючБ, ПолеБ могут быть ссылочного или примитивного типа. Для ключевых полей исключены типы по которым невозможна сортировка или соединение - например строка неограниченной длины.

Примечание 2

Если поля — числовые, то можно использовать агрегатную функцию суммы, вместо Null для пустых полей таких столбцов устанавливать 0. При этом надо помнить, что агрегатные функции Сумма, Максимум «игнорируют» поля типа Null, возвращая результат так, как будто полей Null нет, хотя (Число+Null ) IS Null.

Примечание 3

Колонки могут сами состоять из нескольких колонок, то есть теорема распространяется на источники данных с многими колонками: Ключ1А, Ключ2А, … КлючXА, Поле1А, Поле2А, … ПолеYА.

Примечание 4

Выражение ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) будет равно либо ТаблицаА.КлючА, при ТаблицаБ.КлючБ IS NULL, либо ТаблицаБ.КлючБ, при ТаблицаА.КлючА IS NULL, либо ТаблицаА.КлючА = ТаблицаБ.КлючБ - поскольку полное соединение происходит по условию равенства. То есть выражение ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) симметрично и совпадает с результатом группировки.

Следствие 1

Пример эквивалентных запросов для внутреннего соединения.

Запрос3 = Новый Запрос;
Запрос3.Текст =
"ВЫБРАТЬ
ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) КАК Ключ,
ТаблицаА.КлючА,
ТаблицаА.ПолеА,
ТаблицаБ.КлючБ,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТаблицаБ КАК ТаблицаБ
ПО ТаблицаА.КлючА = ТаблицаБ.КлючБ";

////////////////////////////////////////////////////////////////////////

Запрос4 = Новый Запрос;
Запрос4.Текст =
"ВЫБРАТЬ
ВложеннаяТаблица2.Ключ,
МАКСИМУМ(ВложеннаяТаблица2.КлючА) КАК КлючА,
МАКСИМУМ(ВложеннаяТаблица2.ПолеА) КАК ПолеА,
МАКСИМУМ(ВложеннаяТаблица2.КлючБ) КАК КлючБ,
МАКСИМУМ(ВложеннаяТаблица2.ПолеБ) КАК ПолеБ
ИЗ
(ВЫБРАТЬ
ТаблицаА.КлючА КАК Ключ,
ТаблицаА.КлючА КАК КлючА,
NULL КАК КлючБ,
ТаблицаА.ПолеА КАК ПолеА,
NULL КАК ПолеБ,
1 КАК ОграничительА,
0 КАК ОграничительБ
ИЗ
ТаблицаА КАК ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.ПолеБ,
0,
1
ИЗ
ТаблицаБ КАК ТаблицаБ) КАК ВложеннаяТаблица2

СГРУППИРОВАТЬ ПО
ВложеннаяТаблица2.Ключ

ИМЕЮЩИЕ
СУММА(ВложеннаяТаблица2.ОграничительА) > 0
И СУММА(ВложеннаяТаблица2.ОграничительБ) > 0";

КОНТРПример 1.

Воспроизведем ситуацию, когда условия теоремы НЕ выполняются — результаты запросов не совпадают.

ТаблицаА содержит две строки (Ключ1А, Поле1А), (Ключ1А, Поле2А)

ТаблицаБ содержит две строки (Ключ1Б, Поле1Б), (Ключ2Б, Поле2Б)

ВЫБРАТЬ
"Ключ1А" КАК КлючА,
"Поле1А" КАК ПолеА
ПОМЕСТИТЬ ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
"Ключ1А",
"Поле2А"
;
///////////////////////////////////////////////////////////

ВЫБРАТЬ
"Ключ1Б" КАК КлючБ,
"Поле1Б" КАК ПолеБ
ПОМЕСТИТЬ ТаблицаБ

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
"Ключ2Б",
"Поле2Б"

 

Результат Запрос1

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

NULL

NULL

Ключ1А

Ключ1А

Поле2А

NULL

NULL

Ключ1Б

NULL

NULL

Ключ1Б

Поле1Б

Ключ2Б

NULL

NULL

Ключ2Б

Поле2Б

 

Результат Запрос2

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле2А

NULL

NULL

Ключ1Б

NULL

NULL

Ключ1Б

Поле1Б

Ключ2Б

NULL

NULL

Ключ2Б

Поле2Б

 

КОНТРПример 2

Воспроизведем ситуацию, когда условия теоремы НЕ выполняются — результаты запросов не совпадают.

ТаблицаА содержит одну строку (NULL, Поле1А)

ТаблицаБ содержит одну строку (NULL, Поле1Б)

ВЫБРАТЬ
NULL КАК КлючА,
"Поле1А" КАК ПолеА
ПОМЕСТИТЬ ТаблицаА
;
///////////////////////////////////////////////////////

ВЫБРАТЬ
NULL КАК КлючБ,
"Поле1Б" КАК ПолеБ
ПОМЕСТИТЬ ТаблицаБ

 

Результат Запрос1

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

NULL

NULL

Поле1А

NULL

NULL

NULL

NULL

NULL

NULL

Поле1Б

 

Результат Запрос2

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

NULL

NULL

Поле1А

NULL

Поле1Б

 

Доказательство будем проводить методом математической индукции. На первом шаге проверим утверждение на минимальном числе строк таблиц ТаблицаА, ТаблицаБ. Второй шаг — предположим, что утверждение выполняется для таблиц ТаблицаА, ТаблицаБ в которых содержится X и Y строк соответственно. Третий шаг — используя предположение шага 2 докажем, что утверждение выполняется для таблиц ТаблицаА, ТаблицаБ в которых содержится (X+1) и Y строк соответственно. В случае, если условия симметричны относительно ТаблицаА, ТаблицаБ, на этом доказательство заканчивается. Это хорошо изученный, классический, но трудный для понимания метод.

Шаг первый.

Следует учитывать, что рассматриваемые операции симметричны относительно выборок, поэтому количество вариантов можно сократить.

Вариант 1.

Ключ1А <> Ключ1Б, Ключ2А <> Ключ2Б, Ключ1А <> Ключ2А, Ключ1Б <> Ключ2Б

ТаблицаА, содержит две строки (Ключ1А, Поле1А), (Ключ2А, Поле2А),

ТаблицаБ, содержит две строки (Ключ1Б, Поле1Б), (Ключ2Б, Поле2Б).

 

Результаты Запрос1, Запрос2 совпадают

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

NULL

NULL

Ключ1Б

NULL

NULL

Ключ1Б

Поле1Б

Ключ2А

Ключ2А

Поле2А

NULL

NULL

Ключ2Б

NULL

NULL

Ключ2Б

Поле2Б

Вариант 2.

Ключ1А = Ключ1Б, Ключ2А <> Ключ2Б, Ключ1А <> Ключ2А, Ключ1Б <> Ключ2Б

ТаблицаА, содержит две строки (Ключ1А, Поле1А), (Ключ2А, Поле2А),

ТаблицаБ, содержит две строки (Ключ1А, Поле1Б), (Ключ2Б, Поле2Б).

Результаты Запрос1, Запрос2 совпадают

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

Ключ1А

Поле1Б

Ключ2А

Ключ2А

Поле2А

NULL

NULL

Ключ2Б

NULL

NULL

Ключ2Б

Поле2Б

Мы показали, что запросы дают одинаковый результат при выполнении условий теоремы, если таблицы содержат 2 записи. Случай, когда записей меньше двух — рассмотреть несложно, будем этот случай считать очевидным.

Шаг второй.

Пусть теорема выполняется для таблиц ТаблицаА(X записей), ТаблицаБ (Y записей). ТаблицаА не содержит повторений по полю КлючА и ТаблицаБ не содержит повторений по полю КлючБ. Запрос1 и Запрос2 эквивалентны, то есть дают одинаковый результат на всех наборах данных.

 

ТаблицаА

КлючА

ПолеА

Ключ1А

Поле1А

...

КлючXА

ПолеXА

 

ТаблицаБ

КлючБ

ПолеБ

Ключ1Б

Поле1Б

...

КлючYБ

ПолеYБ

 

Поскольку для выборки порядок строк не важен, мысленно переместим строки внутри выборки так, чтобы образовалось три группы. При этом первые W значений ключевого поля совпадают: Ключ1А = Ключ1Б, … , КлючWА = КлючWБ. Для остальных значений ключевые поля — отличаются.

 

Результаты Запрос1, Запрос2 совпадают:

 

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

Ключ1Б

Поле1Б

КлючWА

КлючWА

ПолеWА

КлючWБ

ПолеWБ

Ключ(W+1)А

Ключ(W+1)А

Поле(W+1)А

NULL

NULL

КлючXА

КлючXА

ПолеXА

NULL

NULL

Ключ(W+1)Б

NULL

NULL

Ключ(W+1)Б

Поле(W+1)Б

КлючYБ

NULL

NULL

КлючYБ

ПолеYБ

Шаг третий.

Добавим в ТаблицаА еще одну строку Ключ(X+1)А, Значение(X+1)А. По условиям теоремы, ТаблицаА не содержит повторений по полю КлючА, то есть все значения поля различные.

Вариант 1.

Среди значений поля КлючБ нет ни одного, равного Ключ(X+1)А.

При расчете результата Запрос1 (Полное соединение) добавится еще одна строка.

 

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

Ключ1Б

Поле1Б

КлючWА

КлючWА

ПолеWА

КлючWБ

ПолеWБ

Ключ(W+1)А

Ключ(W+1)А

Поле(W+1)А

NULL

NULL

КлючXА

КлючXА

ПолеXА

NULL

NULL

Ключ(X+1)А

Ключ(X+1)А

Поле(X+1)А

NULL

NULL

Ключ(W+1)Б

NULL

NULL

Ключ(W+1)Б

Поле(W+1)Б

КлючYБ

NULL

NULL

КлючYБ

ПолеYБ

При расчете результата Запрос2 — строка добавится в ВложеннаяТаблица2 как Объединение, при группировке эта строка не сгруппируется ни с одной строкой по условиям выше — тоже будет дополнительная строка. Результаты Запрос1, Запрос2 совпадают.

Вариант 2.

В силу требований теоремы значения поля КлючБ различны между собою. Поэтому не может быть случая, когда несколько полей равно Ключ(X+1)А. Однако, одно из значений поля КлючБ может быть равно Ключ(X+1)А. Совпадают (W+1) значений ключевого поля. Запишем результат в таблицу, проверим Запрос1, Запрос2 опираясь на результаты второго шага.

Ключ

КлючА

ПолеА

КлючБ

ПолеБ

Ключ1А

Ключ1А

Поле1А

Ключ1Б

Поле1Б

КлючWА

КлючWА

ПолеWА

КлючWБ

ПолеWБ

Ключ(W+1)А

Ключ(W+1)А

Поле(W+1)А

Ключ(W+1)Б

Поле(W+1)Б

Ключ(W+2)А

Ключ(W+2)А

Поле(W+2)А

NULL

NULL

Ключ(X+1)А

Ключ(X+1)А

Поле(X+1)А

NULL

NULL

Ключ(W+2)Б

NULL

NULL

Ключ(W+2)Б

Поле(W+2)Б

КлючYБ

NULL

NULL

КлючYБ

ПолеYБ

Результаты Запрос1, Запрос2 совпадают. Что и требовалось доказать.

Надеюсь, что эта теорема позволит нам избежать ошибок при замене левых соединений на объединение и значит — сделать программирование лучше.

14

См. также

Специальные предложения

Вознаграждение за ответ
Показать полностью
Комментарии
Избранное Подписка Сортировка: Древо
1. bulpi 137 15.03.18 12:26 Сейчас в теме
Уважаемый, я ничего не понял. А я ведь мехмат заканчивал, хоть и давно. Зачем пытаться доказать теорему, которая явно не верна ? Результаты запросов 1 и 2 совпадают не всегда, даже при выполнении указанных условий. И Вы сами это показали в примерах. Чувствую, что я где-то туплю, но где ?
ipoloskov; starik-2005; +2 Ответить
2. vasilev2015 770 15.03.18 12:50 Сейчас в теме
Здравствуйте ! Примеры приведены корректно: в них условия теоремы НЕ выполняются - поэтому запросы не эквивалентны. Почему считаете, что теорема не верна ? Добавил символичное вознаграждение, чтобы Вам было интереснее.
alexei366; +1 Ответить
3. vasilev2015 770 15.03.18 14:30 Сейчас в теме
Коллеги, я вижу что не все понимают.

Извините за сухой язык изложения. Я по-другому не умею, правда.

Вместо слов "пример" поставил слова "КонтрПример" чтобы было понятнее.

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

Под это подведено математическое доказательство на уровне первого курса мехмата.

Добавил еще немного вознаграждения ))
4. TODD22 17 15.03.18 14:37 Сейчас в теме
Один из приемов оптимизации запросов - замена соединения на объединение.

А что оптимизируют таким способом? Скорость выполнения?
itriot11; +1 Ответить
5. vasilev2015 770 15.03.18 14:44 Сейчас в теме
(4) таким образом программисты 1С помогают СУБД выбрать оптимальный план запроса, а от этого выбора фундаментально зависит скорость работы запроса и блокировки, которые могут появляться вследствие работы запроса.
6. TODD22 17 15.03.18 15:07 Сейчас в теме
(5) А сравнительные тесты методов будут? Какой вариант быстрее работает в повседневных задачах на файловой, на SQL сервере.
7. vasilev2015 770 15.03.18 15:15 Сейчас в теме
(6)
Не будем обсуждать преимущества и недостатки такого приема - применение зависит от конкретной ситуации.

Для MS SQL сравнивать нужно в MS Profiler. Это отдельная тема.
8. TODD22 17 15.03.18 15:33 Сейчас в теме
(7) Да хотя бы простое сравнение. Без профайлера. Интересует какая реально будет разница, на одном и том же объёме данных. А так без цифр говорить об оптимизации. Чем то же её надо измерить, оптимизацию.
Не будем обсуждать преимущества и недостатки такого приема - применение зависит от конкретной ситуации.

А где можно почитать про преимущества и недостатки и для какой конкретной ситуации можно применять, а для какой не имеет смысла? Что бы для себя понять, есть ли практический смысл или нет.
9. vasilev2015 770 15.03.18 15:37 Сейчас в теме
Вкратце, если применять левое соединение которое соответствует в плане Nested Loops, то при замене на объединение скорость увеличится в разы для достаточно большой выборки.
10. bulpi 137 16.03.18 12:59 Сейчас в теме
Все , понял, где я туплю. МАКСИМУМ(NULL) будет NULL. Возражения снял.
11. vasilev2015 770 16.03.18 13:42 Сейчас в теме
(10) я сам долго шел к этой теореме. Сначала я задумался: почему вообще можно заменять соединение на объединение. Потом сообразил, что наборы должны быть уникальными по ключам соединения. Через несколько месяцев догадался, что можно использовать метод мат. индукции для доказательства. И еще через месяц - что нужно исключить NULL из-за его особенностей. Как написано https://technet.microsoft.com/ru-ru/library/ms191270%28v=sql.105%29.aspx
значения NULL всегда считаются равными для ключевых слов ORDER BY, GROUP BY и DISTINCT
хотя (NULL=NULL) всегда ложь.
12. bulpi 137 16.03.18 14:04 Сейчас в теме
Теперь следующий вопрос :
если применять левое соединение которое соответствует в плане Nested Loops, то при замене на объединение скорость увеличится в разы для достаточно большой выборки.


Это не вызывает возражений. Но ведь потом Вы берете группировку и функцию МАКСИМУМ. Это, по идее, должно сожрать весь выигрыш . А может, и нет. Тут нужны тесты!
13. vasilev2015 770 16.03.18 14:14 Сейчас в теме
(12) этот способ не я придумал. Это из программы подготовки к 1С:Эксперт. Но конечно безоглядно им пользоваться не стоит. Тесты никогда не помешают. Иначе бы операции "левое соединение" не придумали ))
14. bulpi 137 16.03.18 17:50 Сейчас в теме
А я вот не поленился, и протестировал.
Результаты ... хм... неоднозначны.
На 2 таблицы по 100 000 записей выигрыш примерно в 2 раза у объединения .
Взял 2 таблицы на 1 млн записей каждая с частичным пересечением ключей. В результате соединение дало 1.5 млн записей, а объединение (до группировки) - 2 млн записей. И вот эти 2 млн не поместились в физическую оперативную память, началось использование файла подкачки и вуаля! Проигрыш в 1.5 раза. Перевернул порядок тестов, получил все таки выигрыш в 30 %.
Так что идут они лесом с этой программой 1С:Эксперт
15. vasilev2015 770 16.03.18 21:10 Сейчас в теме
(14) Вы меня спровоцировали, нужно экспертов защищать )). Потестирую тож. Там должны быть условия специальные, например: Первый запрос - две (или более) виртуальные таблицы, обе с индексами, но при соединении должно быть nested loops (соединение циклами) - поэтому медленно. Второй запрос - таблицы объединяем, потом делаем группировки steam aggregate (один проход выборки, используется индекс). Требования по памяти одинаковые.
16. bulpi 137 17.03.18 13:48 Сейчас в теме
(15)
Я не использовал индексы. С индексами картина другая - выигрыш есть, но маленький, около 10% . Не верю , что "Требования по памяти одинаковые.". Похоже, тут закон рычага - выиграли в быстродействии, проиграли в памяти. Если ее хватает с запасом, то все хорошо. Если нет - внезапно проигрыш. Для любого значения ОП можно найти достаточное кол-во записей в таблицах такое, что этот эффект проявится.
vaskomain; +1 Ответить
19. IvSchekin 26.03.18 05:33 Сейчас в теме
(16) нет такого закона в оптимизации запросов как "выиграли в быстродействии, проиграли в памяти".
У запросов прямая зависимость времени выполнения как раз от необходимой памяти.
Если для запроса приходится сканить всю таблицу, то приходится и памяти больше использовать и по этому скорость выполнения растет.

Для скорости выполнения запросов, особенно при соединении таблиц самое важное это наличие индексов по полям по которым осуществляются связи и которые указаны в секции ГДЕ. Индексы увеличивают скорость в десятки разов на больших таблицах.
17. Hatson 108 26.03.18 00:01 Сейчас в теме
Не, Николай)) Я это лайкать не буду ))
24. vasilev2015 770 02.04.18 11:51 Сейчас в теме
(17) Ну вот, одумался. Поставил лайк. Я заметил.
18. IvSchekin 26.03.18 05:29 Сейчас в теме
(9) Можно пояснить фразу "скорость увеличится в разы для достаточно большой выборки".
Если выборка маленькая что скорость разве не в те же разы увеличится?

В относительных величинах всегда одинаково, а вот в абсолютный действительно будет заметно так в два раза меньше для 10 минутного запроса сильно отличается от уменьшения минутного запроса.
20. vasilev2015 770 26.03.18 09:08 Сейчас в теме
(18) Скорость увеличивается нелинейно в зависимости от размера выборки.
21. w3bstr 65 26.03.18 09:39 Сейчас в теме +5.1 $m
23. vasilev2015 770 02.04.18 10:23 Сейчас в теме
(21) Спасибо за участие, но sm вернул. Мне кажется, так справедливо. Статья получилась узкоспециальная, для широкой публики не подходящая.
22. ildarovich 6249 26.03.18 11:41 Сейчас в теме
Статья интересная, постановка вопроса необычная, есть пища для размышлений...
Оставьте свое сообщение