#33: Query optimizations: эвристики и cost-based

[00:21] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. В сегодняшнем выпуске мы разберём один из самых сложных компонентов баз данных — оптимизатор запросов. Именно благодаря ему базы данных работают быстро. А ещё поговорим про параллелизм и поймём, почему некоторые базы данных пишут свой собственный уровень операционной системы для параллельного выполнения запросов. Это последний выпуск второго сезона подкаста «Тысяча фичей». Поехали!

[01:06] Чтобы понять, как работает оптимизатор запросов, нужно понять, с чем он работает. А работает он с планом запроса. В течение всего выпуска планом запроса я буду называть следующую структуру. Представьте, что у нас есть обычный запрос, для которого мы строим план. Сам запрос выглядит так: SELECT table1.id, table2.value FROM table1 JOIN table2 WHERE table1.value > 10. По сути, мы селектим две колонки — из первой таблицы и из второй, делаем JOIN двух таблиц по условию общего идентификатора и фильтрацию WHERE по одному из полей первой таблицы. То есть SELECT, JOIN и WHERE — три операции на двух таблицах. Довольно стандартный небольшой запрос.

[02:26] Для такого запроса база данных построит план. Логично сначала сделать фильтрацию, а потом читать, потому что у нас есть WHERE, в котором мы выполняем предикаты. И та таблица, над значением которой мы делаем предикат, перед тем как её считать, получит в плане ещё оператор «отфильтровать». Таким образом получается дерево, растущее сверху вниз: наверху проекция, потом JOIN, слева — просто вычитывание данных из таблицы, справа — фильтр плюс вычитывание данных из другой таблицы. Такой простенький план для относительно простого запроса. И когда я говорю «план запроса», мы представляем себе что-то подобное.

[03:02] Имея перед глазами этот план, мы понимаем, как по нему потекут данные. А потекут они снизу вверх, потому что внизу — операторы доступа к данным: sequential scan, index scan (про них поговорим). Это наши источники данных: они посылают данные наверх, где-то по дороге проходят фильтры, проходит JOIN, и JOIN возвращает самому верхнему оператору проекции какие-то тюплы, а те уже отображаются проекцией. То есть данные текут по этому дереву снизу вверх.

[03:39] И вообще говоря, течь они могут по-разному. Существует три способа передачи данных от нижних операторов, которые работают с таблицами и страницами, к верхним, которые делают JOIN, фильтры, агрегации, проекции. Первая — так называемая модель итератора. Думаю, многим она знакома, а если вы пишете на Java — тем более знаете паттерн «итератор». Это когда есть источник данных, какая-то коллекция, у которой глобально два метода в интерфейсе: «дай мне следующий элемент» (next) и «есть ли у тебя следующий элемент». Реализовать можно по-разному — например, возвращать null, если данных больше нет, и тогда метод останется один. Но суть в том, что у каждого оператора, у каждого актора внутри плана есть метод next, который дёргают родительские операторы, — так данные и текут снизу вверх. Верхний оператор проекции дёргает JOIN — говорит next. JOIN, в свою очередь, дёргает два своих оператора — next слева, next справа. Нижние операторы — там, где фильтр дёргает next у оператора доступа к данным, — вычитывают страницу, берут тюпл и возвращают наверх. Так данные по одному тюплу переходят снизу вверх.

[05:05] Большинство баз данных используют эту модель, потому что она самая очевидная, наивная и проверенная временем. Проблема модели итератора в том, что не всегда можно так работать с данными — не всегда получается процессить их в рантайме, как в стриминговой модели, один тюпл за другим. Например, когда в запросе есть ORDER BY: мы должны вернуть отсортированные данные, а значит — вычитать все данные, прежде чем начать возвращать результат клиенту. Стримить по одному next уже нельзя. Поэтому где-то наверху оператор, который делает агрегацию или сортировку, соберёт все эти next, next, next в одну коллекцию — в памяти или сдампленную на диск, — отсортирует, заново вычитает и вернёт наверх. То есть модель итераторов подходит не для всех запросов, но там, где подходит, её логично использовать.

[06:04] Есть вторая модель — материализации. По сути, это противоположность модели итераторов. Вместо того чтобы стримить данные по одному снизу вверх, нижние операторы сначала полностью вычитывают данные в память, собирают в коллекцию, а потом возвращают наверх — по одному или батчами, в зависимости от реализации. Таким образом данные на каждом этапе хранятся в оперативной памяти, операторы их держат. Это удобно, когда данные умещаются в оперативку: меньше оверхеда на вызовы функций и на координацию между операторами — мы выполняем одну большую операцию на каждом операторе и передаём результат наверх. Если таблички маленькие, скорее всего, будет использована именно эта модель.

