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

हैश

संरचना

सामान्य सिद्धांत

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

एक नियम के रूप में, डेटा प्रकारों में अनुमेय मूल्यों की बहुत बड़ी श्रृंखला होती है: हम "पाठ" प्रकार के कॉलम में संभावित रूप से कितने अलग-अलग तार जोड़ सकते हैं? उसी समय, किसी तालिका के पाठ स्तंभ में वास्तव में कितने भिन्न मूल्य संग्रहीत हैं? आमतौर पर, उनमें से बहुत सारे नहीं।

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

समान रूप से एक हैश फ़ंक्शन बाल्टी द्वारा स्रोत मान वितरित करता है, उतना ही बेहतर है। लेकिन यहां तक ​​कि एक अच्छा हैश फ़ंक्शन कभी-कभी विभिन्न स्रोत मूल्यों के लिए समान परिणाम देगा - इसे टकराव कहा जाता है । इसलिए, एक बाल्टी TID को अलग-अलग कुंजियों के अनुसार स्टोर कर सकती है, और इसलिए, सूचकांक से प्राप्त TID को फिर से जाँचने की आवश्यकता होती है।

उदाहरण के लिए: स्ट्रिंग्स के लिए क्या हैश फ़ंक्शन हम सोच सकते हैं? बाल्टियों की संख्या 256 होने दें। फिर एक बाल्टी संख्या के उदाहरण के लिए, हम पहले वर्ण का कोड (एकल-बाइट वर्ण एन्कोडिंग मानकर) ले सकते हैं। क्या यह एक अच्छा हैश फ़ंक्शन है? जाहिर है, नहीं: यदि सभी तार एक ही चरित्र से शुरू होते हैं, तो सभी एक बाल्टी में मिल जाएंगे, इसलिए एकरूपता इस सवाल से बाहर है, सभी मूल्यों को फिर से जाँचने की आवश्यकता होगी, और हैशिंग का कोई मतलब नहीं होगा। क्या होगा यदि हम सभी वर्णों के कोड को मापते हैं 256 modulo? यह बहुत बेहतर होगा, लेकिन आदर्श होने से बहुत दूर है। यदि आप PostgreSQL में इस तरह के हैश फ़ंक्शन के आंतरिक में रुचि रखते हैं, तो hashfunc.c में hash_any () की परिभाषा देखें ।

सूचकांक संरचना

हैश इंडेक्स पर लौटते हैं। कुछ डेटा प्रकार (एक इंडेक्स की) के मूल्य के लिए, हमारा काम जल्दी से मिलान TID को ढूंढना है।

इंडेक्स में सम्मिलित करते समय, कुंजी के लिए हैश फ़ंक्शन की गणना करते हैं। PostgreSQL में हैश फ़ंक्शंस हमेशा "पूर्णांक" प्रकार लौटाते हैं, जो 2 ³² billion 4 बिलियन मानों की सीमा में होता है। बाल्टियों की संख्या शुरू में दो के बराबर होती है और डेटा के आकार को समायोजित करने के लिए गतिशील रूप से बढ़ जाती है। बाल्टी संख्या को बिट अंकगणित का उपयोग करते हुए हैश कोड से गणना की जा सकती है। और यह बाल्टी है जहाँ हम अपना TID डालेंगे।

लेकिन यह अपर्याप्त है क्योंकि TID के मिलान के लिए अलग-अलग कुंजियों को एक ही बाल्टी में रखा जा सकता है। हम क्या करेंगे? TID के अलावा, एक बाल्टी में कुंजी के स्रोत मूल्य को संग्रहीत करना संभव है, लेकिन इससे सूचकांक आकार में काफी वृद्धि होगी। एक कुंजी के बजाय अंतरिक्ष को बचाने के लिए, बाल्टी कुंजी के हैश कोड को संग्रहीत करती है।

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

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

डेटा संरचनाओं को पृष्ठों पर मैप करना

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



हैश इंडेक्स, जैसा कि चित्र में दिखाया गया है, चार प्रकार के पृष्ठों (ग्रे आयतों) का उपयोग करता है:

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

इंडेक्स पेज एलिमेंट्स पर शुरू होने वाले डाउन एरो टीआईडी ​​का प्रतिनिधित्व करते हैं, यानी टेबल पंक्तियों के संदर्भ में।

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

ध्यान दें कि हैश इंडेक्स आकार में नहीं घट सकता है। यदि हम कुछ अनुक्रमित पंक्तियों को हटाते हैं, तो एक बार आबंटित पृष्ठ ऑपरेटिंग सिस्टम में वापस नहीं आएंगे, लेकिन केवल VACUUMING के बाद नए डेटा के लिए पुन: उपयोग किए जाएंगे। सूचकांक आकार को कम करने का एकमात्र विकल्प REINDEX या VACUUM FULL कमांड का उपयोग करके इसे फिर से बनाना है।

उदाहरण

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

demo=# create index on flights using hash(flight_no); 

 WARNING: hash indexes are not WAL-logged and their use is discouraged CREATE INDEX 

 demo=# explain (costs off) select * from flights where flight_no = 'PG0001'; 

  QUERY PLAN ---------------------------------------------------- Bitmap Heap Scan on flights Recheck Cond: (flight_no = 'PG0001'::bpchar) -> Bitmap Index Scan on flights_flight_no_idx Index Cond: (flight_no = 'PG0001'::bpchar) (4 rows) 

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

