Postgres extensíveis

No último PGConf.Russia, havia um relatório sobre a extensão MobilityDB , e Andrei Borodin propôs a idéia de expandir métodos de índice para a tarefa.

Continuarei o tópico com a extensão Postgres para a tarefa a ser resolvida usando o exemplo da extensão feita como parte da HighLoad Cup 2018, o código está disponível no GithHub . No habr já existe um artigo do blackmaster . A extensão adiciona dois tipos com suporte para índices btree e GIN.

Esquema inicial:

CREATE TABLE accounts ( id INTEGER PRIMARY KEY, email VARCHAR(100) UNIQUE, fname SMALLINT, sname VARCHAR(50), phone VARCHAR(16) UNIQUE, birth TIMESTAMP NOT NULL, country SMALLINT, city SMALLINT, email_domain SMALLINT, joined TIMESTAMP NOT NULL, status status, sex sex NOT NULL, interests SMALLINT[], premium tsrange, likes_ids INTEGER[], likes_tss INTEGER[], CHECK ( joined >= '01.01.2011'::timestamp ), CHECK ( joined <= '01.01.2018'::timestamp ) ); CREATE INDEX IF NOT EXISTS interests_ids_index ON accounts USING GIN(interests); 

O número de registros é 1.300.000 e o tamanho do relacionamento de interesse:

O circuito final:

 CREATE UNLOGGED TABLE accounts ( id INTEGER PRIMARY KEY, email VARCHAR(100) UNIQUE, fname SMALLINT, sname VARCHAR(50), phone phone UNIQUE, birth TIMESTAMP NOT NULL, country SMALLINT, city SMALLINT, email_domain SMALLINT, joined TIMESTAMP NOT NULL, status status, sex sex NOT NULL, interests bit128, premium tsrange, likes_ids INTEGER[], likes_tss INTEGER[], CHECK ( joined >= '01.01.2011'::timestamp ), CHECK ( joined <= '01.01.2018'::timestamp ) ); 

Dimensões:

Dois tipos foram adicionados: telefone e bit128 .

telefone

O número de telefone é 8 (929) 5481819 , os oito podem ser descartados. O código do operador se encaixa em 10 bits, o número é 24 bits, e você precisa de 5 bytes. Não é um número muito conveniente devido ao alinhamento de dados na memória. Para a questão de qual a melhor forma de ajustar os dados em 5, 6 ou 8 bytes, apenas os testes podem dar uma resposta.

Se você seguir o exemplo da documentação, precisará de um pouco. Definir tipo:

 class Phone : public PAllocNew<Phone> { public: bool fromCString(char* str) noexcept; char* toCString() const noexcept; int code() const noexcept; bool operator==(const Phone& b) const noexcept; bool operator<(const Phone& b) const noexcept; bool operator<=(const Phone& b) const noexcept; bool operator>(const Phone& b) const noexcept; bool operator>=(const Phone& b) const noexcept; private: uint64_t m_data = 0; }; #define GETARG_PHONE(x) reinterpret_cast<Phone*>(PG_GETARG_POINTER(x)) 

Classe auxiliar PAllocNew sobrecarregando new :

 template<typename T> class PAllocNew { public: static void* operator new(std::size_t count, const std::nothrow_t& tag) { return palloc(count); } }; 

A memória alocada através do palloc é liberada quando a transação é concluída. Adicionar funções de E / S:

 Datum phone_in(PG_FUNCTION_ARGS) { char* str = PG_GETARG_CSTRING(0); auto v = new(std::nothrow) Phone; if (!v->fromCString(str)) { ereport(ERROR, (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION), errmsg( "invalid input syntax for phone: \"%s\"", str ))); } PG_RETURN_POINTER(v); } Datum phone_out(PG_FUNCTION_ARGS) { const auto phone = GETARG_PHONE(0); PG_RETURN_CSTRING(phone->toCString()); } 

E tipo de registro:

 CREATE TYPE phone; CREATE OR REPLACE FUNCTION phone_in ( cstring ) RETURNS phone AS 'libhighloadcup' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE; CREATE OR REPLACE FUNCTION phone_out ( phone ) RETURNS cstring AS 'libhighloadcup' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE; CREATE TYPE phone ( INTERNALLENGTH = 8, INPUT = phone_in, OUTPUT = phone_out, ALIGNMENT = int4, COLLATE TRUE ); 

Porque o novo tipo tem um tamanho não superior a 8 bytes, pode ser transmitido não por referência, mas por valor. Nesse caso, você deve especificar o sinalizador PASSEDBYVALUE em CREATE TYPE . Ou use LIKE :

 CREATE TYPE phone ( INPUT = phone_in, OUTPUT = phone_out, LIKE = int8, COLLATE TRUE ); 

Em seguida, INTERNALLENGTH , ALIGNMENT e PASSEDBYVALUE herdados de int8.

índice btree

