Русский
Русский
English
Статистика
Реклама

Parallelism

Разгоняем REACTOR

12.06.2021 18:20:44 | Автор: admin

Кому будет интересно?

Реактор сегодня - это стильно, модно, молодежно. Почему многие из нас практикуют реактивное программирование? Мало кто может ответить однозначно на этот вопрос. Хорошо - если Вы понимаете свой выигрыш, плохо - если реактор навязан организацией как данность. Большинство аргументов "ЗА" - это использование микросервисной архитектуры, которая в свою очередь обязывает микросервисы часто и много коммуницировать между собой. Для коммуникации в большинстве случаев выбирают HTTP взаимодействие. Для HTTP нужен легковесный веб-сервер, а что первое приходит на ум? Tomcat. Тут появляются проблемы с лимитом на максимальное количество сессий, при превышении которого веб-сервер начинает реджектить запросы (хотя лимита этого не так уж и легко достичь). Здесь на подмогу приходит реактор, который подобными лимитами не ограничен, и, например, Netty в качестве веб-сервера, который работает с реактивностью из коробки. Раз есть реактивный веб-сервер, нужен реактивный веб-клиент (Spring WebClient или Reactive Feign), а раз клиент реактивный, то вся эта жуть просачивается в бизнес логику, Mono и Flux становятся Вашими лучшими друзьями (хотя по началу есть только ненависть :))

Среди бизнес задач, очень часто встречаются серьезные процедуры, которые обрабатывают большие массивы данных, и нам приходится применять реактор и для них. Тут начинаются сюрпризы, если реактор не уметь готовить, можно и проблем схлопотать очень много. Превышение лимита файловых дескрипторов на сервере, OutOfMemory из-за неконтролируемой скорости работы неблокирующего кода и многое многое другое, о чем мы сегодня поговорим. Мы с коллегами испытали очень много трудностей из-за проблем с пониманием как держать реактор под контролем, но всё что нас не убивает - делает нас умнее!

Блокирующий и неблокирующий код

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

Лидер здесь - HTTP взаимодействие, вариантов масса, выбирай любой. Я предпочитаю Reactive Feign от Playtika, в комбинации со Spring Boot + WebFlux + Eureka мы получаем очень годную сборку для микросервисной архитектуры.

Давайте по-простому: НЕблокирующий код, это обычно всё, в названии чего есть reactive, а блокирующий - все оставшееся :) Hibernate + PostgreSQL - блокирующий, отправить почту через JavaMail - блокирующий, скинуть сообщение в очередь IBMMQ - блокирующий. Но есть, например, реактивный драйвер для MongoDB - неблокирующий. Отличительной особенностью блокирующего кода, является то, что глубоко внутри произойдет вызов метода, который заставит Ваш поток ждать (Thread.sleep() / Socket.read() и многие подобные), что для реактора - как нож в спину. Что же делать? Большинство бизнес логики завязано на базу данных, без нее никуда. На самом деле достаточно знать и уметь делать 2 вещи:

  • Необходимо понимать где блокирующий код. В этом может помочь проект BlockHound или его аналоги (тут тема для отдельной статьи)

  • Исполнение блокирующего кода необходимо переключать на пулы, готовые его выполнять, например: Schedulers.boundedElastic(). Делается это при помощи операторов publishOn & subscribeOn

Разгоняемся сами

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

Уровень 1

    @Test    fun testLevel1() {        val result = Mono.just("")            .map { "123" }            .block()        assertEquals("123", result)    }

Начнем с простого, такой код обычно пишут начинающие reactor программисты. Как начать цепочку? Mono.just и ты на коне :) Оператор map трансформирует пустую строку в "123" и оператор block делает subscribe.

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

Уровень 2

    fun nonBlockingMethod1sec(data: String)     = data.toMono().delayElement(Duration.ofMillis(1000))    @Test    fun testLevel2() {        val result = nonBlockingMethod1sec("Hello world")            .flatMap { nonBlockingMethod1sec(it) }            .block()        assertEquals("Hello world", result)    }

