पिछले लेखों में, हमने PostgreSQL इंडेक्सिंग इंजन , एक्सेस विधियों के इंटरफ़ेस और दो एक्सेस विधियों: हैश इंडेक्स और बी-ट्री पर चर्चा की। इस लेख में, हम GiST अनुक्रमितों का वर्णन करेंगे।

सार

GiST "सामान्यीकृत खोज ट्री" का एक संक्षिप्त नाम है। यह एक संतुलित खोज पेड़ है, जैसे कि पहले चर्चा की गई "बी-ट्री"।

अंतर क्या है? "बीट्री" सूचकांक सख्ती से तुलनात्मक शब्दार्थ से जुड़ा हुआ है: "अधिक", "कम", और "समान" ऑपरेटरों का समर्थन यह सब सक्षम है (लेकिन बहुत सक्षम है!) हालांकि, आधुनिक डेटाबेस डेटा प्रकारों को संग्रहीत करते हैं जिसके लिए ये ऑपरेटर हैं! बस कोई मतलब नहीं है: जियोडेटा, पाठ दस्तावेज़, चित्र, ...

इन डेटा प्रकारों के लिए हमारी सहायता के लिए GiST इंडेक्स मेथड आता है। यह एक संतुलित पेड़ के पार मनमाने प्रकार के डेटा को वितरित करने के लिए एक नियम को परिभाषित करने और कुछ ऑपरेटर द्वारा इस प्रतिनिधित्व का उपयोग करने के लिए एक विधि का उपयोग करने की अनुमति देता है। उदाहरण के लिए, जीएसटी इंडेक्स सापेक्ष स्थिति ऑपरेटरों (बाईं ओर, दाईं ओर स्थित है, आदि) के समर्थन के साथ स्थानिक डेटा के लिए आर-ट्री को "समायोजित" कर सकते हैं या आरडी-ट्री को चौराहे या समावेशन ऑपरेटरों के समर्थन के साथ सेट कर सकते हैं।

एक्स्टेंसिबिलिटी के लिए धन्यवाद, पोस्टग्रेक्यूएल में स्क्रैच से पूरी तरह से एक नया तरीका बनाया जा सकता है: इस अंत तक, इंडेक्सिंग इंजन के साथ एक इंटरफ़ेस लागू किया जाना चाहिए। लेकिन इसके लिए न केवल अनुक्रमण तर्क की पूर्वता की आवश्यकता होती है, बल्कि पृष्ठों के लिए डेटा संरचनाओं की मैपिंग, तालों के कुशल कार्यान्वयन और राइट-फॉरवर्ड लॉग के समर्थन की भी आवश्यकता होती है। यह सब उच्च डेवलपर कौशल और एक बड़ा मानव प्रयास मानता है। जीईएसटी निम्न-स्तरीय समस्याओं को लेने और अपने स्वयं के इंटरफ़ेस की पेशकश के द्वारा कार्य को सरल बनाता है: कई कार्य तकनीकों से संबंधित नहीं हैं, लेकिन एप्लिकेशन डोमेन के लिए। इस अर्थ में, हम नए एक्सेस तरीकों के निर्माण के लिए एक ढांचे के रूप में जीएसटी को मान सकते हैं।

संरचना

GiST एक ऊंचाई-संतुलित पेड़ है जिसमें नोड पेज होते हैं। नोड्स में सूचकांक पंक्तियाँ होती हैं।

लीफ नोड (पत्ती पंक्ति) की प्रत्येक पंक्ति, सामान्य रूप से, कुछ विधेय (बूलियन अभिव्यक्ति) और एक तालिका पंक्ति (TID) के संदर्भ में होती है। अनुक्रमित डेटा (कुंजी) इस विधेय को पूरा करना चाहिए।

एक आंतरिक नोड (आंतरिक पंक्ति) की प्रत्येक पंक्ति में एक विधेय और एक बच्चे के नोड का एक संदर्भ होता है, और बच्चे के उप-अनुक्रमित सभी डेटा को इस विधेय को पूरा करना होगा। दूसरे शब्दों में, एक आंतरिक पंक्ति की विधेय में सभी बाल पंक्तियों की विधेय शामिल हैं। GiST इंडेक्स का यह महत्वपूर्ण गुण B- ट्री के सरल क्रम को बदल देता है।

GiST ट्री में खोज एक विशेष संगतता फ़ंक्शन ("सुसंगत") का उपयोग करता है - इंटरफ़ेस द्वारा परिभाषित कार्यों में से एक और प्रत्येक समर्थित ऑपरेटर परिवार के लिए अपने तरीके से लागू किया गया।

संगतता फ़ंक्शन को एक इंडेक्स पंक्ति के लिए कहा जाता है और यह निर्धारित करता है कि क्या इस पंक्ति का विधेय खोज विधेय (" अनुक्रमित-फ़ील्ड ऑपरेटर अभिव्यक्ति " के रूप में निर्दिष्ट) के अनुरूप है या नहीं। एक आंतरिक पंक्ति के लिए, यह फ़ंक्शन वास्तव में यह निर्धारित करता है कि क्या इसे संबंधित उपट्री पर उतरने की आवश्यकता है, और एक पत्ता पंक्ति के लिए, फ़ंक्शन यह निर्धारित करता है कि क्या अनुक्रमित डेटा विधेय से मिलता है।

खोज रूट नोड के साथ शुरू होती है, एक सामान्य पेड़ खोज के रूप में। स्थिरता समारोह यह पता लगाने की अनुमति देता है कि कौन सा बच्चा इसे दर्ज करने के लिए समझ में आता है (उनमें से कई हो सकते हैं) और जो यह नहीं करता है। फिर प्रत्येक बच्चे के नोड के लिए एल्गोरिथ्म दोहराया जाता है। और अगर नोड पत्ता है, तो स्थिरता फ़ंक्शन द्वारा चयनित पंक्ति को परिणामों में से एक के रूप में वापस किया जाता है।

खोज गहराई-पहले है: एल्गोरिथ्म पहले एक पत्ती नोड तक पहुंचने की कोशिश करता है। यह जब भी संभव हो, तो पहले परिणामों को जल्द ही वापस करने की अनुमति देता है (यदि उपयोगकर्ता उन सभी के बजाय केवल कई परिणामों में रुचि रखता है तो महत्वपूर्ण हो सकता है)।

आइए एक बार फिर ध्यान दें कि संगतता फ़ंक्शन को "अधिक", "कम", या "बराबर" ऑपरेटरों के साथ कुछ भी करने की आवश्यकता नहीं है। संगति फ़ंक्शन का शब्दार्थ काफी भिन्न हो सकता है और इसलिए, एक निश्चित क्रम में मानों को वापस करने के लिए सूचकांक नहीं माना जाता है।

