Определение интерфейса метода доступа к индексу

В этой главе описывается интерфейс между ядром QHB и методами доступа к индексам, которые управляют отдельными типами индексов. Ядро системы ничего не знает об индексах, кроме того, что описано здесь, поэтому можно разработать совершенно новые типы индексов, написав дополнительный код.

Все индексы в QHB - это то, что технически известно как вторичные индексы, то есть индекс физически отделен от файла таблицы, который он описывает. Каждый индекс хранится как собственное физическое отношение и описывается записью в каталоге pg_class. Содержание индекса полностью находится под контролем его метода доступа к индексу. На практике все методы доступа к индексам разделяют индексы на страницы стандартного размера, чтобы они могли использовать обычный диспетчер хранилища и диспетчер буферов для доступа к содержимому индекса. (Все существующие методы доступа к индексам, кроме того, используют стандартный макет страницы, описанный в разделе Внутренняя структура страницы базы данных, и большинство используют тот же формат для заголовков индексных записей, но эти решения не являются обязательными для метода доступа).

Индекс это средство эффективного сопоставления некоторых значений ключей с идентификаторами записей (TID) версий строк (записей) в родительской таблице индекса. TID состоит из номера блока и номера записи внутри этого блока (см. раздел Внутренняя структура страницы базы данных). Этой информации достаточно для извлечения определенной версии строки из таблицы. Индексы непосредственно не знают, что при использовании MVCC, может существовать несколько версий одной и той же логической строки; для индекса каждая запись является независимым объектом, который требует своей собственной записи в индексе. Таким образом, обновление строки всегда создает новые записи для всех индексов, в которых участвует запись, даже если значения ключей не изменились. (HOT оптимизация обновления записей является исключением из этого утверждения, но индексы не имеют с ней дело). Индексные записи для мертвых записей в таблице удаляются во время вакуума вместе с удалением самих мертвых записей.

Базовая структура API для индексов

Каждый метод доступа к индексу описывается строкой в системном каталоге pg_am. Запись в pg_am содержит имя и функцию-обработчик метода доступа к индексу. Эти записи могут быть созданы и удалены с помощью SQL команд CREATE ACCESS METHOD и DROP ACCESS METHOD.

Функция-обработчик индексного метода доступа должна принимать один аргумент типа internal и возвращать псевдо-тип index_am_handler. Аргумент является фиктивным значением, предназначенным для предотвращения вызова функций обработчика непосредственно из команд SQL. Результатом работы функции должна быть структура типа IndexAmRoutine, размещенная в куче с помощью palloc и содержащая всё, что ядро должно знать, чтобы использовать метод доступа к индексу. Структура IndexAmRoutine, также называемая API-структурой метода доступа, включает поля, задающие различные фиксированные свойства метода доступа, например, возможность поддержки многоколоночных индексов. Что еще более важно, она содержит указатели на функции, выполняющие всю реальную работу для индексного метода доступа. Эти вспомогательные функции являются простыми функциями на C и не видны и не вызываются на уровне SQL. Вспомогательные функции описаны в разделе Функции доступа к индексу .

Структура IndexAmRoutine определяется таким образом:

typedef struct IndexAmRoutine
{
    NodeTag     type;

    /*
     * Total number of strategies (operators) by which we can traverse/search
     * this AM.  Zero if AM does not have a fixed set of strategy assignments.
     */
    uint16      amstrategies;
    /* total number of support functions that this AM uses */
    uint16      amsupport;
    /* does AM support ORDER BY indexed column's value? */
    bool        amcanorder;
    /* does AM support ORDER BY result of an operator on indexed column? */
    bool        amcanorderbyop;
    /* does AM support backward scanning? */
    bool        amcanbackward;
    /* does AM support UNIQUE indexes? */
    bool        amcanunique;
    /* does AM support multi-column indexes? */
    bool        amcanmulticol;
    /* does AM require scans to have a constraint on the first index column? */
    bool        amoptionalkey;
    /* does AM handle ScalarArrayOpExpr quals? */
    bool        amsearcharray;
    /* does AM handle IS NULL/IS NOT NULL quals? */
    bool        amsearchnulls;
    /* can index storage data type differ from column data type? */
    bool        amstorage;
    /* can an index of this type be clustered on? */
    bool        amclusterable;
    /* does AM handle predicate locks? */
    bool        ampredlocks;
    /* does AM support parallel scan? */
    bool        amcanparallel;
    /* does AM support columns included with clause INCLUDE? */
    bool        amcaninclude;
    /* type of data stored in index, or InvalidOid if variable */
    Oid         amkeytype;

    /* interface functions */
    ambuild_function ambuild;
    ambuildempty_function ambuildempty;
    aminsert_function aminsert;
    ambulkdelete_function ambulkdelete;
    amvacuumcleanup_function amvacuumcleanup;
    amcanreturn_function amcanreturn;   /* can be NULL */
    amcostestimate_function amcostestimate;
    amoptions_function amoptions;
    amproperty_function amproperty;     /* can be NULL */
    ambuildphasename_function ambuildphasename;   /* can be NULL */
    amvalidate_function amvalidate;
    ambeginscan_function ambeginscan;
    amrescan_function amrescan;
    amgettuple_function amgettuple;     /* can be NULL */
    amgetbitmap_function amgetbitmap;   /* can be NULL */
    amendscan_function amendscan;
    ammarkpos_function ammarkpos;       /* can be NULL */
    amrestrpos_function amrestrpos;     /* can be NULL */

    /* interface functions to support parallel index scans */
    amestimateparallelscan_function amestimateparallelscan;    /* can be NULL */
    aminitparallelscan_function aminitparallelscan;    /* can be NULL */
    amparallelrescan_function amparallelrescan;    /* can be NULL */
} IndexAmRoutine;