[06:56] Вычитывать данные в память дорого, поэтому для оптимизации можно применять трюки. Например, pushdown — это когда информацию сверху плана мы передаём вниз, нижним операторам. Скажем, наверху может быть сказано, что у запроса LIMIT 10 и он не отсортирован — значит, нам нужно всего 10 записей. Но это знание живёт наверху, на уровне проекции, на уровне оператора SELECT; нижние операторы про LIMIT 10 ничего не знают. Или, например, что мы выбираем всего одну колонку из всей таблицы. Можно сделать pushdown, который передаст это знание сверху вниз, и нижние операторы вычитают всего 10 записей, а не всю таблицу в память, из которой потом возьмётся 10, — это неоптимально. Поэтому pushdown лимитов и pushdown проекций сильно оптимизирует модель материализации, сокращая объём используемой оперативной памяти, что всегда хорошо. Такие модели используются, например, в MonetDB или VoltDB.

[08:11] Но есть и третья модель — векторизации. По сути, это комбинация итераторов и материализации. Семантика итераторов next, next, next сохраняется, но next возвращает не один тюпл, а пачку тюплов, вектор. Так мы обрабатываем данные батчами. Почему это называется векторизацией? Потому что размер пачки можно рассчитать так, чтобы к ней применить векторизованные инструкции — так называемые SIMD-инструкции процессора — и за один процессорный такт высчитать какой-то предикат или выполнить операцию над вектором. Вместо того чтобы применять предикат к тюплам по одному в памяти, мы применяем векторизованную инструкцию сразу к вектору из нескольких тюплов. Эта модель очень распространена в аналитических базах данных — таких, как Snowflake или ClickHouse.

[09:14] С моделями процессинга вроде разобрались: мы понимаем, как данные передаются от одного оператора верхнему. Теперь опустимся немного вниз по плану и посмотрим на те самые нижние операторы, которые доступаются к данным. По сути, сейчас разберёмся в access-методах — методах доступа к данным, которые, кстати, не определены в реляционной алгебре: она вообще не говорит, как мы вычитываем данные. А работая с конкретной базой, мы понимаем, что способов считать данные на нижнем уровне несколько. Самый первый, очевидный и неоптимальный — sequential scan, иногда его называют full scan. По сути, это открытие курсора на таблицу, вычитывание страниц в buffer pool и обработка тюплов внутри каждой страницы один за другим в цикле, пока не закончатся все тюплы и все страницы. Мы просто итерируемся по всем страницам. Это самый неоптимальный вариант доступа, но иногда выбора не остаётся, и это единственный способ вычитать данные с диска — так что порой мы обязаны его использовать.

[10:20] И sequential scan тоже можно оптимизировать: несмотря на ужасный с точки зрения перформанса способ доступа, мы можем получить более-менее адекватную скорость. Какие оптимизации есть? Например, prefetching страниц, про который я рассказывал в предыдущем выпуске: мы знаем, что обрабатываем страницы последовательно, и можем в другом потоке сделать prefetch, чтобы не ходить за каждой страницей на диск. Ещё есть оптимизация buffer pool bypass — когда мы не используем buffer pool для страниц, вычитываемых full scan-ом, чтобы его не загрязнять. Представьте: есть запросы, которые действительно используют buffer pool по назначению — держат там индекс, внутренние страницы B+tree-индекса, и когда эти страницы в buffer pool, перформанс растёт. Но когда какой-то запрос делает full scan, он вычитывает страницу, один раз процессит тюпл, возвращает наверх — больше эта страница ему не нужна. А своим full scan он забьёт buffer pool, вымоет страницы, нужные индексу, и индекс начнёт перформить хуже. Вся система деградирует из-за того, что кто-то забил buffer pool нерелевантными страницами, которые вот-вот вытеснятся. Так зачем их туда вообще класть? Поэтому buffer pool bypass берёт страницы напрямую с диска, обрабатывает и выкидывает в обход buffer pool.