हालाँकि, यह इस शरद ऋतु (2017) के रूप में जल्द ही बदल जाएगा, एक बार PostgreSQL के संस्करण 10 जारी होने के बाद। इस संस्करण में, हैश इंडेक्स को राइट-फॉरवर्ड लॉग के लिए समर्थन मिला; इसके अतिरिक्त स्मृति आवंटन को अनुकूलित किया गया और समवर्ती कार्य को अधिक कुशल बनाया गया।

यह सच है। चूंकि PostgreSQL 10 हैश इंडेक्स को पूर्ण समर्थन मिला है और इसका उपयोग प्रतिबंधों के बिना किया जा सकता है। चेतावनी अब प्रदर्शित नहीं की गई है।

शब्दार्थ को नापसंद करना

लेकिन कभी भी हैश इंडेक्स पोस्टग्रेक्यूएल के बहुत जन्म से लगभग 9.6 तक अनुपयोगी होने से क्यों बच गया? बात यह है कि DBMS हैशिंग एल्गोरिथ्म का व्यापक उपयोग करते हैं (विशेष रूप से, हैश जॉन्स और ग्रुपिंग के लिए), और सिस्टम को यह जानना चाहिए कि कौन से हैश फ़ंक्शन किस डेटा प्रकार पर लागू होते हैं। लेकिन यह पत्राचार स्थिर नहीं है, और यह एक बार और सभी के लिए सेट नहीं किया जा सकता क्योंकि PostgreSQL मक्खी पर नए डेटा प्रकारों को जोड़ने की अनुमति देता है। और यह हैश द्वारा एक एक्सेस विधि है, जहां यह पत्राचार संग्रहीत किया जाता है, ऑपरेटर परिवारों के साथ सहायक कार्यों के एक संघ के रूप में प्रतिनिधित्व किया जाता है।

 demo=# select opf.opfname as opfamily_name, amproc.amproc::regproc AS opfamily_procedure from pg_am am, pg_opfamily opf, pg_amproc amproc where opf.opfmethod = am.oid and amproc.amprocfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_procedure; 

  opfamily_name | opfamily_procedure --------------------+-------------------- abstime_ops | hashint4 aclitem_ops | hash_aclitem array_ops | hash_array bool_ops | hashchar ... 

हालांकि इन कार्यों को प्रलेखित नहीं किया जाता है, लेकिन उनका उपयोग उचित डेटा प्रकार के मूल्य के लिए हैश कोड की गणना करने के लिए किया जा सकता है। उदाहरण के लिए, "हैशटेक्स्ट" फ़ंक्शन यदि "text_ops" ऑपरेटर परिवार के लिए उपयोग किया जाता है:

 demo=# select hashtext('one'); 

  hashtext ----------- 127722028 (1 row) 

 demo=# select hashtext('two'); 

  hashtext ----------- 345620034 (1 row) 

गुण

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

  name | pg_indexam_has_property ---------------+------------------------- can_order | f can_unique | f can_multi_col | f can_exclude | t name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t bitmap_scan | t backward_scan | t 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 

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

 demo=# select opf.opfname AS opfamily_name, amop.amopopr::regoperator AS opfamily_operator from pg_am am, pg_opfamily opf, pg_amop amop where opf.opfmethod = am.oid and amop.amopfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_operator; 

  opfamily_name | opfamily_operator ---------------+---------------------- abstime_ops | =(abstime,abstime) aclitem_ops | =(aclitem,aclitem) array_ops | =(anyarray,anyarray) bool_ops | =(boolean,boolean) ... 

नतीजतन, हैश इंडेक्स डेटा ("कैन_ऑर्डर", "ऑर्डरेबल") वापस नहीं कर सकता है। हैश इंडेक्स एक ही कारण से NULLs में कोई हेरफेर नहीं करता है: NULL ("search_nulls") के लिए "बराबर" ऑपरेशन का कोई मतलब नहीं है।

चूंकि हैश इंडेक्स कीज़ को स्टोर नहीं करता है (लेकिन केवल उनके हैश कोड), इसका उपयोग इंडेक्स-ओनली एक्सेस ("रिटर्नेबल") के लिए नहीं किया जा सकता है।

यह एक्सेस विधि मल्टी-कॉलम इंडेक्स ("can_multi_col") का भी समर्थन नहीं करती है।

internals

संस्करण 10 से शुरू होकर, " पेजइन्स्पेक्ट " एक्सटेंशन के माध्यम से हैश इंडेक्स इंटर्नल में देखना संभव होगा। यह वही है जो ऐसा दिखेगा:

 demo=# create extension pageinspect; 

मेटा पेज (हमें इंडेक्स और मैक्सिमल यूज्ड बकेट नंबर में पंक्तियों की संख्या मिलती है):

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',0)); 

  hash_page_type ---------------- metapage (1 row) 

 demo=# select ntuples, maxbucket from hash_metapage_info(get_raw_page('flights_flight_no_idx',0)); 

  ntuples | maxbucket ---------+----------- 33121 | 127 (1 row) 

एक बकेट पेज (हमें लाइव ट्यूपल्स और डेड ट्यूपल्स की संख्या मिलती है, यानी जिन्हें वैक्यूम किया जा सकता है):

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',1)); 

  hash_page_type ---------------- bucket (1 row) 

 demo=# select live_items, dead_items from hash_page_stats(get_raw_page('flights_flight_no_idx',1)); 

  live_items | dead_items ------------+------------ 407 | 0 (1 row) 

और इसी तरह। लेकिन स्रोत कोड की जांच के बिना सभी उपलब्ध क्षेत्रों के अर्थ का पता लगाना संभव नहीं है। यदि आप ऐसा करना चाहते हैं, तो आपको README से शुरुआत करनी चाहिए।

पर पढ़ें ।