Чтобы быть полезным, метод доступа к индексу также должен иметь одно или несколько семейств операторов и классов операторов, определенных в pg_opfamily, pg_opclass, pg_amop и pg_amproc. Эти записи позволяют планировщику определить, какие виды запросов могут использоваться с индексами данного метода доступа. Семейства операторов и классы описаны в Интерфейсные расширения для индексов, который является необходимым материалом для чтения этой главы.

Индивидуальный индекс определяется записью в pg_class, описывающей его как физическое отношение, плюс запись в pg_index, показывающей логическое содержимое индекса, то есть набор столбцов входящих в индекс, и семантику этих столбцов, то есть связь с классами операторов. Столбцы индекса (ключевые значения) могут быть либо простыми столбцами таблицы, для которой строится индекс, либо выражениями над строками этой таблицы. Обычно для индексного метода доступа не имеет значения, откуда берутся значения ключей индекса (ему всегда передаются предварительно вычисленные значения ключей), но очень важна информация о классе оператора в pg_index. Обе эти записи каталога могут быть доступны в составе структуры данных Relation, которая передается всем операциям с индексом.

Некоторые из полей флагов структуры IndexAmRoutine имеют нетривиальное назначение. Требования, предъявляемые к amcanunique, обсуждаются в разделе Проверка уникальности индекса. Флаг amcanmulticol утверждает, что метод доступа поддерживает многоколоночные индексы, в то время как amoptionalkey указывает, что метод доступа разрешает сканирование, когда для первого столбца индекса не задано ограничение. Когда amcanmulticol равен false, amoptionalkey, говорит, что метод доступа поддерживает сканирование с полным перебором без каких-либо ограничительных условий. Методы доступа, поддерживающие несколько столбцов в индексе, должны поддерживать сканирования, позволяющие пропускать ограничения для любого или всех столбцов после первого; однако им разрешено требовать, чтобы использовались ограничения для первого столбца индекса, об этом сигнализирует флаг amoptionalkey равный false. Одна из причин, по которой метод доступа может установить значение amoptionalkey равным false, если он не индексирует нулевые значения. Поскольку большинство индексируемых операторов являются строгими и, следовательно, не могут возвращать true, если поле содержит NULL, на первый взгляд кажется правильным не хранить записи индекса для нулевых значений: они никогда не могут быть возвращены при сканировании индекса. Однако этот аргумент неверен, если проверка индекса не содержит условия ограничения для данного столбца индекса. На практике это означает, что индексы, у которых amoptionalkey равным true, должен индексировать значения NULL, так как планировщик может решить использовать такой индекс без ключей сканирования вообще. Связанное с этим ограничение заключается в том, что метод доступа к индексам, поддерживающий несколько столбцов индекса, должен поддерживать индексирование NULL значений в столбцах после первого, поскольку планировщик будет предполагать, что индекс может использоваться для запросов, которые не ограничивают эти столбцы. Например, рассмотрим индекс на (a, b) и запрос с WHERE a = 4. Система будет считать, что индекс может быть использован для сканирования строк с помощью а = 4, что неверно, если индекс пропускает строки, где b - это null. Однако допустимо пропускать строки, в которых первый индексированный столбец имеет значение NULL. Метод доступа к индексу, позволяющий индексировать значения NULL, также может установить значение amsearchnulls в true, указывая, что он поддерживает предложения IS NULL и IS NOT NULL в условиях поиска.

Функции доступа к индексу

Функции построения и обслуживания индекса

Функции построения и обслуживания индекса, которые должен предоставить метод доступа к индексу в структуре IndexAmRoutine:

ambuild

IndexBuildResult *
ambuild (Relation heapRelation,
         Relation indexRelation,
         IndexInfo *indexInfo);

Создает новый индекс. Отношение индекса физически создано, но является пустым. Метод должен заполнить отношение любыми фиксированными данными, необходимыми для собственного функционирования, а также записями для всех строк, уже существующих в таблице. Обычно функция ambuild будет вызывать table_index_build_scan() для сканирования таблицы на наличие существующих записей и вычисления ключей, которые необходимо вставить в индекс. Функция должна возвращать структуру, размещенную в куче с помощью palloc и содержащую статистику о новом индексе.

ambuildempty

void
ambuildempty (Relation indexRelation);

Создает пустой индекс и записывает его в слой инициализации (INIT_FORKNUM) данного отношения. Этот метод вызывается только для нежурналируемых индексов. Пустой индекс, записанный в слой инициализации, будет скопирован поверх основного слоя отношения при каждом перезапуске сервера.

aminsert

bool
aminsert (Relation indexRelation,
          Datum *values,
          bool *isnull,
          ItemPointer heap_tid,
          Relation heapRelation,
          IndexUniqueCheck checkUnique,
          IndexInfo *indexInfo);

Вставляет новую запись в существующий индекс. Входные массивы values и isnull задают значения ключей для индексирования, heap_tid - это TID для индексации. Если метод доступа поддерживает уникальные индексы (его флаг amcanunique равен true), тогда аргумент checkUnique указывает выполняется или нет проверка уникальности. Это зависит от того, является ли ограничение уникальности откладываемым; смотрите раздел Проверка уникальности индекса для получения подробной информации. Обычно метод доступа требует только параметр heapRelation при выполнении проверки уникальности (так как должен будет заглянуть в таблицу, чтобы проверить живучесть записи).