A exclusividade do campo é suportada pela criação de um índice de árvore B exclusivo. Isso é feito através de classes de operadores e estratégias .

 CREATE OPERATOR = ( PROCEDURE = phone_equal, LEFTARG = phone, RIGHTARG = phone, COMMUTATOR = =, NEGATOR = != ); CREATE OPERATOR < ( PROCEDURE = phone_lt, LEFTARG = phone, RIGHTARG = phone, NEGATOR = > ); CREATE OPERATOR <= ( PROCEDURE = phone_le, LEFTARG = phone, RIGHTARG = phone ); CREATE OPERATOR >= ( PROCEDURE = phone_ge, LEFTARG = phone, RIGHTARG = phone ); CREATE OPERATOR > ( PROCEDURE = phone_gt, LEFTARG = phone, RIGHTARG = phone, NEGATOR = < ); CREATE OPERATOR CLASS btree_phone_ops DEFAULT FOR TYPE phone USING btree AS OPERATOR 1 <, OPERATOR 2 <=, OPERATOR 3 =, OPERATOR 4 >=, OPERATOR 5 >, FUNCTION 1 phone_equal_internal ( phone, phone ); 

Os operadores retornam bool e phone_equal_internal int:

 Datum phone_equal_internal(PG_FUNCTION_ARGS) { const auto a = GETARG_PHONE(0); const auto b = GETARG_PHONE(1); if (*a < *b) { PG_RETURN_INT32(-1); } if (*a > *b) { PG_RETURN_INT32(1); } PG_RETURN_INT32(0); } 

Tudo isso deu uma ligeira diminuição nos dados:

O número de contas com os números 533.289, que é 41%. Pelo menos não há comparação de cadeias ao trabalhar com um índice.

bit128

Eu queria ter um campo de bits com operações de interseção (&&), ocorrência (<@) e com suporte GIN. Foi o suficiente para 96 ​​bits, mas seguiu um caminho simples e tomou o uint128 .

 class BitSet128: public PAllocNew<BitSet128> { public: bool haveIntersection(const BitSet128& b) const noexcept; bool contains(const BitSet128& b) const noexcept; bool operator==(const BitSet128& b) const noexcept; bool operator<(const BitSet128& b) const noexcept; bool operator>(const BitSet128& b) const noexcept; bool fromCString(char* str) noexcept; char* toCString() const noexcept; std::vector<uint8_t> keys() const; private: uint128 m_bits = 0; }; #define GETARG_BIT128(x) reinterpret_cast<BitSet128*>(PG_GETARG_POINTER(x)) 

Registro do tipo e operação:

 CREATE TYPE bit128 ( INTERNALLENGTH = 16, INPUT = bit128_in, OUTPUT = bit128_out, ALIGNMENT = int4 ); CREATE OPERATOR = ( PROCEDURE = bit128_equal, LEFTARG = bit128, RIGHTARG = bit128, COMMUTATOR = =, NEGATOR = != ); CREATE OPERATOR && ( PROCEDURE = bit128_intersection, LEFTARG = bit128, RIGHTARG = bit128 ); CREATE OPERATOR @> ( PROCEDURE = bit128_containts, LEFTARG = bit128, RIGHTARG = bit128 ); 

Índice Invertido Generalizado / GIN

Egor Rogov erogov escreveu bem sobre o GIN no Postgres no artigo Indexes no PostgreSQL - 7 , aplicando-o à tarefa de pesquisa de texto completo. A documentação de extensibilidade do GIN sugere que é suficiente implementar 4 funções:

Recuperando uma matriz de chaves de um objeto indexado:

 Datum *extractValue(Datum itemValue, int32 *nkeys, bool **nullFlags) 

Recupera as chaves para o valor solicitado:

 Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode) 

Por exemplo, em uma consulta:

 SELECT * FROM test WHERE a && ARRAY[1, 2, 3] 

extractQuery é aplicado à matriz ARRAY[1, 2, 3] e as chaves podem ser 1, 2, 3.
Verifica se o valor corresponde à consulta:

 bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[]) 

Como as chaves extraídas são armazenadas na árvore de pesquisa, precisamos de uma função de comparação:

 int compare(Datum a, Datum b) 

A API pode parecer redundante, mas fornece tudo o que pode ser útil. Vamos para a implementação. Extração de chave:

 Datum gin_extract_value_bit128(PG_FUNCTION_ARGS) { auto bitset = GETARG_BIT128(0); const auto bits = bitset->keys(); int32* nentries = (int32*) PG_GETARG_POINTER(1); *nentries = bits.size(); Datum* entries = NULL; entries = (Datum*) palloc(sizeof(Datum) * bits.size()); for (int i = 0; i < bits.size(); ++i) { entries[i] = DatumGetInt16(bits[i]); } PG_RETURN_POINTER(entries); } 

No parâmetro nentries saída nentries escreva o número de chaves e retorne uma matriz de entries de chaves. Comparação de chaves:

 Datum bit128_cmp(PG_FUNCTION_ARGS) { const auto a = PG_GETARG_INT16(0); const auto b = PG_GETARG_INT16(1); if (a < b) { PG_RETURN_INT32(-1); } if (a > b) { PG_RETURN_INT32(1); } PG_RETURN_INT32(0); } 

