gifts2017

Ускорение запросов к СУБД при помощи горизонтального масштабирования

Опубликовал Дмитрий Дудин (dmurk) в раздел Администрирование - Оптимизация БД (HighLoad)

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

Стандартные методы оптимизации запросов

Стандартная методика оптимизации запросов предлагает:

  • Производить для обрабатываемой матрицы индексированную выборку
  • Уменьшать затраты на выборку путем наложения предварительных фильтров.

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

В то же время перестройка индексов под нужды конкретного запроса зачастую ведет к последствиям в виде снижения производительности для всего решения в целом, либо требует серьезных затрат на проектирование новой модели данных. Как следствие, руководители отделов автоматизации и фирм-франчайзи могут напрямую запрещать внесение изменений в модель данных.

Однако помимо стандартных методов существуют еще и различные способы алгоритмической оптимизации запросов. Правда, их в среде 1С можно наблюдать достаточно редко, поскольку многие программисты пришли в 1С из смежных отраслей, не имея за плечами глубокой подготовки в области программирования. Поэтому они избегают сложных задач, в том числе и по экономическим соображениям, потому что сложно найти клиента, который бы оплачивал практику отработки экспериментальных решений без гарантии конечного результата.

Недостатки стандартных инструментов многопоточной обработки при их использовании в 1С

На сегодняшний день развитие платформы 1С направлено на обработку вычислительной нагрузки сервером приложений. Такой подход объясняется тем, что он удешевляет разработку кода, позволяет не нанимать дорогостоящих специалистов и делает решение максимально доступным широкому кругу пользователей и программистов. В результате этого подхода, в частности, родились всем известные надстройки над языком: «Построитель отчета» и «СКД». Однако, как мы видим, такое распределение ролей приводит к тому, что сервер приложений загружен, а SQL-сервер простаивает.

Кроме этого, хочется отметить, что инструменты многопоточного исполнения на данный момент практически не затронуты вниманием разработчиков 1С:

  • Например, мы часто сталкиваемся с тем, что многопоточная обработка запросов на уровне сервера приложений предъявляет высокие требования к вычислительным ресурсам и пропускной способности памяти, а это ставит под угрозу готовность СУБД к выполнению тысяч микрозапросов остальных пользователей. В данном случае, концепция максимальной доступности приложения вступает в конфликт с концепцией выделения максимальных ресурсов на решение одной задачи. Исключительным решением этого конфликта видится дальнейшее развитие функций кластера 1С, выделение дополнительных ролей серверов в кластере, когда отдельно назначаются высокопроизводительные серверы для тяжелых запросов, и отдельные серверы – для поддержки текущей нагрузки в кластере.
  • Конечно, у 1С существует решение и для массовых вычислений. Это – выделение экземпляра фоновых заданий. Но практика его использования показывает некоторые минусы:
    • В частности, запуск вычислений дает гарантированный возврат результата только при применении дополнительного регистра сведений, который будет эти результаты собирать.
    • А также необходима специальная процедура, которая будет проверять готовность этих фоновых заданий, синхронизировать их результаты и размещать их в этот регистр сведений. Таким образом, разрешение конфликтов переносится на уровень СУБД.
  • Есть еще одна сложность, связанная с тем, что в платформе 1С существует ошибка, связанная с самоидентификацией регламентных заданий, запускаемых автоматически (например, 20 штук запустившихся в одну секунду заданий не имеют назначенного им уникального идентификатора). Это не позволяет полноценно программировать стек запуска фоновых заданий для его выборки, поскольку вызываемая для него серверная процедура не получает во входящих параметрах уникальный идентификатор собственного экземпляра. Здесь очень не помешал бы дополнительный объект 1С, который позволил централизованно помещать задания в стек, обрабатывать и возвращать результаты.

Обзорно об APDEX

Если процитировать «Настольную книгу 1С: Эксперт по технологическим вопросам», то там написано: «Фирма 1С считает, что удобной и корректной является методика APDEX». Но многие согласятся с тем, что при расчете по методике APDEXпроизводительность решений оценивается исключительно по результатам распределения запросов внутри мягкого и жесткого пределов. Получается, что, согласно данной методике, запросы, которые выполняются достаточно редко, не оказывают влияния на итоговый показатель даже тогда, когда их выполнение вызывает сверхнормативную нагрузку и требует значительного времени.

