TL;DR: в конце есть резюме с ключевыми словами, выделенными жирным шрифтом

YugabyteDB использует планировщик запросов PostgreSQL, который является оптимизатором на основе затрат. По состоянию на версию 2.15 ANALYZE все еще находится в бета-версии, не запускается автоматически, и планировщик запросов полагается на некоторые эвристики для таблиц без статистики. Опытные DBA Oracle назвали бы это оптимизатором на основе ПРАВИЛ. Звучит слишком упрощенно? Помните, что YugabyteDB оптимизирована в первую очередь для OLTP, а в критических OLTP нагрузках вам не нужен слишком творческий оптимизатор. Вы можете посмотреть курс Энди Павло об оптимизаторах, чтобы понять, почему эвристика подходит для дорогостоящих OLTP-запросов.

Я быстро сравню две базы данных, одну SQL, Oracle Database, и одну NoSQL, DynamoDB, чтобы объяснить, что зависимость пути доступа от правил может быть хорошей особенностью. Основные OLTP-программы, которые я видел, работающие на Oracle, использовали RULE или, поскольку он уже давно устарел, его эквивалент, настраивая некоторые поправки на стоимость, чтобы заставить индексы и вложенные циклы, независимо от оценки кардинальности.

В DynamoDB отсутствие интеллектуального оптимизатора на основе затрат — это то, что разработчики действительно ценят. Стоимость запроса зависит только от типа запроса: Scan, Query или Get. Если вы знакомы с DynamoDB, вы можете перевести shard/sharding, используемый в этом посте, на partition/разделение, используемое в NoSQL базах данных. Нам нужно быть точными в терминах, потому что, помимо распределения по шардам, YugabyteDB добавляет декларативное разделение PostgreSQL для контроля гео-распределения или управления жизненным циклом.

Эвристики YugabyteDB очень похожи, и я опишу их с той же идеей. Они находятся в yb_scan.c, и я упомяну константы, используемые там.

Я проведу примеры на простой таблице с уникальным индексом на (a,b), который фактически является первичным ключом, и неуникальным вторичным индексом на (c,d).

drop table if exists demo;
create table demo (
   a int, b int
 , primary key(a,b)
 , c int, d int, e int
);
create index demo_cd on demo(c,d);