Усложняем наш код, добавляем неблокирующий метод nonBlockingMethod1sec, все что он делает - ожидает одну секунду. Все что делает данный код - дважды, по очереди, запускает неблокирующий метод.

Уровень 3

    fun collectTasks() = (0..99)    @Test    fun testLevel3() {        val result = nonBlockingMethod1sec("Hello world")            .flatMap { businessContext ->                collectTasks()                    .toFlux()                    .map {                        businessContext + it                    }                    .collectList()            }            .block()!!        assertEquals(collectTasks().toList().size, result.size)    }

Начинаем добавлять самое интересное - Flux! У нас появляется метод collectTasks, который собирает массив из сотни чисел, и далее мы делаем из него Flux - это будет наш список задач. К каждой задаче мы применяем трансформацию через оператор map. Оператор collectList собирает все результаты в итоговый список для дальнейшего использования.

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

Уровень 4

    fun collectTasks() = (0..100)        @Test    fun testLevel4() {        val result = nonBlockingMethod1sec("Hello world")            .flatMap { businessContext ->                collectTasks().toFlux()                    .flatMap {                        Mono.deferContextual { reactiveContext ->                            val hash = businessContext + it + reactiveContext["requestId"]                            hash.toMono()                        }                    }.collectList()            }            .contextWrite { it.put("requestId", UUID.randomUUID().toString()) }            .block()!!        assertEquals(collectTasks().toList().size, result.size)    }

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

Уровень 5

    fun collectTasks() = (0..1000)        fun doSomethingNonBlocking(data: String)        = data.toMono().delayElement(Duration.ofMillis(1000))        fun doSomethingBlocking(data: String): String {        Thread.sleep(1000); return data    }    val pool = Schedulers.newBoundedElastic(10, Int.MAX_VALUE, "test-pool")    private val logger = getLogger()    @Test    fun testLevel5() {        val counter = AtomicInteger(0)        val result = nonBlockingMethod1sec("Hello world")            .flatMap { _ ->                collectTasks().toFlux()                    .parallel()                    .runOn(pool)                    .flatMap {                        Mono.deferContextual { _ ->                            doSomethingNonBlocking(it.toString())                                .doOnRequest { logger.info("Added task in pool ${counter.incrementAndGet()}") }                                .doOnNext { logger.info("Non blocking code finished ${counter.get()}") }                                .map { doSomethingBlocking(it) }                                .doOnNext { logger.info("Removed task from pool ${counter.decrementAndGet()}") }                        }                    }.sequential()                    .collectList()            }            .block()!!        assertEquals(collectTasks().toList().size, result.size)    }

Вот мы и добрались до итогового варианта! Часть с реактивным контекстом была опущена для более наглядной демонстрации того, зачем мы здесь собрались. У нас появились два новых метода: doSomethingNonBlocking (3) & doSomethingBlocking (6) - один с неблокирующим ожиданием в секунду, второй с блокирующим. Мы создали пул потоков для обработки задач (10), добавили счетчик активных задач в реакторе (15). У нас появился оператор parallel (19) и обратный ему sequential (29). Задачи мы назначили на свежесозданный пул (20). Для понимания, что же происходит внутри, добавили логирование внутри операторов doOnRequest (вызывается перед исполнением метода), doOnNext (вызывается после исполнения метода). Основная задумка - на примере, определить сколько задач одновременно выполняется в реакторе и за какое время цепочка завершит свою работу.

Такой "паттерн", мы с коллегами очень часто применяем для выполнения сложных задач, таких как отправка отчетов или массовая обработка транзакций. Первым делом собирается бизнес контекст - это некая структура, содержащая в себе информацию, полученную в результате вызовов других микросервисов. Бизнес контекст необходим нам для выполнения самих задач, и собирается он заранее, чтобы не тратить время в процессе обработки. Далее мы собираем список задач, превращаем их во Flux и скармливаем реактору на параллельную обработку.

И вот здесь начинается самое интересное. Попробуйте ответить на несколько вопросов. Как Вы считаете, сколько времени будет выполнятся данная цепочка? В ней 100 задач, в каждой задаче неблокирующее ожидание в 1 секунду, блокирующее ожидание в 1 секунду, и у нас в наличии пул из 10 потоков? (Вполне годная задачка на собеседование senior reactor developer :))