Но такие запросы, естественно, будут оказывать негативное влияние на работу системы, и мы в любом случае должны научиться работать с ними.

Необходимость разделения понятий многопользовательской работы и монопольной обработки данных

В процессе своей работы отделы автоматизации регулярно сталкиваются с проблемой разделения рабочего времени серверов между живыми пользователями и регулярной сервисной обработкой данных. На оптимизацию ежедневной обработки данных может тратиться годичный бюджет отдела с итоговым результатом в 30% прироста производительности. Но одновременно с этим вычислительное время сервера СУБД показывает простой. Подобный дисбаланс нагрузки между сервером 1С:Предприятие и сервером СУБД является чем-то привычным только вследствие недостаточных знаний большинства программистов в области низкоуровневого программирования и настройки СУБД SQL.

Критичность малого времени выполнения сервисных процедур

Представьте себе, каким кошмаром является обслуживание предприятия, выполняющего отгрузку грузовика каждые 15 минут в течение недели. На все монопольные действия с 1С это предприятие предоставляет время только в воскресенье с 1:00 ночи до 8:00 утра, а это накладывает весьма специфичные требования к производительности сервисных обработок. В этом случае использование многоядерных серверов на 100% их возможностей позволило бы значительно снизить критичность выделяемого рабочего времени.

Применение методики горизонтального масштабирования для оптимизации обработки «Поиск и замена дублей»

В качестве возможного применения методики горизонтального масштабирования мы рассмотрим интегрированную во множество типовых решений обработку «Поиск и замена дублей». Практика показывает, что практически на всех проектах очень быстро возникает потребность в этой обработке. И проблема даже не в низком опыте или в слабости команды внедрения.Дело в том, что большинство проектов запускается как замена уже существующему программному обеспечению, дальнейшая эксплуатация которого невозможна вследствие изменения условий ведения бизнеса, либо в случае перехвата «проблемного» проекта, в котором долгое время велась работа по наполнению данными. Бесконтрольность такого наполнения приводит к однозначной необходимости устранения дублей в многочисленных справочниках.

Оценка порядка матрицы при широкой базе.

В качестве базы для практического примера возьмем проект, на котором в результате ошибки разработчиков система долгое время автоматически генерировала дубли справочника «Статусы заказов» к документу «Заказ покупателя». Оценка выборки показала, что два вида состояний в справочнике были продублированы в количестве 139 тысяч элементов.

Поскольку стандартная обработка замены дублей делает запрос к СУБД по неравенству ссылки, то сложность задачи в данном случае можно выразить в виде квадратной матрицы, которая сводится к 19 миллиардам сравнений на SQL-сервере.

При рассмотрении запроса была выявлена слабость исходного алгоритма в том месте, где стандартная обработка «Поиск и замена дублей» выполняет сравнение Т1.Ссылка<>Т2.Ссылка. Это ужасное сравнение, вызывающее падение общей алгоритмической производительности.

Снижение порядка матрицы

Однако если учесть, что ссылка в таблице справочника является индексом, мы можем произвести быструю упорядоченную выборку любой части таблицы запросом вида «ВЫБРАТЬ ПЕРВЫЕ 1000». Например, как показано на слайде, мы можем выбрать первые 1000 из последних 42000. То есть - имеем доступ к любой части таблицы, которую нам необходимо сравнивать с другими элементами.

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

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

При этом формула сложности алгоритма трансформируется из квадратичной (N2) в квадратичную с уменьшенным порядком, кратно количеству выделенных секций (это количество мы обозначим литерой M).

Таким образом, отношение между начальной и конечной сложностью алгоритма будет равно числу выделенных секций (М).

На практике, если мы разделим первоначальную таблицу на секции, которые помещаются в память SQL-сервера, оптимизатор SQL каждое уникальное сравнение внутри секции будет выполнять по упрощенной схеме, обрабатывая только половину значений, иформируя вместо квадратичной матрицы треугольную – это дает дополнительный двукратный выигрыш по времени.

Чтение секции в терминах SQL-процесса INDEXSCAN

В итоге элементом результирующего запроса является секция, для образования которой производится индексированное сканирование, и завершает процесс обработки секции также индексированное сканирование. При этом мы должны понимать, что:

  • Применение данной алгоритмической оптимизации накладывает сопутствующие издержки на сканирование индекса, причем затраты на это тем значительнее, чем короче выборка.
  • Сами по себе издержки на UNION тоже весьма велики, соответственно, чтобы это имело смысл, вычислительная нагрузка должна быть серьезной. И если у вас, например, размер выборки составляет около полутора тысяч, разбивать ее на потоки смысла нет.
  • Кроме этого, мы несем издержки на финализацию результата, так как каждая локальная секция вернет свой список дублей, который может частично пересекаться с результатами других секций.