При отсутствии статистики ANALYZE, YugabyteDB устанавливает значение по умолчанию в одну тысячу строк (#define YBC_DEFAULT_NUM_ROWS 1000)

Сканирование таблицы

Полное сканирование таблицы считывает все строки, избирательность составляет 100% (#define YBC_FULL_SCAN_SELECTIVITY 1.0), поэтому оценка составляет rows=1000.

explain select * from demo;

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on demo  (cost=0.00..100.00 rows=1000 width=20)
(1 row)

Небольшое замечание о cost: стоимость одного кортежа — это YB_DEFAULT_PER_TUPLE_COST=10, умноженная на cpu_tuple_cost, которая по умолчанию равна 0.01, так что 0.1 за кортеж, без начальных затрат. Это объясняет cost=0.00..100.00 для rows=1000.

Обратите внимание, что предикаты, не относящиеся к ключевым столбцам, не меняют оценку, поскольку все строки сканируются в любом случае, даже когда фильтрация переносится в хранилище:

/*+ Set(yb_enable_expression_pushdown off) */
explain select * from demo where d=1;

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on demo  (cost=0.00..102.50 rows=1000 width=20)
   Filter: (d = 1)
(2 rows)

/*+ Set(yb_enable_expression_pushdown on) */
explain select * from demo where d=1;

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on demo  (cost=0.00..102.50 rows=1000 width=20)
   Remote Filter: (d = 1)
(2 rows)

С точки зрения вызовов DynamoDB, это было бы Scan. Здесь я сравниваю только распределенные схемы доступа — все остальное отличается, поскольку YugabyteDB — это распределенный SQL, ACID на всех узлах, тогда как DynamoDB — распределенное хранилище NoSQL с согласованностью по разделам. В Oracle Rule Base Optimizer это последний выбор (RBO Path 15: Full Table Scan)

Одиночный хэш-запрос

Первичный ключ был определен как primary key(a,b), что эквивалентно primary key(a hash, b asc):

yugabyte=> d demo
                Table "public.demo"
 Column |  Type   | Collation | Nullable | Default
--------+---------+-----------+----------+---------
 a      | integer |           | not null |
 b      | integer |           | not null |
 c      | integer |           |          |
 d      | integer |           |          |
 e      | integer |           |          |
Indexes:
    "demo_pkey" PRIMARY KEY, lsm (a HASH, b ASC)
    "demo_cd" lsm (c HASH, d ASC)

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

Расчетная кардинальность для эвристической модели затрат составляет 100 строк из 1000, что дает селективность 10% (#define YBC_HASH_SCAN_SELECTIVITY (100.0 / YBC_DEFAULT_NUM_ROWS)), поэтому оценка составляет rows=100:

explain select * from demo where a=1 ;

                                 QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..15.25 rows=100 width=20)
   Index Cond: (a = 1)
(2 rows)

С точки зрения вызовов DynamoDB, это будет Запрос, читающий коллекцию из одного раздела. В Oracle Rule Base Optimizer это последний вариант доступа по индексу (RBO Path 10-11: Range Search on Indexed Columns)

Запрос по одному ключу

Вторичные индексы YugabyteDB являются глобальными и могут быть уникальными или нет. Уникальный вторичный индекс — это то же самое, что и для первичного ключа. Но при неуникальном есть возможность запросить полный ключ, который возвращает несколько строк.

Расчетная кардинальность для эвристической модели затрат составляет между уникальным и неполным ключом 100 строк из 1000, что доводит селективность до 1% (#define YBC_SINGLE_KEY_SELECTIVITY (10.0 / YBC_DEFAULT_NUM_ROWS)), поэтому оценка составляет rows=10:

explain select * from demo where c=1 and d=1;

                              QUERY PLAN
----------------------------------------------------------------------
 Index Scan using demo_cd on demo  (cost=0.00..5.25 rows=10 width=20)
   Index Cond: ((c = 1) AND (d = 1))
(2 rows)

В терминах DynamoDB это все еще запрос. Разница в том, что в DDB вы должны запросить вторичный индекс явно, с последующим чтением. В базе данных SQL вы упоминаете таблицу, и планировщик запросов обратится к индексу, когда это будет быстрее, с сильной согласованностью. В Oracle Rule Base Optimizer это последний вариант доступа по индексу (RBO Path 8-9: Indexes with equality)

Получение одной строки

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

Тогда расчетная кардинальность составляет 1 строку из 1000, что дает селективность 0.1% (#define YBC_SINGLE_ROW_SELECTIVITY (1.0 / YBC_DEFAULT_NUM_ROWS)), поэтому оценка будет rows=1:

explain select * from demo where a=1 and b=1;

                              QUERY PLAN
-----------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..4.12 rows=1 width=20)
   Index Cond: ((a = 1) AND (b = 1))
(2 rows)

В терминах DynamoDB это было бы Get для одного элемента. Но здесь, поскольку это SQL, вам не нужно указывать, какой индекс. Имея условие равенства на ключевых столбцах, вы попадаете в нужную структуру. В Oracle Rule Base Optimizer это первый выбор, когда он доступен (RBO Path 4: Single Row by Unique or Primary Key).

Почему ANALYZE все еще находится в бета-версии в версии 2.15

Вот краткий обзор того, что мы увидели:

yugabyte=> explain select * from demo;
                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on demo  (cost=0.00..100.00 rows=1000 width=20)

yugabyte=> explain select * from demo where a=1 ;
                                QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..15.25 rows=100 width=20)
   Index Cond: (a = 1)

yugabyte=> explain select * from demo where c=1 and d=1;
                              QUERY PLAN
----------------------------------------------------------------------
 Index Scan using demo_cd on demo  (cost=0.00..5.25 rows=10 width=20)
   Index Cond: ((c = 1) AND (d = 1))

yugabyte=> explain select * from demo where a=1 and b=1;
                              QUERY PLAN
-----------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..4.12 rows=1 width=20)
   Index Cond: ((a = 1) AND (b = 1))

Я упомянул, что ANALYZE находится в бета-версии, и у вас будет предупреждение при его использовании. Давайте добавим один миллион строк и ANALYZE:

yugabyte=> insert into demo select n,n,n,n,n
           from generate_series(1,1000000) n;

INSERT 0 1000000

yugabyte=> analyze demo;

WARNING:  'analyze' is a beta feature!
LINE 1: analyze demo;
        ^
HINT:  Set 'ysql_beta_features' yb-tserver gflag to true to suppress the warning for all beta features.
ANALYZE

Теперь для оценки кардинальности следуйте формулам выше, применяя селективность, рассчитанную на 1000 строк, но теперь на 1000000 строк:

yugabyte=> explain analyze select * from demo;
                           QUERY PLAN
----------------------------------------------------------------
 Seq Scan on demo  (cost=0.00..100114.80 rows=1001148 width=20) (actual time=4.545..4064.165 rows=1000000 loops=1)

yugabyte=> explain analyze select * from demo where a=1 ;
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..11266.92 rows=100115 width=20) (actual time=0.815..0.817 rows=1 loops=1)
   Index Cond: (a = 1)