Логическое значение результата функции является значимым только тогда, когда значение параметра checkUnique является UNIQUE_CHECK_PARTIAL. В этом случае true означает, что новая запись является уникальной, тогда как false означает, что она может быть неуникальной (и отложенная проверка уникальности должна быть запланирована). В других случаях рекомендуется всегда возвращать false.

Некоторые индексы могут индексировать не все записи. Если запись не будет индексироваться, параметр aminsert надо просто вернуть, ничего не делая.

Если индексный метод доступа хочет кэшировать данные через последовательные вставки индекса в инструкции SQL, он может выделить пространство в indexInfo->ii_Context и хранить указатель на данные внутри indexInfo->ii_AmCache (который изначально будет равен нулю).

ambulkdelete

IndexBulkDeleteResult *
ambulkdelete (IndexVacuumInfo *info,
              IndexBulkDeleteResult *stats,
              IndexBulkDeleteCallback callback,
              void *callback_state);

Удаляет запись(и) из индекса. Это операция "массового удаления", которая должна быть реализована путем сканирования всего индекса и проверки каждой записи, чтобы определить, следует ли ее удалить. Для каждой записи нужно вызвать функцию обратного вызова: callback( __TID__, callback_state) и проверить возвращаемое значение типа bool. Если возвращаемое значение равно true, запись необходимо удалить из индекса. Метод ambulkdelete должен возвращать либо NULL, либо структуру, размещенную в куче с помощью palloc и содержащую статистику о результатах операции удаления. Можно вернуть NULL, если индекс не был изменен в процессе операции VACUUM, в противном случае должна быть возвращена корректная статистика.

Из-за ограничения maintenance_work_mem, функцию ambulkdelete, возможно, потребуется вызывать несколько раз, когда требуется удалить много записей. Аргумент stats является результатом предыдущего вызова для этого индекса (он равен NULL для первого вызова в рамках операции VACUUM). Это позволяет методу доступа накапливать статистику по всей операции. Как правило, ambulkdelete будет изменять и возвращать ту же структуру, если переданная stats не является нулем.

amvacuumcleanup

IndexBulkDeleteResult *
amvacuumcleanup (IndexVacuumInfo *info,
                 IndexBulkDeleteResult *stats);

Выполнить очистку после операции VACUUM (до этого могло быть 0 или больше вызовов ambulkdelete). Функция не должна делать ничего, кроме возврата статистики, но может выполнить массовую очистку, такую как удаление пустых страниц индекса. Параметр stats содержит результат последнего вызова метода ambulkdelete, или NULL, если ambulkdelete не был вызван, потому что никакие записи не нужно было удалять. Результат функции является структурой, размещенной в куче с помощью palloc. Содержащаяся в нем статистика будет использована для обновления pg_class и выводится операцией VACUUM, если задан ключ VERBOSE. Метод может вернуть NULL, если индекс не изменялся во время операции VACUUM, в противном случае должна возвращаться корректная статистика..

Метод amvacuumcleanup также будет вызван по завершении операции ANALYZE. В этом случае параметр stats всегда имеет значение NULL, и любое возвращаемое значение игнорируется. Этот случай можно отличить проверкой info->analyze_only. Рекомендуется, чтобы в таком вызове метод доступа не делал ничего, кроме очистки после вставки, и это только в рабочем процессе autovacuum.

amcanreturn

bool
amcanreturn (Relation indexRelation, int attno);

Проверяет, поддерживает ли индекс сканирование только по индексу для данного столбца, возвращая его значение из индексной записи в виде структуры IndexTuple. Нумерация атрибутов начинается с 1, т.е. параметр attno для первого столбца должен быть равен 1. Метод возвращает true, если поддерживается, иначе false. Если метод доступа вообще не поддерживает сканирование только по индексу, то поле amcanreturn в его структуре IndexAmRoutine можно установить в значение NULL.

amcostestimate

void
amcostestimate (PlannerInfo *root,
                IndexPath *path,
                double loop_count,
                Cost *indexStartupCost,
                Cost *indexTotalCost,
                Selectivity *indexSelectivity,
                double *indexCorrelation,
                double *indexPages);

Оценивает стоимость на сканирование индекса. Эта функция полностью описана в разделе Функции оценки стоимости индекса ниже.

amoptions

bytea *
amoptions (ArrayType *reloptions,
           bool validate);

Разбирает и анализирует массив reloptions. Метод вызывается только, когда для индекса существует ненулевой массив reloptions. Аргумент reloptions это текстовый массив, содержащий записи форме name=value. Функция должна сформировать bytea значение, которое будет скопировано в поле rd_options записи индекса в relcache. Содержимое bytea определяется самим методом доступа; большинство стандартных методов доступа используют структуру StdRdOptions. Когда аргумент validate равен true, функция должна выдавать соответствующее сообщение об ошибке, если какой-либо из параметров в массиве reloptions не распознан или имеет недопустимое значение; если validate имеет значение false, недопустимые значения должны молча игнорироваться. (validate имеет значение false при загрузке уже сохраненных параметров из pg_catalog; недопустимая запись может быть найдена только в том случае, если метод доступа изменил свои правила для опций, и в этом случае игнорирование устаревших записей является уместным). Можно вернуть значение NULL, если требуется поведение по умолчанию.

