ناقشنا في المقالات السابقة محرك فهرسة PostgreSQL وواجهة طرق الوصول ، بالإضافة إلى فهارس التجزئة ، و B- tree ، و GiST ، و SP-GiST ، و GIN ، و RUM ، و BRIN . لكننا ما زلنا بحاجة إلى النظر إلى فهارس بلوم.

إزهار

المفهوم العام

عامل تصفية Bloom الكلاسيكي هو بنية بيانات تمكننا من التحقق بسرعة من عضوية عنصر في مجموعة. المرشح مضغوط للغاية ، لكنه يسمح بالإيجابيات الخاطئة: يمكن أن يعتبر عن طريق الخطأ عنصرًا ما كعضو في مجموعة (إيجابية خاطئة) ، لكن لا يجوز اعتبار عنصر مجموعة لا يكون عضوًا (سلبية سلبية) .

المرشح هو مجموعة من $$$م دولا$ البتات (وتسمى أيضًا التوقيع ) المملوءة في البداية بالأصفار. $$$ك$ يتم اختيار وظائف التجزئة المختلفة التي تعين أي عنصر من عناصر المجموعة $$$ك$ بت من التوقيع. لإضافة عنصر إلى المجموعة ، نحتاج إلى تعيين كل من هذه البتات في التوقيع على واحد. وبالتالي ، إذا تم تعيين كل البتات المقابلة لعنصر على واحد ، فيمكن أن يكون العنصر عضوًا في المجموعة ، ولكن إذا كان بت واحد على الأقل يساوي الصفر ، فلن يكون العنصر في المجموعة بالتأكيد.

في حالة DBMS ، لدينا بالفعل $$$N$ مرشحات منفصلة بنيت لكل صف مؤشر. كقاعدة عامة ، يتم تضمين العديد من الحقول في الفهرس ، وقيم هذه الحقول هي التي تشكل مجموعة من العناصر لكل صف.

عن طريق اختيار طول التوقيع $$$م دولا$ ، يمكننا إيجاد مفاضلة بين حجم المؤشر واحتمال الإيجابيات الخاطئة. مساحة التطبيق لمؤشر Bloom كبيرة ، حيث يتم الاستعلام عن الجداول "الواسعة" بشكل كبير باستخدام المرشحات في كل حقل. يمكن اعتبار طريقة الوصول هذه ، مثل BRIN ، مسرعًا للمسح المتسلسل: يجب إعادة فحص جميع المطابقات التي وجدها الفهرس مع الجدول ، ولكن هناك فرصة لتجنب النظر في معظم الصفوف على الإطلاق.

هيكل

لقد ناقشنا بالفعل أشجار التوقيع في سياق طريقة الوصول إلى GiST . على عكس هذه الأشجار ، فإن مؤشر بلوم هو بنية مسطحة. وهو يتألف من ملف تعريف متبوعًا بصفحات عادية بها صفوف فهرس. يحتوي كل صف فهرس على توقيع ومرجع إلى صف جدول (TID) ، كما هو موضح تخطيطيًا في الشكل.

إنشاء واختيار قيم المعلمات

عند إنشاء فهرس Bloom ، يتم تحديد الحجم الكلي للتوقيع ("الطول") ، وكذلك عدد البتات المراد تعيينها لكل حقل فردي مدرج في الفهرس ("col1" - "col32"):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

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

لسوء الحظ ، لا يوجد أي تقدم إضافي في هذا الشأن.

كيف يمكننا اختيار القيم المناسبة؟ النظرية تنص على أنه بالنظر إلى الاحتمال $$$ع$ مرشح لإرجاع إيجابية كاذبة ، ويمكن تقدير العدد الأمثل من بت التوقيع على النحو $$$m = −n \ log_2 p / \ ln 2$ اين $$$ن$ هو عدد الحقول في الفهرس وعدد البتات المراد تعيينها هو $$$k = - \ log_2 p$ .

يتم تخزين التوقيع داخل الفهرس كصفيف من أعداد صحيحة ثنائية البايت ، وبالتالي فإن قيمة $$$م دولا$ يمكن تقريب بأمان تصل إلى $$ .

عند اختيار الاحتمال $$$ع$ ، نحن بحاجة إلى أن نأخذ في الاعتبار حجم الفهرس ، والذي سوف يساوي تقريبًا $$$(م / 8 + 6) N$ اين $$$N$ هو عدد الصفوف في الجدول و $$ هو حجم مؤشر TID بالبايت.

بعض النقاط التي يجب ملاحظتها:

• الاحتمال $$$ع$ من إيجابية كاذبة يرتبط مرشح واحد ، وبالتالي ، فإننا نتوقع الحصول عليها $$$Np دولا$ الإيجابيات الخاطئة أثناء فحص الجدول (بالطبع ، لاستعلام يُرجع بضعة صفوف). على سبيل المثال ، بالنسبة للجدول الذي يحتوي على مليون صف واحتمال 0.01 ، في خطة الاستعلام ، في المتوسط ​​، يمكننا أن نتوقع "إزالة الصفوف بواسطة إعادة فحص الفهرس: 10000".
• مرشح بلوم هو هيكل احتمالي. من المنطقي التحدث عن أرقام محددة فقط عند حساب متوسط ​​كثير من القيم ، بينما في كل حالة معينة ، يمكننا الحصول على ما يمكننا التفكير فيه.
• تستند التقديرات المذكورة أعلاه إلى نموذج رياضي مثالي وبعض الافتراضات. في الممارسة العملية ، من المرجح أن تكون النتيجة أسوأ. لذلك ، لا تبالغ في تقدير الصيغ: فهي مجرد وسيلة لاختيار القيم الأولية للتجارب المستقبلية.
• بالنسبة لكل حقل على حدة ، تتيح لنا طريقة الوصول اختيار عدد البتات المراد تعيينها. يوجد افتراض معقول أن العدد الأمثل يعتمد في الواقع على توزيع القيم في العمود. لعمق الغوص ، يمكنك قراءة هذه المقالة (الإشارات إلى البحوث الأخرى هي موضع ترحيب). ولكن نعيد قراءة العنصر السابق أولاً.

تحديث

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

لا يدعم مرشح Bloom العادي حذف العناصر ، لكن هذا غير مطلوب لفهرس Bloom: عندما يتم حذف صف الجدول ، يتم حذف التوقيع بأكمله ، بالإضافة إلى صف الفهرس.

كالمعتاد ، يتكون التحديث من حذف إصدار الصف القديم وإدراج الإصدار الجديد (يتم حساب التوقيع من البداية).

مسح

نظرًا لأن الشيء الوحيد الذي يمكن لمرشح Bloom القيام به هو التحقق من عضوية عنصر في مجموعة ما ، فإن العملية الوحيدة التي يدعمها فهرس Bloom هي التحقق من المساواة (مثل في فهرس التجزئة).

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

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

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

مثال

طاولة

دعنا ننظر إلى فهرس بلوم على سبيل المثال لجدول كبير "flight_bi" من المقالة السابقة . لتذكيرك ، حجم هذا الجدول هو 4 غيغابايت مع ما يقرب من 30 مليون صف. تعريف الجدول:

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

لنقم أولاً بإنشاء الامتداد: على الرغم من تضمين فهرس Bloom في التسليم القياسي بدءًا من الإصدار 9.6 ، إلا أنه لا يتوفر افتراضيًا.

 demo=# create extension bloom; 

آخر مرة تمكنا من فهرسة ثلاثة حقول باستخدام BRIN ("sched_time" ، و "actual_time" ، و "airport_utc_offset"). نظرًا لأن فهارس Bloom لا تعتمد على الترتيب الفعلي للبيانات ، فلنحاول تضمين جميع حقول الجدول تقريبًا في الفهرس. مع ذلك ، دعنا نستبعد حقول الوقت ("sched_time" و "actual_time"): الطريقة تدعم المقارنة من أجل المساواة فقط ، ولكن من الصعب إثارة أي استفسار في الوقت المحدد لأي شخص (يمكننا بناء الفهرس على تعبير ، مع تقريب الوقت ليوم واحد ، لكننا لن نفعل هذا). سيتعين علينا أيضًا استبعاد الإحداثيات الجغرافية للمطارات ("airport_coord"): بالنظر إلى المستقبل ، لا يتم اعتماد نوع "النقطة".

لاختيار قيم المعلمات ، دعونا نضبط احتمالية الموجبة الخاطئة على 0.01 (مع الأخذ في الاعتبار أننا سنحصل على المزيد). الصيغ أعلاه ل $$$ن = 9 دولارا$ و $$$N = 30 \ ، 000 \ ، 000 دولا$ أعط حجم التوقيع 96 بت واقترح إعداد 7 بت لكل عنصر. الحجم المقدر للمؤشر هو 515 ميجابايت (حوالي الثامن من الجدول).

(مع الحد الأدنى لحجم التوقيع وهو 16 بت ، تعد الصيغ بحجم الفهرس أصغر مرتين ، ولكنها تسمح بالاعتماد فقط على الاحتمال البالغ 0.5 وهو ضعيف للغاية.)

فئات المشغل

لذلك ، دعونا نحاول إنشاء الفهرس.

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

لسوء الحظ ، فإن الملحق يوفر لنا فئتين فقط من المشغلين:

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

لكن لحسن الحظ ، من السهل جدًا إنشاء فئات مماثلة لأنواع البيانات الأخرى أيضًا. يجب أن تحتوي فئة المشغل الخاصة بأسلوب الوصول إلى Bloom على عامل تشغيل واحد - المساواة - ووظيفة المساعدة الإضافية تمامًا - التجزئة. إن أبسط طريقة للعثور على المشغلين والوظائف اللازمة لنوع تعسفي هي البحث في كتالوج النظام لفئات المشغلين الخاصة بأسلوب "التجزئة":

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