[11:56] Ещё одна оптимизация — параллельное считывание: создаём несколько воркеров, каждый делает full scan своего сегмента; тоже логично. Ещё можно, если не нужно сразу считать предикат на тюпл, сделать late materialization — не вычитывать само значение тюпла, а хранить только record id и манипулировать одними ключами; если так можно, это тоже хорошо. И самая интересная, на мой взгляд, оптимизация full scan — это data skipping, «пропуски данных» по-русски. Глобально есть два способа пропустить данные. Первый — приближённые запросы, так называемые approximate queries, которые поддерживают, например, Snowflake, Databricks, BigQuery. Мы можем попросить базу вернуть что-то неточно — например, среднее число каких-то записей по условию, — и база очень быстро вернёт приблизительный результат, посчитав его на сэмпле данных, а не на всём датасете. Если нас устраивает приблизительный ответ, это выполнится очень быстро.

[13:16] Вторая, более интересная группа оптимизаций точнее — она уже не приближённая, результат настоящий — называется zone maps. Zone maps — это когда внутри страницы мы держим предпосчитанные агрегаты для каждой колонки. Например, в странице лежат данные таблицы с полями id, возраст и пол; страница знает свою схему — и мы можем положить ей в заголовок максимальный возраст, минимальный, средний, количество мальчиков, девочек, людей с другим полом. Тогда все эти часто выполняемые агрегаты будут лежать в заголовке страницы, и нам даже не придётся вычитывать данные, если нужно посчитать только такой агрегат. Это супероптимизация: зная о ней, можно очень быстро считать грубые агрегаты, вообще не читая данные. Конечно, за это есть плата. Во-первых, при каждом обновлении данных надо пересчитывать агрегаты — добавлять, умножать, делить, — но это база делает за нас, мы как пользователи об этом не думаем. Во-вторых, размер страниц разрастётся, потому что агрегатов может быть много. Так что тут трейд-офф между размером страницы, временем вставки и скоростью чтения.

[14:43] Итак, мы поговорили про метод доступа sequential scan и ряд его оптимизаций. Но помимо него всегда есть способ лучше — я ведь говорил, что sequential scan худший. Так вот, это index scan. Думаю, вы догадались: index scan значит, что данные мы читаем из индекса. Если у нас, например, кластеризованный индекс и данные лежат прямо внутри него, это будет супербыстро: в индексе легко найти кусок данных, отвечающий нашему запросу (если индекс по возрасту), и вычитать только его — не всю таблицу, а только нужное. index scan — это супер. Помимо него есть multi-index scan: когда у нас несколько индексов и в условии, например, возраст больше 10 и пол «девочка», а индексы построены и на возраст, и на пол. Тогда мы вычитываем из индекса все записи с возрастом больше 10, все записи с полом «девочка», оба датасета кладём в память, как на кругах Эйлера соединяем по условиям, берём пересечение и возвращаем наружу. То есть одновременно вычитываем по двум индексам два датасета, а потом в памяти их соединяем. Такая оптимизация — если есть несколько индексов и по значениям в предикатах эти индексы построены.

[16:05] Помимо доступа к данным на чтение есть доступ на модификацию — мы можем апдейтить тюплы, добавлять новые. Тут свои правила и ограничения: например, при обновлении данных надо брать блокировки, обновлять индексы — это трейд-офф на доступ к индексу. Про то, как всё это менеджится — про конкаренси, лечи, блокировки, — я рассказывал в предыдущих выпусках. А тут, в контексте плана запроса и доступа, есть одна интересная штука. Допустим, есть таблица с полем salary (зарплата), и мы хотим всем, кто зарабатывает меньше 100 тысяч рублей, сделать надбавку 10 тысяч, чтобы они зарабатывали больше. Прикол в том, что мы найдём, например, запись человека с зарплатой 50 тысяч, добавим 10. Но что значит «добавим»? Мы не апдейтим тюпл in place в странице индекса — мы удаляем этот тюпл из индекса и добавляем заново, чтобы индекс перестроился правильно. Значит, найдя человека с зарплатой 50 тысяч, добавив до 60, потом обработав другие записи, мы можем снова прийти к той же записи, увидеть зарплату 60, добавить ещё 10, снова удалить и добавить, — и так до тех пор, пока зарплата не станет 100 тысяч и запись не перестанет удовлетворять условию. Очевидно, составляя запрос, мы такого не хотели — хотели один раз добавить 10 тысяч, и всё. Эта проблема в базах данных старая, называется Halloween Problem, и решается очень просто: мы трекаем id записей, обновлённых в текущем запросе. Да, это оверхед, интересная особенность, но по-другому вроде бы никак.