amproperty

bool
amproperty (Oid index_oid, int attno,
            IndexAMProperty prop, const char *propname,
            bool *res, bool *isnull);

Метод amproperty позволяет методу доступа переопределить поведение по умолчанию pg_index_column_has_property и связанных функций. Если метод доступа не имеет никакого специального поведения для запросов свойств индекса, то поле amproperty в структуре IndexAmRoutine можно установить в значение NULL. В противном случае, метод amproperty будет вызван с аргументами index_oid и attno равными нулю для pg_indexam_has_property, или с валидным значением в index_oid и attno больше нуля для pg_index_column_has_property. Атрибут prop является значением enum, идентифицирующим проверяемое свойство, в то время как атрибут propname является исходной строкой имени свойства. Если ядро не распознает имя свойства, то параметр prop будет содержать AMPROP_UNKNOWN. Методы доступа могут определять имена настраиваемых свойств путем проверки propname на соответствие (используйте pg_strcasecmp, чтобы проверить соответствие единообразно с основным кодом); для имен, известных ядру базы данных, лучше проверить параметр prop. Если метод amproperty возвращает true, значит он определил результат проверки свойства. В этом случае он должен установить значение res или значение *isnull в true, чтобы вернуть NULL. (Обе указанные переменные инициализируются в false перед вызовом). Если метод amproperty возвращает false, тогда ядро базы данных продолжит свою обычную логику для определения результата проверки свойства.

Методы доступа, поддерживающие операторы сортировки, должны реализовывать проверку свойства AMPROP_DISTANCE_ORDERABLE, так как ядро не знает, как это сделать, и вернет значение NULL. Также стоит реализовать проверку AMPROP_RETURNABLE, если это можно сделать дешевле, чем открыть индекс и вызвать метод amcanreturn, что является поведением ядра базы данных по умолчанию. Поведение по умолчанию должно быть удовлетворительным для всех других стандартных свойств.

ambuildphasename

char *
ambuildphasename (int64 phasenum);

Возвращает текстовое имя заданного номера фазы сборки. Номера фаз-это те, которые сообщаются во время построения индекса через вызов pgstat_progress_update_param. Названия фаз затем доступны во view pg_stat_progress_create_index.

amvalidate

bool
amvalidate (Oid opclassoid);

Проверяет записи каталога для указанного класса операторов, насколько метод доступа может сделать это. Например, может убедится, что реализованы всех обязательные функций в методе доступа. Метод amvalidate должен вернуть false, если opclass является недопустимым. О проблемах следует сообщать с помощью вызова ereport.

Функции поддержки сканирования

Цель индекса, конечно же, заключается в поддержке сканирования для записей, соответствующих индексируемому условию WHERE, часто называемым квалификатором или ключом сканирования. Семантика индексного сканирования более подробно описана в разделе Индексное сканирование ниже. Метод доступа к индексу может поддерживать "простые" индексные сканирования, bitmap индексные сканирования или оба. Связанные со сканированием функции, которые должен или может предоставить метод доступа к индексам:

ambeginscan

IndexScanDesc
ambeginscan (Relation indexRelation,
             int nkeys,
             int norderbys);

Выполняет подготовку к сканированию индекса. Параметры nkeys и norderbys указывают количество операторов сравнения и сортировки, которые будут использоваться в сканировании; это может быть полезно для целей выделения памяти. Обратите внимание, что фактические значения ключей сканирования еще не предоставлены. Результатом работы должна быть структура, выделенная в куче с помощью palloc. В связи с особенностями реализации, метод доступа к индексу должен создать эту структуру путем вызова функции RelationGetIndexScan(). В большинстве случаев ambeginscan мало что делает, кроме данного вызова и, возможно, получения блокировок; интересные части запуска сканирования индекса находятся в функции amrescan.

amrescan

void
amrescan (IndexScanDesc scan,
          ScanKey keys,
          int nkeys,
          ScanKey orderbys,
          int norderbys);

Запускает или перезапускает сканирование индекса, возможно, с новыми ключами сканирования. (Для перезапуска с использованием ранее переданных ключей параметры keys и/или orderbys устанавливаются в NULL). Обратите внимание, что не допускается, чтобы количество ключей или операторов сортировки было больше, чем то, что передано ambeginscan. На практике функция перезапуска используется, когда в соединении со вложенным циклом выбирается новая внешняя запись и, поэтому, требуется новое сравнение с ключем, но структура, содержащая состояние сканирования, остается прежней.

amgettuple

boolean
amgettuple (IndexScanDesc scan,
            ScanDirection direction);

Выбирает следующую запись в заданном сканировании, двигаясь в указанном направлении (вперед или назад в индексе). Возвращает true, если запись получена, false, если не осталось совпадающих записей. Если запись найдена, ее TID сохраняется в структуре сканирования. Обратите внимание, что "успех" означает только то, что индекс содержит запись, соответствующую ключам сканирования, а не то, что запись обязательно все еще существует в таблице или пройдет тест видимости в снимке вызывающего объекта. В случае успеха, функция amgettuple должна также установить scan->xs_recheck в true или false. False означает, что запись индекса обязательно соответствует ключам сканирования. True означает, что это не обязательно, и условия, представленные ключами сканирования, должны быть повторно проверены после извлечения записи из таблицы. Это условие поддерживает операторы индекса c ”потерями". Обратите внимание, что повторная проверка будет распространяться только на условия сканирования; частичный индексный предикат (если таковой имеется) никогда не перепроверяется кодом, который вызывал amgettuple.

