Postgres extensible

Lors du dernier PGConf.Russia, il y avait un rapport sur l'extension MobilityDB , et Andrei Borodin a proposé l' idée d' étendre les méthodes d'indexation pour la tâche.

Je continuerai le sujet avec l'extension Postgres pour la tâche à résoudre en utilisant l'exemple de l'extension faite dans le cadre de la HighLoad Cup 2018, le code est disponible sur GithHub . Sur habr il y a déjà un article de blackmaster . L'extension ajoute deux types avec prise en charge des index btree et GIN.

Schéma initial:

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); 

Le nombre d'enregistrements est de 1 300 000 et la taille de la relation d'intérêt:

Le circuit 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 ) ); 

Dimensions:

Deux types ont été ajoutés: téléphone et bit128 .

téléphone

Le numéro de téléphone est le 8 (929) 5481819 , les huit peuvent être supprimés. Le code opérateur tient en 10 bits, nombre 24 bits, il s'avère que vous avez besoin de 5 octets. Pas un nombre très pratique en raison de l'alignement des données en mémoire. À la question de savoir comment ajuster au mieux les données en 5, 6 ou 8 octets, seuls les tests peuvent donner une réponse.

Si vous suivez l' exemple de la documentation, vous en avez besoin d'un peu. Définir le type:

 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)) 

PAllocNew classe d'assistance surchargeant new :

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

La mémoire allouée via palloc est libérée à la fin de la transaction. Ajouter des fonctions d'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()); } 

Et type d'enregistrement:

 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 ); 

Parce que le nouveau type a une taille ne dépassant pas 8 octets, il peut être transmis non pas par référence, mais par valeur. Dans ce cas, vous devez spécifier l'indicateur PASSEDBYVALUE dans CREATE TYPE . Ou utilisez LIKE :

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

Puis INTERNALLENGTH , PASSEDBYVALUE et PASSEDBYVALUE hérités de int8.

indice btree

L'unicité du champ est prise en charge par la création d'un index B-tree unique. Cela se fait à travers des classes d'opérateurs et des stratégies .

 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 ); 

Les opérateurs renvoient bool et 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); } 

Tout cela a donné une légère diminution des données:

Le nombre de comptes avec les numéros 533 289, soit 41%. Au moins, il n'y a pas de comparaison de chaînes lorsque vous travaillez avec un index.

bit128

Je voulais avoir un champ de bits avec des opérations d'intersection (&&), d'occurrence (<@) et avec le support GIN. Il suffisait de 96 bits, mais a suivi un chemin simple et a pris 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)) 

Enregistrement du type et du fonctionnement:

 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 ); 

Index inversé généralisé / GIN

Egor Rogov erogov a bien écrit sur GIN dans Postgres dans l'article Indexes de PostgreSQL - 7 , en l'appliquant à la tâche de recherche en texte intégral. La documentation d' extensibilité de GIN suggère qu'il suffit de mettre en œuvre 4 fonctions:

Récupération d'un tableau de clés à partir d'un objet indexé:

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

Récupère les clés de la valeur demandée:

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

Par exemple, dans une requête:

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

extractQuery est appliqué au tableau ARRAY[1, 2, 3] et les clés peuvent être 1, 2, 3.
Vérifie si la valeur correspond à la requête:

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

Puisque les clés extraites sont stockées dans l'arbre de recherche, nous avons besoin d'une fonction de comparaison:

 int compare(Datum a, Datum b) 

L'API peut sembler redondante, mais fournit tout ce qui peut être utile. Passons à la mise en œuvre. Extraction de clés:

 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); } 

Dans les nentries paramètres de sortie nentries écrivez le nombre de clés et renvoyez un tableau d' entries de clés. Comparaison clé:

 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); } 

Ces deux fonctions suffisent pour créer un index. D'autres fonctions sont utilisées lors de la recherche par index. Extraire des clés d'une requête:

 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); } 

Le premier paramètre transmet la valeur à droite de l'opérateur, le troisième paramètre est responsable de la stratégie (opérateur) par laquelle la recherche est effectuée. Les modes de recherche sont mieux connus dans la documentation . Fonction de conformité:

 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); } 

Renvoie true si l'objet indexé satisfait l'opérateur de requête avec le numéro de stratégie. Le tableau de contrôle est long de nkeys , ce qui correspond au nombre de clés retournées par gin_extract_query_bit128 . La vérification de check[i] = true signifie que la i-ème clé de gin_extract_query_bit128 est présente dans l'objet indexé. C'est suffisant pour traverser, mais parce que dans GIN, nous ne travaillons pas avec les valeurs elles-mêmes, puis pour la stratégie d'entrée, nous réglons revérifier sur true. Cela appellera l'opérateur approprié pour vérifier le résultat. Classe d'opérateur:

 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; 

STORAGE a été ajouté, il indique quel type de données est utilisé pour les clés. Quel est le résultat du disque:

Un résultat intéressant, car il y a des nuances:

• stockage physique de la base de données;
• distribution des données.

Tous les types créés ont une taille fixe, donc le stockage PLAIN est sélectionné pour eux. La compression et le stockage séparé ne leur sont pas applicables. Les tableaux et les chaînes en tant que types de longueur variable passent par TOAST. Oui, il y a des frais généraux pour stocker la taille, mais il y a aussi la compression.

La répartition des intérêts est la suivante:

Honnêtement, je ne sais pas comment SMALLINT[] libéré, mais supposons 4 octets par taille et 2 octets par valeur. Ensuite, en 16 octets, vous pouvez adapter un tableau de 6 éléments. Et 98% des éléments tiendraient dans 16 octets et des différences de 16 Mo. Il semble que le type bit128 redondant, mais le type standard est redondant sur cet ensemble de données.