[17:59] Ещё из интересных оптимизаций, которые могут взорвать мозг — мне в своё время так и случилось, — это just-in-time-компиляция выражений. Выражение может быть таким: WHERE какое-то поле меньше значения AND другое поле больше другого значения. Такой WHERE-клоз по сути — if, и внутри execution engine он представляется деревом, на вершине которого висит оператор AND с двумя дочерними нодами: одна — «больше значения», другая — «меньше значения». Это дерево выражения каждый раз для каждого тюпла выполняется в памяти: специальный процесс проходит по дереву и интерпретирует его, принимая на вход тюпл и возвращая результат. Это, мягко говоря, не очень эффективно, и базы данных — например, Postgres — умеют делать just-in-time-компиляцию: понимают, что есть такой expression, компилируют его в C-функцию и применяют её непосредственно к каждому тюплу, что значительно ускоряет вычисление конкретного выражения. Интересная техника. Теперь вы знаете, что just-in-time-компиляцию делает не только JVM, но и базы данных. Про JIT мы ещё поговорим в будущем, когда пойдут распределённые базы данных, но Postgres такое умеет.

[19:19] Ещё одна огромная тема при разговоре про оптимизацию запросов — параллельное выполнение. Оно улучшает два показателя системы. Во-первых, растёт throughput: в один момент времени мы можем выполнить больше запросов. Во-вторых, снижается latency — среднее время ожидания клиента уменьшается, потому что мы быстрее обрабатываем запросы. Если бы всё выполнялось в один поток, запросы вставали бы в очередь, и каждый клиент ждал бы, пока выполнятся другие, — latency высокое. А при параллелизме latency снижается, что хорошо для клиента. При этом к параллельному плану есть строгое требование, которому база данных обязана следовать: параллельное выполнение запроса должно возвращать точно такой же результат, что и непараллельное. Ну, не прям один в один: если данные в запросе не отсортированы, порядок записей для параллельного и непараллельного планов может отличаться, — но с точки зрения логики, алгебры и корректности результаты будут валидны в обоих случаях.

[20:42] Говоря про параллельное выполнение, нужно осветить и такую тему, как распределённые базы данных — distributed-выполнение — против parallel-баз данных. Сегодня мы говорим про parallel. Чем они отличаются от distributed? В параллельных базах ресурсы физически очень близко друг к другу: на одном диске или на соседнем, на RAID-массиве, на одной машине; они соединены высокоскоростным интерконнектом. Проблем коммуникации нет — соединение надёжное и дешёвое. А в распределённых базах ресурсы находятся далеко друг от друга, реально на разных концах планеты, интерконнект медленный (сообщения могут идти под океаном), поэтому коммуникация между нодами очень дорогая, и мы не можем игнорировать её проблемы — например, обрыв интернета. Эти проблемы обсудим в следующем сезоне подкаста «Тысяча фичей». Сегодня — только параллельные базы данных.

[22:00] Почти все базы данных параллельны, так что я буду просто говорить «в базах данных». Есть несколько моделей выполнения кода, по сути три: процесс на воркер, тред на воркер и embedded. Что я имею в виду? Есть некоторый воркер внутри базы, который выполняет часть работы, часть запроса — так называемую таску. Воркер может быть отдельным процессом операционной системы, настоящим. Может быть тредом — абстракцией над процессом, которой управляет сама база данных, а не ОС. А embedded — это когда мы встраиваем базу в приложение, и уже приложение управляет многопоточностью. Сконцентрируемся на том, чем «процесс на воркер» отличается от «тред на воркер» и когда какая модель лучше.

[22:44] Один процесс на один воркер — модель, которая используется, например, в Postgres. Её особенность в том, что для шедулинга — управления процессами — используется операционная система, потому что это её собственные процессы, и там используется shared memory. И то и другое в контексте баз данных я бы назвал скорее негативными особенностями, потому что база данных, как мы потом поймём, знает больше. Некоторые базы данных имплементируют свой собственный уровень операционной системы для работы с тредами, чтобы умнее делать шедулинг и не использовать shared memory. Имея перед собой план выполнения запроса, база может понять, сколько задач нужно создать для его выполнения, сколько ядер задействовать, какой процессор взять, какой метод доступа к данным использовать, где хранить output. Эти детали помогают лучше зашедулить, лучше скоординировать воркеров. И когда у базы есть доступ к координации воркеров, эта модель — «тред на воркер» — скорее всего, лучше использует параллелизм, чем операционная система. Поэтому некоторые базы данных, например SQL Server, прямо имплементируют свой слой операционной системы: ОС вообще не знает, что там за среды используются, а система делает всё в обход неё.