हम GiST में सम्मिलन और मूल्यों को हटाने के एल्गोरिदम पर चर्चा नहीं करेंगे: कुछ और इंटरफ़ेस फ़ंक्शन इन ऑपरेशनों को करते हैं। हालांकि एक महत्वपूर्ण बिंदु है। जब एक नया मान इंडेक्स में डाला जाता है, तो पेड़ में इस मान के लिए स्थिति का चयन किया जाता है, ताकि इसकी मूल पंक्तियों की विधेयकों को यथासंभव कम बढ़ाया जा सके (आदर्श रूप से, बिल्कुल नहीं बढ़ाया गया)। लेकिन जब कोई मूल्य हटा दिया जाता है, तो मूल पंक्ति की विधेय अब कम नहीं होती है। यह केवल इस तरह के मामलों में होता है: एक पृष्ठ दो लोगों में विभाजित होता है (जब पृष्ठ में नई सूचकांक पंक्ति को सम्मिलित करने के लिए पर्याप्त स्थान नहीं होता है) या सूचकांक को स्क्रैड (REINDEX या VACUUM FULL कमांड के साथ) से फिर से बनाया जाता है। इसलिए, अक्सर बदलते डेटा के लिए GiST सूचकांक की दक्षता समय के साथ कम हो सकती है।

आगे हम विभिन्न डेटा प्रकारों और GiST के उपयोगी गुणों के लिए अनुक्रमित के कुछ उदाहरणों पर विचार करेंगे:

• अंक (और अन्य ज्यामितीय निकाय) और निकटतम पड़ोसियों की खोज।
• अंतराल और बहिष्करण बाधा।
• पूर्ण-पाठ खोज।

अंकों के लिए आर-ट्री

हम एक विमान में बिंदुओं के लिए एक सूचकांक के उदाहरण से ऊपर का वर्णन करेंगे (हम अन्य ज्यामितीय संस्थाओं के लिए भी इसी तरह के सूचकांक का निर्माण कर सकते हैं)। एक नियमित बी-ट्री इस डेटा प्रकार के डेटा के अनुरूप नहीं है क्योंकि कोई तुलना ऑपरेटर बिंदुओं के लिए परिभाषित नहीं है।

आर-ट्री का विचार विमान को आयतों में विभाजित करने के लिए है जो कुल कवर में सभी बिंदुओं को अनुक्रमित करता है। एक अनुक्रमणिका पंक्ति एक आयत को संग्रहीत करती है, और विधेय को इस तरह परिभाषित किया जा सकता है: "दी गई आयत में दी गई बात निहित है"।

आर-ट्री की जड़ में कई सबसे बड़े आयत (संभवतः प्रतिच्छेद) होंगे। बाल नोड्स में छोटे आकार के आयताकार होंगे जो मूल एक में और कुल कवर सभी अंतर्निहित बिंदुओं में अंतर्निहित हैं।

सिद्धांत रूप में, लीफ नोड्स में अनुक्रमित होने वाले बिंदु होने चाहिए, लेकिन डेटा प्रकार सभी सूचकांक पंक्तियों में समान होना चाहिए और इसलिए, फिर से आयताकार संग्रहीत किए जाते हैं, लेकिन अंक में "ढह गए"।

ऐसी संरचना की कल्पना करने के लिए, हम आर-ट्री के तीन स्तरों के लिए चित्र प्रदान करते हैं। पॉइंट्स एयरपोर्ट्स के कॉर्डिनेट होते हैं ( डेमो डेटाबेस के "एयरपोर्ट्स टेबल" से मिलते-जुलते हैं, लेकिन Openflights.org से अधिक डेटा प्रदान किया गया है)।


लेवल एक: दो बड़े इंटरसेक्टिंग आयताकार दिखाई दे रहे हैं।


स्तर दो: बड़े आयत छोटे क्षेत्रों में विभाजित हैं।


लेवल तीन: प्रत्येक आयत में एक इंडेक्स पेज को फिट करने के लिए कई बिंदु होते हैं।

अब आइए एक बहुत ही सरल "एक-स्तरीय" उदाहरण पर विचार करें:

postgres=# create table points(p point); postgres=# insert into points(p) values (point '(1,1)'), (point '(3,2)'), (point '(6,3)'), (point '(5,5)'), (point '(7,8)'), (point '(8,6)'); postgres=# create index on points using gist(p); 

इस विभाजन के साथ, सूचकांक संरचना निम्नानुसार दिखाई देगी:



बनाए गए सूचकांक का उपयोग निम्न क्वेरी को गति देने के लिए किया जा सकता है, उदाहरण के लिए: "दिए गए आयत में निहित सभी बिंदुओं को ढूंढें"। इस स्थिति को इस प्रकार औपचारिक रूप दिया जा सकता है: p <@ box '(2,1),(6,3)' (ऑपरेटर <@ से "points_ops" परिवार का अर्थ है "में निहित"):

 postgres=# set enable_seqscan = off; postgres=# explain(costs off) select * from points where p <@ box '(2,1),(7,4)'; 

  QUERY PLAN ---------------------------------------------- Index Only Scan using points_p_idx on points Index Cond: (p <@ '(7,4),(2,1)'::box) (2 rows) 

ऑपरेटर की निरंतरता फ़ंक्शन (" अनुक्रमित-फ़ील्ड <@ अभिव्यक्ति ", जहां अनुक्रमित-फ़ील्ड एक बिंदु है और अभिव्यक्ति एक आयत है) को निम्नानुसार परिभाषित किया गया है। आंतरिक पंक्ति के लिए, यह "हाँ" देता है यदि इसकी आयत अभिव्यक्ति द्वारा परिभाषित आयत के साथ प्रतिच्छेद करती है । एक पत्ता पंक्ति के लिए, फ़ंक्शन "हाँ" लौटाता है यदि इसका बिंदु ("ढह गया" आयत) अभिव्यक्ति द्वारा परिभाषित आयत में निहित है।



खोज रूट नोड के साथ शुरू होती है। आयत (2,1) - (7,4) (1,1) - (6,3) के साथ प्रतिच्छेदन, लेकिन (5,5) - (8,8) के साथ प्रतिच्छेद नहीं करता है, इसलिए, कोई आवश्यकता नहीं है दूसरे उपशीर्षक में उतरना।



एक पत्ती नोड तक पहुंचने पर, हम वहां मौजूद तीन बिंदुओं से गुजरते हैं और उनमें से दो को परिणाम के रूप में वापस करते हैं: (3.2) और (6.3)।

 postgres=# select * from points where p <@ box '(2,1),(7,4)'; 

  p ------- (3,2) (6,3) (2 rows) 

internals

दुर्भाग्य से, प्रथागत "पेजिंस्पेक्ट" GiST सूचकांक में देखने की अनुमति नहीं देता है। लेकिन एक और तरीका उपलब्ध है: "जवेल" विस्तार। यह मानक वितरण में शामिल नहीं है, इसलिए स्थापना निर्देश देखें ।

यदि सब सही किया जाता है, तो तीन कार्य आपके लिए उपलब्ध होंगे। सबसे पहले, हम कुछ आँकड़े प्राप्त कर सकते हैं:

 postgres=# select * from gist_stat('airports_coordinates_idx'); 

  gist_stat ------------------------------------------ Number of levels: 4 + Number of pages: 690 + Number of leaf pages: 625 + Number of tuples: 7873 + Number of invalid tuples: 0 + Number of leaf tuples: 7184 + Total size of tuples: 354692 bytes + Total size of leaf tuples: 323596 bytes + Total size of index: 5652480 bytes+ (1 row) 

