Генерация простых чисел в запросе (SQL) и сравнение производительности

09.01.22

Разработка - Запросы

Пишем запрос по генерацию последовательности простых чисел на языке запросов 1С и SQL.

Чтобы более качественно понимать, как работает механизм соединений, решил написать поиск простых чисел через запрос, используя классический алгоритм Решето Эратосфена с элементами оптимизации. Позже уже увидел в этой публикации подобные решения, однако они сегодня менее производительны (для 10не дождался вычислений). В новой версии платформы 8.3.20 в языке запросов появились новые функции возведения в степень/вычисление квадратного корня и округления до целого без лишних конструкций. Поэтому решение получается более простым и быстрым. Кроме того добавлено больше элементов оптимизации. Также приведена сравнительная характеристика по скорости вычисления для разных СУБД.

Публикация состоит из трех разделов:

  1. Краткое описание алгоритма
  2. Решение
  3. Скорость вычисления и сравнение производительности вычислений с двумя основными СУБД, файловым вариантом, чистым MSSQL и императивным кодом на 1С.

Простым числом называется такое число, которое больше единицы и без остатка делится только на единицу и самого себя. Наиболее простой вариант нахождения простых чисел - это брать последовательно каждое число и проверять его делимость на все предыдущие. Быстро приходим к выводу, что проверять все числа избыточно. Как минимум, нужно идти до половины (понятно, что при делении числа N на число Целое(N / 2) + k целового не получится), а если быть точнее, то делить будем только до квадратного из искомого числа. По одной из теорем наименьший положительный и отличный от единицы делитель составного числа a не превосходит его квадратный корень.

Запрос построен из двух частей: 

  1. Генерация чисел, которые будем проверять на простоту
  2. Вычисление, является ли число простым

В качестве параметра запроса передаем верхнюю границы последовательности.

Генерация чисел осуществляется классическим способом через декартово произведение. Но написано немного хитро, чтобы быстро работало при любых значениях параметра. Если не отсеивать ненужные объединения при мелком значении параметра, то будет затрачиваться много времени на генерацию последовательности (чтобы всегда десять миллионов чисел не генерировалось). Поэтому использую полное соединение по Истина. Если не указывать соединения, то результат выборки будет только тогда, когда у всех выбираемых таблиц есть хотя бы одно значение. При полном соединении по Истина всегда выберутся данные хотя бы с одной таблицы, если там что-то есть.
Добавляем +2 внутри первого запроса, где получаются числа, чтобы генерация началась с двойки, так как 1 - это не простое число. 
Далее отсекаем все числа, оканчивающиеся на четные цифры и кратные 5. Такие числа точно не будут являться простыми, нет смысла их рассматривать.
Не уверен, что здесь нужен индекс. Кажется, что он тут не срабатывает. Однако на скорость работы его наличия не влияет по тестам, так что оставил.
Генерируется максимум до 10чисел.

 
 Запрос 1. Генерация нужной числовой последовательности

Далее соединяем эту числовую последовательность саму с собой по условию <= от квадратного корня числа. В итоге каждому числу первой таблицы будет сопоставлено каждое число второй таблицы до квадратного корня.
При этом не будем рассматривать числа, кратные 2, 3, 5 или 7. Такая проверка в условии соединения будет выполняться быстрее, чем дальнейшее рассмотрение таких чисел. Выигрыш в скорости почти в 2 раза. 
Выражение N - M * ЦЕЛ(N / M) равносильно выражению N % M (это остаток от деления).
В условии ИМЕЮЩИЕ помещаем выражение, которое возвращает остаток от деления числа, которое мы выбираем, на числа второй таблицы. Если все числа поделились с остатком, то МИНИМУМ вернет число большее нуля.
В объединениях добавляем нерассмотренные простые числа, которые выпали на уровне условия соединения.

 
 Запрос 2. Генерация последовательности простых чисел

Также решил написать запрос на чистом SQL (используя T-SQL в MSSQL). Чтобы сравнить производительность запроса, написанного через 1С-овскую обертку и напрямую. Разница в производительность оказалось огромной. Для того, чтобы результат сравнения был релевантный, то сделал также вариант запроса без использования оператора "%". Так как оператор остатка от деления почему-то не завезли в язык запросов 1С.
Здесь, в T-SQL, созданный вручную индекс во временной таблице работает. Скорость выполнения с индексом выше почти в 1,5 раза.

 
 Запрос на T-SQL (без оператора "%" остатка от деления)
 
 Запрос на T-SQL (более быстрый, с использованием "%")

Далее представлена скорость вычислений в секундах для разных размеров последовательности и разных СУБД (Postgres и MSSQL), включая файловый вариант. Код для варианта с использованием императивного языка был использован из этой публикации.

N 100 103 104 105 106 107
1С+Файловый режим 0.006 0.02 0.22 5.07 125 3550 (59.2 мин)
1С+Postgres 0.532 0.52 0.63 2.72 50 1356 (22.6 мин)
1С+MSSQL 0.003 0.01 0.11 1.60 37 1009 (16.8 мин)
MSSQL без "%" 0.037 0.04 0.08 0.66 13 347 (5.8 мин)
MSSQL с "%" 0.009 0.02 0.07 0.54 12 309 (5 мин)
Императивный код 1С 0.004 0.01 0.09 1.00 10 112 (2 мин)


На графике наглядней видна разница в скорости вычислений для режимов работы с разными СУБД (здесь по горизонтали - размер последовательности, по вертикали - время выполнения в секундах).

Отдельно приведу график сравнения выполнения аналогичного кода на чистом MSSQL и через 1С-овскую обертку.

SQL Запросы Алгоритмы

См. также

Инструментарий разработчика Роли и права Запросы СКД Программист Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

10000 руб.

02.09.2020    136159    750    391    

779

Запросы СКД Программист Стажер Система компоновки данных Россия Бесплатно (free)

Часто при разработке отчетов в СКД возникает ситуация, когда не совсем понятно, почему отчет выводит не те данные, которые нужны, либо не выводит вовсе. Возникает потребность увидеть конечный запрос, который формирует СКД. Как это сделать, рассмотрим в этой статье.

15.05.2024    4582    implecs_team    6    

41

Запросы Программист Стажер Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Часто поступают задачи по произвольному распределению общих сумм. После распределения иногда пропадают копейки. Суть решения добавить АвтоНомерЗаписи() в ВТ распределения, и далее используя функции МАКСИМУМ или МИНИМУМ можем положить разницу копеек в первую или последнюю строку знаменателя распределения.

11.04.2024    2806    andrey_sag    10    

32

Запросы СКД Программист Стажер Платформа 1С v8.3 Запросы Система компоновки данных 1С:ERP Управление предприятием 2 Бесплатно (free)

В типовых конфигурациях разработчики компании 1С иногда используют в отчетах, построенных на СКД, такую конструкцию, как "ГДЕ ЛОЖЬ". Такая конструкция говорит о том, что данные в запросе не будут получены совсем. Для чего же нужен тогда запрос?

13.02.2024    6563    KawaNoNeko    23    

26

Запросы СКД Программист Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Абонемент ($m)

Есть список полей в виде текста, или запрос - закидываем в набор СКД.

1 стартмани

31.01.2024    2461    2    Yashazz    0    

33

Инструментарий разработчика Запросы Программист Стажер Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Бесплатно (free)

Пишем на человеческом языке, что нам надо, и получаем текст запроса на языке 1С. Используются большие языковые модели (LLM GPT) от OpenAI или Яндекс на выбор.

15.01.2024    7900    70    mkalimulin    32    

58

Инструментарий разработчика Запросы Программист Стажер Платформа 1С v8.3 Бесплатно (free)

Одной из интересных задач, стоящих в процессе разработки, была поддержка механизма представлений в ЗУП. Но не просто возможность исполнения запросов с ними. Основная проблема была в том, чтобы с ними было удобно работать, а именно: создавать, модифицировать и отлаживать. Кратко о том, что в итоге получилось...

14.12.2023    2176    vandalsvq    7    

29

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

Работа с запросом и СКД, Полная поддержка пакетных запросов, временных таблиц. Главное скорость отладки запроса и данных, а красота вторична.

1 стартмани

07.12.2023    3660    52    DrZombi    54    

21
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. Said-We 07.03.23 14:06 Сейчас в теме
Так генерировать последовательности проще - рекурсивный запрос от 0 до 9, далее сколько разрядов необходимо, столько и рисуй:

with vt_dec as
(sel ect
0 as a
uni on all
select
t.a+1 as a
fr om
vt_dec as t
wh ere
t.a+1 <=9
)
SEL ECT 100*t3.a + 10*t2.a + t1.a as aa fr om vt_dec as t1,vt_dec as t2,vt_dec as t3
order by aa
AtamanovYS; +1 Ответить
2. Said-We 07.03.23 16:55 Сейчас в теме
Решето Эратосфена в начале применил для первых нескольких натуральных чисел 2, 3, 5, 7.

Наглядно тут показано как:
https://habr.com/ru/post/468833/

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