Расчет эффективности применения алгоритмической оптимизации

Оранжевая линия на этом слайде – это нагрузка SQL-сервера при стандартном сравнении, она небольшая, загружено только одно ядро из восьми на сервере.

А вот так выглядит нагрузка, когда мы запускаем оптимизированное сравнение. Падение загрузки SQL-сервера означает, что он применяет треугольную оптимизацию, постепенно уменьшая количество элементов в строке.

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

Здесь показано сравнение времени выполнения для количества секций, допустим, равного 28. Как вы видите, мы имеем при этом 56-кратный прирост:

  • Двойной прирост мы получаем за счет треугольных матриц;
  • И 28-кратный за счет разделения исходной таблицы на 28 частей.

С учетом небольшой погрешности выигрыш во времени кратен расчетному порядку = .

Здесь показано графическое сравнение расчетного времени выполнения (основанного на приведенных математических формулах) с фактическими замерами.

Практическое время выполнения показало, что стандартный и оптимизированный поиск соотносятся как 12600 / 220 = 57,(27), что на 2,27% выше расчетного показателя.

Расхождение в 2,27 % – это влияние тех самых издержек на финализацию результатов по объединению отдельных микрозапросов.

Особенности методики горизонтального масштабирования

Хочу отметить, что для вычисления количества планируемых потоков в запросе у меня была написана специальная функция, которая оценивала объем памяти на сервере, количество ядер, операционную систему, запущен или нет терминальный сервер и сколько ему надо потоков. А потом рассчитывала для оставшегося количества свободных ядер, сколько можно запустить цепочек и насколько параллельно их можно запускать.

Применение методики горизонтального масштабирования в разных условиях

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

Рекомендации по многопоточной обработке данных

Если обратиться к документации на СУБД MSSQL, то мы увидим, что Microsoft выделяет два условия, влияющие на принятие решения о параллельном выполнении плана запросов. Это доступность памяти и уникальность источников данных.

  • Доступность памяти. С этим все понятно – память у нас дешевая, мы можем для сервера выделить и 500 Гб.
  • И уникальность источников данных. В данном случае мы должны обеспечить построчную непересекающуюся выборку из таблиц. При построчном делении таблиц с заранее заданным количеством ссылок необходимо следить за тем, что:
    • Во-первых, упорядоченная выборка должна покрывать всю таблицу, чтобы мы не упустили какую-то строку;
    • И во-вторых, эта выборка не должна быть избыточна, потому что в этом случае оптимизатор SQL-сервера посчитает вложенные запросы недостаточно разрешенными для того, чтобы запустить их на параллельное выполнение.

Описанная мною методика заключается в том, что вы формируете секции на уровне запроса в 1С за счет применения виртуальных таблиц и вложенных запросов. И для того, чтобы эти «секции» выполнились в разных потоках, ваша задача – сделать так, чтобы оптимизатор не посчитал их конфликтующими.

Методика является поводом для дальнейших исследований, поскольку надо понимать, что при включенном на сервере параллелизме любая выборка, содержащая конструкцию ОБЪЕДИНИТЬ ВСЕ, может быть запущена на параллельное выполнение в соответствии с тем количеством ядер, которое настроено в свойствах SQL-сервера. И тут надо быть очень аккуратными, потому что если у вас на одном аппаратном узле находятся и RDP-клиенты, и сервер приложений 1С, и SQL-сервер,  то в результате обработки какого-то «тяжелого» запроса SQL-сервер может «убить» всех остальных.

******************

Данная статья написана по итогам доклада, прочитанного на конференции INFOSTART EVENT 2015 CONNECTION 15-17 октября 2015 года.

