Erweiterbare Postgres

Auf der letzten PGConf.Russia gab es einen Bericht über die Erweiterung MobilityDB , und Andrei Borodin schlug die Idee vor , die Indexmethoden für die Aufgabe zu erweitern.

Ich werde das Thema mit der Postgres-Erweiterung für die zu lösende Aufgabe am Beispiel der Erweiterung fortsetzen, die im Rahmen des HighLoad Cup 2018 erstellt wurde. Der Code ist auf GithHub verfügbar. Auf habr gibt es schon einen Artikel von blackmaster . Die Erweiterung fügt zwei Typen mit Unterstützung für btree- und GIN-Indizes hinzu.

Erstes Schema:

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

Die Anzahl der Datensätze beträgt 1.300.000 und die Größe des interessierenden Verhältnisses:

Die letzte Runde:

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

Abmessungen:

Zwei Typen wurden hinzugefügt: Telefon und Bit128 .

Telefon

Die Telefonnummer ist 8 (929) 5481819 , die acht können verworfen werden. Der Operatorcode passt in 10 Bit, die Zahl ist 24 Bit, es stellt sich heraus, dass Sie 5 Bytes benötigen. Aufgrund der Datenausrichtung im Speicher keine sehr bequeme Zahl. Auf die Frage, wie Daten am besten in 5, 6 oder 8 Bytes eingepasst werden können, können nur Tests eine Antwort geben.

Wenn Sie dem Beispiel aus der Dokumentation folgen, brauchen Sie ein wenig. Typ definieren:

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

Überladung der PAllocNew-Hilfsklasse new :

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

Der über Palloc zugewiesene Speicher wird freigegeben, wenn die Transaktion abgeschlossen ist. E / A-Funktionen hinzufügen:

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

Und Registrierungsart:

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

Weil Der neue Typ hat eine Größe von nicht mehr als 8 Bytes. Er kann nicht als Referenz, sondern als Wert übertragen werden. In diesem Fall müssen Sie das Flag PASSEDBYVALUE in CREATE TYPE angeben. Oder verwenden Sie LIKE :

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

Dann werden INTERNALLENGTH , ALIGNMENT und PASSEDBYVALUE von int8 geerbt.

btree index

Die Eindeutigkeit des Feldes wird durch die Erstellung eines eindeutigen B-Baum-Index unterstützt. Dies geschieht durch Klassen von Operatoren und Strategien .

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

Die Operatoren geben bool und phone_equal_internal int zurück:

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

All dies führte zu einem leichten Rückgang der Daten:

Die Anzahl der Konten mit den Nummern 533.289, was 41% entspricht. Zumindest gibt es keinen Zeichenfolgenvergleich, wenn mit einem Index gearbeitet wird.

Bit128

Ich wollte ein Bitfeld mit Operationen der Schnittmenge (&&), des Auftretens (<@) und mit GIN-Unterstützung haben. Es war genug 96 Bit, ging aber auf einen einfachen Weg und nahm 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)) 

Registrierung von Typ und Betrieb:

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

Generalisierter invertierter Index / GIN

Egor Rogov erogov hat im Artikel Indexes in PostgreSQL - 7 gut über GIN in Postgres geschrieben und es auf die Volltextsuche angewendet . Die Dokumentation zur GIN-Erweiterbarkeit legt nahe, dass es ausreicht, 4 Funktionen zu implementieren:

Abrufen eines Schlüsselarrays von einem indizierten Objekt:

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

Ruft die Schlüssel für den angeforderten Wert ab:

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

Zum Beispiel in einer Abfrage:

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

extractQuery wird auf das Array ARRAY[1, 2, 3] angewendet, und die Schlüssel können 1, 2, 3 sein.
Überprüft, ob der Wert mit der Abfrage übereinstimmt:

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

Da die extrahierten Schlüssel im Suchbaum gespeichert sind, benötigen wir eine Vergleichsfunktion:

 int compare(Datum a, Datum b) 

Die API mag redundant erscheinen, bietet aber alles, was nützlich sein kann. Fahren wir mit der Implementierung fort. Schlüsselextraktion:

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

Schreiben Sie in die Ausgabeparametereinträge die Anzahl der Schlüssel und geben Sie ein Array von Schlüsseleinträgen zurück. Schlüsselvergleich:

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

Diese beiden Funktionen reichen aus, um einen Index zu erstellen. Andere Funktionen werden bei der Suche nach Index verwendet. Schlüssel aus einer Anfrage extrahieren:

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

Der erste Parameter übergibt den Wert rechts vom Operator, der dritte Parameter ist für die Strategie (Operator) verantwortlich, mit der die Suche durchgeführt wird. Über die Suchmodi ist in der Dokumentation besser bekannt. Compliance-Funktion:

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

Gibt true wenn das indizierte Objekt den Abfrageoperator mit der Strategienummer erfüllt. Das Prüfarray ist nkeys lang, was der Anzahl der von gin_extract_query_bit128 zurückgegebenen Schlüssel entspricht . Das Überprüfen von check[i] = true bedeutet, dass der i-te Schlüssel von gin_extract_query_bit128 im indizierten Objekt vorhanden ist. Das reicht zum Überqueren, aber weil In GIN arbeiten wir nicht mit den Werten selbst. Für die Eingabestrategie setzen wir die Überprüfung auf true. Dadurch wird der entsprechende Operator aufgerufen, um das Ergebnis zu überprüfen. Bedienerklasse:

 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 wurde hinzugefügt und gibt an, welcher Datentyp für Schlüssel verwendet wird. Was ist das Ergebnis der Festplatte:

Ein interessantes Ergebnis, denn es gibt Nuancen:

• physische Speicherung der Datenbank;
• Datenverteilung.

Alle erstellten Typen haben eine feste Größe, daher wird für sie der PLAIN- Speicher ausgewählt . Komprimierung und separate Speicherung gelten nicht für sie. Arrays und Strings als Typen variabler Länge durchlaufen TOAST. Ja, es gibt Overhead zum Speichern der Größe, aber es gibt auch Komprimierung.

Die Verteilung der Interessen ist wie folgt:

Ehrlich gesagt weiß ich nicht, wie SMALLINT[] veröffentlicht wird, aber nehme an, 4 Bytes pro Größe und 2 Bytes pro Wert. Dann können Sie in 16 Bytes ein Array von 6 Elementen anpassen. Und 98% der Elemente würden in 16 Bytes und Unterschiede von 16 MB passen. Es scheint, dass der Typ bit128 redundant ist, aber der Standardtyp ist für diesen Datensatz redundant.