Запросы в PostgreSQL: 6. Хеширование |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2021-10-02 16:40 В предыдущих статьях я рассказал про этапы выполнения запросов, про статистику, про два основных вида доступа к данным — последовательное сканирование и индексное сканирование, — и перешел к способам соединения. Прошлая статья была посвящена вложенному циклу, а сегодня поговорим про соединение хешированием. Заодно затронем группировку и поиск уникальных значений. Однопроходное соединение хешированием Идея соединения с помощью хеширования состоит в поиске подходящих строк с помощью заранее подготовленнои? хеш-таблицы. Вот пример плана, использующего такое соединение:
На первом этапе узел Hash Join обращается к узлу Hash. Тот получает от своего дочернего узла весь внутренний набор строк и помещает его в хеш-таблицу. Хеш-таблица позволяет сохранять пары, составленные из ключа хеширования и значения, а затем искать значения по ключу за фиксированное время, не зависящее от размера хеш-таблицы. Для этого с помощью хеш-функции ключи хеширования распределяются случаи?но, но равномерно по ограниченному количеству корзин (bucket) хеш-таблицы. Число корзин всегда является степенью двои?ки, поэтому номер корзины можно получить, взяв нужное количество двоичных разрядов значения хеш-функции. Итак, на первом этапе последовательно читаются строки внутреннего набора, и для каждои? из них вычисляется хеш-функция. Ключом хеширования в данном случае являются поля, участвующие в условии соединения (Hash Cond), а в самои? хеш-таблице сохраняются все поля строки из внутреннего набора, необходимые для запроса. Наиболее эффективно — за один проход по данным — соединение хешированием работает, если хеш-таблица целиком помещается в оперативную память. Отведенныи? еи? размер ограничен значением work_mem ? hash_mem_multiplier (значение последнего параметра по умолчанию равно 1.0). Вот пример, в котором запрос выполнен с помощью команды
В отличие от соединения вложенным циклом, для которого внутреннии? и внешнии? наборы существенно отличаются, соединение на основе хеширования позволяет переставлять наборы местами. Как правило, в качестве внутреннего используется меньшии? набор, поскольку это уменьшает размер памяти, необходимыи? для хеш-таблицы. Здесь объема памяти хватило для размещения всеи? хеш-таблицы, которая заняла около 143 Mбаи?т (Memory Usage) на 4 М = 222 корзин (Buckets). Соединение поэтому выполняется в один проход (Batches). Однако если бы в запросе использовался один столбец, для хеш-таблицы хватило бы 111 Мбаи?т:
Это еще одна причина не использовать в запросах лишние поля, в том числе «звездочку». Количество корзин хеш-таблицы выбирается так, чтобы в полностью загруженнои? данными таблице каждая корзина содержала в среднем одну строку. Более плотное заполнение повысило бы вероятность хеш-коллизии? и, следовательно, снизило бы эффективность поиска, а более разреженная хеш-таблица слишком неэкономно расходовала бы память. Рассчитанное количество корзин увеличивается до первои? подходящеи? степени двои?ки. (Если, исходя из оценки среднеи? «ширины» однои? строки, размер хеш-таблицы с расчетным количеством корзин превышает ограничение по памяти, используется двухпроходное хеширование.) До того, как хеш-таблица полностью построена, соединение хешированием не может начать возвращать результаты. На втором этапе (хеш-таблица к этому моменту уже готова) узел Hash Join обращается ко второму дочернему узлу за внешним набором строк. Для каждои? прочитаннои? строки проверяется наличие соответствующих еи? строк в хеш-таблице. Для этого хеш-функция вычисляется от значении? полеи? внешнего набора, входящих в условие соединения. Наи?денные соответствия возвращаются вышестоящему узлу. Для тренировки чтения «развесистых» планов можно посмотреть пример с двумя соединениями хешированием. Этот запрос выводит имена всех пассажиров и реи?сы, которые они бронировали:
Сначала соединяются билеты ( Оценка стоимости. Оценку кардинальности я уже рассматривал и она не зависит от способа соединения, поэтому дальше я буду говорить только об оценке стоимости. Стоимость узла Hash выставляется равнои? полнои? стоимости его дочернего узла. Это фиктивная цифра, просто чтобы было что показать в плане запроса. Все реальные оценки включены в стоимость узла Hash Join. Рассмотрим пример:
Начальная стоимость соединения отражает в основном создание хеш-таблицы и складывается из:
Полная стоимость соединения добавляет к начальнои? оценке стоимость собственно выполнения соединения:
Наиболее сложнои? частью оценки здесь является определение количества перепроверок, которые потребуются в ходе соединения. Это количество оценивается произведением числа строк внешнего набора на некоторую долю числа строк внутреннего набора (находящегося в хеш-таблице). Оценка учитывает в том числе и возможное неравномерное распределение значении?; я не буду вдаваться в подробности, а для данного примера оценка этои? доли равна 0,150112. Итак, для нашего примера оценка вычисляется следующим образом:
Двухпроходное соединение хешированием Если на этапе планирования оценки показывают, что хеш-таблица не поместится в отведенные рамки, внутреннии? набор строк разбивается на отдельные пакеты (batch), каждыи? из которых обрабатывается отдельно. Количество пакетов (как и корзин) всегда является степенью двои?ки; номер пакета определяется соответствующим количеством битов хеш-значения. Любые две строки, соответствующие друг другу при соединении, принадлежат одному и тому же пакету, поскольку у строк из разных пакетов не могут совпасть хеш-коды. К каждому пакету относится одинаковое количество хеш-значении?. Если данные распределены равномерно, то и размеры всех пакетов будут примерно одинаковыми. Потреблением памяти планировщик может управлять, выбирая подходящее количество пакетов так, чтобы каждыи? из них по отдельности поместился в память. На первом этапе выполнения читается внутреннии? набор строк и строится хеш-таблица. Если очередная строка внутреннего набора относится в первому пакету, она добавляется к хеш-таблице и остается в оперативнои? памяти. Если же строка относится к какому-либо другому пакету, она записывается во временныи? фаи?л — свои? для каждого из пакетов. Объем используемых сеансом временных фаи?лов на диске можно ограничить, установив предельное значение в параметре temp_file_limit (временные таблицы в это ограничение не входят). Если сеанс исчерпает ограничение, запрос будет аварии?но прерван. На втором этапе читается внешний набор строк. Если очередная строка принадлежит первому пакету, она сопоставляется с хеш-таблицеи?, которая как раз содержит строки первого пакета внутреннего набора (а в других пакетах соответствии? быть не может). Если же строка принадлежит другому пакету, она сбрасывается во временныи? фаи?л — опять же, свои? для каждого пакета. Таким образом, при N пакетах будет использоваться 2(N ? 1) фаи?лов (возможно меньше, если часть пакетов окажется пустыми). После окончания второго этапа память, занимаемая хеш-таблицеи?, освобождается. На этот момент уже имеется частичныи? результат соединения по одному из имеющихся пакетов. Далее оба этапа повторяются поочередно для каждого из сохраненных на диск пакетов. Из временного фаи?ла в хеш-таблицу добавляются строки внутреннего набора, затем из другого временного фаи?ла считываются и сопоставляются строки внешнего набора, соответствующие тому же пакету. Использованные временные фаи?лы удаляются, и процедура повторяется для следующего пакета, пока соединение не будет полностью завершено. Двухпроходное соединение в выводе команды
Я уже приводил этот пример выше, но с увеличенным значением work_mem. В 4 Мбаи?та по умолчанию вся хеш-таблица не помещается; здесь задеи?ствовано 64 пакета, хеш-таблица использует 64 К корзин. На этапе построения хеш-таблицы (узел Hash) выполняется запись во временные фаи?лы (temp written); на этапе соединения (узел Hash Join) фаи?лы и записываются, и читаются (temp read, written). Более детальную информацию о временных фаи?лах можно получить, установив параметр log_temp_files в нулевое значение: в журнале сообщении? сервера будет отмечен каждыи? фаи?л и его размер (на момент удаления фаи?ла). Динамическая корректировка плана Запланированныи? ход событии? могут нарушить две проблемы. Во-первых, неравномерное распределение. При неравномерном распределении значении? в столбцах, входящих в ключ соединения, разные пакеты будут иметь разное количество строк. Если большим окажется любои? пакет, кроме первого, все его строки придется сначала записать на диск, а затем прочитать с диска. Особенно это касается внешнего набора данных, потому что обычно он больше. Поэтому, если для внешнего набора строк доступна статистика по наиболее частым значениям (то есть внешнии? набор представлен таблицеи?, и соединение выполняется по одному столбцу — многовариантные списки не используются), то строки с хеш-кодами, соответствующими нескольким наиболее частым значениям, считаются принадлежащими первому пакету. Эта оптимизация (skew optimization) позволяет несколько уменьшить ввод-вывод при двухпроходном соединении. Во-вторых, некорректная статистика. Обе причины могут привести к тому, что размер некоторых (или всех) пакетов окажется больше расчетного, хеш-таблица для них не поместится в запланированныи? размер и выи?дет за рамки ограничении?. Поэтому, если в процессе построения хеш-таблицы выясняется, что ее размер не укладывается в ограничения, количество пакетов увеличивается (удваивается) на лету. Фактически каждыи? пакет разделяется на два новых: примерно половина строк (если предполагать равномерное распределение) остается в хеш-таблице, а другая половина сбрасывается на диск в новыи? временныи? фаи?л. Это может произои?ти и в том случае, когда планировалось однопроходное соединение. По сути, одно- и двухпроходное соединение — один и тот же алгоритм, реализуемыи? одним и тем же кодом. Я разделяю их только для удобства изложения. Количество пакетов может только увеличиваться. Если оказывается, что планировщик ошибся в бo?льшую сторону, пакеты не объединяются. Однако при неравномерном распределении увеличение числа пакетов может не помочь. Например, ключевои? столбец может содержать одно и то же значение во всех строках: очевидно, что все они попадут в один пакет, поскольку хеш-функция будет возвращать одно и то же значение. Увы, в таком случае хеш-таблица будет просто расти, невзирая на значения ограничивающих параметров. (Теоретически для такои? ситуации можно было бы применить многопроходное соединение, рассматривая за один раз только часть пакета, но это не реализовано.) Для демонстрации динамического увеличения количества пакетов придется приложить некоторые усилия, чтобы обмануть планировщик:
В результате этих манипуляции? у нас есть таблица В результате планировщик полагал, что будет достаточно 8 пакетов, но в процессе выполнения соединения их число выросло до 32:
Оценка стоимости. Вот тот же пример, на котором я показывал расчет стоимости для однопроходного соединения, но теперь я предельно уменьшаю размер доступнои? памяти, и планировщик вынужден использовать два пакета. Стоимость соединения при этом увеличилась:
К стоимости однопроходного соединения добавляются расходы, связанные с записью строк во временные фаи?лы и чтением их. К начальнои? стоимости добавляется оценка записи такого количества страниц, которое будет достаточно для сохранения нужных полеи? всех строк внутреннего набора. Хотя первыи? пакет и не записывается на диск при построении хеш-таблицы, это не учитывается в оценке, поэтому она не зависит от количества пакетов. К полнои? стоимости добавляется оценка чтения записанных ранее строк внутреннего набора и оценка сначала записи, а затем и чтения строк внешнего набора. И запись, и чтение однои? страницы оцениваются, исходя из последовательного характера ввода-вывода, значением параметра seq_page_cost. В данном примере количество страниц для строк внутреннего набора оценено как 7, а для внешнего — как 2309. Добавив оценки к стоимости, которая была получена выше для однопроходного соединения, получаем цифры, совпадающие со стоимостью в плане запроса:
Таким образом, при нехватке оперативнои? памяти алгоритм соединения становится двухпроходным и эффективность его падает. Поэтому важно, чтобы:
Соединение хешированием в параллельных планах Соединение хешированием может участвовать в параллельных планах в том виде, в котором я описывал его выше. Это означает, что сначала несколько параллельных процессов независимо друг от друга строят собственные (совершенно одинаковые) хеш-таблицы по внутреннему набору данных, а затем используют параллельныи? доступ к внешнему набору строк. Выигрыш здесь достигается за счет того, что каждыи? из процессов просматривает только часть внешнего набора строк. Вот пример плана с участием обычного (однопроходного в данном случае) соединения хешированием:
Здесь каждыи? процесс хеширует таблицу Ограничение на память под хеш-таблицу применяется к каждому параллельному процессу, так что суммарно будет выделено в три (в данном случае) раза больше памяти, чем это указано в плане (Memory Usage). Параллельное однопроходное хеш-соединение Несмотря на то, что и обычное соединение хешированием может давать определенную выгоду в параллельных планах (особенно в случае небольшого внутреннего набора, которыи? нет смысла обрабатывать параллельно), для больших наборов данных лучше работает специальныи? параллельныи? алгоритм хеш-соединения, доступный с версии PostgreSQL 11. Важное отличие от непараллельнои? версии алгоритма состоит в том, что хеш-таблица создается не в локальнои? памяти процесса, а в общеи? динамически выделяемои? памяти, и доступна каждому параллельному процессу, участвующему в соединении. Это позволяет вместо нескольких отдельных хеш-таблиц создать одну общую, используя суммарныи? объем памяти, доступныи? всем процессам-участникам. Благодаря этому увеличивается вероятность того, что соединение сможет выполниться за один проход. На первом этапе, представляемом в плане узлом Parallel Hash, все параллельные процессы строят общую хеш-таблицу, используя параллельныи? доступ к внутреннему набору строк. Чтобы можно было двигаться дальше, каждыи? из параллельных процессов должен завершить свою часть первого этапа. На втором этапе (узел Parallel Hash Join), когда хеш-таблица построена, каждыи? процесс сопоставляет с неи? свою часть строк внешнего набора, используя параллельныи? доступ. Вот пример такого плана:
Это тот же запрос, что я показывал в предыдущем разделе, но там параллельная версия хеш-соединения была специально отключена параметром enable_parallel_hash. Несмотря на то, что я уменьшил объем памяти под хеш-таблицу вдвое по сравнению с обычным хеш-соединением из предыдущего раздела, соединение осталось однопроходным за счет совместного использования памяти всех параллельных процессов (Memory Usage). Хеш-таблица занимает теперь немного больше памяти, однако она существует в единственном экземпляре, так что суммарное использование памяти уменьшилось. Параллельное двухпроходное хеш-соединение Даже совместнои? памяти всех параллельных процессов может не хватить для размещения всеи? хеш-таблицы. Это может стать понятно как на этапе планирования, так и позже, во время выполнения. В таком случае используется двухпроходныи? алгоритм, которыи? существенно отличается от всех уже рассмотренных. Важное отличие состоит в том, что используется не одна большая общая хеш-таблица, а каждыи? процесс работает со своеи? таблицеи? меньшего размера и обрабатывает пакеты независимо от других процессов. (Однако и отдельные хеш-таблицы располагаются в общеи? памяти, так что другие процессы могут получить к ним доступ.) Если уже на этапе планирования становится ясно, что одним пакетом не обои?тись, для каждого процесса сразу создается своя хеш-таблица. Если решение принимается во время выполнения, таблица перестраивается. Итак, на первом этапе процессы параллельно читают внутреннии? набор строк, разделяя его на пакеты и записывая эти пакеты во временные фаи?лы. Поскольку каждыи? процесс читает только свою часть строк внутреннего набора, ни один из них не построит полную хеш-таблицу ни для одного пакета (не исключая и первыи?). Полныи? набор строк любого пакета собирается только в фаи?ле, запись в которыи? ведут все параллельные процессы, синхронизируясь друг с другом. Поэтому, в отличие от непараллельнои? версии алгоритма и от параллельнои? однопроходнои? версии, в данном случае на диск сбрасываются все пакеты, включая первыи?. Когда все процессы закончили хеширование внутреннего набора, начинается второи? этап. В случае непараллельнои? версии алгоритма строки внешнего набора, относящиеся к первому пакету, сразу же сопоставляются с хеш-таблицеи?. Но в параллельнои? версии в памяти еще нет готовои? хеш-таблицы, а кроме того пакеты обрабатываются процессами независимо. Поэтому в начале второго этапа внешнии? набор строк читается параллельно, распределяется по пакетам и каждыи? пакет записывается в свои? временныи? фаи?л. В отличие от первого этапа, прочитанные строки не помещаются в хеш-таблицу и увеличение количества пакетов произои?ти не может. Когда все процессы закончили чтение внешнего набора данных, на диске имеется 2N временных фаи?лов, содержащих пакеты внутреннего и внешнего наборов. Затем каждыи? процесс выбирает один из пакетов и выполняет соединение: загружает внутреннии? набор строк в свою хеш-таблицу в памяти, читает строки внешнего набора и сопоставляет их со строками в хеш-таблице. Когда процесс завершает обработку одного пакета, он выбирает следующии? еще не обработанныи?. Когда необработанные пакеты заканчиваются, освободившии?ся процесс подключается к обработке одного из еще не завершенных пакетов, пользуясь тем, что все хеш-таблицы находятся в разделяемои? памяти. Такая схема работает лучше, чем одна большая общая хеш-таблица, которую совместно используют все процессы: проще организовать совместную работу, меньше ресурсов тратится на синхронизацию. Модификации Алгоритм соединения хешированием может использоваться не только для внутренних соединении?, но и для любых других типов: левых, правых и полных внешних соединении?, для полу- и антисоединении?. Однако, как я уже говорил, в качестве условия соединения допускается только равенство. Часть операции? я уже показывал на примере соединения вложенным циклом. Вот пример правого внешнего соединения:
Обратите внимание, как логическая операция левого соединения в SQL-запросе превратилась в физическую операцию правого соединения в плане выполнения. На логическом уровне внешнеи? таблицеи? (стоящеи? слева от операции соединения) являются бронирования ( На физическом уровне внешнии? и внутреннии? наборы данных определяются не по положению в тексте запроса, а исходя из стоимости соединения. Обычно это означает, что внутренним набором будет тот, чья хеш-таблица меньше. Так происходит и здесь: в качестве внутреннего набора выступает таблица бронировании?. Поэтому в плане выполнения тип соединения меняется с левого на правыи?. И наоборот, если в запросе указать правое внешнее соединение (желая вывести билеты, не связанные с бронированиями), то в плане выполнения тип соединения поменяется на правое:
И для полноты картины пример плана запроса с полным соединением:
В настоящее время параллельное соединение хешированием не поддерживается для правых и полных соединении? (но работа над этим ведется). Обратите внимание, что в следующем примере таблица бронировании? использована в качестве внешнего набора данных, хотя, если бы правое соединение поддерживалось, планировщик предпочел бы его:
Группировка и уникальные значения Группировка значении? для агрегации и устранение дубликатов могут выполняться алгоритмами, схожими с алгоритмами соединения. Один из способов состоит в том, чтобы построить хеш-таблицу по нужным полям. Каждое значение помещается в хеш-таблицу, только если его там еще нет. Таким образом в конечном итоге в хеш-таблице остаются только уникальные значения. В плане выполнения узел, отвечающии? за агрегацию методом хеширования, обозначается как HashAggregate. Вот несколько примеров ситуации?, в которых может использоваться такои? узел. Количество мест для каждого класса обслуживания (
Список классов обслуживания (
Классы обслуживания и еще одно значение (
Узел Append соответствует объединению двух наборов строк, но не удаляет дубликаты, как этого требует операция Память, выделяемая под хеш-таблицу, ограничена значением work_mem ? hash_mem_multiplier, как и в случае хеш-соединения. Если хеш-таблица помещается в отведенную память, агрегация выполняется за один проход (Batches) по набору строк, как в этом примере:
Уникальных значении? стоимости не так много, поэтому хеш-таблица заняла всего 61 Кбаи?т (Memory Usage). Как только во время построения хеш-таблицы новые значения перестают помещаться в отведенныи? объем, они сбрасываются во временные фаи?лы, распределяясь по разделам (partition) на основе нескольких битов хеш-значения. Количество разделов является степенью двои?ки и выбирается так, чтобы хеш-таблица для каждого из них поместилась целиком в оперативную память. Конечно, оценка зависит от качества статистики, поэтому расчетное значение умножается на полтора, чтобы еще уменьшить размер разделов и увеличить вероятность того, что каждыи? из них можно будет обработать за один раз. После того как весь набор данных прочитан, узел возвращает результаты агрегации по тем значениям, которые попали в хеш-таблицу. Затем хеш-таблица очищается и каждыи? из разделов, записанных на предыдущем шаге во временные фаи?лы, читается и обрабатывается точно так же, как обычныи? набор строк. При неудачном стечении обстоятельств хеш-таблица раздела может снова не поместиться в память; тогда «лишние» строки снова будут разбиты на разделы и записаны на диск для последующеи? обработки. В двухпроходном алгоритме соединения хешированием наиболее частые значения специальным образом переносятся в первыи? пакет, чтобы избежать ненужного ввода-вывода. Для агрегации такая оптимизация не нужна, поскольку на разделы разбиваются не все строки, а только те, которым не хватило отведеннои? памяти. Частые значения сами по себе с большои? вероятностью встретятся в наборе строк достаточно рано, чтобы успеть занять место.
В этом примере количество уникальных идентификаторов относительно велико, поэтому хеш-таблица не помещается в память целиком. Для выполнения запроса потребовалось пять итерации? (Batches): одна по начальному набору данных и еще четыре по каждому из записанных на диск разделов. Окончание следует. Источник: habr.com Комментарии: |
|