# Оптимизатор на основе стоимости

Когда Manticore выполняет полносканирующий запрос, он может либо использовать простой скан для проверки каждого документа с учётом фильтров, либо применять дополнительные данные и/или алгоритмы для ускорения выполнения запроса. Manticore использует оптимизатор на основе стоимости (CBO), также известный как «оптимизатор запросов», для определения подходящего способа.

CBO также может улучшать производительность полнотекстовых запросов. Подробнее см. ниже.

CBO может решить заменить один или несколько фильтров запроса одним из следующих элементов, если он определит, что это улучшит производительность:

1. **Индекс docid** использует специальный вторичный индекс только по docid, хранящийся в файлах с расширением `.spt`. Помимо улучшения фильтрации по числовым ID документов, индекс docid также используется для ускорения сопоставления ID документа с ID строки и для более быстрой обработки больших killlist при запуске демона.
2. **колоночное сканирование** опирается на колоночное хранение и может использоваться только на колоночном атрибуте. Оно сканирует каждое значение и проверяет его по фильтру, но при этом сильно оптимизировано и обычно быстрее подхода по умолчанию.
3. **вторичные индексы** создаются по умолчанию для всех атрибутов (кроме JSON). Они используют [PGM индекс](https://pgm.di.unipi.it/) вместе с встроенным инвертированным индексом Manticore для получения списка идентификаторов строк, соответствующих значению или диапазону значений. Вторичные индексы хранятся в файлах с расширениями `.spidx` и `.spjidx`.
Для информации о том, как создавать вторичные индексы по JSON атрибутам, см. [json_secondary_indexes](../Creating_a_table/Local_tables/Plain_and_real-time_table_settings.md#json_secondary_indexes).

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

1. Информацию о распределении данных внутри атрибута (гистограммы, хранящиеся в файлах `.sphi`). Гистограммы создаются автоматически при индексации данных и служат основным источником информации для CBO.
2. Информацию от PGM (вторичных индексов), которая помогает оценить количество списков документов для чтения. Это помогает оценить производительность объединения doclist и выбрать подходящий алгоритм слияния (слияние с приоритетной очередью или слияние битмапов).
3. Статистику кодирования колонок, используемую для оценки производительности декомпрессии колоночных данных.
4. Колоночное дерево min-max. В то время как CBO использует гистограммы для оценки количества документов, остающихся после применения фильтра, он также должен определить, сколько документов фильтр пришлось обработать. Для колоночных атрибутов частичная оценка min-max дерева служит этой цели.
5. Полнотекстовый словарь. CBO использует статистику терминов для оценки стоимости вычисления полнотекстового дерева.

Оптимизатор вычисляет стоимость выполнения для каждого фильтра, используемого в запросе. Поскольку некоторые фильтры можно заменить несколькими разными сущностями (например, для числового ID документа Manticore может использовать обычный проход, обращение к индексу docid, колоночный проход (если ID документа хранится в колонках) и вторичный индекс), оптимизатор оценивает все доступные комбинации. Однако максимальный предел составляет 1024 комбинации.

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

Оптимизатор сравнивает стоимости каждого пути выполнения и выбирает путь с наименьшей стоимостью для выполнения запроса.

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

Ещё один фактор — многопоточное выполнение запросов (когда включён `pseudo_sharding`). CBO знает, что некоторые запросы могут выполняться в нескольких потоках, и учитывает это. CBO отдаёт предпочтение более короткому времени выполнения запроса (то есть задержке) по сравнению с пропускной способностью. Например, если запрос с использованием колоночного сканирования может быть выполнен в нескольких потоках (и занять несколько ядер CPU) и при этом быстрее, чем запрос, выполненный в одном потоке с использованием вторичных индексов, будет предпочтительным многопоточное выполнение.

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

На данный момент оптимизатор учитывает только затраты CPU и не принимает во внимание использование памяти или диска.

<!-- proofread -->