Essas duas funções são suficientes para criar um índice. Outras funções são usadas ao pesquisar por índice. Extraindo chaves de uma solicitação:

 Datum gin_extract_query_bit128(PG_FUNCTION_ARGS) { const auto a = GETARG_BIT128(0); int32* nentries = (int32*) PG_GETARG_POINTER(1); StrategyNumber strategy = PG_GETARG_UINT16(2); int32* searchMode = (int32*) PG_GETARG_POINTER(6); Datum* res = nullptr; const auto keys = a->keys(); *nentries = keys.size(); res = (Datum*) palloc(sizeof(Datum) * keys.size()); for (int i = 0; i < keys.size(); ++i) { res[i] = DatumGetInt16(keys[i]); } switch (strategy) { case RTOverlapStrategyNumber: // && if (*nentries > 0) { *searchMode = GIN_SEARCH_MODE_DEFAULT; } else { *searchMode = GIN_SEARCH_MODE_ALL; } break; case RTContainsStrategyNumber: // @> if (*nentries > 0) { *searchMode = GIN_SEARCH_MODE_DEFAULT; } else { *searchMode = GIN_SEARCH_MODE_ALL; } break; } PG_RETURN_POINTER(res); } 

O primeiro parâmetro passa o valor à direita do operador, o terceiro parâmetro é responsável pela estratégia (operador) pela qual a pesquisa ocorre. Sobre os modos de pesquisa é melhor familiarizado na documentação . Função de conformidade:

 Datum gin_bit128_consistent(PG_FUNCTION_ARGS) { bool* check = (bool*) PG_GETARG_POINTER(0); StrategyNumber strategy = PG_GETARG_UINT16(1); int32 nkeys = PG_GETARG_INT32(3); bool* recheck = (bool*) PG_GETARG_POINTER(5); bool res = true; switch (strategy) { case RTOverlapStrategyNumber: // && { for (int i = 0; i < nkeys; ++i) { if (check[i]) { res = true; } }; *recheck = false; } break; case RTContainsStrategyNumber: // @> { for (int i = 0; i < nkeys; ++i) { if (check[i]) { res = true; } }; *recheck = true; } break; } PG_RETURN_BOOL(res); } 

Retorna true se o objeto indexado satisfizer o operador de consulta com o número da estratégia. A matriz de verificação possui um número de chaves, que corresponde ao número de chaves retornadas por gin_extract_query_bit128 . Marcar check[i] = true significa que a i-ésima chave de gin_extract_query_bit128 está presente no objeto indexado. Isso é o suficiente para atravessar, mas porque no GIN, não trabalhamos com os próprios valores; em seguida, para a estratégia de entrada que definimos, verifique novamente como true. Isso chamará o operador apropriado para verificar o resultado. Classe de Operador:

 CREATE OR REPLACE FUNCTION gin_extract_value_bit128 ( bit128, internal, internal) RETURNS internal AS 'libhighloadcup' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE; CREATE OR REPLACE FUNCTION gin_extract_query_bit128(bit128, internal, int2, internal, internal) RETURNS internal AS 'libhighloadcup' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE; CREATE OR REPLACE FUNCTION gin_bit128_consistent(internal, int2, anyelement, int4, internal, internal) RETURNS bool AS 'libhighloadcup' LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE; CREATE OPERATOR CLASS bit128_ops DEFAULT FOR TYPE bit128 USING gin AS OPERATOR 3 &&, OPERATOR 6 =, OPERATOR 7 @>, FUNCTION 1 bit128_cmp (int2, int2 ), FUNCTION 2 gin_extract_value_bit128(bit128, internal, internal), FUNCTION 3 gin_extract_query_bit128(bit128, internal, int2, internal, internal), FUNCTION 4 gin_bit128_consistent(internal, int2, anyelement, int4, internal, internal), STORAGE int2; 

ARMAZENAMENTO foi adicionado, indica que tipo de dados é usado para chaves. Qual é o resultado do disco:

Um resultado interessante, porque existem nuances:

• armazenamento físico do banco de dados;
• distribuição de dados.

Todos os tipos criados têm um tamanho fixo, portanto, o armazenamento PLAIN é selecionado para eles. Compactação e armazenamento separado não se aplicam a eles. Matrizes e seqüências de caracteres como tipos de comprimento variável passam pelo TOAST. Sim, há sobrecarga para armazenar tamanho, mas também há compactação.

A distribuição de interesses é a seguinte:

Honestamente, não sei como o SMALLINT[] lançado, mas suponha 4 bytes por tamanho e 2 bytes por valor. Em 16 bytes, você pode ajustar uma matriz de 6 elementos. E 98% dos elementos caberiam em 16 bytes e diferenças de 16 MB. Parece que o tipo bit128 redundante, mas o tipo padrão é redundante neste conjunto de dados.