यह स्पष्ट है कि हवाई अड्डे के निर्देशांक पर सूचकांक का आकार 690 पृष्ठों का है और सूचकांक में चार स्तर होते हैं: जड़ और दो आंतरिक स्तर ऊपर दिए गए आंकड़ों में दिखाए गए थे, और चौथा स्तर पत्ती है।

वास्तव में, आठ हजार अंकों के लिए सूचकांक काफी छोटा होगा: यहां इसे स्पष्टता के लिए 10% भराव के साथ बनाया गया था।

दूसरा, हम इंडेक्स ट्री का उत्पादन कर सकते हैं:

 postgres=# select * from gist_tree('airports_coordinates_idx'); 

  gist_tree ----------------------------------------------------------------------------------------- 0(l:0) blk: 0 numTuple: 5 free: 7928b(2.84%) rightlink:4294967295 (InvalidBlockNumber) + 1(l:1) blk: 335 numTuple: 15 free: 7488b(8.24%) rightlink:220 (OK) + 1(l:2) blk: 128 numTuple: 9 free: 7752b(5.00%) rightlink:49 (OK) + 1(l:3) blk: 57 numTuple: 12 free: 7620b(6.62%) rightlink:35 (OK) + 2(l:3) blk: 62 numTuple: 9 free: 7752b(5.00%) rightlink:57 (OK) + 3(l:3) blk: 72 numTuple: 7 free: 7840b(3.92%) rightlink:23 (OK) + 4(l:3) blk: 115 numTuple: 17 free: 7400b(9.31%) rightlink:33 (OK) + ... 

और तीसरा, हम सूचकांक पंक्तियों में संग्रहीत डेटा को आउटपुट कर सकते हैं। निम्नलिखित बारीकियों पर ध्यान दें: फ़ंक्शन के परिणाम को आवश्यक डेटा प्रकार में डालना होगा। हमारी स्थिति में, यह प्रकार "बॉक्स" (एक बाउंडिंग आयत) है। उदाहरण के लिए, शीर्ष स्तर पर पाँच पंक्तियों पर ध्यान दें:

 postgres=# select level, a from gist_print('airports_coordinates_idx') as t(level int, valid bool, a box) where level = 1; 

  level | a -------+----------------------------------------------------------------------- 1 | (47.663586,80.803207),(-39.2938003540039,-90) 1 | (179.951004028,15.6700000762939),(15.2428998947144,-77.9634017944336) 1 | (177.740997314453,73.5178070068359),(15.0664,10.57970047) 1 | (-77.3191986083984,79.9946975708),(-179.876998901,-43.810001373291) 1 | (-39.864200592041,82.5177993774),(-81.254096984863,-64.2382965088) (5 rows) 

दरअसल, ऊपर दिए गए आंकड़े सिर्फ इस डेटा से बनाए गए थे।

खोज और ऑर्डर करने के लिए ऑपरेटर्स

ऑपरेटरों ने अब तक चर्चा की (जैसे कि <@ in the predicate p <@ box '(2,1),(7,4)' ) को खोज ऑपरेटर कहा जा सकता है क्योंकि वे किसी क्वेरी में खोज की स्थिति निर्दिष्ट करते हैं।

एक अन्य ऑपरेटर प्रकार भी है: ऑर्डर करने वाले ऑपरेटर। उनका उपयोग स्तंभ नामों के पारंपरिक विनिर्देशों के बजाय ORDER BY क्लॉज में क्रम क्रम के विनिर्देशों के लिए किया जाता है। निम्नलिखित ऐसी क्वेरी का एक उदाहरण है:

 postgres=# select * from points order by p <-> point '(4,7)' limit 2; 

  p ------- (5,5) (7,8) (2 rows) 

p <-> point '(4,7)' यहां एक अभिव्यक्ति है जो एक ऑर्डरिंग ऑपरेटर का उपयोग करता है <-> , जो एक तर्क से दूसरे तक की दूरी को दर्शाता है। क्वेरी का अर्थ बिंदु (4.7) के करीब दो बिंदुओं को वापस करना है। इस तरह की खोज को k-NN - k-निकटतम पड़ोसी खोज के रूप में जाना जाता है।

इस तरह के प्रश्नों का समर्थन करने के लिए, एक एक्सेस विधि को एक अतिरिक्त दूरी फ़ंक्शन को परिभाषित करना होगा, और ऑर्डर करने वाले ऑपरेटर को उपयुक्त ऑपरेटर क्लास (उदाहरण के लिए, "points_ops" क्लास फॉर पॉइंट्स) में शामिल करना होगा। नीचे दी गई क्वेरी ऑपरेटरों को उनके प्रकार ("s" - खोज और "o" - ऑर्डरिंग) के साथ दिखाती है:

 postgres=# select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop where opc.opcname = 'point_ops' and opf.oid = opc.opcfamily and am.oid = opf.opfmethod and amop.amopfamily = opc.opcfamily and am.amname = 'gist' and amop.amoplefttype = opc.opcintype; 

  amopopr | amoppurpose | amopstrategy -------------------+-------------+-------------- <<(point,point) | s | 1 strictly left >>(point,point) | s | 5 strictly right ~=(point,point) | s | 6 coincides <^(point,point) | s | 10 strictly below >^(point,point) | s | 11 strictly above <->(point,point) | o | 15 distance <@(point,box) | s | 28 contained in rectangle <@(point,polygon) | s | 48 contained in polygon <@(point,circle) | s | 68 contained in circle (9 rows) 

रणनीतियों के नंबर भी दिखाए गए हैं, उनके अर्थ के साथ समझाया गया है। यह स्पष्ट है कि "बीट्री" की तुलना में कहीं अधिक रणनीतियां हैं, उनमें से केवल कुछ बिंदुओं के लिए समर्थित हैं। अन्य डेटा प्रकारों के लिए विभिन्न रणनीतियों को परिभाषित किया जा सकता है।

डिस्टेंस फंक्शन को इंडेक्स एलिमेंट के लिए कहा जाता है, और इसमें दिए गए एलिमेंट को एक्सप्रेशन (" इंडेक्सड-फील्ड ऑर्डरिंग-ऑपरेटर एक्सप्रेशन ") से परिभाषित वैल्यू से डिस्टेंस (खाते में संचालक शब्दार्थ को ध्यान में रखते हुए) की गणना करनी चाहिए। एक पत्ती तत्व के लिए, यह अनुक्रमित मूल्य के लिए सिर्फ दूरी है। एक आंतरिक तत्व के लिए, फ़ंक्शन को चाइल्ड लीफ तत्वों के लिए न्यूनतम दूरी वापस करनी होगी। चूंकि सभी चाइल्ड रो के माध्यम से जाना काफी महंगा होता है, इसलिए फंक्शन को आशावादी रूप से दूरी को कम करने की अनुमति दी जाती है, लेकिन खोज दक्षता को कम करने की कीमत पर। हालाँकि, फ़ंक्शन को कभी भी दूरी से अधिक की अनुमति नहीं दी जाती है क्योंकि यह सूचकांक के काम को बाधित करेगा।

डिस्टेंस फ़ंक्शन किसी भी प्रकार के मानों को वापस कर सकता है (मानों को ऑर्डर करने के लिए, PostgreSQL, "btree" एक्सेस विधि के उपयुक्त ऑपरेटर परिवार से तुलना शब्दार्थ का उपयोग करेगा, जैसा कि पहले वर्णित है )।