[24:16] Как, например, можно зашедулить задачу в воркер? Самый банальный подход — точки остановки внутри задачи. Есть задача и условие, что каждая задача должна выполняться не более четырёх миллисекунд (по-моему, так в SQL Server и есть). Каждая задача перед тем, как запроцессить новый чанк своей работы, обращается к своему времени выполнения и смотрит: прошло ли четыре миллисекунды с момента, как меня вызвали? Если нет — продолжаю работать, процессить новый кусок данных. А если время вышло и я работаю больше четырёх миллисекунд — возвращаю управление координатору потоков, делаю так называемую операцию yield (в Python, по-моему, такой оператор есть). То есть мы возвращаем управление из своего треда в тред, который координирует запросы. И этот координирующий тред, получив управление, может понять, что таска работает уже достаточно долго, и заменить её другой, а эта посидит в очереди, подождёт. Так координация тасок происходит на уровне базы данных, а не операционной системы. Ну и про embedded-базы стоит пару слов сказать — это, например, RocksDB, WiredTiger или SQLite. Они встраиваются в клиентское приложение, и потоками там, конечно, управляет приложение — всё зависит от него.

[25:40] Вернёмся к параллельности — к параллельности планов и выполнения запросов. Как их вообще запараллелить? В самом термине «параллельное выполнение запросов» есть две перспективы. Первая — мы можем параллелить выполнение запросов, то есть выполнять несколько запросов в один момент времени на одной машине; это тоже параллельное выполнение, называется inter-query parallelization. Вторая — мы можем распараллелить сам запрос, то есть операторы внутри него могут быть распараллелены; это intra-query parallelization. И то и другое используется в современных базах данных. В плане каждый оператор обладает однопоточной и многопоточной версией. Например, JOIN: есть hash join, который можно делать в один поток, а можно использовать несколько тредов — тогда он называется parallel Grace hash join, когда каждый батч джойнится отдельным тредом. Довольно логичное распараллеливание такого оператора, как JOIN.

[26:39] Помимо JOIN можно, например, разделить входящий датасет на фрагменты и послать тредам работу над каждым независимым фрагментом. Скажем, full scan так и выполняется: делим данные на кусочки, каждый обрабатывается full scan-ом параллельно, а потом где-то наверху всё собирается и возвращается вышестоящему оператору. И оператор, который берёт данные next, next, next, даже не догадается, что работает с параллельным оператором, — интерфейс взаимодействия тот же. Операция соединения нескольких input-стримов в один output называется gather: мы соединяем результаты из многих воркеров, из многих потоков, в один output stream. Затем можно взять этот один input stream в каком-то операторе, сделать операцию distribute и получить много output-стримов — просто разбить данные на несколько чанков. И есть ещё вариант — repartition: берём много input-стримов, по какому-то условию перераспределяем их во много output-стримов. Это так называемый горизонтальный параллелизм.

[27:49] Есть ещё вертикальный параллелизм — про него расскажу, наверное, в следующем сезоне. Нужно знать, что он, скорее всего, хорошо подойдёт под pipeline, под real-time-обработку, под стриминг, потому что операторы могут быть соединены между собой и передавать друг другу кусочки данных. Но в контексте баз данных, которые мы сейчас рассматриваем — нераспределённых и не делающих стриминг, — нас интересует только горизонтальный параллелизм. Однако распараллелить запрос на десятки или сотни воркеров одновременно может быть как эффективно, так и наоборот. Почему? У нас может быть узкое место в виде диска, и тогда хоть один поток с ним работает, хоть десять — перформанс не меняется, а иногда даже становится хуже: чем больше запросов одновременно передаём диску, тем ему сложнее. Поэтому иногда непараллельная версия работает чуть быстрее параллельной. Решается это параллелизмом на уровне IO, на уровне дисков, чтобы много воркеров не стучались в одни и те же сегменты. Грубо говоря — партицирование таблицы по ключу и хранение партиций в разных директориях, в разных файлах, чтобы в один файл не обращалось много потоков. Или, например, храним одну базу данных в одной директории, другую — в другой; тогда сильная нагрузка на первую от распараллеленного запроса никак не отразится на второй — до тех пор, пока они не используют общий write-ahead log (тут уже ничего не сделаешь). Но на уровне файловой системы такой параллелизм тоже можно делать.

