Общий pipeline SELECT-запроса

В этом разделе рассматривается общий алгоритм выполнения SELECT-запросов. Аналогичная логика применяется и для UPDATE/DELETE (за исключением части подготовки). Описание актуально для v3.15.0 и v4.11.0 и относится только к core-части выполнения (то есть на затрагивает логику проксирования при шардинге или raft-кластеризации).

Предвыборки (preselect)

На первом этапе происходит взятие read-блокировок на требуемые неймспейсы и обработка joined-запросов. Тайминги выполненных здесь операций попадают в explain_preselect. Блокировки неймспейсов берутся не одновременно, а по мере необходимости.

Для каждого JOIN оценивается максимально возможное количество документов в joined-подзапросе. Оценка производится по одному из индексов (с наименьшим ожидаемым числом итераций). По результатам оценки может быть 3 варианта:

  1. Если joined-подзапрос по одному из условий возвращает менее 200 документов, будет использован method: preselected_values. Это означает, что все документы, соответсвующие запросу, будут сохранены в буфер, а блокировка на целевой неймспейс будет отпущена сразу после заверешения preselect’a.

  2. Если joined-подзапрос по одному из условий возвращает менее 20000 документов и нет условия, по которому бы он возвращал 200 или менее, будет использован method: preselected_rows. Это означает, что в качестве результатов будут сохранёны только итераторы, соответсвующие запросу, но не сами значения. В дальнейшем эти итераторы будут использованы для пересечения с результатами основного запроса.

  3. Если joined-подзапрос не содержит условий, по которым было бы возвращено 20000 документов или менее, preselect использован не будет (method: no_preselect). В этом случае будут сохранены только итераторы, а их пересечение будет выполняться после завершения остальных выборок основного запроса. В этом случае выполнение joined-подзапроса будет вызвано для каждого документа, вошедшего в результаты фильтрации. Это наименее оптимальный метод join’а из доступных.

Предвыборка/выборка по joined-подзапросам выполняется по той же логике, что и выборка по основному запросу. В случае, если method имеет значение preselected_values или preselected_rows, explain joined-подзапроса будет сохранён в поле explain_preselect. Для method: no_preselect и method: preselected_rows в explain будет также заполнено поле explain_select - туда попадает explain первого joined-подзапроса по конкретному документу.

Выборка по основному запросу

Prepare

Здесь происходит разбор запроса и его преобразование/оптимизация.

  1. При наличии joined-подзапросов reindexer пытается перенести условие из ON внутрь WHERE исходного запроса. Для этого выполняются дополнительные запросы к joined-неймспейсам с Distinct (если в ON испольнуется ==/IN()) или с MAX()/MIN() (если в ON используются операторы </>/<=/>=). В результате получается ещё одно условие для WHERE, чтобы улучшить общую селективность и снизить риск ситуаций, когда потребуется выполнить INNER JOIN для большого числа документов, которые не подходят под условие ON. Ограничения для этой оптимизации настраиваются через параметры min_preselect_size, max_preselect_size и max_preselect_part.

  2. В запрос добавляются сущности, связанные с аггрегациями (в частности distinct).

  3. В несколько итераций (столько раз, сколько возможно) применяются следующие оптимизации:

    • раскрытие скобок;
    • дедубликация условий (объединяются схожие условия по одному и тому же индексу);
    • подстановка композитных индексов. Для операций == и IN() вместо нескольких обычных индексов подставляется один композитный, состоящий из тех же полей.

  4. Приведения значений, переданных в WHERE, к типам индексов, к которым они относятся.

Подготовка итераторов (indexes)

Подготовка сортировок

Если порядок сортировки задан явно, то будет выбран подходящий для этого tree-индекс, если он есть в запросе. При этом, если по tree-индексу присутствуют условия IN() с несколькими значениями или IS NULL, то этот индекс не будет использоваться для сортировки.

Если явная сортировка не задана, но в запросе есть условия </>/<=/>=/range по tree-индексу, тогда будет сгенерировано условие сортировки по подходящему tree-индексу с наибольшей селективностью (с наибольшим числом уникальных значений). Это условие добавляется для того, чтобы результаты выборки по возможности имели консистентный порядок.

Если явная сортировка не задана и при этом найти подходящий tree-индекс не удалось, результаты будут отсортированы в порядке увеличения значения внутреннего id документа. Явная сортировка для этого не применяется. Упорядочивание обеспечивается логикой обхода итераторов.