एक समतल में बिंदुओं के लिए, दूरी की व्याख्या बहुत सामान्य अर्थ में की जाती है: (x1,y1) <-> (x2,y2) का मान एब्सिस और ऑर्डर्स के अंतर के वर्गों के योग के वर्गमूल के बराबर होता है। यदि बिंदु आयत के भीतर स्थित है तो बिंदु से बाउंडिंग आयत तक की दूरी को इस आयत या शून्य से बिंदु से न्यूनतम दूरी पर लिया जाता है। बच्चे के बिंदुओं के माध्यम से चलने के बिना इस मूल्य की गणना करना आसान है, और मूल्य किसी भी बच्चे के बिंदु से दूरी से अधिक नहीं है।

आइए उपरोक्त क्वेरी के लिए खोज एल्गोरिदम पर विचार करें।



खोज रूट नोड के साथ शुरू होती है। नोड में दो बाउंडिंग आयताकार होते हैं। (1,1) - (6,3) की दूरी 4.0 है और (5,5) - (8,8) 1.0 है।

दूरी बढ़ाने के क्रम में बाल नोड्स के माध्यम से चला जाता है। इस तरह, हम पहले निकटतम बच्चे के नोड पर उतरते हैं और बिंदुओं के लिए दूरी की गणना करते हैं (हम दृश्यता में आंकड़े में संख्या दिखाएंगे:)



यह जानकारी पहले दो अंक, (5,5) और (7,8) वापस करने के लिए पर्याप्त है। चूँकि हम जानते हैं कि आयत (1,1) - (6,3) के भीतर झूठ बोलने वाले बिंदुओं की दूरी 4.0 या अधिक है, इसलिए हमें पहले बच्चे के नोड में उतरने की आवश्यकता नहीं है।

लेकिन क्या होगा अगर हमें पहले तीन बिंदु खोजने की जरूरत है?

 postgres=# select * from points order by p <-> point '(4,7)' limit 3; 

  p ------- (5,5) (7,8) (8,6) (3 rows) 

हालाँकि दूसरे बच्चे के नोड में ये सभी बिंदु हैं, लेकिन हम पहले बच्चे के नोड को देखे बिना (8,6) वापस नहीं कर सकते हैं क्योंकि इस नोड में करीब बिंदु (4.0 <4.1) हो सकते हैं।



आंतरिक पंक्तियों के लिए, यह उदाहरण दूरी फ़ंक्शन के लिए आवश्यकताओं को स्पष्ट करता है। दूसरी पंक्ति के लिए छोटी दूरी (वास्तविक 4.5 के बजाय 4.0) का चयन करके, हमने दक्षता कम कर दी (एल्गोरिथ्म ने अनावश्यक रूप से एक अतिरिक्त नोड की जांच शुरू कर दी), लेकिन एल्गोरिथ्म की शुद्धता को नहीं तोड़ दिया।

हाल तक तक, GiST एकमात्र एक्सेस विधि थी जो ऑर्डर करने वाले ऑपरेटरों के साथ व्यवहार करने में सक्षम थी। लेकिन स्थिति बदल गई है: आरयूएम एक्सेस विधि (आगे चर्चा की जानी है) पहले से ही तरीकों के इस समूह में शामिल हो गई है, और यह संभावना नहीं है कि अच्छे पुराने बी-पेड़ उनके साथ जुड़ेंगे: निकिता ग्लुखोव, हमारे सहयोगी, द्वारा विकसित एक पैच। समुदाय द्वारा चर्चा की गई।

मार्च 2019 तक, आगामी PostgreSQL 12 में SP-GiST के लिए k-NN समर्थन जोड़ा गया है (निकिता द्वारा लिखित भी)। बी-ट्री के लिए पैच अभी भी जारी है।

अंतराल के लिए आर-ट्री

GiST एक्सेस विधि का उपयोग करने का एक और उदाहरण अंतराल का अनुक्रमण है, उदाहरण के लिए, समय अंतराल ("tsrange" प्रकार)। सभी अंतर यह है कि आंतरिक नोड्स में आयतों को बांधने के बजाय बाउंडिंग अंतराल होंगे।

आइए एक सरल उदाहरण पर विचार करें। हम एक झोपड़ी को किराए पर लेंगे और एक टेबल में आरक्षण अंतराल को संग्रहीत करेंगे:

 postgres=# create table reservations(during tsrange); postgres=# insert into reservations(during) values ('[2016-12-30, 2017-01-09)'), ('[2017-02-23, 2017-02-27)'), ('[2017-04-29, 2017-05-02)'); postgres=# create index on reservations using gist(during); 

सूचकांक का उपयोग निम्न क्वेरी को गति देने के लिए किया जा सकता है, उदाहरण के लिए:

 postgres=# select * from reservations where during && '[2017-01-01, 2017-04-01)'; 

  during ----------------------------------------------- ["2016-12-30 00:00:00","2017-01-08 00:00:00") ["2017-02-23 00:00:00","2017-02-26 00:00:00") (2 rows) 

 postgres=# explain (costs off) select * from reservations where during && '[2017-01-01, 2017-04-01)'; 

  QUERY PLAN ------------------------------------------------------------------------------------ Index Only Scan using reservations_during_idx on reservations Index Cond: (during && '["2017-01-01 00:00:00","2017-04-01 00:00:00")'::tsrange) (2 rows) 

अंतराल के लिए && ऑपरेटर प्रतिच्छेदन को दर्शाता है; इसलिए, क्वेरी को दिए गए एक के साथ सभी अंतरालों को वापस करना चाहिए। इस तरह के एक ऑपरेटर के लिए, स्थिरता फ़ंक्शन निर्धारित करता है कि दिए गए अंतराल आंतरिक या पत्ती पंक्ति में एक मूल्य के साथ प्रतिच्छेदन करता है या नहीं।

ध्यान दें कि यह या तो एक निश्चित क्रम में अंतराल प्राप्त करने के बारे में नहीं है, हालांकि तुलना ऑपरेटरों को अंतराल के लिए परिभाषित किया गया है। हम अंतराल के लिए "बीटीआरई" सूचकांक का उपयोग कर सकते हैं, लेकिन इस मामले में, हमें इन जैसे कार्यों के समर्थन के बिना करना होगा:

 postgres=# select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop where opc.opcname = 'range_ops' and opf.oid = opc.opcfamily and am.oid = opf.opfmethod and amop.amopfamily = opc.opcfamily and am.amname = 'gist' and amop.amoplefttype = opc.opcintype; 

  amopopr | amoppurpose | amopstrategy -------------------------+-------------+-------------- @>(anyrange,anyelement) | s | 16 contains element <<(anyrange,anyrange) | s | 1 strictly left &<(anyrange,anyrange) | s | 2 not beyond right boundary &&(anyrange,anyrange) | s | 3 intersects &>(anyrange,anyrange) | s | 4 not beyond left boundary >>(anyrange,anyrange) | s | 5 strictly right -|-(anyrange,anyrange) | s | 6 adjacent @>(anyrange,anyrange) | s | 7 contains interval <@(anyrange,anyrange) | s | 8 contained in interval =(anyrange,anyrange) | s | 18 equals (10 rows) 