Правильный ответ

Около 12 секунд. Рассуждаем от блокирующего :) Блокирующее ожидание никуда не деть, и тут имеем 100 блокирующих секунд на 10 потоков, итого 10 секунд. Неблокирующее ожидание заметно нам лишь в первый раз, далее оно незаметно запускается в передышках между блокирующим. Не забываем про одну секунду сбора "бизнес контекста" перед запуском задач.

А теперь уберем строку (26) .map { doSomethingBlocking(it) } . Освободим наш реактор от блокирующего кода, интересно, сколько теперь времени займет выполнение цепочки?

Правильный ответ

2 секунды! 1 на сбор "бизнес контекста" и 1 на выполнение всех задач. Реактор запустит 100 задач одновременно. Но ведь у нас пул из 10 потоков? Как так? Первый разрыв шаблона.

Мы идем до конца и увеличиваем количество задач в методе collectTasks() до ... 1000? а может быть сразу до 15000? Как долго реактор будет выполнять столько задач?

Правильный ответ

2 секунды! 1 на сбор "бизнес контекста" и 1 на выполнение всех задач. Реактор запустит ВСЕ задачи одновременно. Второй разрыв шаблона. Где предел?

А это вообще легально?

Как же так и как это контролировать? Почему это опасно? Что если внутри параллельной обработки Вы решите вызвать другой микросервис? Если у вас 30000 задач, и по завершению каждой, Вам нужно отправлять запрос соседнему микросервису, Вы с удивлением можете обнаружить, что реактор непременно постарается выполнить все вызовы одновременно (Вы ведь используете реактивный web-client или реактивный feign, верно?) Открытие такого большого количества сокетов повлечет за собой превышение лимита открытых файловых дескрипторов в системе, что как минимум создаст проблемы с невозможностью создания новых сокетов в системе и помешает другим сервисам, а как максимум повалит Вам на сервере SSH и Вы потеряете доступ к серверу. Сомневаюсь, что в этот момент, программист будет кричать "зато смотри как быстро работает".

Разрыв шаблона. Thread Pool & Reactor

Основная проблема начинающего реактор программиста - это образ мышления, если есть медленный процесс - добавь X потоков, будет быстрее в X раз, а если слишком быстро - сократи количество потоков. Как всё просто было раньше? :) С реактором это не работает.

Классический thread pool - двери. Больше дверей - больше пропускная способность, все работает быстрее.

Теперь встречайте reactor! Вы видите двери? Нет никаких дверей

Реактор это большой мешок с подарками, или воздушная труба, задачи в которую валятся и летают там пока не выполнятся. А кто эти люди в желтом? Это наши epoll реактивные потоки, которые ни в коем случае нельзя нагружать блокирующими задачами. Можно провести аналогию с прорабами или инженерами. Они здесь, чтобы управлять процессом, а не чтобы выполнять тяжелую работу. Займите одного инженера тяжелой задачей, и когда к нему придет следующий рабочий с вопросом "что делать дальше?", он не сможет ответить, потому что был занят. Вот так и появляются таймауты в реактивном коде. Казалось бы микросервис стоит без нагрузки, выполняет какие-то задачки, а один из 500 запросов к нему падает с тайм-аутом, и непонятно почему. Велика вероятность что инженер был занят блокирующей задачей! Заботьтесь о своих инженерах и поручайте тяжелую работу специально обученным рабочим, например, Schedulers.boundedElastic().

Как контролировать эту "трубу", в которую валится всё без контроля? Вот мы и подошли к кульминации

Конфигурируем реактор!

В своей дефолтной конфигурации, параллельная обработка в реакторе зависит от количества ядер процессора сервера, на котором запускается код, поэтому, к своему удивлению, Вы получите разные результаты, проверяя работу реактора в тесте на локальной машине с 4-8 ядрами и production сервере с 32 ядрами.

Парад настроек открывает parallel с его аргументом parallelism