Если индекс поддерживает сканирование только по индексу (т.е. функция amcanreturn возвращает true для соответствующего свойства), тогда в случае успешного сканирования, метод доступа также должен проверить значение scan->xs_want_itup, и оно равно true, метод доступа обязан вернуть исходные индексированные данные для записи индекса. Данные могут быть возвращены в виде указателя IndexTuple, сохраненного в scan->xs_itup, с дескриптором записи scan->xs_itupdesc; или в форме указателя HeapTuple, сохраненного в scan->xs_hitup, с дескриптором записи scan->xs_hitupdesc. (Последний формат следует использовать при возврате данных, которые могут не вписываться в IndexTuple). В любом случае, управление данными, на которые ссылается указатель, является ответственностью метода доступа. Данные должны оставаться хорошими по крайней мере до следующего вызова amgettuple, amrescan, или amendscan.

Функция amgettuple должна быть реализована только в том случае, если метод доступа поддерживает “простые” индексные сканирования. Если это не так, то поле amgettuple в структуре IndexAmRoutine необходимо установить в значение NULL.

amgetbitmap

int64
amgetbitmap (IndexScanDesc scan,
             TIDBitmap *tbm);

Извлекает все записи в данном сканировании и добавляет их в TIDBitmap, переданной на вход (то есть добавляет TID найденных записей к уже находящимся в битовой карте). Функция возвращает количество извлеченных записей (это может быть только приблизительное значение, например, некоторые методы доступа не обнаруживают дубликаты). При вставке идентификаторов записей в коллекцию, amgettbitmap может сигнализировать, что для некоторых записей требуется повторная проверка условий сканирования. Это аналогично выходному параметру xs_recheck функции amgettuple. Примечание: в текущей реализации поддержка этой функции объединена с поддержкой хранилища с потерями самой битовой карты, поэтому вызывающий код повторно проверяет и условия сканирования, и частичный индексный предикат (если таковой имеется) для записей, помеченных для повторной проверки. Однако это не всегда может быть правдой. Функции amgettbitmap и amgettuple нельзя использовать в одном и том же сканировании индекса; есть и другие ограничения при использовании amgettbitmap, более подробно они описаны в разделе Индексное сканирование .

Функция amgettbitmap должна быть реализована только в том случае, если метод доступа поддерживает “bitmap” сканирование индекса. Если это не так, то поле amgettbitmap в его структуре IndexAmRoutine необходимо установить в значение NULL.

amendscan

void
amendscan (IndexScanDesc scan);

Завершает сканирование и освобождает ресурсы. Сама структура сканирования не должна быть освобождена, но любые блокировки и закрепления, полеченные внутри метода доступа, должны быть освобождены, а также любая другая память, выделенная методом ambeginscan и другими функциями поддержки сканирования.

ammarkpos

void
ammarkpos (IndexScanDesc scan);

Отмечает текущее положение сканирования. Метод доступа должен поддерживать только одно запоминание позиции на сканирование.

Функция ammarkpos должна быть реализована только в том случае, если метод доступа поддерживает упорядоченные сканирования. Если это не так, то поле ammarkpos в его структуре IndexAmRoutine можно установить в значение NULL.

amrestrpos

void
amrestrpos (IndexScanDesc scan);

Восстанавливает сканирование до самой последней отмеченной позиции.

функция amrestrpos должна быть реализована только в том случае, если метод доступа поддерживает упорядоченные сканирования. Если это не так, то поле amrestrpos в его структуре IndexAmRoutine можно установить в значение NULL.

Функции поддержки параллельного сканирования

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

amestimateparallelscan

Size
amestimateparallelscan (void);

Оценивает и возвращает количество байт в динамической общей памяти, которое необходимо методу доступа для выполнения параллельного сканирования. (Это число является дополнением, а не заменой, объема памяти, необходимого для хранения независимой от метода доступа данных структуры ParallelIndexScanDescData).

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

aminitparallelscan

void
aminitparallelscan (void *target);

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

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

amparallelrescan

void
amparallelrescan (IndexScanDesc scan);

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

Индексное сканирование

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

Ключ сканирования-это внутреннее представление условия WHERE в форме index_key operator constant, где ключ индекса является одним из столбцов индекса, а оператор-одним из членов семейства операторов, связанных с этим столбцом индекса. Сканирование индекса имеет ноль или более ключей сканирования, связанных через И, то есть ожидается, что возвращенные записи, удовлетворяют всем указанным условиям.

Метод доступа может сообщить, что индекс является индексом с потерями или требует повторных проверок для конкретного запроса. Это означает, что сканирование индекса вернет все записи, удовлетворяющие ключу сканирования, а также, возможно, дополнительные записи, которые не удовлетворяют. Часть ядра базы данных, отвечающая за индексное сканирование, затем снова применит условия индекса к записи из таблицы, чтобы проверить, действительно ли она должна быть выбрана. Если опция повторной проверки не задана, сканирование индекса должно возвращать набор данных, полученный от метода доступа.

