64.3. Опорные функции B-деревьев
Пред. НаверхГлава 64. Индексы B-деревьяНачало След.

64.3. Опорные функции B-деревьев

Как показано в Таблице 37.9, btree определяет одну необходимую и четыре необязательных опорных функции. Таким образом, пользователь может задать пять методов:

order

Для всех комбинаций типов данных, для которых семейство операторов btree предоставляет операторы сравнения, оно должно предоставлять опорную функцию сравнения в pg_amproc с номером 1 и c amproclefttype/amprocrighttype, равными левому и правому типу сравнения (то есть тем же типам данных, с которыми соответствующие операторы зарегистрированы в pg_amop). Эта функция сравнения должна принимать два отличных от NULL значения A и B и возвращать значение int32, которое будет < 0, 0 или > 0, когда A < B, A = B или A > B, соответственно. Результат NULL не допускается: все значения типа данных должны быть сравнимыми.

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

sortsupport

Дополнительно семейство операторов btree может предоставить функции поддержки сортировки, которые регистрируются под номером опорной функции 2. Эти функции позволяют реализовывать сравнения для целей сортировки гораздо эффективнее, чем это возможно при прямолинейном вызове функции поддержки сравнения. Задействованные в этом программные интерфейсы определены в src/include/utils/sortsupport.h.

in_range

Дополнительно семейство операторов btree может предоставить опорные функции in_range, которые регистрируются под номером 3. Они не используются в ходе операций с индексом btree; вместо этого они расширяют семантику семейства операторов, чтобы оно могло поддерживать оконные предложения RANGE смещение PRECEDING и RANGE смещение FOLLOWING (см. Подраздел 4.2.8). По сути они предоставляют дополнительную информацию, позволяющую добавлять или вычитать смещение в соответствии с порядком сортировки, принятым в семействе.

Функция in_range должна иметь сигнатуру 

in_range(значение type1, база type1, смещение type2, вычитание bool, меньше bool)
returns bool

Значение и база должны быть одного типа данных, и этот тип должен поддерживаться семейством операторов (то есть это должен быть тип, для которого реализуется сортировка). Однако смещение может быть другого типа, который никаким другим образом не поддерживается данным семейством. Например, встроенное семейство time_ops предоставляет функцию, для которой смещение имеет тип interval. Семейство может предоставлять функции in_range для любых из своих поддерживаемых типов и одного или нескольких типов смещений. Каждая функция in_range должна регистрироваться в pg_amproc с полем amproclefttype, равным type1, и amprocrighttype, равным type2.

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

  • если !вычитание и !меньше, возвращается значение >= (база + смещение)

  • если !вычитание и меньше, возвращается значение <= (база + смещение)

  • если вычитание и !меньше, возвращается значение >= (база - смещение)

  • если вычитание и меньше, возвращается значение <= (база - смещение)

Прежде чем делать это, функция должна проверить знак смещения и, если оно отрицательное, выдать ошибку ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE (22013) с текстом ошибки «invalid preceding or following size in window function» (неверная предшествующая или последующая величина в оконной функции). (Это требуется стандартом SQL, но нестандартные семейства операторов могут проигнорировать данное ограничение, так как оно не несёт большой смысловой нагрузки.) Проверка этого требования делегируется функции in_range, чтобы коду ядра не требовалось понимать, что означает «меньше нуля» для произвольного типа данных.

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

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

  • Если in_range с меньше = true возвращает true для некоторого значения1 и базы, true должно возвращаться для каждого значения2 <= значению1 с той же базой.

  • Если in_range с меньше = true возвращает false для некоторого значения1 и базы, false должно возвращаться для любого значения2 >= значению1 с той же базой.

  • Если in_range с меньше = true возвращает true для некоторого значения и базы1, true должно возвращаться для каждой базы2 >= базе1 с тем же значением.

  • Если in_range с меньше = true возвращает false для некоторого значения и базы1, false должно возвращаться для любой базы2 <= базе1 с тем же значением.

Аналогичные утверждения с противоположными условиями должны выполняться при меньше = false.

Если упорядочиваемый тип (type1) является сортируемым, функции in_range будет передан OID соответствующего правила сортировки через стандартный механизм PG_GET_COLLATION().

Функции in_range не должны обрабатывать NULL в аргументах и обычно помечаются как строгие.

equalimage

Дополнительно семейство операторов btree может предоставить опорные функции equalimage («равенство подразумевает равенство образов»), регистрируемые под номером 4. Эти функции позволяют коду ядра определить, безопасно ли применять исключение дубликатов в B-дереве. В настоящее время функции equalimage вызываются только при построении или перестроении индекса.