Меняя parallelism, мы можем регулировать количество запускаемых rails (это местное понятие реактора, которое похоже на корутины, но по сути является количеством одновременно выполняемых неблокирующих задач). Prefetch мы рассмотрим более подробно в следующем разделе.

Но одного parallelism недостаточно, реактор все еще будет нагребать задач как не в себя.

Мало кто обращал внимание что у оператора flatMap (только того что запускается на Flux) есть перегрузки с интересными аргументами, а именно maxConcurrency

maxConcurrency очень важен, по дефолту значение стоит Integer.MAX_VALUE (определяет сколько неблокирующих задач может выполняться одновременно на одной рельсе. Понимаете теперь откуда аппетит у реактора?

Также, не стоит забывать, что если цепочка будет запущена несколько раз (вызов одного http метода контроллера несколько раз), то все помножится! Никакой пул не спасет.

Количество запусков цепочки напрямую влияет на количество одновременно выполняемых задач.

Подведем небольшой итог:

  • parallel (parallelism)

  • flatMap (maxConcurrency)

  • Количество запусков цепочки

Эти три параметра являются множителями, для расчета количества одновременных задач.

По дефолту это Кол-во ядер * Integer.MAX_VALUE * Количество запусков цепочки

Напротив же, запустив данный код для 5 задач длительностью в секунду мы получим цепочку работающую 5 секунд. Теперь всё под контролем!

        val result = nonBlockingMethod1sec("Hello world")            .flatMap { _ ->                collectTasks().toFlux()                    .parallel(1)                    .runOn(pool, 1)                    .flatMap({                        Mono.deferContextual { _ ->                            doSomethingNonBlocking(it.toString())                        }                    }, false, 1, 1)                    .sequential()                    .collectList()            }            .block()!!

Стоп, или не всё?

Thread Pool

Зачем же нужен пул потоков в реакторе? Думайте о нем как о двигателе для Вашего автомобиля. Чем пул мощнее - тем блокирующие задачи будут разбираться быстрее, а если потоков мало, то и блокирующие задачи задержатся у вас надолго! А куда же мы без блокирующих вызовов? На количество одновременно выполняемых задач в реакторе он не влияет, вот это поворот :)

Надеюсь, Вы не пробовали использовать Schedulers.parallel() для исполнения Вашего блокирующего кода? =) Несмотря на свое подходящее название (ну называется он parallel, значит и нужен для параллельной обработки) использовать этот пул можно только для неблокирующего кода, в доке указано что он живет с одним воркером, и содержит в себе только особенные, реактивные потоки.

Распределение задач по рельсам

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

Зеленые прямоугольники это наши задачи, которые распределяются в реакторе по алгоритму round-robin, что в случае с синтетическими данными дает красивую картинку.

Хорошо загруженный реактор (задачи равномерно распределены). 54 блокирующих задачи (каждая по 1сек), round-robin распределение по 6 рельсамХорошо загруженный реактор (задачи равномерно распределены). 54 блокирующих задачи (каждая по 1сек), round-robin распределение по 6 рельсам

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

Плохо загруженный пул (задачи распределены не равномерно)54 блокирующих задачи (каждая по 1сек кроме 2ух), round-robin распределение по 6 рельсамПлохо загруженный пул (задачи распределены не равномерно)54 блокирующих задачи (каждая по 1сек кроме 2ух), round-robin распределение по 6 рельсам

Оператор collectList() вернет нам результат только после завершения последней задачи, и как мы видим, наш пул будет простаивать пока 1 поток трудится разгребая очередь накопившихся задач. Это создает неприятные задержки, когда Вы знаете что можно быстрее, но быстрее не происходит.

Бороться с этим можно несколькими способами

  • concatMap вместо flatMap (посмотрите в профилировщик на ваш пул, передумаете)

  • правильно планировать задачи, чтобы исключить аномалии (почти невозможно)

  • дробить каждую задачу на много мелких, и также запускать их в параллельную обработку чтобы нивелировать проблемы с распределением (вполне рабочий вариант)

  • prefetch (наш выбор!)