[29:32] Теперь немного поговорим о самой задаче нахождения оптимального плана. Мы рассмотрели техники, которыми его можно улучшить, — а как найти самый лучший план? Ведь потенциально планов может быть очень много. Проблема в том, что мы не можем выполнить каждый план и выбрать самый быстрый — это слишком ресурсоёмко; нужно, исходя из эвристик и какого-то анализа, понять, какой план сгенерировать для исполнения запроса. Доказано, что задача поиска оптимального плана является NP-полной. Другими словами, найти по-настоящему оптимальное решение за конечное время невозможно. Поэтому его никто и не ищет — ищут более-менее нормальное решение, которое не совсем плохое, если коротко.

[30:21] Чтобы погрузиться внутрь оптимайзера, надо представить, в какой момент он вызывается. Представим картину: к нам на сервер базы данных от приложения прилетает SQL-запрос. От микросервиса пришёл SQL — SELECT * FROM table WHERE id > 10 и ещё какой-нибудь JOIN с другой таблицей. Запрос пришёл, допустим, по TCP-соединению; мы вычитали массив байтов, интерпретировали его как строку — и вот видим наш SQL-запрос. Опционально мы можем передать его так называемому SQL-rewriter-у, который немного перезапишет саму строку — чаще всего идентификаторы таблиц, схем и то, как на них ссылаются, — на более удобный для дальнейшей оптимизации нейминг: не person и employees, как таблицы называются оригинально, а, например, table1, table2 и так далее. SQL-rewriter ничего не парсит; парсит уже следующий за ним парсер, который разбирает строку на некоторое внутреннее представление, скорее всего abstract syntax tree. Так же действуют компиляторы языков программирования и другие анализаторы структурных языков: они представляют входящую строку в виде дерева, на вершине которого один оператор, у него дочерние операторы — стандартное абстрактное синтаксическое дерево. Оно передаётся на вход так называемому байндеру.

[31:50] Байндер соединяет имена таблиц, идентификаторы вроде person, с их внутренними id. У системы есть так называемый системный каталог, который хранит, что вот эта таблица employees на самом деле имеет id, скажем, 1234. Внутри системы этот id используется всегда и везде — чтобы хранить данные, ссылаться на них и так далее, — а пользователю id использовать неудобно, поэтому есть такой маппинг: пользователь передаёт public.table1, а мы байндим его на конкретный id в момент процессинга. После того как мы переписали внутри абстрактного синтаксического дерева имена таблиц на id, передаём его так называемому tree-rewriter-у — rewriter-у дерева, который с помощью информации про схемы таблиц, зная, какие там данные, делает некоторые перезаписывания. Например, может развернуть SELECT * в SELECT с конкретными колонками всех участвующих таблиц: звёздочка — синтаксический сахар, облегчающий написание запроса, но потом она разворачивается, и вот тут как раз может развернуться. После этого дерево — где вместо имён id, где уже схема вместо звёздочек — передаётся оптимизатору. И тут начинается сама оптимизация. На вход оптимизатору идёт логический план: в нём нет конкретных деталей доступа к данным (index scan или full scan) — есть просто оператор чтения данных. А на выходе оптимизатор выдаёт физический план, в котором уже есть конкретные методы доступа, конкретные реализации JOIN (sort-merge join, hash join), multi-index-доступ и так далее. Этот физический план — результат работы оптимизатора; он идёт в execution engine и выполняется.

[33:47] Итак, мы разобрались, где находится оптимизатор запросов. Теперь разберёмся, как он находит оптимальный план и какие оптимизации может применять. Все оптимизации можно грубо разделить на две группы. Первая — эвристики: очевидные штуки, которые можно применить, не заглядывая внутрь реальных данных. То есть, просто глядя на план, мы понимаем, что вот здесь можно сделать оптимизацию, даже не зная, какие там лежат данные, много их или, может, там вообще одна запись, — нас это не интересует. Мы просто применяем эвристики, проверенные временем и логически понятные. Вторая группа — cost-based-оптимизации: те, что считают некоторую статистику, что-то знают про данные. Например, зная, что есть доступ по индексу и примерное количество записей в таблице, мы можем предугадать, что чтение этой таблицы займёт примерно 100 миллисекунд или 100 секунд, — просто зная размер таблицы, наш IO и способ доступа. Сначала рассмотрим эвристики, а потом cost-based-оптимизации.