Функция equalimage должна иметь сигнатуру 

equalimage(opcintype oid) returns bool

Её результатом будет статическая информация о классе операторов и правиле сортировки. Результат true означает, что функция order для класса операторов будет возвращать 0 (признак равенства аргументов), только когда аргументы A и B взаимозаменяемы без потери семантической информации. Если функция equalimage не определена или она возвращает false, рассчитывать на выполнение данного условия нельзя.

В аргументе opcintype передаётся pg_type.oid типа данных, индексируемого данным классом операторов. Это сделано для удобства повторного использования нижележащей функции equalimage в разных классах операторов. Если тип opcintype поддерживает правила сортировки, функции equalimage будет передан OID соответствующего правила через стандартный механизм PG_GET_COLLATION().

С точки зрения класса операторов возвращаемое значение true означает, что возможно безопасное применение исключения дубликатов (или оно безопасно для правила сортировки, OID которого был передан функции equalimage). Однако код ядра будет считать исключение дубликатов безопасным для индекса, только если для каждого столбца в этом индексе используется класс операторов, регистрирующий функцию equalimage, и все эти функции при вызове возвращают true.

Равенство образов почти равнозначно простому битовому равенству. Но есть одно небольшое различие: когда индексируется тип данных varlena, представление двух равных образов на диске может отличаться из-за различного применения сжатия TOAST к входным данным. Говоря формально, когда функция equalimage класса операторов возвращает true, можно полагать, что функция на C datum_image_eq() гарантированно будет согласованной с функцией order класса операторов (при условии передачи обеим функциям одинакового OID правила сортировки).

Код ядра в принципе не может сделать какие-то выводы о свойстве класса операторов «равенство подразумевает равенство образов» в семействе операторов для множества типов, анализируя другие классы операторов в том же семействе. Также не имеет смысла регистрировать межтиповую функцию equalimage для семейства операторов, и при попытке сделать это произойдёт ошибка. Это связано с тем, что свойство «равенство подразумевает равенство образов» зависит не только от семантики сортировки/равенства, определяемой в некоторой степени на уровне семейства операторов. Вообще говоря, это свойство относится к конкретному типу и должно рассматриваться отдельно.

Для классов операторов, поставляемых в базовом продукте Postgres Pro, принято соглашение регистрировать универсальную функцию equalimage. Большинство классов операторов регистрируют в качестве такой функции btequalimage(), которая устанавливает, что исключение дубликатов безопасно без дополнительных условий. Операторы классов для типов данных, поддерживающих правила сортировки, например, для типа text, регистрируют функцию btvarstrequalimage(), которая устанавливает, что исключение дубликатов безопасно с детерминированными правилами сортировки. Для сохранения порядка в сторонних расширениях также рекомендуется регистрировать их собственные функции equalimage.

options

В дополнение семейство операторов btree может предоставить опорные функции options («параметры класса операторов»), регистрируемые под номером 5. Эти функции позволяют определить набор видимых пользователю параметров, управляющих поведением класса операторов.

Опорная функция options должна иметь сигнатуру 

options(relopts local_relopts *) returns void

Этой функции передаётся указатель на структуру local_relopts, в которую нужно внести набор параметров, относящихся к классу операторов. Обращаться к этим параметрам из других опорных функций можно с помощью макросов PG_HAS_OPCLASS_OPTIONS() и PG_GET_OPCLASS_OPTIONS().

В настоящее время опорная функция options не определена ни для одного из классов операторов btree. Сама организация B-дерева не позволяет гибко менять представление ключей, как это возможно с GiST, SP-GiST, GIN и BRIN. Поэтому с существующим методом доступа к индексу-B-дереву для функции options нет полезных применений. Тем не менее эта опорная функция была добавлена для B-дерева ради единообразия и не исключено, что она окажется полезной по мере развития реализации B-дерева в PostgreSQL.

Пред. Наверх След.
64.2. Поведение классов операторов B-дерева Начало 64.4. Реализация
40.13. User-Defined Types
Prev UpChapter 40. Extending SQLHome Next

40.13. User-Defined Types

40.13.1. TOAST Considerations

As described in Section 40.2, Postgres Pro can be extended to support new data types. This section describes how to define new base types, which are data types defined below the level of the SQL language. Creating a new base type requires implementing functions to operate on the type in a low-level language, usually C.