yugabyte=> explain analyze select * from demo where c=1 and d=1;
                                 QUERY PLAN
----------------------------------------------------------------------------
 Index Scan using demo_cd on demo  (cost=0.00..1255.43 rows=10011 width=20) (actual time=1.456..1.458 rows=1 loops=1)
   Index Cond: ((c = 1) AND (d = 1))

yugabyte=> explain analyze select * from demo where a=1 and b=1;
                                 QUERY PLAN
----------------------------------------------------------------------------
 Index Scan using demo_pkey on demo  (cost=0.00..119.13 rows=1001 width=20) (actual time=1.278..1.280 rows=1 loops=1)
   Index Cond: ((a = 1) AND (b = 1))

Это правильно для Seq Scan (100% селективность) и, возможно, других запросов с частичным ключом или полным неуникальным. Однако это завышенная оценка для уникального ключа, который всегда возвращает один ряд. Вы можете спросить, почему для него используется селективность 0,1%, а не фиксированное значение. Причина в том, что это правило применяется к списку столбцов без учета предиката, а также используется для where a=1 and b>1, что ближе к одноключевому запросу. Это причина, по которой ANALYZE все еще находится в бета-версии в 2.15 (ветка предварительного просмотра): вы можете иметь побочные эффекты для оценки стоимости при соединении с другими таблицами. Реальное использование таблиц ANALYZE’d происходит, когда оценка селективности основана на статистике столбцов. Описанная выше модель проста и подходит для OLTP-запросов и некоторых простых аналитических запросов. Более сложные запросы могут нуждаться в подсказках для получения правильного плана.

yb_enable_optimizer_statistics=on

В версии 2.14 (стабильная ветка), которая была выпущена на прошлой неделе, вы можете АНАЛИЗИРОВАТЬ свои таблицы (все еще в бета-версии) и установить yb_enable_optimizer_statistics=on, чтобы оценка кардинальности зависела от статистики столбцов, а не от эвристики. Я подробно расскажу об этом в других сообщениях, но, чтобы показать вам, что вы можете иметь точные оценки, вот то же самое, что и выше в 2.14:

Для моей демонстрационной таблицы оценки точны, потому что у меня есть уникальное значение для всех столбцов строки. Значит, оценка для предиката равенства в одном столбце равна единице. Без уникального значения оценка была бы меньше фактического числа, потому что нет статистики о корреляции между столбцами. Это будет исправлено при поддержке CREATE STATISTICS.

Это всего лишь модель

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

• Однострочные запросы должны иметь индекс, начинающийся с их столбцов, хэш-шардинг. Основным шаблоном доступа для точечных запросов должен быть первичный ключ. Он может читать все столбцы с помощью одного seek() в дереве LSM. Вы можете создать уникальные вторичные индексы для остальных и добавить в INCLUDE столбцы, которые вы хотите запросить без дополнительного перехода к таблице.
• Одноключевые запросы, возвращающие много строк, должны находить свой вторичный индекс, начиная с выборочных столбцов, HASH только для предикатов равенства или ASC/DESC для диапазонов. Именно здесь вы должны добавить выбранные столбцы в конец индексного ключа или в INCLUDE, чтобы сделать их охватывающими индексами. Эти запросы читают много строк: вы не хотите добавлять удаленный вызов к распределенной таблице для каждой записи индекса.
• Запросы Single Hash Queries не должны требовать дополнительных индексов, а использовать существующие первичные ключевые или покрывающие вторичные индексы. Их столбцы должны быть первыми в порядке индексированных столбцов.
• Сканирование таблиц — это хорошо, если вам нужно большинство строк из одного или нескольких шардов (ака планшетов), и не забудьте включить yb_enable_expression_pushdown, чтобы фильтры проталкивались в хранилище. Но если селективность высока, возможно, вам не хватает индексов диапазона для этих фильтров. Посмотрите на предикаты фильтров в плане выполнения.