Параметр prefetch у flatMap & runOn позволяет определить, сколько задач будет взято на одну рельсу на старте, а затем при достижении некоторого порога выполнения задач, реквесты будут повторяться с этим количеством. Значение по умолчанию - 256. Сменив значение на 1, можно заставить реактор использовать механизм "work stealing", при котором, рельсы и потоки, которые освободились, будут забирать задачи себе на выполнение и картина получится гораздо более приятная.

Хорошо загруженный пул (задачи равномерно распределены)54 блокирующих задачи (каждая по 1сек кроме 2ух), round-robin распределение по 6 рельсамPrefetch !Хорошо загруженный пул (задачи равномерно распределены)54 блокирующих задачи (каждая по 1сек кроме 2ух), round-robin распределение по 6 рельсамPrefetch !

На этом у меня всё. Будет интересно прочесть Ваши замечания и комментарии, на 100% истину не претендую, но все результаты подкреплены практическими примерами, на Spring Boot + Project Reactor 3.4. Всем спасибо!

Подробнее..
Категории: Kotlin , Java , Concurrency , Parallel , Reactor , Parallelism , Mono , Threads , Flux , Pool , Prefetch

Перевод Как SQL Server использует bitmap-фильтры

28.08.2020 18:19:00 | Автор: admin
Перевод статьи подготовлен в преддверии старта курса MS SQL Server Developer.





Может ли запрос, выполняющийся параллельно, использовать меньше CPU и выполняться быстрее, чем такой же запрос, выполняющийся последовательно?

Да! Для демонстрации я буду использовать две таблицы с одной колонкой типа integer.


Примечание TSQL скрипт в виде текста находится в конце статьи.

Генерируем демо-данные


В таблицу #BuildInt вставляем 5 000 случайных целых чисел (для того, чтобы у вас были такие же значения, как и у меня я использую RAND с seed и цикл WHILE).



В таблицу #Probe вставляем 5 000 000 записей.



Последовательный план


Теперь напишем запрос для подсчета количества совпадений значений в этих таблицах. Используем хинт MAXDOP 1, чтобы быть уверенным, что запрос не будет выполняться параллельно.

Вот его план выполнения и статистика:



Этот запрос выполняется за 891 мс и использует 890 мс CPU.

Параллельный план


Теперь запустим тот же запрос с MAXDOP 2.



Запрос выполняется 221 мс и использует 436 мс CPU. Время выполнения уменьшилось в четыре раза, а использование CPU в два!

Магия Bitmap


Причина, по которой параллельное выполнение запроса намного эффективнее, заключается в операторе Bitmap (битовая карта).

Давайте внимательно посмотрим на фактический план выполнения параллельного запроса:



И сравним его с последовательным планом:



Принцип работы оператора Bitmap достаточно хорошо документирован, поэтому здесь я приведу только краткое описание со ссылками на документацию в конце статьи.

Hash Join (соединение хешированием)


Соединение хешированием (hash join) выполняется в два этапа:

  1. Этап построения (англ. build). Читаются все строки одной из таблиц и создается хеш-таблица для ключей соединения.
  2. Этап проверки (англ. probe). Читаются все строки второй таблицы, вычисляется хеш той же хэш-функцией по тем же ключам соединения и ищется совпадающий бакет в хэш-таблице.


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

Примечание переводчика: подробнее о принципе работы hash join можно посмотреть в статье Визуализируем и разбираемся с Hash Match Join


Bitmap в последовательных планах


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

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

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

Относительно небольшие затраты на построение битовой карты компенсируются экономией времени на отсутствие проверок строк, для которых точно нет совпадений в хеш-таблице. Такая оптимизация часто оказывается эффективной, так как проверка битовой карты значительно быстрее проверки хеш-таблицы.

Bitmap в параллельных планах


В параллельном плане битовая карта отображается как отдельный оператор Bitmap.

При переходе от этапа построения к этапу проверки битовая карта передается оператору HASH MATCH со стороны второй (проверяемой, probe) таблицы. Как минимум, битовая карта передается на сторону probe перед JOIN и оператором обмена (Parallelism).

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