Приглашаем вас на новую конференцию INFOSTART EVENT 2016 DEVELOPER.

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Евгений Ю. (Ganjubas) 13.07.16 22:25
А где можно ознакомиться с практическими примерами данной методики? И есть ли более развернутый пример с оптимизацией кода (в т.ч. запроса) обработки "Поиск и замена дублей" ?
2. Игорь Пашутин (Alien_job) 14.07.16 06:52
На каком основании вы делаете допущение что все ссылки одной секции всегда уникальны по отношению к ссылкам других секций? Если не обосновать этот момент то после применения "оптимизированного" алгоритма придется вновь вызывать нормальный
3. Дмитрий Дудин (dmurk) 14.07.16 10:35
(2) Alien_job, когда вы выбираете первую тысячу записей, в ней не будет ссылок из второй тысячи записей ))
5. ValeriTim (ValeriTim) 14.07.16 11:01
(2) Alien_job, Ну как бы выбирает из одного индексированного источника ...
6. ValeriTim (ValeriTim) 14.07.16 11:05
А вообще не до конца понятно как же оптимизиорован запрос ... конечный результат нужно было в статью ... и с кодом
7. Сергей (ildarovich) 14.07.16 23:25
Что я понял: в запросе можно
1) поделить исходную таблицу на секции приемом "ВЫБРАТЬ ПЕРВЫЕ 100 Х ИЗ (ВЫБРАТЬ ПОСЛЕДНИЕ 1000 Х)",
2) обработать секции отдельными подзапросами,
3) а затем собрать результат юнионами.
Можно надеяться, что при этом СУБД использует параллелизм и будет быстрее.
Что я не понял:
Зачем нужен запрос:
ВЫБРАТЬ РАЗЛИЧНЫЕ
  Т1.НазначениеСостояния КАК ЗначениеРеквизита
  ИЗ
    Справочник.НазначениеСостояния КАК Т1 
      ВНУТРЕННЕЕ СОЕДИНЕНИЕ Справочник.НазначениеСостояния КАК Т2
        ПО T1.НазначениеСостояния = Т2.НазначениеСостояния И 
          Т1.Ссылка <> Т2.Ссылка
...Показать Скрыть

Если та же задача решается запросом:
ВЫБРАТЬ
  НазначениеСостояния
    ИЗ Справочник.НазначениеСостояния
СГРУППИРОВАТЬ ПО
  НазначениеСостояния