(समानता को छोड़कर, जो "btree" एक्सेस विधि के लिए ऑपरेटर वर्ग में निहित है।)

internals

हम उसी "जवेल" एक्सटेंशन का उपयोग करके अंदर देख सकते हैं। हमें केवल कॉल में डेटा प्रकार को gist_print में बदलने के लिए याद रखना चाहिए:

 postgres=# select level, a from gist_print('reservations_during_idx') as t(level int, valid bool, a tsrange); 

  level | a -------+----------------------------------------------- 1 | ["2016-12-30 00:00:00","2017-01-09 00:00:00") 1 | ["2017-02-23 00:00:00","2017-02-27 00:00:00") 1 | ["2017-04-29 00:00:00","2017-05-02 00:00:00") (3 rows) 

बहिष्करण बाधा

GiST सूचकांक का उपयोग बहिष्करण बाधाओं (EXCLUDE) का समर्थन करने के लिए किया जा सकता है।

बहिष्करण बाधा किसी भी दो तालिका पंक्तियों के क्षेत्रों को कुछ ऑपरेटरों के संदर्भ में "पत्राचार" नहीं करने के लिए सुनिश्चित करती है। यदि "बराबर" ऑपरेटर चुना जाता है, तो हम वास्तव में अद्वितीय बाधा प्राप्त करते हैं: किसी भी दो पंक्तियों के दिए गए फ़ील्ड एक दूसरे के बराबर नहीं होते हैं।

बहिष्करण बाधा सूचकांक द्वारा समर्थित है, साथ ही साथ अद्वितीय बाधा भी। हम कोई भी ऑपरेटर चुन सकते हैं ताकि:

1. यह सूचकांक विधि द्वारा समर्थित है - "can_exclude" संपत्ति (उदाहरण के लिए, "btree", GiST, या SP-GiST, लेकिन GIN नहीं)।
2. यह सराहनीय है, अर्थात, शर्त पूरी की जाती है: एक ऑपरेटर b = b ऑपरेटर a।

यह उपयुक्त रणनीतियों और ऑपरेटरों के उदाहरणों की एक सूची है (ऑपरेटरों, जैसा कि हम याद करते हैं, अलग-अलग नाम हो सकते हैं और सभी डेटा प्रकारों के लिए उपलब्ध नहीं हो सकते हैं):

• "बीट्री" के लिए:
  
  • "बराबर" =
• GiST और SP-GiST के लिए:
  
  • "अंतःक्रिया" &&
  • "संयोग" ~=
  • निकटता -|-

ध्यान दें कि हम एक बहिष्करण बाधा में समानता ऑपरेटर का उपयोग कर सकते हैं, लेकिन यह अव्यावहारिक है: एक अद्वितीय बाधा अधिक कुशल होगी। यही कारण है कि जब हमने बी-पेड़ों पर चर्चा की, तो हमने बहिष्कार की बाधाओं को नहीं छुआ।

आइए एक बहिष्करण बाधा का उपयोग करने का एक उदाहरण प्रदान करें। यह उचित है कि अंतराल को पार करने के लिए आरक्षण की अनुमति न दी जाए।

 postgres=# alter table reservations add exclude using gist(during with &&); 

एक बार जब हमने बहिष्करण बाधा बनाई, तो हम पंक्तियाँ जोड़ सकते हैं:

 postgres=# insert into reservations(during) values ('[2017-06-10, 2017-06-13)'); 

लेकिन टेबल में एक इंटरसेक्टिंग अंतराल डालने की कोशिश के परिणामस्वरूप त्रुटि होगी:

 postgres=# insert into reservations(during) values ('[2017-05-15, 2017-06-15)'); 

 ERROR: conflicting key value violates exclusion constraint "reservations_during_excl" DETAIL: Key (during)=(["2017-05-15 00:00:00","2017-06-15 00:00:00")) conflicts with existing key (during)=(["2017-06-10 00:00:00","2017-06-13 00:00:00")). 

"Btree_gist" एक्सटेंशन

आइए समस्या को जटिल करते हैं। हम अपने विनम्र व्यवसाय का विस्तार करते हैं, और हम कई कॉटेज किराए पर लेने जा रहे हैं:

 postgres=# alter table reservations add house_no integer default 1; 

हमें बहिष्करण बाधा को बदलने की आवश्यकता है ताकि घर संख्या को ध्यान में रखा जाए। हालाँकि, GiST पूर्णांक संख्याओं के लिए समानता संचालन का समर्थन नहीं करता है:

 postgres=# alter table reservations drop constraint reservations_during_excl; postgres=# alter table reservations add exclude using gist(during with &&, house_no with =); 

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

इस मामले में, " btree_gist " विस्तार में मदद मिलेगी, जो बी-पेड़ों के लिए निहित संचालन के जीएसटी समर्थन को जोड़ता है। GiST, अंततः, किसी भी ऑपरेटर का समर्थन कर सकता है, इसलिए हमें इसे "अधिक", "कम" और "बराबर" ऑपरेटरों का समर्थन करना क्यों नहीं सिखाना चाहिए?

 postgres=# create extension btree_gist; postgres=# alter table reservations add exclude using gist(during with &&, house_no with =); 

अब हम अभी भी पहली झोपड़ी को उसी तिथियों के लिए आरक्षित नहीं कर सकते हैं:

 postgres=# insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 1); 

 ERROR: conflicting key value violates exclusion constraint "reservations_during_house_no_excl" 

हालाँकि, हम दूसरे को आरक्षित कर सकते हैं:

 postgres=# insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 2); 

लेकिन ध्यान रखें कि हालांकि जीएसटी किसी भी तरह से "अधिक", "कम" और "बराबर" ऑपरेटरों का समर्थन कर सकता है, बी-ट्री अभी भी इसे बेहतर करता है। तो यह इस तकनीक का उपयोग करने के लायक है, जब हमारे उदाहरण में GiST सूचकांक आवश्यक रूप से आवश्यक है।

पूर्ण-पाठ खोज के लिए आरडी-ट्री

पूर्ण-पाठ खोज के बारे में

चलिए PostgreSQL पूर्ण-पाठ खोज के लिए एक न्यूनतम परिचय के साथ शुरू करते हैं (यदि आप जानते हैं, तो आप इस अनुभाग को छोड़ सकते हैं)।

पूर्ण-पाठ खोज का कार्य दस्तावेज़ से उन दस्तावेज़ों का चयन करना है जो खोज क्वेरी से मेल खाते हैं । (यदि कई मिलान दस्तावेज हैं, तो सबसे अच्छा मिलान खोजना महत्वपूर्ण है, लेकिन हम इस बिंदु पर इसके बारे में कुछ नहीं कहेंगे।)

खोज उद्देश्यों के लिए, एक दस्तावेज़ एक विशेष प्रकार के "tsvector" में परिवर्तित हो जाता है, जिसमें दस्तावेज़ में लेक्सेम और उनके पद शामिल हैं। लेक्मेम्स खोज के लिए उपयुक्त रूप में परिवर्तित शब्द हैं। उदाहरण के लिए, शब्दों को आम तौर पर लोअरकेस में बदल दिया जाता है, और चर अंत काट दिया जाता है:

 postgres=# select to_tsvector('There was a crooked man, and he walked a crooked mile'); 

  to_tsvector ----------------------------------------- 'crook':4,10 'man':5 'mile':11 'walk':8 (1 row) 