Конечно, в последовательных планах операторы обмена отсутствуют, поэтому такое перемещение битовой карты за пределы HASH JOIN не даст никаких дополнительных преимуществ по сравнению со встроенной битовой картой внутри оператора HASH MATCH.

В некоторых ситуациях (хотя и только в параллельном плане) оптимизатор может переместить Bitmap еще дальше вниз по плану на probe-стороне соединения.

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

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

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

Перемещение bitmap-фильтра


Вернемся к концепции перемещения bitmap-фильтра на probe-сторону соединения.

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



Он применяется ко всем строкам, которые соответствуют seek-предикату (для Index Seek) или ко всем строкам для Index Scan или Table Scan. Например, на скриншоте выше показан bitmap-фильтр, примененный к Table Scan для heap-таблицы.

Углубляемся ...


Если bitmap-фильтр построен на одном столбце или выражении типа integer или bigint, и применяется к одному столбцу типа integer или bigint, то оператор Bitmap может быть перемещен еще ниже по плану, даже дальше, чем операторы Seek или Scan.

Предикат по-прежнему будет отображаться в операторах Scan или Seek, как в примере выше, но теперь он будет помечен атрибутом INROW, что означает перемещение фильтра в Storage Engine и его применение к строкам при их чтении.

При такой оптимизации строки фильтруются еще до того, как Query Processor увидит эту строку. Из Storage Engine передаются только те строки, которые соответствуют HASH MATCH JOIN.

Условия при которых применяется такая оптимизация зависит от версии SQL Server. Например, в SQL Server 2005, в дополнение к условиям, указанным ранее, проверяемый столбец (probe) должен быть определен как NOT NULL. Это ограничение было ослаблено в SQL Server 2008.

Вам может быть интересно, насколько INROW-оптимизация влияет на производительность. Будет ли перенос оператора как можно ближе к Seek или Scan таким же эффективным, как фильтрация в Storage Engine? Я отвечу на этот интересный вопрос в других статьях. А здесь мы еще посмотрим на MERGE JOIN и NESTED LOOP JOIN.

Другие варианты JOIN


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

Merge Join (соединение слиянием)


Этот тип физического соединения требует отсортированных входных данных, поэтому принудительный MERGE JOIN приводит к тому, что перед ним присутствует сортировка. Последовательный план выглядит следующим образом:



Теперь запрос использует 3105 мс CPU, а общее время выполнения составляет 5632 мс.

Увеличение общего времени выполнения связано с тем, что одна из операций сортировки использует tempdb (несмотря на то, что SQL Server имеет достаточно памяти для сортировки).

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

Продолжим форсировать MERGE JOIN, но разрешим параллелизм (MAXDOP 2):



Как и в параллельном HASH JOIN, который мы видели ранее, bitmap-фильтр располагается на другой стороне MERGE JOIN ближе к Table Scan и применяется с использованием INROW-оптимизации.

При 468 мс CPU и 240 мс затраченного времени MERGE JOIN с дополнительными сортировками работает почти так же быстро, как и параллельный HASH JOIN (436 мс / 221 мс).

Но у параллельного MERGE JOIN есть один недостаток: он резервирует 330 КБ памяти, исходя из ожидаемого количества сортируемых строк. Так как битовые карты такого типа используются после стоимостной оптимизации, то корректировка оценки не производится, несмотря на то, что через нижнюю сортировку проходит только 2488 строк.

Оператор Bitmap может появиться в плане с MERGE JOIN только вместе с последующим блокирующим оператором (например, Sort). Блокирующий оператор должен получить все необходимые значения на вход, прежде чем он сгенерирует первую строку на выход. Это гарантирует, что битовая карта будет полностью заполнена до того, как строки из JOIN-таблицы будут считываться и проверяться по ней.

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

С индексами


Если доступны подходящие индексы, то ситуация будет иной. Распределение наших случайных данных такое, что в таблице #BuildInt можно создать уникальный индекс. А таблица #Probe содержит дубликаты, поэтому в ней придется обойтись неуникальным индексом:



На HASH JOIN (как в последовательный, так параллельный) это изменение не повлияет. HASH JOIN не может воспользоваться индексами, поэтому планы и производительность остаются прежними.