Обратите внимание, что метод доступа обязан убедиться, что он правильно находит все и только удовлетворяющие всем заданным ключам сканирования записи. Кроме того, ядро базы данных просто передаст все условия WHERE, соответствующие ключам индекса, и семейства операторов, без какого-либо семантического анализа на избыточность или противоречивовсть. Например, в выражении WHERE x>4 AND x>14, где x является столбцом в B-tree индексе, только в функции amrescan функции B-tree индекса можно понять, что первый ключ сканирования является избыточным и может быть отброшен. Необходимая степень предварительной обработки в функции amrescan зависит от степени, которая требуется методу доступа к индексу, чтобы уменьшить ключи сканирования до ”нормализованной" формы.

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

  • Методы доступа, всегда возвращающие записи в порядке хранения данных в индексе (например, btree), должны установить amcanorder в true. В настоящее время такие методы доступа должны использовать btree-совместимые стратегии для их операторов равенства и сортировки.

  • Методы доступа, поддерживающие операторы сортировки должны установить amcanorderbyop в true. Это указывает на то, что индекс способен возвращать записи в порядке, удовлетворяющем ORDER BY index_key operator constant. Модификаторы сканирования этой формы могут быть переданы в функцию amrescan как описано ранее.

Функция amgettuple имеет аргумент direction, который может принимать значения или ForwardScanDirection (обычный случай), или BackwardScanDirection. Если первый вызов после amrescan получит BackwardScanDirection, тогда набор совпадающих индексных записей должен сканироваться назад-вперед, а не в обычном направлении вперед-назад, поэтому методу amgettuple необходимо вернуть последнюю совпадающую запись в индексе, а не первую, как это обычно делается. (Это будет происходить только для методов доступа, установивших флаг amcanorder в true). После первого вызова, функции amgettuple необходимо быть готовым к дальнейшему сканированию в любом направлении от последней возвращенной записи. (Но если флаг amcanbackward имеет значение false, все последующие вызовы будут иметь то же направление, что и первый).

Методы доступа, поддерживающие упорядоченное сканирование, должны поддерживать "маркировку" позиции в сканировании и последующий возврат к отмеченной позиции. Одна и та же позиция может быть восстановлена несколько раз. Однако, необходимо сохранять только одно положение на сканирование; новый вызов функции ammarkpos переопределяет ранее отмеченную позицию. Методам доступа, не поддерживающим упорядоченное сканирование, не нужно реализовывать функции ammarkpos и amrestrpos внутри IndexAmRoutine; вместо этого установите эти указатели в значение NULL.

Текущее положение сканирования и отмеченная позиция (если такая есть) должны оставаться в согласованном состоянии во время одновременных вставок или удалений из индекса. Это нормально, если только что вставленная запись не возвращается сканированием, которое обнаружило бы запись, если бы она существовала, когда сканирование началось. Так же нормально для сканирования вернуть такую запись при повторном сканировании или возврате, даже если она не была возвращена в первый раз. Аналогично, одновременное удаление может быть отражено или не отражено в результатах сканирования. Важно, чтобы вставки или удаления не приводили к пропуску или к дублированию возвращаемых записей, которые не были вставлены или удалены.

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

Вместо использования функции amgettuple, сканирование индекса можно выполнить с помощью вызова amgettbitmap, чтобы получить все записи в одном вызове. Это может быть заметно более эффективным, чем amgettuple, потому что это позволяет избежать циклов блокировки/разблокировки в рамках метода доступа. В принципе, вызов amgettbitmap должен иметь такие же последствия, как и последовательные вызовы amgettuple, но есть несколько ограничений, чтобы упростить дело. Прежде всего, amgettbitmap возвращает все записи сразу и маркировка или восстановление позиции сканирования не поддерживается. Во-вторых, записи возвращаются в виде битовой карты, которая не имеет никакой сортировки, поэтому amgettbitmap не принимает аргумент direction. (Операторы сортировки также никогда не будут предоставлены для такого сканирования). Кроме того, не предусмотрено использование только индексных сканирований с помощью amgettbitmap, так как нет никакого способа вернуть содержимое индексных записей. В-третьих, amgettbitmap не гарантирует никакой блокировки возвращенных записей, с последствиями, указанными в разделе Вопросы блокировки индекса .

Обратите внимание, что для метода доступа разрешено реализовать только amgettbitmap и не реализовывать amgettuple или наоборот, если его внутренняя реализация не подходит для одного API или другого.

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

Методы доступа к индексам должны обрабатывать одновременные обновления индекса несколькими процессами. Ядро QHB получает AccessShareLock на индекс во время сканирования индекса и RowExclusiveLock при обновлении индекса (включая обычный VACUUM). Поскольку эти типы блокировок не конфликтуют, метод доступа отвечает за обработку любых более мелких блокировок, которые можгут потребоваться. Исключительная блокировка индекса целиком может потребоваться только во время его создания, уничтожения или REINDEX .

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

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

  • Новая запись в таблице создается перед созданием для нее записи в индексе. (Поэтому одновременное сканирование индекса, скорее всего, не сможет увидеть запись в таблице. Это нормально, потому что читатель индекса не заинтересован в получении незафиксированной строки в любом случае. Для более детальной информации смотрите раздел Проверка уникальности индекса).

  • Когда запись удаляется из таблицы (с помощью VACUUM), все ее индексные записи должны быть удалены первыми.

  • Сканирование индекса должно закреплять страницу индекса, содержащую элемент, возвращенный последним вызовом amgettuple, и функция ambulkdelete не может удалить записи со страниц, закрепленных другими бэкэндами. Необходимость в этом правиле объясняется ниже.