A user-defined type must always have input and output functions. These functions determine how the type appears in strings (for input by the user and output to the user) and how the type is organized in memory. The input function takes a null-terminated character string as its argument and returns the internal (in memory) representation of the type. The output function takes the internal representation of the type as argument and returns a null-terminated character string. If we want to do anything more with the type than merely store it, we must provide additional functions to implement whatever operations we'd like to have for the type.

Suppose we want to define a type complex that represents complex numbers. A natural way to represent a complex number in memory would be the following C structure: 

typedef struct Complex {
    double      x;
    double      y;
} Complex;

We will need to make this a pass-by-reference type, since it's too large to fit into a single Datum value.

As the external string representation of the type, we choose a string of the form (x,y).

The input and output functions are usually not hard to write, especially the output function. But when defining the external string representation of the type, remember that you must eventually write a complete and robust parser for that representation as your input function. For instance: 

PG_FUNCTION_INFO_V1(complex_in);

Datum
complex_in(PG_FUNCTION_ARGS)
{
    char       *str = PG_GETARG_CSTRING(0);
    double      x,
                y;
    Complex    *result;

    if (sscanf(str, " ( %lf , %lf )", &x, &y) != 2)
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
                 errmsg("invalid input syntax for type %s: \"%s\"",
                        "complex", str)));

    result = (Complex *) palloc(sizeof(Complex));
    result->x = x;
    result->y = y;
    PG_RETURN_POINTER(result);
}

The output function can simply be: 

PG_FUNCTION_INFO_V1(complex_out);

Datum
complex_out(PG_FUNCTION_ARGS)
{
    Complex    *complex = (Complex *) PG_GETARG_POINTER(0);
    char       *result;

    result = psprintf("(%g,%g)", complex->x, complex->y);
    PG_RETURN_CSTRING(result);
}

You should be careful to make the input and output functions inverses of each other. If you do not, you will have severe problems when you need to dump your data into a file and then read it back in. This is a particularly common problem when floating-point numbers are involved.

Optionally, a user-defined type can provide binary input and output routines. Binary I/O is normally faster but less portable than textual I/O. As with textual I/O, it is up to you to define exactly what the external binary representation is. Most of the built-in data types try to provide a machine-independent binary representation. For complex, we will piggy-back on the binary I/O converters for type float8: 

PG_FUNCTION_INFO_V1(complex_recv);

Datum
complex_recv(PG_FUNCTION_ARGS)
{
    StringInfo  buf = (StringInfo) PG_GETARG_POINTER(0);
    Complex    *result;

    result = (Complex *) palloc(sizeof(Complex));
    result->x = pq_getmsgfloat8(buf);
    result->y = pq_getmsgfloat8(buf);
    PG_RETURN_POINTER(result);
}

PG_FUNCTION_INFO_V1(complex_send);

Datum
complex_send(PG_FUNCTION_ARGS)
{
    Complex    *complex = (Complex *) PG_GETARG_POINTER(0);
    StringInfoData buf;

    pq_begintypsend(&buf);
    pq_sendfloat8(&buf, complex->x);
    pq_sendfloat8(&buf, complex->y);
    PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
}

Once we have written the I/O functions and compiled them into a shared library, we can define the complex type in SQL. First we declare it as a shell type: 

CREATE TYPE complex;

This serves as a placeholder that allows us to reference the type while defining its I/O functions. Now we can define the I/O functions: 

CREATE FUNCTION complex_in(cstring)
    RETURNS complex
    AS 'filename'
    LANGUAGE C IMMUTABLE STRICT;

CREATE FUNCTION complex_out(complex)
    RETURNS cstring
    AS 'filename'
    LANGUAGE C IMMUTABLE STRICT;

CREATE FUNCTION complex_recv(internal)
   RETURNS complex
   AS 'filename'
   LANGUAGE C IMMUTABLE STRICT;

CREATE FUNCTION complex_send(complex)
   RETURNS bytea
   AS 'filename'
   LANGUAGE C IMMUTABLE STRICT;

Finally, we can provide the full definition of the data type: 

CREATE TYPE complex (
   internallength = 16,
   input = complex_in,
   output = complex_out,
   receive = complex_recv,
   send = complex_send,
   alignment = double
);

When you define a new base type, Postgres Pro automatically provides support for arrays of that type. The array type typically has the same name as the base type with the underscore character (_) prepended.

Once the data type exists, we can declare additional functions to provide useful operations on the data type. Operators can then be defined atop the functions, and if needed, operator classes can be created to support indexing of the data type. These additional layers are discussed in following sections.