ИМЕЮЩИЕ КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Ссылка) > 1
...Показать Скрыть
gadjik; soulsteps; i_lo; BigB; bulpi; starik-2005; v3rter; h00k; +8 Ответить 4
8. Игорь Пашутин (Alien_job) 15.07.16 06:56
(3) dmurk, Хм.. я имел ввиду другое. Вы же дубли удаляете - уникальность ПО T1.НазначениеСостояния = Т2.НазначениеСостояния. У вас в результате оптимизированной обработки в каждой выбранной секции назначения состояния будут разными. Но после объединения результатов итоговая таблица будет полна "дублей" ПО T1.НазначениеСостояния = Т2.НазначениеСостояния примерно по 28 на каждое назначение состояния
9. Эстер Коган (e.kogan) 15.07.16 10:22
Очень хочется поставить сразу много плюсов за идею.
10. Руслан Хитров (Sheff) 15.07.16 12:18
11. Игорь Пашутин (Alien_job) 15.07.16 12:48
Некорректно сравнивать время работы нормального и "оптимизорованного" подхода т.к. результат разный.
12. Роберт В е р т и н с к и й (v3rter) 15.07.16 13:03
Длиннотекст. Суть, видимо в "если мы разделим первоначальную таблицу на секции, которые помещаются в память SQL-сервера, оптимизатор SQL каждое уникальное сравнение внутри секции будет выполнять по упрощенной схеме". И непонятно, будет ли выигрыш на алгоритмах с линейной сложностью.
13. Sergey Andreev (starik-2005) 15.07.16 13:32
Суть статьи в том, чтобы программисты использовали многопоточность. Это однозначный плюс. Минус в том, что идиотский алгоритм поиска дублей оставили идиотским и не смогли найти решения, которое бы вместо поиска дублей сравнивало не все со всем, а только с правильным. Для 139к Х 2 состояния нужно всего лишь 139к Х 2 сравнения с правильными значениями, которыми и будут заменены все остальные. Для этого достаточно выбрать различные по наименованию ((если у нас наименование является определителем уникальности) - в итоге будет 2 значения, потом выбрать максимумы или минимумы ссылок - без разницы - с данными наименованиям и считать их верными. Дальше найти все неверные и заменить. Никаких 18ккк сравнений не нужно. И это уже показывает "силу" команды внедрятелей, которые дальше совершенно правильных мыслей, которые можно было вычитать даже в моей статье о многопоточности, где я говорил о наличии мощностей на серверах 1С и SQL, которые можно и нужно утилизировать, не пошли. Алгоритмическое мышление - это то, что неприсуще многим специалистам 1С, но ведь надо как-то самосовершенствоваться, учиться, развиваться...
14. Дмитрий Дудин (dmurk) 15.07.16 14:14
(8) Alien_job, именно так. Но сложность задачи уже уменьшена
15. Дмитрий Дудин (dmurk) 15.07.16 14:17
(6) ValeriTim, Боюсь, формат доклада для аудитории не подразумевал многостраничных текстов. Весь проект можно скачать: http://www.dudin.by/Technodemo.zip
16. Дмитрий Дудин (dmurk) 15.07.16 14:18
(12) v3rter, идея комплексная, не упрощайте
17. Дмитрий Дудин (dmurk) 15.07.16 14:19
(7) ildarovich, первая часть кода - написана разработчиками 1С. Действительно, и зачем так писать? )))
18. Дмитрий Дудин (dmurk) 15.07.16 14:21
(7) ildarovich, по второй части кода рекомендую скачать проект и попробовать применить ваш вариант кода
19. Дмитрий Дудин (dmurk) 15.07.16 14:25
(13) starik-2005, вы описываете нерабочий алгоритм. По ВЫБРАТЬ РАЗЛИЧНЫЕ вы получите ПЯТЬ наименований. И что? ))))
20. Игорь Пашутин (Alien_job) 15.07.16 14:27
(14) dmurk, Конкретно для ваших данных (тысячи дублей одного и того же) такой подход уменьшит сложность, но если дубли распределены равномерно (по 5 дублей на каждое НазначениеСостояния ) то такой подход ничего не даст
21. Дмитрий Дудин (dmurk) 15.07.16 14:28
(13) starik-2005, применяя МАКСИМУМ или МИНИМУМ ссылок вы можете получить более одной записи в таблице. В случаях когда ссылки получены из разных узлов РИБ максимум и минимум возвращает количество строк идентичное количеству узлов исходной таблицы. Глюк-с платформы, однако, все вопросы разработчикам...
22. Дмитрий Дудин (dmurk) 15.07.16 14:29
23. Дмитрий Дудин (dmurk) 15.07.16 14:30
(20) Alien_job, хотя, можно сгенерировать и проверить ))
24. Сергей (ildarovich) 15.07.16 14:32
(18) dmurk, скачать проект - это как? и зачем это мне?
Меня такой ответ категорически не устраивает. Да и ссылка (17) на разработчиков 1С тоже не в кассу. На то мы и внедренцы, чтобы кастомизировать решения на всякие частные случаи типа 139 тысяч дублей.
25. bulpi bulpi (bulpi) 15.07.16 14:35
Криворукость предыдущей команды программистов попытались исправить чуть менее криворукие. Получилась красивая диаграмка.
26. Роберт В е р т и н с к и й (v3rter) 15.07.16 14:36
То есть пока получается эмпирическая оптимизация запроса разбивкой по группам строк и, исходя из размера таблицы, количество процессоров, объем выделенной SQL памяти, предложить относительно оптимальную разбивку не получится?
27. bulpi bulpi (bulpi) 15.07.16 14:36
П.С.
Читайте ildarovich , кланяйтесь, и благодарите.
28. Сергей (ildarovich) 15.07.16 14:37
+(24) Кстати, по ссылке из (15) вместо проекта - сообщение
404 - файл или каталог не найден.
Запрашиваемый ресурс перемещен, переименован либо временно недоступен.
29. Игорь Пашутин (Alien_job) 15.07.16 14:40
(28) ildarovich, на 10-й раз загрузка пошла. Если постараетесь, возможно получится скачать
30. Сергей (ildarovich) 15.07.16 14:42
(27) bulpi, спасибо на добром слове, но вот кланяться точно не нужно. Идеи должны проходить апробацию, строго критиковаться, без оглядки на авторитет. Иначе большой риск допустить ошибку, которая надолго останется в коде и будет портить жизнь нам и нашим клиентам.
h00k; roofless; starik-2005; +3 Ответить
31. Дмитрий Дудин (dmurk) 16.07.16 11:20
32. Дмитрий Дудин (dmurk) 16.07.16 11:25
(25) bulpi, видимо Ваш гений программирования не имеет желания публиковать свой единственной ровный вариант решения этой проблемы. Зачем что-то обсуждать, если можно обгадить? ))
33. Sergey Andreev (starik-2005) 16.07.16 14:35
(21) dmurk, минимум или максимум возвращают ссылку, которая в SQL - суть число. Какие-то отсылы к РИБ тут совершенно неуместны, ибо это число для разных узлов в принципе одинаково, либо это разные ссылки. И даже если "ВЫБРАТЬ РАЗЛИЧНЫЕ Наименование ИЗ Справочник.Статусы" дает нам пять значений - это не повод сравнивать все со всем, ибо в статье описана четкая задача замены дублей ссылок. Тут не нужны 18ккк сравнений если хоть немного подумать мозгом, но, как я понял, авторы мозгом думать не желают.
34. Дмитрий Дудин (dmurk) 17.07.16 13:33
(33) starik-2005, вы имеете ввиду такое решение?
"ВЫБРАТЬ
| СостоянияСогласования.НазначениеСостояния,
| МИНИМУМ(СостоянияСогласования2.Ссылка) КАК СсылкаМин
|ИЗ
| Справочник.СостоянияСогласования КАК СостоянияСогласования
| ЛЕВОЕ СОЕДИНЕНИЕ Справочник.СостоянияСогласования КАК СостоянияСогласования2
| ПО СостоянияСогласования.НазначениеСостояния = СостоянияСогласования2.НазначениеСостояния
|
|СГРУППИРОВАТЬ ПО
| СостоянияСогласования.НазначениеСостояния
|
|ИМЕЮЩИЕ
| КОЛИЧЕСТВО(РАЗЛИЧНЫЕ СостоянияСогласования2.Ссылка) > 1";
35. Дмитрий Дудин (dmurk) 17.07.16 13:35
(26) v3rter, так как я не ставил себе задач по коммерческому применению методики, то да, оптимизировано под конкретный сервер.
36. Sergey Andreev (starik-2005) 17.07.16 14:51
(34) dmurk, если поле "НазначениеСостояния" является уникальным, то и представленное Вами решение может подойти, полагаю, для чего-нибудь. Но если задача - это найти все "неправильные" статусы и заменить их на произвольно выбранные "правильные", то даже такого не надо - достаточно на первом шаге отобрать уникальные, на втором шаге найти минимум или максимум ссылки, чтобы привязать правильное к одной ссылке из множества. На третьем шаге найти все, отличные от "правильных" и заменить их на "правильные", сопоставив по полю уникальности. Агрегация тут при наличии множества ссылок на одинаковые статусы не нужна, на выходе (139к - количество_уникальных_статусов) неверных ссылок, которые уже можно искать в системе и менять. Дальше можно разбить их на примерно равные части и скормить приемлемому количеству потоков для изменения. Если скармливать постепенно, то можно получить примерно равнораспределенную нагрузку, если скормить сразу все, поделив случайным образом, то можно ожидать, что часть заданий отработают раньше что приведет к замедлению обработки.
37. Дмитрий Дудин (dmurk) 18.07.16 10:04
(36) starik-2005, в данной задаче, на практике справочник был заполнен заново двумя элементами, и их ссылки записаны в объекты. Поднятый вопрос - адаптация стандартного ПоискИЗаменаДублей для универсального применения, но в более вменяемые сроки, для того чтобы сопровождение проекта не нагружало отдел разработки типовыми решениями.
38. Роберт В е р т и н с к и й (v3rter) 18.07.16 11:35
В любом случае новый приём оптимизации - это хорошо )
39. Роман С (Dach) 19.07.16 10:21
Господа, хочу на Ваш суд вынести вот такой вариант решения озвученной задачи.