سنقوم بإنشاء فئتين مفقودتين باستخدام هذه المعلومات:

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

لا يتم تعريف دالة التجزئة للنقاط (نوع "النقطة") ، ولهذا السبب لا يمكننا بناء فهرس بلوم في مثل هذا الحقل (تمامًا كما لا يمكننا تنفيذ ارتباط التجزئة في الحقول من هذا النوع).

المحاولة مرة أخرى:

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

حجم الفهرس 526 ميغابايت ، وهو أكبر إلى حد ما من المتوقع. وذلك لأن الصيغة لا تأخذ في الحسبان الصفحة.

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

الاستفسارات

يمكننا الآن إجراء البحث باستخدام معايير مختلفة ، وسوف يدعمه الفهرس.

كما ذكرنا بالفعل ، فإن مرشح Bloom هو بنية احتمالية ، وبالتالي ، فإن الكفاءة تعتمد بشكل كبير على كل حالة معينة. على سبيل المثال ، لنلقِ نظرة على الصفوف المتعلقة بالركاب ، ميروسلاف سيدوروف:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

ومرفا سولوفيفا:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

في إحدى الحالات ، سمح المرشح بـ 40 ألفًا فقط من الإيجابيات الخاطئة وما يصل إلى 4 ملايين منهم في الحالة الأخرى ("تمت إزالة الصفوف بواسطة إعادة فحص الفهرس"). تختلف أوقات تنفيذ الاستعلامات تبعًا لذلك.

فيما يلي نتائج البحث في الصفوف نفسها بواسطة معرف المسافر بدلاً من الاسم. ميروسلاف:

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

و المرفأ:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

تختلف الكفاءات مرة أخرى كثيرًا ، وهذه المرة كان حظ مرفأ أكثر.

لاحظ أن البحث عن طريق حقلين في وقت واحد سيتم بشكل أكثر كفاءة نظرًا لاحتمالية إيجابية كاذبة $$$ع$ يتحول إلى $$$p ^ 2$ :

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

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

مقارنة مع BRIN وهاش

تتقاطع مجالات التطبيق الخاصة بفهارس Bloom و BRIN. هذه جداول كبيرة يستحسن فيها ضمان البحث عن طريق الحقول المختلفة ، ويتم التضحية بدقة البحث من أجل الاكتناز.

فهارس BRIN أكثر إحكاما (على سبيل المثال ، بعشرات ميغابايت في مثالنا) ويمكن أن تدعم البحث حسب النطاق ، ولكن لها قيود قوية تتعلق بالترتيب الفعلي للبيانات في ملف. فهارس Bloom أكبر (بمئات الميجابايت) ، ولكن ليس لها قيود باستثناء توفر وظيفة تجزئة مناسبة.

مثل فهارس بلوم ، تدعم فهارس التجزئة العملية الوحيدة للتحقق من المساواة. يضمن مؤشر التجزئة دقة البحث التي يتعذر الوصول إليها لـ Bloom ، ولكن حجم الفهرس أكبر بكثير (في مثالنا ، غيغابايت لحقل واحد فقط ، ولا يمكن إنشاء فهرس التجزئة في عدة حقول).

خصائص

كالعادة ، دعونا نلقي نظرة على خصائص بلوم ( تم تقديم الاستعلامات بالفعل ).

فيما يلي خصائص طريقة الوصول:

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

من الواضح أن طريقة الوصول تمكننا من بناء فهرس على عدة أعمدة. بالكاد يكون من المنطقي إنشاء فهرس بلوم في عمود واحد.

تتوفر خصائص طبقة الفهرس التالية:

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

تقنية المسح المتاحة فقط هي فحص الصورة النقطية. نظرًا لأن الفهرس يتم مسحه ضوئيًا تمامًا تمامًا ، فليس من المنطقي تطبيق وصول فهرس منتظم يُرجع الصفوف TID بواسطة TID.

  name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

شرطات فقط هنا ؛ لا يمكن للطريقة التعامل مع القيم الفارغة.

وأخيرا:

ليس من المستحيل أن تستمر هذه السلسلة من المقالات في المستقبل ، عندما تظهر أنواع جديدة من الاهتمامات ، ولكن حان الوقت للتوقف الآن.

أود أن أعرب عن تقديري لزملائي من Postgres Professional (بعضهم مؤلفون للعديد من طرق الوصول التي تمت مناقشتها) لقراءة المسودات وتقديم تعليقاتهم. وأنا ، بالتأكيد ، ممتن لك على سعة صدرك وتعليقاتك القيمة. شجعني انتباهك للوصول إلى هذه النقطة. شكرا لك