Объяснение мема Postgres - Уровень 6: Зона ультраабиссали
Добро пожаловать в зону ультраабиссали! По мере достижения экстремальных глубин мы будем обсуждать различные специализированные темы PostgreSQL, о которых Вы, скорее всего, даже и не догадывались!
Векторизованный - не значит SIMD
SIMD расшифровывается как "Single instruction, multiple data" и представляет собой тип параллельной обработки, когда одна инструкция процессора одновременно применяется сразу к нескольким различным потокам данных.
Термины "вектор" и "векторизованный" в компьютерной литературе обычно сопровождаются термином "SIMD". Векторное программирование (оно же программирование массивов) относится к решениям, позволяющим применять операции сразу к целому набору значений. Собственно говоря, набор инструкций, который был добавлен в архитектуру набора инструкций x86 для реализации SIMD, называется Advanced Vector Extensions (AVX).
SIMD - это один из подходов к использованию векторных вычислений, но далеко не единственный. При этом, векторы PostgreSQL поддерживаются инструкциями SIMD .
NULL равны в DISTINCT, но не равны в UNIQUE
Предположим, у Вас есть таблица unique_items:
create table unique_items(item text unique);
PostgreSQL не позволит вставить дублирующиеся значения 'hi', так как это будет нарушать ограничение уникальности:
insert into unique_items values ('hi');
-- INSERT 0 1
-- Query returned successfully in 89 msec.
insert into unique_items values ('hi');
-- ERROR: duplicate key value violates unique constraint "unique_items_item_key"
-- DETAIL: Key (item)=(hi) already exists.
Однако мы можем вставить столько null, сколько только захотим:
insert into unique_items values (null); -- INSERT 0 1; Query returned successfully insert into unique_items values (null); -- INSERT 0 1; Query returned successfully insert into unique_items values (null); -- INSERT 0 1; Query returned successfully table unique_items; -- item -- -- "hi" -- `null` -- `null` -- `null`
Это означает, что для SQL null значения не являются одинаковыми, так как это неизвестные значения.
Теперь, если мы select distinct отдельные элементы таблицы unique_items, то получим следующий результат:
select distinct item from unique_items; -- item -- -- `null` -- "hi"
Все null значения отображаются как один элемент, как если бы PostgreSQL сгруппировал все неизвестные значения в одно значение.
Модель Volcano
"Volcano - расширяемая и параллельная система оценки запросов" - научная статья Гетца Графе, опубликованная в журнале IEEE Transactions on Knowledge and Data Engineering в феврале 1994 года. Эта система оценки называется моделью Volcano, моделью итераторов Volcano, или иногда просто моделью итераторов.
Каждый реляционно-алгебраический оператор порождает поток кортежей, и потребитель может итерировать входные потоки. Интерфейс кортежного потока состоит, по сути, из следующих элементов: open, next и close; все операторы предлагают один и тот же интерфейс, а его реализация непрозрачна.
Каждый вызов next создает новый кортеж из потока, если он доступен. Для получения выходных данных запроса необходимо выполнить "next-next-next" на конечном операторе RA, который, в свою очередь, будет использовать "next" на своих входах для получения кортежей, позволяющих ему производить выходные кортежи, и т.д. Некоторые "next" займут очень много времени, так как потребуется выполнить много "next" на предыдущих операторах, прежде чем они выдадут какой-либо выход.
Пример: select max(v) from t может потребовать перебора всего t, чтобы найти этот самый максимум.
Упрощенный псевдокод итерационной модели Volcano: define volcano_iterator_evaluate(root): q = root // operator `q` is the root of the query plan open(q) t = next(q) while t != null: emit(t) // ship current row to application t = next(q) close(q)
Аннотация к статье:
«Для исследования взаимодействия расширяемости и параллелизма в обработке запросов к базам данных мы разработали новую систему выполнения запросов на основе потока данных под названием Volcano. Система Volcano представляет собой обширную среду для исследований и обучения в области проектирования систем баз данных, оптимизации запросов, параллельного выполнения запросов и распределения ресурсов. Volcano использует стандартный интерфейс, что позволяет легко добавлять новых операторов и их реализации. Операции над отдельными элементами, например, предикатами, импортируются в операторы обработки запросов с помощью вспомогательных функций.
В состав Volcano входят два новых метаоператора. Метаоператор choose-plan поддерживает динамические планы оценки запросов, позволяющие откладывать принятие отдельных оптимизационных решений до времени выполнения, например, для встраиваемых запросов со свободными переменными. Метаоператор exchange поддерживает внутриоператорный параллелизм на разделенных наборах данных, а также вертикальный и горизонтальный межоператорный параллелизм, позволяющий организовать поток данных по запросу внутри процессов и поток данных между процессами. Все операторы, за исключением оператора обмена, были разработаны и реализованы в однопроцессной среде и распараллелены с помощью оператора обмена. Даже еще не разработанные операторы могут быть распараллелены с помощью этого нового оператора, если они используют и предоставляют интерфейс interator. Таким образом, Volcano является первым механизмом выполнения запросов, эффективно сочетающим расширяемость и параллелизм.
Дополнительная информация: Volcano-расширяемая и параллельная система оценки запросов
Упорядочивание Join – NP-трудная задача
Когда в SQL-запросе имеется несколько join, механизму базы данных необходимо найти порядок их выполнения. Поиск оптимального порядка выполнения join является NP-трудной задачей. Поэтому для поиска порядка их выполнения используются оценки и статистика, так как поиск оптимального решения займет бесконечное количество времени.
Это упрощенная таблица классов задач:
|
Класс проблемы |
Проверка решений |
Поиск решений |
Пример |
|
P |
легко |
легко |
умножение чисел |
|
NP |
легко |
сложно |
8 королев |
|
NP-трудная |
сложно |
сложно |
Лучший следующий ход в шахматах |
NP-трудные задачи по крайней мере столь же трудны, как и самые трудные задачи в NP. Это означает, что если P ≠ NP (что, вероятно, так и есть, по крайней мере, в настоящее время), то NP-трудные задачи не могут быть решены за полиномиальное время.
“Если бы P=NP, то мир был бы совершенно иным, чем мы его представляем. Не было бы никакой особой ценности в "творческих скачках", никакого фундаментального разрыва между решением проблемы и осознанием решения после того, как оно было найдено. Каждый, кто мог бы оценить симфонию, был бы Моцартом; каждый, кто мог бы следовать пошаговому аргументу, был бы Гауссом; каждый, кто мог бы распознать хорошую инвестиционную стратегию, был бы Уорреном Баффетом".
Скотт Ааронсон
Cracking
Cracking - это техника, которая переносит затраты на обслуживание индекса с обновлений на обработку запросов. Эта техника позволяет уменьшить время доступа к данным.
Другими словами, cracking в случае баз данных - это подход к индексированию данных и поддержанию индексов в самоорганизованном состоянии. В системе баз данных, где используется cracking, входящий запрос, запрашивающий все элементы, удовлетворяющие некоторому условию, не только возвращает результат, но и вызывает перестройку физической базы данных таким образом, чтобы все элементы, удовлетворяющие условию, хранились в смежном пространстве памяти. Таким образом, физическая база данных разделяется на множество частей (и ставится cracked).
С помощью этого механизма база данных реорганизуется наиболее благоприятным образом в соответствии с возлагаемой на нее нагрузкой.
Дополнительная информация: Cracking, автор Дэвид Вернер
WCOJ
Традиционные алгоритмы бинарных соединений, такие как хэш-соединение, работают с двумя отношениями одновременно (r1 join r2); соединения между более чем двумя отношениями реализуются путем многократного применения бинарных соединений (r1 join (r2 join r3)).
WCOJ (Worst-Case Optimal Join) - это такой алгоритм объединения, время выполнения которого оптимально в худшем случае для всех запросов объединения и асимптотически быстрее в худшем случае по сравнению с любым другим алгоритмом объединения, основанным на итерированных бинарных объединениях.
Дополнительная информация: WСOJ
Learned Index
Обучаемые индексы - это стратегии индексирования, в которых используются подходы искусственного интеллекта и модели глубокого обучения, позволяющие превзойти оптимизированные для кэша B-деревья и снизить потребление памяти. Инженеры Google и Массачусетского технологического института разработали такую модель и опубликовали свою работу в виде новаторской статьи под названием "The Case for Learned Index Structures". Основная идея заключается в том, что модель может изучить порядок сортировки или структуру ключей поиска и использовать этот сигнал для эффективного предсказания положения или существования записей.
Дополнительная информация: Learned Index
TXID
Transaction ID Exhaustion или "Wraparound Problem" (Переполнение счетчика транзакций) возникает из-за ограниченного количества доступных идентификаторов транзакций и отсутствия регулярного обслуживания базы данных с помощью Vacuum.
Семантика транзакций MVCC в PostgreSQL зависит от возможности сравнения номеров идентификаторов транзакций (XID): версия строки с XID вставки больше, чем XID текущей транзакции, находится "в будущем" и не должна быть видна текущей транзакции. Но поскольку идентификаторы транзакций имеют ограниченный размер (32 бита), то в кластере, работающем длительное время (более 4 млрд. транзакций), может произойти "сворачивание" идентификатора транзакции: счетчик XID сворачивается до нуля, и вдруг транзакции, которые были в прошлом, оказываются в будущем, то есть их вывод становится невидимым. Короче говоря, происходит катастрофическая потеря данных. (На самом деле данные все еще есть, но это слабое утешение, если Вы не можете до них добраться).
Чтобы избежать этого, необходимо выполнять vacuum для каждой таблицы в каждой базе данных по крайней мере раз в два миллиарда транзакций.
Дополнительная информация: Рутинный Vacuum: как не довести ситуацию до Transaction ID Wraparound
Далее: Уровень 7: Зона черной дыры: NULL, проблема Хэллоуина, fsyncgate, ...