If the internal representation of the data type is variable-length, the internal representation must follow the standard layout for variable-length data: the first four bytes must be a char[4] field which is never accessed directly (customarily named vl_len_). You must use the SET_VARSIZE() macro to store the total size of the datum (including the length field itself) in this field and VARSIZE() to retrieve it. (These macros exist because the length field may be encoded depending on platform.)

For further details see the description of the CREATE TYPE command.

40.13.1. TOAST Considerations

If the values of your data type vary in size (in internal form), it's usually desirable to make the data type TOAST-able (see Section 70.2). You should do this even if the values are always too small to be compressed or stored externally, because TOAST can save space on small data too, by reducing header overhead.

To support TOAST storage, the C functions operating on the data type must always be careful to unpack any toasted values they are handed by using PG_DETOAST_DATUM. (This detail is customarily hidden by defining type-specific GETARG_DATATYPE_P macros.) Then, when running the CREATE TYPE command, specify the internal length as variable and select some appropriate storage option other than plain.

If data alignment is unimportant (either just for a specific function or because the data type specifies byte alignment anyway) then it's possible to avoid some of the overhead of PG_DETOAST_DATUM. You can use PG_DETOAST_DATUM_PACKED instead (customarily hidden by defining a GETARG_DATATYPE_PP macro) and using the macros VARSIZE_ANY_EXHDR and VARDATA_ANY to access a potentially-packed datum. Again, the data returned by these macros is not aligned even if the data type definition specifies an alignment. If the alignment is important you must go through the regular PG_DETOAST_DATUM interface.

Note

Older code frequently declares vl_len_ as an int32 field instead of char[4]. This is OK as long as the struct definition has other fields that have at least int32 alignment. But it is dangerous to use such a struct definition when working with a potentially unaligned datum; the compiler may take it as license to assume the datum actually is aligned, leading to core dumps on architectures that are strict about alignment.

Another feature that's enabled by TOAST support is the possibility of having an expanded in-memory data representation that is more convenient to work with than the format that is stored on disk. The regular or “flat” varlena storage format is ultimately just a blob of bytes; it cannot for example contain pointers, since it may get copied to other locations in memory. For complex data types, the flat format may be quite expensive to work with, so Postgres Pro provides a way to “expand” the flat format into a representation that is more suited to computation, and then pass that format in-memory between functions of the data type.

To use expanded storage, a data type must define an expanded format that follows the rules given in src/include/utils/expandeddatum.h, and provide functions to “expand” a flat varlena value into expanded format and “flatten” the expanded format back to the regular varlena representation. Then ensure that all C functions for the data type can accept either representation, possibly by converting one into the other immediately upon receipt. This does not require fixing all existing functions for the data type at once, because the standard PG_DETOAST_DATUM macro is defined to convert expanded inputs into regular flat format. Therefore, existing functions that work with the flat varlena format will continue to work, though slightly inefficiently, with expanded inputs; they need not be converted until and unless better performance is important.

C functions that know how to work with an expanded representation typically fall into two categories: those that can only handle expanded format, and those that can handle either expanded or flat varlena inputs. The former are easier to write but may be less efficient overall, because converting a flat input to expanded form for use by a single function may cost more than is saved by operating on the expanded format. When only expanded format need be handled, conversion of flat inputs to expanded form can be hidden inside an argument-fetching macro, so that the function appears no more complex than one working with traditional varlena input. To handle both types of input, write an argument-fetching function that will detoast external, short-header, and compressed varlena inputs, but not expanded inputs. Such a function can be defined as returning a pointer to a union of the flat varlena format and the expanded format. Callers can use the VARATT_IS_EXPANDED_HEADER() macro to determine which format they received.

The TOAST infrastructure not only allows regular varlena values to be distinguished from expanded values, but also distinguishes “read-write” and “read-only” pointers to expanded values. C functions that only need to examine an expanded value, or will only change it in safe and non-semantically-visible ways, need not care which type of pointer they receive. C functions that produce a modified version of an input value are allowed to modify an expanded input value in-place if they receive a read-write pointer, but must not modify the input if they receive a read-only pointer; in that case they have to copy the value first, producing a new value to modify. A C function that has constructed a new expanded value should always return a read-write pointer to it. Also, a C function that is modifying a read-write expanded value in-place should take care to leave the value in a sane state if it fails partway through.

Prev Up Next
40.12. User-Defined Aggregates Home 40.14. User-Defined Operators