Merge Join (соединение слиянием)


MERGE JOIN больше не должен выполнять операцию соединения многие ко многим и больше не требует оператора Sort на входных данных.
Отсутствие блокирующего оператора сортировки означает, что Bitmap не может быть использован.

В результате мы видим последовательный план, вне зависимости от параметра MAXDOP, а производительность хуже, чем у параллельного плана до добавления индексов: 702 мс CPU и 704 мс затраченного времени:



Однако здесь есть заметное улучшение по сравнению с исходным планом последовательного MERGE JOIN (3105 мс / 5632 мс). Это связано с устранением сортировки и лучшей производительностью соединения один-ко-многим.

Nested Loops Join (соединение вложенными циклами)
Как и следовало ожидать, NESTED LOOP работает значительно лучше. Аналогично MERGE JOIN, оптимизатор решает не использовать параллелизм:



На данный момент это самый эффективный план всего 16 мс CPU и 16 мс затраченного времени.

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

На моем ноутбуке выполнение NESTED LOOP с холодным кэшем заняло 78 мс CPU и 2152 мс затраченного времени. При тех же обстоятельствах MERGE JOIN использовал 686 мс CPU и 1471 мс. HASH JOIN 391 мс CPU и 905 мс.

MERGE JOIN и HASH JOIN выигрывают при большом, возможно, последовательном вводе-выводе с использованием упреждающего чтения (read-ahead).

Дополнительные ресурсы


Parallel Hash Join (Craig Freedman)
Query Execution Bitmap Filters (SQL Server Query Processing Team)
Bitmaps in Microsoft SQL Server 2000 (статья из MSDN)
Interpreting Execution Plans Containing Bitmap Filters (документация SQL Server)
Understanding Hash Joins (документация SQL Server)

Тестовый скрипт


USE tempdb;GOCREATE TABLE #BuildInt(    col1    INTEGER NOT NULL);GOCREATE TABLE #Probe(    col1    INTEGER NOT NULL);GO-- Load 5,000 rows into the build tableSET NOCOUNT ON;SET STATISTICS XML OFF;DECLARE @I INTEGER = 1;INSERT #BuildInt    (col1) VALUES     (CONVERT(INTEGER, RAND(1) * 2147483647));WHILE @I < 5000BEGIN    INSERT #BuildInt        (col1)    VALUES         (RAND() * 2147483647);    SET @I += 1;END;-- Load 5,000,000 rows into the probe tableSET NOCOUNT ON;SET STATISTICS XML OFF;DECLARE @I INTEGER = 1;INSERT #Probe    (col1) VALUES     (CONVERT(INTEGER, RAND(2) * 2147483647));BEGIN TRANSACTION;WHILE @I < 5000000BEGIN    INSERT #Probe        (col1)     VALUES         (CONVERT(INTEGER, RAND() * 2147483647));    SET @I += 1;    IF @I % 25 = 0    BEGIN        COMMIT TRANSACTION;        BEGIN TRANSACTION;    END;END;COMMIT TRANSACTION;GO-- DemosSET STATISTICS XML OFF;SET STATISTICS IO, TIME ON;-- SerialSELECT     COUNT_BIG(*) FROM #BuildInt AS bi JOIN #Probe AS p ON     p.col1 = bi.col1 OPTION (MAXDOP 1);-- ParallelSELECT     COUNT_BIG(*) FROM #BuildInt AS bi JOIN #Probe AS p ON     p.col1 = bi.col1 OPTION (MAXDOP 2);SET STATISTICS IO, TIME OFF;-- IndexesCREATE UNIQUE CLUSTERED INDEX cuq ON #BuildInt (col1);CREATE CLUSTERED INDEX cx ON #Probe (col1);-- Vary the query hints to explore plan shapesSELECT     COUNT_BIG(*) FROM #BuildInt AS bi JOIN #Probe AS p ON     p.col1 = bi.col1 OPTION (MAXDOP 1, MERGE JOIN);GODROP TABLE #BuildInt, #Probe;




Читать ещё:


Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru