可扩展的Postgres

在上届PGConf.Russia上，有一个关于MobilityDB扩展的讨论，Andrei Borodin提出了扩展该任务的索引方法的想法 。

我将使用Postgres扩展名继续讨论该主题，并使用作为HighLoad Cup 2018一部分的扩展名示例解决要解决的任务，该代码可在GithHub上找到 。 在habr上已经有blackmaster 的文章 。 该扩展添加了两种类型，它们支持btree和GIN索引。

初始方案：

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

记录数为1,300,000 ，并且感兴趣的关系的大小为：

最终电路：

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

尺寸图

添加了两种类型： phone和bit128 。

电话

电话号码是8（929）5481819 ，八个可以丢弃。 操作员代码适合10位，数字为24位，原来您需要5个字节。 由于内存中的数据对齐，这不是一个非常方便的数字。 对于如何最好地将数据装入5、6或8个字节的问题，只有测试才能给出答案。

如果您遵循文档中的示例 ，则只需要一点。 定义类型：

 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 helper类重载new ：

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

事务完成后，将释放通过palloc分配的内存。 添加I / O功能：

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

并注册类型：

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

因为 新类型的大小不超过8个字节，它不能通过引用而是通过值进行传输。 在这种情况下，必须在CREATE TYPE指定PASSEDBYVALUE标志。 或使用LIKE ：

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

然后从int8继承INTERNALLENGTH ， ALIGNMENT和PASSEDBYVALUE 。

btree索引

通过创建唯一的B树索引来支持字段的唯一性。 这是通过类别的运营商和策略来完成的 。

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

运算符返回bool和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); } 

所有这些使数据略有减少：

帐户数量为533,289，占41％。 使用索引时，至少没有字符串比较。

位128

我想对交集（&&），出现（<@）和GIN支持进行操作。 足够使用96位，但是走了一条简单的路，就用了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)) 

注册类型和操作：

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

广义倒排索引/ GIN

Egor Rogov erogov 在PostgreSQL-7中的索引中的文章中在Postgres中很好地描述了GIN，并将其应用于全文搜索任务。 GIN可扩展性文档表明，足以实现4个功能：

从索引对象中检索键的数组：

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

检索要求的值的键：

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

例如，在查询中：

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

extractQuery应用于ARRAY[1, 2, 3]数组，并且键可以是1、2、3。
检查值是否与查询匹配：

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

由于提取的关键字存储在搜索树中，因此我们需要一个比较函数：

 int compare(Datum a, Datum b) 

该API似乎是多余的，但提供了可能派上用场的所有内容。 让我们继续执行。 密钥提取：

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

在输出参数nentries输入键的数量并返回键entries的数组。 关键比较：

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

这两个函数足以创建索引。 按索引搜索时使用其他功能。 从请求中提取密钥：

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

第一个参数将值传递到运算符的右侧，第三个参数负责执行搜索的策略（运算符）。 有关搜索模式的信息，请更好地了解文档 。 合规功能：

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

如果索引对象满足策略运算符的查询运算符，则返回true 。 check数组的长度为nkeys ，与gin_extract_query_bit128返回的键数相对应。 检查check[i] = true表示索引对象中存在来自gin_extract_query_bit128的第i个密钥。 这足以克服，但是因为 在GIN中，我们不使用值本身，因此对于进入策略，我们将recheck设置为true。 这将调用适当的运算符以检查结果。 操作员类别：

 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 ，它指示密钥使用什么数据类型。 磁盘的结果是什么：

一个有趣的结果，因为存在细微差别：

• 数据库的物理存储；
• 数据分发。

所有创建的类型都有固定的大小，因此为它们选择了PLAIN 存储 。 压缩和独立存储不适用于它们。 数组和字符串作为可变长度类型通过TOAST。 是的，存储大小有开销，但也有压缩。

利益分配如下：

老实说，我不知道如何释放SMALLINT[] ，但是假设每个大小4个字节，每个值2个字节。 然后，您可以在16个字节中容纳6个元素的数组。 98％的元素适合16个字节，相差16 MB。 似乎bit128类型bit128冗余的，但标准类型在此数据集上是冗余的。