Без третьего правила читатель индекса может видеть запись индекса непосредственно перед ее удалением VACUUM, а затем получить соответствующую запись из таблицы после того, как она была удалена VACUUM. Это не создает никаких серьезных проблем, если этот номер элемента еще не используется (после очистки), когда читатель достигает его, так как пустой слот элемента будет игнорироваться при извлечении записей из таблицы. Но что делать, если третий сервер уже повторно использовал данный слот элемента для чего-то другого? При использовании моментального снимка, совместимого с MVCC, нет никаких проблем, потому что новый пользователь слота наверняка будет слишком новым, чтобы пройти тест видимости для моментального снимка. Однако с моментальным снимком, не совместимым с MVCC (например SnapshotAny), возможна ситуация, когда будет принята и возвращена строка, которая фактически не соответствует ключам сканирования. Можно защититься от этого сценария, требуя, перепроверки ключей сканирования для записи из таблицы во всех случаях, но это слишком дорого. Вместо этого используется закрепление страницы индекса в качестве прокси, как указание, что читатель все еще может быть “в процессе” обращение от записи индекса к соответствующей записи в таблице. Создание таких блоков функцией ambulkdelete гарантирует, что VACUUM не сможет удалить запись из таблицы до того, как читатель закончит работать с ней. Это решение не требует больших затрат во время выполнения и добавляет накладные расходы на блокировку только в редких случаях, когда на самом деле существует конфликт.

Такое решение требует, чтобы сканирование индекса было “синхронным”: необходимо прочитать запись из таблицы сразу после сканирования соответствующей записи индекса. Это дорого по ряду причин. "Асинхронное" сканирование, при котором собирается много TID из индекса, a только через некоторое время выполняется чтение таблицы, требует гораздо меньше накладных расходов на блокировку индекса и позволяет более эффективно реализовать доступ к таблице. В соответствии с приведенным выше анализом, синхронный подход необходимо использовать для не-MVCC-совместимых снимков, а асинхронное сканирование применимо для запроса, использующего снимок MVCC.

В функции amgetbitmap, метод доступа не сохраняет защелок индексных страниц для возвращенных записей. Поэтому безопасно использовать такие сканирования только с MVCC-совместимыми моментальными снимками.

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

Проверка уникальности индекса

QHB реализует ограничения уникальности SQL через использование уникальных индексов, которые являются индексами, запрещающими несколько записей с одинаковыми ключами. Метод доступа, поддерживающий эту функцию, устанавливает для флага amcanunique значение true. (В настоящее время его поддерживают только B-tree индексы). Столбцы, перечисленные в предложении INCLUDE не учитываются при обеспечении уникальности.

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

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

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

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

Кроме того, непосредственно перед сообщением о нарушении уникальности в соответствии с вышеуказанными правилами, метод доступа должен повторно проверить жизнеспособность вставляемой строки. Если запись мертва, то не нужно сообщать о каких-либо нарушениях. (Этот случай не может произойти во время обычного сценария вставки строки, только что созданной текущей транзакцией. Однако, это может произойти при выполнении CREATE UNIQUE INDEX CONCURRENTLY.)

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

Если ограничение уникальности является отложенным, возникает дополнительная сложность: нужно иметь возможность вставлять запись индекса для новой строки, но откладывать любую ошибку нарушения уникальности до конца оператора или даже позже. Чтобы избежать ненужных повторных поисков индекса, метод доступа к индексу должен выполнить предварительную проверку уникальности во время начальной вставки. Если проверка показывает, что нет конфликтующей живой записи, дальнейшие проверки не проводятся. В противном случае планируется повторная проверка, когда придет время применить ограничение. Если во время повторной проверки и вставленный запись, и какая-то другая запись с тем же ключом являются живыми, то необходимо сообщить об ошибке. (Обратите внимание, что в данном случае “живая” фактически означает “в HOT цепочке в индексе существует живая запись”). Чтобы реализовать повторные проверки, в функцию aminsert передается параметр checkUnique, имеющий одно из следующих значений:

  • UNIQUE_CHECK_NO указывает, что проверка уникальности не должна выполняться (это не уникальный индекс).

  • UNIQUE_CHECK_YES указывает, что этот уникальный индекс без отложенной проверки, и проверка уникальности должна быть выполнена немедленно, как описано выше.

  • UNIQUE_CHECK_PARTIAL указывает, что ограничение уникальности является отложенным. QHB будет использовать этот режим для вставки каждой строки в индекс. Метод доступа должен разрешать повторяющиеся записи в индексе и сообщать о любых потенциальных дубликатах, возвращая false из aminsert. Для каждой строки, для которой возвращается false, будет запланирована отложенная повторная проверка.

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

  • UNIQUE_CHECK_EXISTING указывает, что это отложенная повторная проверка строки, промеченной как потенциальное нарушение уникальности. Хотя это реализуется путем вызова aminsert, метод доступа не должен вставлять новую запись индекса в этом случае. Запись индекса уже присутствует. Вместо этого метод доступа должен проверить, есть ли другая "живая" запись в индексе. Если это так, и если целевая строка также все еще активна, сообщить об ошибке.

    Рекомендуется, чтобы в вызове UNIQUE_CHECK_EXISTING, метод доступа далее проверял, что целевая строка, действительно, имеет существующую запись в индексе, и сообщает об ошибке, если ее нет. Это хорошая идея, потому что значения индексной записи, переданной в aminsert, будут пересчитаны. Если определение индекса включает в себя функции, которые на самом деле не являются неизменяемыми, возможна проверка неправильной области индекса. Верификация того, что целевая строка найдена при повторной проверке, убеждается, что сканируются те же значения записи, которые использовались в исходной вставке.