Попробую своими словами, немного абстрагируясь от исходной задачи.

Итак, предположим, у нас есть некая таблица, пусть в ней 100 строк. По колонке Поле1 у нас есть дубли. Мы выяснили, что дублей из 100 строк ровно половина, то есть 50.

Далее, я сознательно вношу некое допущение, весьма важное. Я буду считать, что внутри этих строк дубли распределены равномерно. Считаю, что чем больше строк, то тем более равномерно внутри нее распределены дубли. Конечно, это может быть не так, если например алгоритм системы, порождающий дубли - долгое время работал неправильно и создавал дубли, а затем пришел разработчик и что-то там исправил, в результате чего дубли стали рождаться намного более редко.

Да, и еще очень важно - считаю, что дубли располагаются относительно "рядом" друг с другом". Ну то есть ситуация, когда дублируются строки номер 1 и номер 7 - вероятность 99 процентов, а строки с номерами 1 и 100 - вероятность такого события 1 процент. То есть, если алгоритм, порождающий дубли - более менее цикличен, то наверное это допустимо.

В стандартном случае, если мне искать дубли, по сути, нужно каждый элемент-строку сравнить с каждой строкой из 100. Мое любимое декартово произведение "каждый с каждым", то есть в данном случае 100*100 = 10000. То есть, чтобы выявить дубли - придется сделать 10000 проходов. Запомним.