हम यह भी देख सकते हैं कि कुछ शब्द (जिन्हें स्टॉप शब्द कहा जाता है) पूरी तरह से गिरा दिया गया है ("वहाँ", "था", "ए", "और", "वह") क्योंकि वे संभवतया अक्सर समझदारी के लिए खोज के लिए होते हैं। इन सभी रूपांतरणों को निश्चित रूप से कॉन्फ़िगर किया जा सकता है, लेकिन यह एक और कहानी है।

एक खोज क्वेरी को दूसरे प्रकार से दर्शाया गया है: "tsquery"। मोटे तौर पर, एक क्वेरी में संयोजकों द्वारा संयुक्त एक या कई लेक्समेस होते हैं: "और", "या" | ​​"," नहीं "! .. हम ऑपरेशन पूर्वता को स्पष्ट करने के लिए कोष्ठक का भी उपयोग कर सकते हैं।

 postgres=# select to_tsquery('man & (walking | running)'); 

  to_tsquery ---------------------------- 'man' & ( 'walk' | 'run' ) (1 row) 

पूर्ण-पाठ खोज के लिए केवल एक मैच ऑपरेटर @@ का उपयोग किया जाता है।

 postgres=# select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (walking | running)'); 

  ?column? ---------- t (1 row) 

 postgres=# select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (going | running)'); 

  ?column? ---------- f (1 row) 

यह जानकारी अब के लिए पर्याप्त है। हम GIN इंडेक्स को पेश करने वाले अगले लेख में पूर्ण-पाठ खोज में थोड़ा गहरा डुबकी लगाएंगे।

RD-पेड़

तेजी से पूर्ण-पाठ खोज के लिए, सबसे पहले, तालिका को "tsvector" प्रकार के कॉलम को संग्रहीत करने की आवश्यकता होती है (प्रत्येक बार खोज करते समय महंगा रूपांतरण करने से बचने के लिए) और दूसरी बात, इस स्तंभ पर एक सूचकांक बनाया जाना चाहिए। इसके लिए संभावित पहुंच विधियों में से एक है जीएसटी।

 postgres=# create table ts(doc text, doc_tsv tsvector); postgres=# create index on ts using gist(doc_tsv); postgres=# insert into ts(doc) values ('Can a sheet slitter slit sheets?'), ('How many sheets could a sheet slitter slit?'), ('I slit a sheet, a sheet I slit.'), ('Upon a slitted sheet I sit.'), ('Whoever slit the sheets is a good sheet slitter.'), ('I am a sheet slitter.'), ('I slit sheets.'), ('I am the sleekest sheet slitter that ever slit sheets.'), ('She slits the sheet she sits on.'); postgres=# update ts set doc_tsv = to_tsvector(doc); 

यह निश्चित रूप से, अंतिम चरण के साथ एक ट्रिगर सौंपने के लिए सुविधाजनक है ("tsvector" दस्तावेज़ में रूपांतरण)।

 postgres=# select * from ts; 

 -[ RECORD 1 ]---------------------------------------------------- doc | Can a sheet slitter slit sheets? doc_tsv | 'sheet':3,6 'slit':5 'slitter':4 -[ RECORD 2 ]---------------------------------------------------- doc | How many sheets could a sheet slitter slit? doc_tsv | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7 -[ RECORD 3 ]---------------------------------------------------- doc | I slit a sheet, a sheet I slit. doc_tsv | 'sheet':4,6 'slit':2,8 -[ RECORD 4 ]---------------------------------------------------- doc | Upon a slitted sheet I sit. doc_tsv | 'sheet':4 'sit':6 'slit':3 'upon':1 -[ RECORD 5 ]---------------------------------------------------- doc | Whoever slit the sheets is a good sheet slitter. doc_tsv | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1 -[ RECORD 6 ]---------------------------------------------------- doc | I am a sheet slitter. doc_tsv | 'sheet':4 'slitter':5 -[ RECORD 7 ]---------------------------------------------------- doc | I slit sheets. doc_tsv | 'sheet':3 'slit':2 -[ RECORD 8 ]---------------------------------------------------- doc | I am the sleekest sheet slitter that ever slit sheets. doc_tsv | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6 -[ RECORD 9 ]---------------------------------------------------- doc | She slits the sheet she sits on. doc_tsv | 'sheet':4 'sit':6 'slit':2 

सूचकांक को कैसे संरचित किया जाना चाहिए? आर-ट्री का उपयोग सीधे एक विकल्प नहीं है क्योंकि यह स्पष्ट नहीं है कि दस्तावेजों के लिए "बाउंडिंग आयत" को कैसे परिभाषित किया जाए। लेकिन हम सेट के लिए इस दृष्टिकोण के कुछ संशोधन लागू कर सकते हैं, एक तथाकथित आरडी-ट्री (आरडी का अर्थ "रूसी गुड़िया" है)। एक सेट को इस मामले में लेक्सेस का एक सेट माना जाता है, लेकिन सामान्य तौर पर, एक सेट कोई भी हो सकता है।

आरडी-पेड़ों का एक विचार एक बाउंडिंग सेट के साथ एक बाउंडिंग आयत को बदलना है, अर्थात एक सेट जिसमें बाल सेट के सभी तत्व शामिल हैं।

एक महत्वपूर्ण सवाल यह है कि सूचकांक पंक्तियों में सेट का प्रतिनिधित्व कैसे करें। सबसे सीधा तरीका सिर्फ सेट के सभी तत्वों की गणना करना है। यह इस प्रकार लग सकता है:



उदाहरण के लिए, हालत doc_tsv @@ to_tsquery('sit') तक पहुंच के लिए हम केवल उन नोड्स तक उतर सकते हैं जिनमें "बैठना" है:



इस प्रतिनिधित्व में स्पष्ट मुद्दे हैं। किसी दस्तावेज़ में लेक्समेस की संख्या बहुत बड़ी हो सकती है, इसलिए सूचकांक पंक्तियों का आकार बड़ा होगा और यह टोस्ट में मिल जाएगा, जिससे सूचकांक बहुत कम कुशल हो जाएगा। यहां तक ​​कि अगर प्रत्येक दस्तावेज़ में कुछ अद्वितीय लेक्सेम हैं, तो सेट का संघ अभी भी बहुत बड़ा हो सकता है: जड़ से बड़े सूचकांक पंक्तियों तक।

इस तरह का एक प्रतिनिधित्व कभी-कभी उपयोग किया जाता है, लेकिन अन्य डेटा प्रकारों के लिए। और पूर्ण-पाठ खोज एक और, अधिक कॉम्पैक्ट, समाधान का उपयोग करती है - एक तथाकथित हस्ताक्षर पेड़ । इसका विचार उन सभी से काफी परिचित है जो ब्लूम फ़िल्टर से निपटते हैं।

प्रत्येक लेक्मे को उसके हस्ताक्षर के साथ दर्शाया जा सकता है: एक निश्चित लंबाई का एक सा तार जहां सभी बिट्स लेकिन एक शून्य होता है। इस बिट की स्थिति को lexeme के हैश फ़ंक्शन के मूल्य से निर्धारित किया जाता है (हमने पहले हैश फ़ंक्शन के आंतरिक पर चर्चा की)।

दस्तावेज़ हस्ताक्षर बिटक्वाइन या सभी दस्तावेज़ lexemes के हस्ताक्षर का है।

आइए लेक्मेम्स के निम्नलिखित हस्ताक्षरों को मानते हैं:

 1,000,000 हो सकता है
 कभी 0001000
 अच्छा 0000010
 मणि 0000100
 चादर 0000100
 सबसे चिकना 0100000
 0010000 बैठें
 भट्ठा 0001000
 फिसलन 0000001
 0000010 पर
 जो भी 0010000

फिर दस्तावेजों के हस्ताक्षर इस प्रकार हैं:

 क्या एक शीट स्लिट स्लिट शीट हो सकती है?  0001101
 एक शीट में कितनी शीट फिसल सकती हैं?  1001101
 मैं एक चादर, एक चादर मैं भट्ठा।  0001100
 एक तिरछी चादर के ऊपर मैं बैठता हूँ।  0011110
 जो भी चादरों को खिसकाते हैं वह एक अच्छी चादर होती है।  0011111
 मैं एक चादर का टुकड़ा हूँ।  0000101
 मैं चादर ओढ़ लेता हूं।  0001100
 मैं सबसे चिकना चादर है जो कभी चादरें काटता हूं।  0101101
 वह जिस चादर पर बैठती है, उसे काट देती है।  0011100

इंडेक्स ट्री को निम्नानुसार दर्शाया जा सकता है:



इस दृष्टिकोण के फायदे स्पष्ट हैं: सूचकांक पंक्तियों के छोटे आकार समान हैं, और ऐसा सूचकांक कॉम्पैक्ट है। लेकिन एक खामी यह भी स्पष्ट है: सटीकता को कॉम्पैक्ट करने के लिए बलिदान किया जाता है।

आइए एक ही स्थिति पर विचार करें doc_tsv @@ to_tsquery('sit') । और चलो खोज क्वेरी के हस्ताक्षर की गणना उसी तरह करें जैसे कि दस्तावेज़ के लिए: इस मामले में 0010000। संगतता फ़ंक्शन को उन सभी बाल नोड्स को वापस करना होगा जिनके हस्ताक्षर क्वेरी हस्ताक्षर से कम से कम एक बिट होते हैं:



ऊपर की आकृति के साथ तुलना करें: हम देख सकते हैं कि पेड़ पीला हो गया, जिसका अर्थ है कि झूठी सकारात्मकता होती है और खोज के दौरान अत्यधिक नोड्स होते हैं। यहां हमने "जो कोई" लेक्मे को उठाया, जिसके हस्ताक्षर दुर्भाग्य से "सिट" लेक्सेम के हस्ताक्षर के समान थे। यह महत्वपूर्ण है कि पैटर्न में कोई भी गलत नकारात्मक नहीं हो सकता है, अर्थात, हम निश्चित मानों को याद नहीं करना सुनिश्चित करते हैं।

इसके अलावा, ऐसा हो सकता है कि विभिन्न दस्तावेजों में भी एक ही हस्ताक्षर होंगे: हमारे उदाहरण में, अशुभ दस्तावेज "मैं स्लिट ए शीट, शीट आई स्लिट" और "आई स्लिट शीट" (दोनों में 0001100 के हस्ताक्षर हैं)। और अगर एक लीफ इंडेक्स पंक्ति "tsvector" के मूल्य को संग्रहीत नहीं करती है, तो इंडेक्स स्वयं गलत सकारात्मकता देगा। बेशक, इस मामले में, विधि अनुक्रमणिका इंजन को तालिका के साथ परिणाम का पुन: परीक्षण करने के लिए कहेगी, इसलिए उपयोगकर्ता इन झूठी सकारात्मक को नहीं देखेगा। लेकिन खोज दक्षता से समझौता हो सकता है।

दरअसल, आंकड़ों में 7-बिट के बजाय मौजूदा कार्यान्वयन में एक हस्ताक्षर 124-बाइट बड़ा है, इसलिए उपरोक्त मुद्दों के उदाहरण की तुलना में बहुत कम होने की संभावना है। लेकिन वास्तव में, बहुत अधिक दस्तावेजों को भी अनुक्रमित किया जाता है। किसी तरह से सूचकांक विधि की झूठी सकारात्मकता को कम करने के लिए, कार्यान्वयन थोड़ा मुश्किल हो जाता है: अनुक्रमित "tsvector" को पत्ती सूचकांक पंक्ति में संग्रहीत किया जाता है, लेकिन केवल तभी इसका आकार बड़ा नहीं होता है (1/16 से थोड़ा कम) एक पृष्ठ, जो 8-केबी पृष्ठों के लिए लगभग आधा किलोबाइट है)।

उदाहरण

यह देखने के लिए कि अनुक्रमण वास्तविक डेटा पर कैसे काम करता है, आइए "pgsql-hackers" ईमेल का संग्रह लें। उदाहरण में उपयोग किए गए संस्करण में भेजने की तारीख, विषय, लेखक और पाठ के साथ 356125 संदेश हैं:

 fts=# select * from mail_messages order by sent limit 1; 

 -[ RECORD 1 ]------------------------------------------------------------------------ id | 1572389 parent_id | 1562808 sent | 1997-06-24 11:31:09 subject | Re: [HACKERS] Array bug is still there.... author | "Thomas G. Lockhart" <Thomas.Lockhart@jpl.nasa.gov> body_plain | Andrew Martin wrote: + | > Just run the regression tests on 6.1 and as I suspected the array bug + | > is still there. The regression test passes because the expected output+ | > has been fixed to the *wrong* output. + | + | OK, I think I understand the current array behavior, which is apparently+ | different than the behavior for v1.0x. + ... 

"Tsvector" प्रकार के कॉलम में जोड़ना और भरना और इंडेक्स का निर्माण करना। यहां हम एक वेक्टर (विषय, लेखक और संदेश पाठ) में तीन मानों को जोड़ेंगे, यह दिखाने के लिए कि दस्तावेज़ को एक फ़ील्ड की आवश्यकता नहीं है, लेकिन पूरी तरह से अलग-अलग मनमाने भागों से मिलकर बना सकते हैं।

 fts=# alter table mail_messages add column tsv tsvector; fts=# update mail_messages set tsv = to_tsvector(subject||' '||author||' '||body_plain); 

 NOTICE: word is too long to be indexed DETAIL: Words longer than 2047 characters are ignored. ... UPDATE 356125 

 fts=# create index on mail_messages using gist(tsv); 

जैसा कि हम देख सकते हैं, बहुत बड़े आकार के कारण कुछ निश्चित शब्द हटा दिए गए थे। लेकिन सूचकांक अंततः बनाया गया है और खोज प्रश्नों का समर्थन कर सकता है:

 fts=# explain (analyze, costs off) select * from mail_messages where tsv @@ to_tsquery('magic & value'); 

  QUERY PLAN ---------------------------------------------------------- Index Scan using mail_messages_tsv_idx on mail_messages (actual time=0.998..416.335 rows=898 loops=1) Index Cond: (tsv @@ to_tsquery('magic & value'::text)) Rows Removed by Index Recheck: 7859 Planning time: 0.203 ms Execution time: 416.492 ms (5 rows) 

हम देख सकते हैं कि 898 पंक्तियों के साथ स्थिति का मिलान करते हुए, एक्सेस विधि ने 7859 अधिक पंक्तियाँ लौटा दीं जिन्हें तालिका के साथ पुन: जाँच कर फ़िल्टर किया गया। यह दक्षता पर सटीकता की हानि के नकारात्मक प्रभाव को प्रदर्शित करता है।

internals

सूचकांक की सामग्री का विश्लेषण करने के लिए, हम फिर से "जवेल" एक्सटेंशन का उपयोग करेंगे:

 fts=# select level, a from gist_print('mail_messages_tsv_idx') as t(level int, valid bool, a gtsvector) where a is not null; 

  level | a -------+------------------------------- 1 | 992 true bits, 0 false bits 2 | 988 true bits, 4 false bits 3 | 573 true bits, 419 false bits 4 | 65 unique words 4 | 107 unique words 4 | 64 unique words 4 | 42 unique words ... 

विशेष प्रकार के "gtsvector" के मान जो कि अनुक्रमणिका पंक्तियों में संग्रहीत हैं, वास्तव में हस्ताक्षर प्लस, हो सकता है, स्रोत "tsvector"। यदि वेक्टर उपलब्ध है, तो आउटपुट में लेक्सेम (अद्वितीय शब्द) की संख्या होती है, अन्यथा, हस्ताक्षर में सच्चे और झूठे बिट्स की संख्या।

यह स्पष्ट है कि रूट नोड में, हस्ताक्षर "सभी लोगों" के लिए पतित हो गया, अर्थात, एक सूचकांक स्तर बिल्कुल बेकार हो गया (और एक और लगभग बेकार हो गया, केवल चार झूठे बिट्स के साथ)।

गुण

आइए GiST पहुंच विधि के गुणों को देखें (प्रश्न पहले प्रदान किए गए थे ):

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

मूल्यों की छंटाई और अद्वितीय बाधा का समर्थन नहीं किया जाता है। जैसा कि हमने देखा, सूचकांक को कई स्तंभों पर बनाया जा सकता है और बहिष्करण बाधाओं में इस्तेमाल किया जा सकता है।

निम्नलिखित सूचकांक-परत गुण उपलब्ध हैं:

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

और सबसे दिलचस्प गुण स्तंभ परत के हैं। कुछ गुण ऑपरेटर वर्ग से स्वतंत्र हैं:

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

(सॉर्टिंग समर्थित नहीं है; किसी सरणी को खोजने के लिए इंडेक्स का उपयोग नहीं किया जा सकता; नल समर्थित हैं।)

लेकिन दो शेष गुण, "दूरी_क्रमनीय" और "वापस करने योग्य", उपयोग किए गए ऑपरेटर वर्ग पर निर्भर करेगा। उदाहरण के लिए, अंकों के लिए हमें मिलेगा:

  name | pg_index_column_has_property --------------------+------------------------------ distance_orderable | t returnable | t 

पहली संपत्ति बताती है कि निकटतम पड़ोसी की खोज के लिए दूरी ऑपरेटर उपलब्ध है। और दूसरा बताता है कि सूचकांक का उपयोग केवल सूचकांक स्कैन के लिए किया जा सकता है। हालाँकि लीफ इंडेक्स पंक्तियाँ अंकों के बजाय आयतों को संग्रहित करती हैं, फिर भी एक्सेस विधि वापस आ सकती है।

निम्नलिखित अंतराल के लिए गुण हैं:

  name | pg_index_column_has_property --------------------+------------------------------ distance_orderable | f returnable | t 

अंतराल के लिए, दूरी फ़ंक्शन परिभाषित नहीं है और इसलिए, निकटतम पड़ोसियों की खोज संभव नहीं है।

और पूर्ण-पाठ खोज के लिए, हम प्राप्त करते हैं:

  name | pg_index_column_has_property --------------------+------------------------------ distance_orderable | f returnable | f 

इंडेक्स-ओनली स्कैन का समर्थन खो गया है क्योंकि पत्ता पंक्तियों में केवल डेटा के बिना केवल हस्ताक्षर हो सकते हैं। हालांकि, यह एक मामूली नुकसान है क्योंकि किसी को भी "tsvector" प्रकार के मूल्य में कोई दिलचस्पी नहीं है: यह मान पंक्तियों का चयन करने के लिए उपयोग किया जाता है, जबकि यह स्रोत पाठ है जिसे दिखाने की आवश्यकता है, लेकिन वैसे भी सूचकांक से गायब है।

अन्य डेटा प्रकार

अंत में, हम कुछ और प्रकारों का उल्लेख करेंगे जो वर्तमान में पहले से ही चर्चा किए गए ज्यामितीय प्रकारों (अंकों के उदाहरण से), अंतराल और पूर्ण-पाठ खोज प्रकारों के अलावा GiST पहुंच विधि द्वारा समर्थित हैं।

मानक प्रकारों में, यह IP- पतों के लिए " inet " प्रकार है। बाकी सभी एक्सटेंशन के माध्यम से जोड़ा जाता है:

• क्यूब बहु-आयामी क्यूब्स के लिए "क्यूब" डेटा प्रकार प्रदान करता है। इस प्रकार के लिए, जैसे किसी विमान में ज्यामितीय प्रकारों के लिए, GiST ऑपरेटर वर्ग को परिभाषित किया गया है: आर-ट्री, निकटतम पड़ोसियों की खोज का समर्थन करता है।
  
• seg एक निश्चित सटीकता के लिए निर्दिष्ट सीमाओं के साथ अंतराल के लिए "seg" डेटा प्रकार प्रदान करता है और इस डेटा प्रकार (R- ट्री) के लिए GiST सूचकांक का समर्थन जोड़ता है।
  
• अंतरायन पूर्णांक सरणियों की कार्यक्षमता का विस्तार करता है और उनके लिए GiST समर्थन जोड़ता है। दो ऑपरेटर कक्षाएं कार्यान्वित की जाती हैं: "gist__int_ops" (सूचकांक पंक्तियों में कुंजियों के पूर्ण प्रतिनिधित्व के साथ आरडी-ट्री) और "gist__bigint_ops" (हस्ताक्षर आरडी-ट्री)। पहली कक्षा का उपयोग छोटे सरणियों के लिए किया जा सकता है, और दूसरे में - बड़े आकारों के लिए।
  
• ltree पेड़ की तरह संरचनाओं के लिए "ltree" डेटा प्रकार जोड़ता है और इस डेटा प्रकार (RD- ट्री) के लिए GiST समर्थन करता है।
  
• पूर्ण-पाठ खोज में ट्रिगर्स के उपयोग के लिए pg_trgm एक विशेष ऑपरेटर वर्ग "gist_trgm_ops" जोड़ता है। लेकिन GIN इंडेक्स के साथ इस पर आगे चर्चा की जानी है।
  

पर पढ़ें ।