Выборка из индексов

Последовательно для каждого из условий запроса осуществляется выборка из соответсвующего индекса. После каждой выборки обновляется значение maxIterations - максимальное число итераций в select loop, равное размеру наименьшей выборки из одного индекса.

Сами индексы представляют из себя иерархическую структуру.

IndexStore (’-')

Базовый индекс. Выполняет задачу хранения значений и дедубликации строк. Также наличие store-индекса на поле гарантирует быстрый доступ к значению этого поля в компараторах. Не даёт никаких возможностей выборки кроме компараторов. Является базовой частью любого другого индекса.

Использование компаратора обозначает, что вместо слияния упорядоченных наборов внутренних id будет явная проверка полей документа на соответсвие условию фильтрации. В случае с IndexStore reindexer заранее знает смещение индексного значения в документе, поэтому компаратор для IndexStore (или любого другого индекса) будет работать в несколько раз быстрее, чем компаратор с использованием не индексного поля.

Также он необходим для создания композитных индексов поверх этого поля (нельзя создать композитный индекс поверх неиндексного поля).

IndexUnordered (‘hash’)

Наследуется от IndexStore.

Обеспечивает возможность быстрой выборки для условий IN(), ==, IS NULL, ALLSET при помощи хэш-таблицы.

  • Условия <, >, <=, >=, range всегда работают через компараторы (в explain будет scan).

  • Условия IS NULL, ALLSET всегда работают через индекс (в explain будет index).

  • Условия IN() и == могут работать как через индекс, так и через компаратор. Reindexer сам определяет, какой метод будет на его взгляд более эффективным. Компаратор будет использоваться, если выполняется одно из условий:

    1. Количество выбранных документов превышает 30% от общего числа документов в неймспейсе и количетсво полученных IdSet’ов больше одного (каждое значение в условии будет соответствовать не более чем 1 IdSet’у).
    2. Число ключей для выборки более чем в 8 раз превышает текущее значение maxIterations и в данном условии нет distinct.
    3. Количество выбранных документов более чем в 2 раза превышает текущее значение maxIterations и количетсво полученных IdSet’ов больше одного (каждое значение в условии будет соответствовать не более чем 1 IdSet’у).

  • Условие IS NOT NULL работает через индекс, если оно используется для distinct и сам индекс содержит не более 500 уникальных ключей. В остальных случаях оно порождает компаратор.

IndexOrdered (’tree')

Наследуется от IndexUnordered.

Обеспечивает возможность быстрой выборки для условий <, >, <=, >=, range при помощи B-tree. Выборка выполняется при помощи b-tree в том случае, если верно одно из условий:

  • Для текущего индекса не произведена фоновая оптимизация и этот индекс используется для сортировки.
  • Для текущего индекса произведена фоновая оптимизация, этот индекс используется для сортировки и это не distinct условие.
  • Выбранный диапазон содержит не более 50 уникальных значений.

Для остальных условий использует нижележащие IndexUnordered и IndexStore.

FastIndexText (’text')

Наследуется от IndexUnordered.

Существует 2 сценария выборки по индексам этого типа:

  1. Если в настройках индекса enable_preselect_before_ft: false, тогда выборка по полнотекстовому индексу всегда будет производиться до выборки по всем остальным. В этому случае все остальные фильтры будут обработаны через компараторы.

  2. Если в настройках индекса enable_preselect_before_ft: true, тогда первой будет произведена выборка по всем индексам, кроме полнотекстового. А выборка из полнотекстового индекса будет проиводиться с учётом предыдущих результатов.

Итераторы

IdSet - в контекстер reindexer’a это упорядоченный массив внутренних id документов. В некоторых случаях может быть представлен деревом.

Результатом выборки из каждого индекса является итератор (или набор итераторов). Каждый итератор содержит внутри себя либо 1+ IdSet’ов, либо диапазон id.

Итераторы нужны для упорядоченного итерирования по документам. При этом логика и алгоритмическая сложность получения следующего документа зависит от типа итератора (в explain он попадает в поле type).

Возможные типы итераторов:

  • SingleRange, RevSingleRange - диапазон и инвертированный диапазон. Содержит только начальное и конечное значения id.

  • OnlyComparator - компаратор. Вообще не содержит информацию об id. При выборке требует наличия других IdSet’ов, по которым можно было бы проихводить фильтрацию.

  • Forward, Reverse - итератор, состоящий из нескольких IdSet’ов. Использует внутри алгоритм N-way merge для получения следующего значения.

  • SingleIdset, RevSingleIdset - содержит ровно один IdSet. Итерирование сводится либо к проходу по вектору, либо к проходу по rb-дереву.

  • SingleIdSetWithDeferedSort, RevSingleIdSetWithDeferedSort - итератор, который состоит из нескольких IdSet’ов, но вместо N-way merge производит предварительное слияние, сортировку и дедубликацию. Reindexer применияет их, если по предварительной оценке N-way merge оказывается более дорогим, чем сортировка за N*log(N).

  • Unsorted - несортированный итератор. Нужен для полнотекстовых выборок, поскольку там сортировка происходит по релевантности, а не по id.

  • UnbuiltSortOrdersIndex - итератор поверх B-tree (из ordered-индекса). Порядок обхода совпадает с порядком внутри соответствующего индекса, а не с порядком id.

Postprocess (часть 1)

Раздел postprocess в explain содержит в себе 2 части: первая выполняется перед select-loop, а втора после него.

Здесь происходит следующее:

  1. Оценка эффективности итерирования по tree-индексу, использованному для сортировки (если он использовался). Оценка происходит с учётом maxIterations, limit’a и offset’a. Для этого сравнивается ожидаемая сложность (итерирования по наиболее эффективному условию + general sort) и ожидаемая сложность итерирования по выбранному btree-индексу.

  2. Подстановка полного IdSet’а неймспейса (если требуется). Каждая выборка требует хотя бы одного IdSet’a для фильтрации. Если ни одно из условий выборки не может его обеспечить, то происходит подстановка всего неймспейса в качестве IdSet’a (fullscan). В explain такой IdSet будет помечен как -scan.

  3. Выбор наиболее оптимального основного итератора для select loop’a. «Наиболее оптимальным» считается либо итератор, для которого cost минимален, либо тот, по которому будет производиться сортировка.

  4. Сортировка всех итераторов по возрастанию cost’a. Cost для итераторов с методом ‘index’ определяется по максимальному ожидаемому числу операций и зависит от типа итератора и количетсва документов в нём.
    Cost для компараторов является фиктивным и проставляется на основе значения maxIterations. При этом cost для компараторов по не индексным полям будет выше, чем по индексным. Для сортировки используется stable_sort, поэтому условия, имеющие одинаковый cost (например, компараторы по индесам) сохранят тот порядок, который был в исходном запросе.

  5. Все join’ы передвигаются к концу скобок, объединённых OR (join’ы должны выполняться после всех остальных фильтров).

  6. Подготовка итераторов. Например, отложенная сортировка для SingleIdSetWithDeferedSort будет выполнена на этом этапе (если она ещё актуальна с учётом обновлённого значения maxIterations).

Select loop

Цикл пересечения итераторов при помощи алгоритма N-way merge. Цикл останавливается в тот момент, когда в одном из итераторов больше нет подходящих под условие данных, либо когда достигнуты требуемые LIMIT/OFFSET. Если запрос предполагает сортировку и не использует B-tree индекс для сортировки, то даже при наличии LIMIT потребуется сделать полную выборку.

На этом же этапе происходит выполнение INNER JOIN’ов, заполнение explain_select для каждого из joined-подзапросов, выполнившегося хотя бы один раз, и заполнение результатов агрегаций.

После пересечения итераторов выполняется явная сортировка выбранных документов (если она требуется). Время такой сортировки отражается в explain в поле general_sort_us.

Postprocess (часть 2)

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

  1. LEFT JOIN. Логика выполнения аналогичная INNER JOIN и точно также использует 1 из 3 типов preselect’a, который был сделан (или не сделан) перед началом запроса.
  2. Заполнение значений после сортировки по выражениям, если она была (преобразование невладеющих ссылок во владеющие указатели).

MERGE

MERGE-позапросы выполняются в самом конце. На этом этапе происходят последовательные выборки для всех merge-подзапросов, добавления результатов к предыдущим, дополнительная сортировка (по ID неймспейса и полнотекстому рангу) и повторное применение LIMIT/OFFSET к общему результату мерджа.

Применение SELECT-функций

На последнем этапе применяются функции, модифицирующие выборку: highlight, snippet и snippet_n (если они были в запросе).