Функции оценки стоимости индекса

Функция amcostestimate предоставляет информацию, описывающую возможное сканирование индекса, включая списки Where и ORDER BY, которые были определены для использования с индексом. Метод должен возвращать оценку стоимости доступа к индексу и селективность предложений WHERE (то есть доли строк родительской таблицы, которые будут получены во время сканирования индекса). Для простых случаев почти вся работа оценщика затрат может быть выполнена путем вызова стандартных подпрограмм в оптимизаторе; смысл наличия функции amcostestimate заключается в том, чтобы позволить методу доступа к индексам предоставлять специфические знания о конкретных типах индексов, если это может улучшить стандартные оценки.

Каждая функция amcostestimate должна иметь следующие параметры:

void
amcostestimate (PlannerInfo *root,
                IndexPath *path,
                double loop_count,
                Cost *indexStartupCost,
                Cost *indexTotalCost,
                Selectivity *indexSelectivity,
                double *indexCorrelation,
                double *indexPages);

Первые три параметра являются входными данными:

root

  • Информация планировщика об обрабатываемом запросе.

path

  • Рассматривается путь доступа к индексу. Все поля, кроме indexTotalCost и indexSelectivity являются валидными.

loop_count

  • Число повторений сканирования индекса, которое должно быть учтено в оценке стоимости. Значение обычно будет больше единицы при рассмотрении параметризованного сканирования для использования внутри соединения с помощью вложенных запросов. Обратите внимание, что оценка стоимости все еще должна быть только для одного сканирования; большое значение loop_count означает, что его можно учесть для планирования кэширования при нескольких сканированиях.

Последние пять параметров являются выходными данными по ссылке:

indexStartupCost

  • Значение стоимость начальной обработки индекса

indexTotalCost

  • Общая стоимость обработки индекса

indexSelectivity

  • Индекс селективности

indexCorrelation

  • Коэффициент корреляции между порядком сканирования индекса и порядком базовой таблицы

indexPages

  • Число листовых страниц индекса

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

Стоимость доступа к индексу должна быть рассчитана с использованием параметров, используемых src/backend/optimizer/path/costsize.c: последовательная выборка дискового блока имеет стоимость seq_page_cost, произвольная выборка имеет стоимость random_page_cost, и стоимость обработки одной строки индекса обычно следует принимать как cpu_index_tuple_cost. Кроме того, следует использовать соответствующее умножение на cpu_operator_cost для любых операторов сравнения, вызываемых во время обработки индекса (особенно вычисление самих условий индекса).

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

indexStartupCost - это часть общей стоимости сканирования, которая должна быть израсходована, прежде чем станет возможно извлечь первую строку. Для большинства индексов это значение можно принять равным нулю, но тип индекса с высокой начальной стоимостью может захотеть установить его ненулевым.

В indexSelectivity должно быть записано значение предполагаемой доли строк родительской таблицы, которая будет получена во время сканирования индекса. В случае запроса с потерями, как правило, значение будет выше, чем доля строк, которые фактически удовлетворяют условиям сравнения.

В indexCorrelation следует записать корреляцию (в диапазоне от -1,0 до 1,0) между порядком индекса и порядком таблицы. Это используется для корректировки оценки стоимости извлечения строк из родительской таблицы.

В indexPages необходимо записать количество листовых страниц. Значение используется для оценки количества рабочих процессов для параллельного сканирования индекса.

Когда loop_count больше единицы, возвращаемые числа должны быть средними, ожидаемыми для любого одного сканирования индекса.

Оценка стоимости

Типичный оценщик стоимости будет действовать следующим образом:

  1. Оценивает и возвращает долю строк родительской таблицы, которые будут посещены на основе заданных условий сравнения. При отсутствии каких-либо специфических знаний для данного типа индекса нужно использовать стандартную функцию оптимизатора clauselist_selectivity():
*indexSelectivity = clauselist_selectivity(root, path->indexquals,
                                           path->indexinfo->rel->relid,
                                           JOIN_INNER, NULL);

  1. Оценивает количество строк индекса, которые будут посещены во время сканирования. Для многих типов индексов это то же самое, что indexSelectivity, умноженное на число строк в индексе, но может быть и больше. (Обратите внимание, что размер индекса в страницах и строках доступен из входного параметра path->indexinfo).

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

  3. Вычисляет стоимость доступа к индексу. Универсальный оценщик может сделать это так:

/*
 * Our generic assumption is that the index pages will be read
 * sequentially, so they cost seq_page_cost each, not random_page_cost.
 * Also, we charge for evaluation of the indexquals at each index row.
 * All the costs are assumed to be paid incrementally during the scan.
 */
cost_qual_eval(&index_qual_cost, path->indexquals, root);
*indexStartupCost = index_qual_cost.startup;
*indexTotalCost = seq_page_cost * numIndexPages +
    (cpu_index_tuple_cost + index_qual_cost.per_tuple) * numIndexTuples;

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

  1. Оценивает коэффициент корреляции. Для простого упорядоченного индекса по одному полю значение можно получить из pg_statistic. Если корреляция неизвестна, то консервативная оценка равна нулю (без корреляции).

Примеры функций оценки стоимости можно найти в разделе src/backend/utils/adt/selfuncs.c.