[34:56] Какие эвристики можно применить к плану запроса? Их ещё называют логическими оптимизациями. Например, можно посмотреть, что у нас есть оператор WHERE — оператор фильтрации, — состоящий из множества условий: WHERE условие_1 AND условие_2 AND условие_3 OR условие_4. Это много условий по разным колонкам, по разным данным, и мы можем разбить их прямо в плане — из одного жирного условия в много маленьких по одной колонке. Насколько можно разбить, настолько и разбиваем. В чём фишка? Потом можно сделать predicate pushdown — опустить фильтрацию вниз; и чем гранулярнее фильтрация, тем точнее мы находим место и тем ниже её опускаем. Например, если сложное условие задействует три таблицы, то, чтобы его опустить, самая нижняя точка — та, которая вмещает данные из трёх таблиц, и данные придётся тянуть до этого предиката. А если разбить его на три и понять, что каждое отдельное условие относится к отдельной таблице, то эти маленькие условия можно опустить вниз, к самым нижним операторам, — и по плану потечёт намного меньше данных. Так что разбиение предикатов вместе с predicate pushdown — суперлогичная и крутая оптимизация, просто эвристика.

[36:27] Дальше можно, например, всякие перемножения множеств переписать как JOIN и сделать projection pushdown, про который я говорил в начале: те колонки, которые нужны наверху, можно спустить вниз — при вычитывании тюплов из страниц вернуть только нужные операторам вверху колонки, а ненужные не передавать наверх. В случае с columnar-сториджами, когда у нас колончатое представление данных, это суперэффективная оптимизация, она всегда используется, потому что тогда мы даже с диска не будем вычитывать ненужные колонки. А если у нас row store, посрочное представление, то даже с projection pushdown придётся физически вычитать тюпл в оператор, и оператор просто передаст наверх меньше данных, но с диска они всё равно вычитаны будут. В колончатом же виде ненужные колонки не будут вычитаны даже с диска.

[37:22] Какая ещё оптимизация может быть? Можно, например, декомпозировать subquery — так называемые подзапросы, — либо влить подзапрос и превратить его в JOIN, если это можно сделать на логическом уровне, на уровне плана: сделать такие трансформации с деревом. Либо можно записать результат подзапроса: понять, что он дёргается на каждую строчку и каждый раз выполняется, и вместо того чтобы выполнять его каждый раз, записать в отдельную временную таблицу (temporary table) и уже сверять результаты с ней. Тоже очевидная оптимизация. Например, если подзапрос содержит агрегат вроде SELECT max(age) FROM person, мы понимаем, что достаточно выполнить его один раз, достать максимальный возраст и потом просто переписать его внутри физического плана как конкретную циферку, а не выполнять каждый раз. Помимо подзапросов можно перезаписывать и экспрешены — условия внутри WHERE, если понимаем, что их можно перезаписать.

[38:32] Самая очевидная оптимизация WHERE-запроса — это когда на этапе просмотра логического плана мы понимаем, что условие всегда возвращает false, просто константа false. Например, 1 = 0. Мы понимаем, что 1 не равно 0, и на этапе оптимизации логического плана осознаём, что таблицу даже вычитывать не нужно: у нас предикат, который всегда false, и мы моментально, ничего не читая и не выполняя, возвращаем клиенту результат — пустое множество. Когда это возможно, так, естественно, всегда и делается — супероптимизация. Но прикол в том, что возможно это не всегда: иногда, даже если человек посмотрит и скажет «да здесь всегда false», оптимизатор может перестраховаться и всё-таки выполнить запрос. Так что в очевидных случаях оптимизация работает, а в неочевидных — скорее всего, нет. Помимо разделения предикатов, некоторые предикаты можно смержить. Например, если предикат на одну и ту же колонку одной и той же таблицы, какой-нибудь BETWEEN: h BETWEEN 10 AND 15 AND h BETWEEN 14 AND 20 — можно объединить в один h BETWEEN 14 AND 15. Таким образом будет на один оператор меньше, на один вызов функции меньше — тоже довольно очевидная оптимизация.

[39:47] Это мы поговорили про эвристики, про логические оптимизации. А теперь посмотрим, как на основе статистик и знаний о том, на каком железе бежит база данных, можно посчитать так называемый cost — по-русски, наверное, стоимость выполнения конкретного оператора — и уже на основе этих циферок понять, какой план лучший. Костов у нас несколько. Первый — физический кост: мы можем посчитать количество процессорных циклов на выполнение того или иного оператора, количество IO (обращений к диску), количество кэш-миссов, объём оперативной памяти, количество вызовов по сети и так далее. В некоторых случаях операторы могут эту статистику предоставить. Интересно, что некоторые базы данных перед стартом на конкретной машине — а все эти цифры сильно зависят от железа: на последнем макбуке будут одни значения использования оперативки, на моём стареньком i9-макбуке — совсем другие — с помощью микробенчмарков подкорректируют эти статистики и будут иметь нормальное представление о железе, на котором бегут. Но не все базы так умеют, и иногда эти цифры должны проставлять сами администраторы. Есть какие-то дефолты, работающие в среднем случае, но если хотите выжать максимум из базы и железа, лучше прописать все эти константы самому — если ваша база не делает микробенчмарки на старте.

