بوستجر الموسعة

في PGConf.Russia الأخيرة ، كان هناك حديث عن امتداد MobilityDB ، واقترح Andrei Borodin فكرة توسيع أساليب الفهرسة للمهمة.

سأواصل الموضوع مع ملحق Postgres للمهمة التي يتعين حلها باستخدام مثال الامتداد الذي تم إجراؤه كجزء من HighLoad Cup 2018 ، الكود متوفر على GithHub . على هابر بالفعل هناك مقال من 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 ) ); 

الأبعاد:

تمت إضافة نوعين: الهاتف و 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 فئة مساعد التحميل الزائد 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 بايتات ، ويمكن إرساله ليس بالرجوع ، ولكن حسب القيمة. في هذه الحالة ، يجب عليك تحديد علامة PASSEDBYVALUE في CREATE TYPE . أو استخدم LIKE :

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

ثم ALIGNMENT INTERNALLENGTH ، ALIGNMENT و PASSEDBYVALUE من int8.

مؤشر btree

يتم دعم تفرد الحقل من خلال إنشاء فهرس B-tree فريد من نوعه. يتم ذلك من خلال فئات المشغلين والاستراتيجيات .

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

يعرض المشغلون phone_equal_internal ، و phone_equal_internal

 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 ٪. على الأقل لا توجد مقارنة سلسلة عند العمل مع فهرس.

bit128

كنت أرغب في الحصول على حقل بت فيه عمليات التقاطع (&&) ، وحدث (<@) وبدعم 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

كتب إيغور روغوف erogov جيدًا عن GIN في Postgres في مقال فهارس في PostgreSQL - 7 ، وقام بتطبيقه على مهمة البحث عن النص الكامل. تشير وثائق القابلية للتوسعة في 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) 

قد تبدو واجهة برمجة التطبيقات زائدة عن الحاجة ، ولكنها توفر كل شيء مفيد. دعنا ننتقل إلى التنفيذ. استخراج المفتاح:

 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 معلمة الإخراج 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 إذا كان الكائن المفهرسة يرضي عامل الاستعلام برقم الاستراتيجية. صفيف التحقق عبارة عن مفاتيح طويلة ، والتي تتوافق مع عدد المفاتيح التي يتم إرجاعها بواسطة gin_extract_query_bit128 . التحقق من check[i] = true يعني أن مفتاح i-th من gin_extract_query_bit128 موجود في الكائن المفهرس. هذا يكفي لعبور ، ولكن بسبب في GIN ، لا نعمل مع القيم نفسها ، ثم لاستراتيجية الإدخال التي حددناها لإعادة التحقق إلى 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; 

تمت إضافة التخزين ، وهو يشير إلى نوع البيانات المستخدم للمفاتيح. ما هي نتيجة القرص:

نتيجة مثيرة للاهتمام ، لأن هناك فروق دقيقة:

• التخزين الفعلي لقاعدة البيانات ؛
• توزيع البيانات.

جميع الأنواع التي تم إنشاؤها لها حجم ثابت ، لذلك يتم تحديد تخزين PLAIN لهم. لا ينطبق الضغط والتخزين المنفصلين عليها. المصفوفات والسلاسل لأنواع متغيرة الطول تمر عبر TOAST. نعم ، يوجد حمل لتخزين الحجم ، ولكن يوجد أيضًا ضغط.

توزيع المصالح على النحو التالي:

بصراحة ، لا أعرف كيف SMALLINT[] إصدار SMALLINT[] ، لكن لنفترض 4 بايت لكل حجم و 2 بايت لكل قيمة. ثم في 16 بايت يمكنك احتواء مجموعة من 6 عناصر. و 98 ٪ من العناصر تناسب 16 بايت والاختلافات من 16 ميغابايت. يبدو أن نوع bit128 متكرر ، لكن النوع القياسي متكرر في مجموعة البيانات هذه.