Генерация простых чисел в запросе (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 Запросы Алгоритмы

См. также

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

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

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

10000 руб.

02.09.2020    124609    681    389    

732

Пропорциональное распределение в запросе с использованием АвтоНомерЗаписи()

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

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

11.04.2024    2036    andrey_sag    9    

25

Для чего используют конструкцию запроса "ГДЕ ЛОЖЬ" в СКД на примере конфигурации 1С:ERP

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

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

13.02.2024    5971    KawaNoNeko    23    

25

Набор-объект для СКД по тексту или запросу

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

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

1 стартмани

31.01.2024    2138    2    Yashazz    0    

30

Запрос 1С copilot

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

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

5 стартмани

15.01.2024    6593    31    mkalimulin    27    

51

PrintWizard: поддержка представлений ЗУП в конструкторе

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

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

14.12.2023    1872    vandalsvq    7    

29

Объектная модель запроса "Схема запроса" 2

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

Далеко уже не новый тип данных "Схема запроса". Статья о том, как использовать его "попроще". Примеры создания текста запроса с нуля и изменение имеющегося запроса.

06.12.2023    5596    user1923546    26    

46

Начните уже использовать хранилище запросов

HighLoad оптимизация Запросы

Очень немногие из тех, кто занимается поддержкой MS SQL, работают с хранилищем запросов. А ведь хранилище запросов – это очень удобный, мощный и, главное, бесплатный инструмент, позволяющий быстро найти и локализовать проблему производительности и потребления ресурсов запросами. В статье расскажем о том, как использовать хранилище запросов в MS SQL и какие плюсы и минусы у него есть.

11.10.2023    16555    skovpin_sa    14    

101
Комментарии
Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
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 ограничена количеством итераций.
Оставьте свое сообщение