[41:25] Помимо физических костов есть логические. Например, мы можем знать размер аутпута для каждого оператора. Если на какую-то таблицу навешен оператор, мы понимаем, что там примерно столько-то элементов, и можем прикинуть аутпут этого оператора — не используя predicate pushdown, ничего не используя, — посчитать количество данных, которые он вернёт, даже не исполняя его, просто примерно, и положить логическую стоимость оператора в виде количества возвращаемых элементов. Тоже вариант. И последний вариант костов — алгоритмическая сложность каждого оператора: по сути, сложность реализации алгоритма, который этот оператор представляет. У sort-merge join будет одна алгоритмическая сложность, у hash join — другая. Говоря о магических константах и о Postgres: там по дефолту считается, что работа с тюплом на уровне оперативной памяти в 400 раз быстрее, чем вычитывание того же тюпла с диска. Или, например, что sequential scan — последовательное чтение с диска — в 4 раза быстрее, чем random scan, когда мы читаем с диска рандомно. Такие вот интересные факты.

[42:39] Также базы данных собирают очень много статистики. Для каждой колонки каждой таблицы, скорее всего, будут посчитаны какие-то статистики — разные. Глубоко в них углубляться не будем, но, например, они могут отвечать на вопрос: сколько данных может заселектить вот этот предикат? Если есть статистика в виде гистограммы по таблице — скажем, таблица person и гистограмма по колонке возраста, — мы понимаем, что примерно 10 тысяч записей имеют возраст от 0 до 10, 20 тысяч — от 10 до 20, от 20 до 25 — 100 тысяч, от 25 до 30 — тоже около 110 тысяч. То есть мы знаем количество записей по каждому условию этой колонки. И если предикат «возраст меньше 10», мы можем сказать, что его selection cardinality — то, сколько данных он вернёт — довольно низкая, потому что по статистике возраст меньше 10 — самое маленькое значение: хоть таблица и большая, там всего 10 тысяч таких записей. Эту информацию можно использовать наверху.

[43:46] Помимо гистограмм есть ещё разные структуры данных, статистики, которые называются скетчами. Это может быть, например, среднее количество записей в бакете — оно работает довольно быстро. Мы ведь понимаем, что, высчитывая косты, не можем позволить себе посчитать количество записей в таблице full scan-ом: это глупо — мы бы оптимизировали запрос, выполняя самый долгий способ. Нам нужен быстрый ответ, пусть даже примерный; поэтому структура данных типа HyperLogLog — вероятностная, наподобие Bloom-фильтра — может очень быстро и довольно близко сказать, сколько записей внутри таблицы. Вся эта статистика, конечно, используется внутри оптимизатора, чтобы понять, какой план будет самым оптимальным. Ещё может использоваться не гистограмма и не скетч, а full scan — просто сэмпл данных, небольшой сабсет, более-менее отражающий реальную таблицу; на нём можно прогнать кусочек оператора, чтобы посчитать его стоимость и экстраполировать поведение на реальные данные — примерно оценить, насколько быстро оператор работает.

[44:57] Теперь мы понимаем, что оптимизатору нужно учесть очень много аспектов, и построение оптимального — а точнее, просто нормального — плана является очень сложной задачей, и базы данных строят их по-разному. В этом плане какие-то коммерческие базы данных, заточенные узко, в которые влили больше денег, чем в опенсорсные, скорее всего, будут лучше, потому что нужно очень много мозгов, инженеров и усилий, чтобы создать оптимальный план, используя всю ту информацию, которую мы обговорили. И, конечно, многое мы упустили, не рассмотрели, — потому что просмотреть все возможные оптимизации в одном подкасте было бы самоубийством; думаю, это вообще топик для отдельной книги, если не для серии книг.

[45:48] На этом выпуск подошёл к концу. Сегодня мы разобрались, как базы данных оптимизируют запросы. Мне кажется, самый главный вывод этого выпуска — оптимизация запросов очень сложная задача. Если мы хотим выжать максимум из системы, необходимо глубоко разбираться в том, как она работает. Надеюсь, что второй сезон подкаста «Тысяча фичей» помог вам систематизировать знания, а возможно, и узнать что-то новое. Впереди новый сезон — про распределённые базы данных. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!