Что если решить задачу так:

1. Разбиваем наши 100 записей на части, каждая по 20 записей. 20, 20, 20, 20 и еще раз 20. 20 строк - выборка, которая охватывает возможные дубли наиболее вероятно, то есть расстояние между дублями не более 20 строк.
2. Внутри каждой выборки выполняем поиск "каждый с каждым". Получается: (20*20) * 5 = 2000 проходов.
3. Учитывая, что дубли распределены равномерно - 50 дублей должны сидеть внутри каждой выборки по 20. 50 дублей на 5 выборок по 20 - по 10 дублей "сидит" в каждой.
4. В результате, после выполнения - остается 5 выборок по 10 строк в каждой. Это, если бы не было перекрестных дублей. Пусть перекрестных дублей 10 из 50.,
тогда в каждой выборке "сидит" 8 схлопываемых дублей. То есть на самом деле, не по 10 строк остается, а по 12 строк в каждой выборке.
5. Теперь нужно избавиться от возможных" перекрестных дублей, когда дубли "сидят" в разных выборках.

Ищем "каждый с каждым", выборка №1 (все строки) - с выборкой №2 (все строки); выборка №1 (все строки) - с выборкой №3 (все строки) ; выборка №1 (все строки) - с выборкой №4 (все строки) ; выборка №1 (все строки) - с выборкой №5 (все строки) = (12*12) * 4 = 576. Ну и для каждой выборки = 576 * 5 = 2880 проходов.

Итого, чтобы выявить все дубли, при таком подходе - понадобилось 2000 + 2880 = 4880 проходов.

Что чуть более чем в 2 раз меньше, чем если делать 100 на 100.

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

Как думаете, мои рассуждения имеют место быть или они ошибочны?
40. Роберт В е р т и н с к и й (v3rter) 19.07.16 10:49
Дубли, считаю, неудачный пример, особенно если "задублившееся" поле индексировано.
41. Роман С (Dach) 19.07.16 11:09
(40) v3rter, считаем, что оно не индексируемое. И таблица не сортированная
42. Сергей (ildarovich) 19.07.16 13:11
(39) Dach, рассуждения нормальные, но только вслед за автором вы пытаетесь слегка поправить решение, дополнить его, решив проблему остающихся дублей. Тогда как, по моему мнению, нужно было кардинально поменять основу - сам алгоритм решения.

Пусть у вас есть пачки банкнот (лотерейных билетов), среди которых есть фальшивые. Номера фальшивых повторяются. Они - дубли.
Мало кому придет в голову сравнивать номер каждой купюры с номерами всех других купюр. Чаще всего люди в данном случае либо сортируют купюры, когда их немного, либо заводят таблицу, в которой отмечают встретившиеся номера.
Трудоемкость последней операции, очевидно, пропорциональна числу купюр. Такой способ и предлагается в (7).

Ошибка автора, вероятно, в том, что гибкий универсальный настраиваемый алгоритм поиска дублей, нацеленный на разные варианты выявления относительно немногочисленных дублей по похожести наименований, сравнения по равенству разных реквизитов он применил к очень редкому частному случаю, на который наверняка не рассчитывали разработчики.
43. Роман С (Dach) 19.07.16 14:28
(42) ildarovich, постойте-постойте.

Я оперирую низкоуровневым понятием "проход". Это нечто даже более детальное, чем операторы SQL-инструкций. Это именно проход в цикле.
Скажем так, я подразумеваю, что наиболее вероятным и чаще всего применяемым является алгоритм вложенных циклов.

"Чаще всего люди в данном случае либо сортируют купюры, когда их немного, либо заводят таблицу, в которой отмечают встретившиеся номера."

Ок. Начинаю перебирать номера. Номер 12345 - встретился 1 раз. Записываю в таблицу.
Номер 234 - встретился 1 раз.

