Преобразование запросов

11.07.21

Разработка - Математика и алгоритмы

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

Два утверждения.

Мы все куда-то торопимся, поэтому кратко.

  1. Левое соединение с дополнительным условием в запросе SQL можно заменить внутренним соединением, если не используются функции null.
  2. Полное соединение в запросе SQL можно заменить объединением с группировкой, если поля группировки не содержат значений null.

Статья окончена, спасибо за внимание.

Пояснение.

  • Многие программисты используют эти преобразования запросов, но не задумываются об условиях применения.
  • Предполагаем, что поля таблиц СУБД не содержат null, это настройки по умолчанию:

MS https://docs.microsoft.com/ru-RU/sql/connect/ado-net/sql/handle-null-values?view=sql-server-2017

PG https://postgrespro.ru/docs/postgrespro/13/ddl-constraints#id-1.5.4.6.6

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

  • Функции null – например: (Аргумент) is null, (Аргумент)  is not null, isnull(Аргумент1, Аргумент2)

MS https://docs.microsoft.com/ru-ru/sql/t-sql/queries/is-null-transact-sql?view=sql-server-ver15

PG https://postgrespro.ru/docs/postgresql/9.6/functions-comparison

  • Два значения null никогда не равны между собой, однако если столбец группирования содержит значения NULL, они рассматриваются как равные и помещаются в одну группу.

MS https://docs.microsoft.com/ru-ru/sql/t-sql/queries/select-group-by-transact-sql?view=sql-server-ver15

 
 Пример для левого соединения
 
 Предыдущая версия статьи.

 

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4424    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7464    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8842    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7807    dusha0020    8    

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

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

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

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

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

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

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

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

А где можно почитать про преимущества и недостатки и для какой конкретной ситуации можно применять, а для какой не имеет смысла? Что бы для себя понять, есть ли практический смысл или нет.
9. vasilev2015 2686 15.03.18 15:37 Сейчас в теме
Вкратце, если применять левое соединение которое соответствует в плане Nested Loops, то при замене на объединение скорость увеличится в разы для достаточно большой выборки.
10. bulpi 215 16.03.18 12:59 Сейчас в теме
Все , понял, где я туплю. МАКСИМУМ(NULL) будет NULL. Возражения снял.
11. vasilev2015 2686 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 215 16.03.18 14:04 Сейчас в теме
Теперь следующий вопрос :
если применять левое соединение которое соответствует в плане Nested Loops, то при замене на объединение скорость увеличится в разы для достаточно большой выборки.


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

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

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