*****
спустя 500 шагов цикла

Номер 12345! Как узнать, сколько раз он мне встретился? Абстрагируйтесь, плз, от всяких кэшей, соответствий, индексированных таблиц, ибо чтобы ответить на этот вопрос, все равно придется
перебрать от начала до конца (ну или до тех пор, пока не встретится) весь второй список!

Так вот, ИМХО, ключевая фраза тут "до тех пор, пока не встретится".

Как Вы думаете, как сервер на физическом уровне выполняет сортировку? А как группировку? Думаю, что да - как Вы верно подметили удачной аналогией, "записывая номер".
Но это далеко не дает гарантий, что количество проходов будет существенно меньше, чем в моем способе. Да к тому же это намного более трудно прогнозируемо, тогда как как мой способ при известных входящих данных куда более легко просчитать.
44. Роман С (Dach) 19.07.16 14:43
(43) +

поэтому я не подпишусь, что в задаче поиска дублей в большой таблице более 100 тыс строк запрос вида

ВЫБРАТЬ
НазначениеСостояния
ИЗ Справочник.НазначениеСостояния
СГРУППИРОВАТЬ ПО
НазначениеСостояния
ИМЕЮЩИЕ КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Ссылка) > 1

отработает быстрее, чем алгоритм, предложенный автором. К слову, мне кажется, он не просто так порекомендовал опробировать на реальных данных. Доберусь вечером до ноута - сам проверю в удовольствием
45. Сергей (ildarovich) 19.07.16 14:45
(43) Dach,
Но это далеко не дает гарантий, что количество проходов будет существенно меньше, чем в моем способе
Будет существенно меньше. Проход будет ровно один. С гарантией. Посмотрите запрос в (7). Он решает ту же самую задачу. Приведу его еще раз.
ВЫБРАТЬ
  НазначениеСостояния
    ИЗ Справочник.НазначениеСостояния
СГРУППИРОВАТЬ ПО
  НазначениеСостояния
ИМЕЮЩИЕ КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Ссылка) > 1
...Показать Скрыть

Вы думаете, что расчет агрегата КОЛИЧЕСТВО(РАЗЛИЧНЫЕ потребует нескольких проходов по таблице и поиска? - Тогда вы ошибаетесь.
(44) Отработает ГОРАЗДО БЫСТРЕЕ - на два порядка, меньше, чем за секунду, скорее всего, то есть быстрее примерно в 200 раз.
46. Роман С (Dach) 19.07.16 14:56
(45) ildarovich, один проход по таблице-источнику - это ок, согласен.

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

Ответьте на один вопрос, когда встречается дубль - для того, чтобы понять - дубль он (или "трубль" или "четверубль" ;))) ) - Вы будете заглядывать во второй список? Вы будете его перебирать или нет? Мне кажется да, потому что как иначе? Ну и в чем тогда принципиальное отличие от джойна на физическом уровне?

Да только во фразе "буду перебирать весь второй список, пока не найду искомый элемент, чтобы понять, сколько он раз встречался в первой таблице"

То есть там в цикле стоит "Прервать", грубо говоря. Вот и все.

Ну и если во втором списке наша строка сидит в самом конце - разве мне его весь не придется просмотреть?

Разве не логично рассуждаю?
47. Сергей (ildarovich) 19.07.16 15:21
(46) Dach, агрегатные функции считаются с использованием хэшей. Грубо говоря, найденные номера купюр заносятся в соответствие. В этом случае нет необходимости перебора списка ранее встретившихся элементов. Обращение к соответствию - это простая и быстрая операция.
48. Роман С (Dach) 19.07.16 15:25
(47) ildarovich, то есть второй список хэшируется и индексируется? Ну, тогда вопросов нет.

Однако, способ рабочий, если возможностей использовать соответствие нет
49. Сергей (ildarovich) 19.07.16 15:36
(48) Dach,
если возможностей использовать соответствие нет
соответствие я привел для удобства объяснения. План запроса может и сортировку использовать и индекс-скан. Но все это будет еще быстрее или не медленнее. Квадратичной зависимости в этой задаче не должно быть, если специально не накосячить.
Способ рабочий? - А есть ли вообще этот способ, если нет задачи?
50. Яков Коган (Yashazz) 19.07.16 16:41
(9) e.kogan, этой идее сто лет в обед.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа