बिटमैप गो में अनुक्रमणिका: अविश्वसनीय खोज गति

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



अतिरिक्त सामग्री, स्लाइड और सभी स्रोत कोड यहां देखे जा सकते हैं:

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

मूल वीडियो रिकॉर्डिंग:


चलो शुरू करो!

परिचय

आज मैं बात करने जा रहा हूं

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

तो अनुक्रमित क्या हैं?

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

यह एक बहुत बड़ा और जटिल विषय है जिसमें बहुत सारे ट्रेडऑफ़ शामिल हैं, लेकिन डेटाबेस कार्यान्वयन और अनुसंधान के दशकों में वापस देखने पर मैं यह तर्क दूंगा कि कुछ ही दृष्टिकोण हैं जो आमतौर पर उपयोग किए जाते हैं:



सबसे पहले, पूरे क्षेत्र को छोटे भागों में काटकर, खोज क्षेत्र को कम किया जा रहा है।

आमतौर पर, यह पेड़ों का उपयोग करके प्राप्त किया जाता है। यह आपकी अलमारी में बक्से के बक्से के समान है। प्रत्येक बॉक्स में ऐसी सामग्री होती है जिसे आगे छोटे बॉक्स में क्रमबद्ध किया जाता है, प्रत्येक एक विशिष्ट उपयोग के लिए। यदि हमें सामग्री की आवश्यकता है, तो हम "कुकीज़" लेबल वाले बॉक्स के बजाय "सामग्री" लेबल वाले बॉक्स की तलाश करना बेहतर होगा।



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



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



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

जैसा कि मैंने पहले ही कहा था, खोज में एक टन का व्यापार होता है, इसलिए अक्सर हम गति को और अधिक बढ़ाने के लिए या हमारे सभी संभावित खोज प्रकारों को कवर करने के लिए कई दृष्टिकोणों का उपयोग करेंगे।

आज मैं इनमें से एक दृष्टिकोण के बारे में बोलना चाहूंगा जो कम ज्ञात है: बिटमैप इंडेक्स।

लेकिन मैं इस विषय पर बात करने वाला कौन हूं?

मैं एक टीम का नेतृत्व कर रहा हूँ (शायद आप हमारे ब्रांडों में से एक को जानते हैं: भौंरा)। हमारे पास दुनिया भर में 400 मिलियन से अधिक उपयोगकर्ता हैं और बहुत सी विशेषताएं हैं जिनमें हमने आपके लिए सर्वश्रेष्ठ मैच की खोज की है! इन कार्यों के लिए हम कस्टम-मेड सेवाओं का उपयोग करते हैं जो दूसरों के बीच बिटमैप इंडेक्स का उपयोग करते हैं।

अब, बिटमैप इंडेक्स क्या है?

जैसा कि उनके नाम से पता चलता है, बिटमैप इंडेक्स खोज सूचकांक को लागू करने के लिए बिटमैप्स उर्फ ​​बिटसेट का उपयोग करते हैं। एक पक्षी की दृष्टि से इस सूचकांक में एक या कई बिटमैप होते हैं जो संस्थाओं (जैसे लोग) और उनके मापदंडों (जैसे उम्र, या आंख का रंग) का प्रतिनिधित्व करते हैं और बिटवेयर ऑपरेशन जैसे, या, या, नहीं, आदि का उपयोग करके खोज प्रश्नों का उत्तर देने के लिए एक एल्गोरिथ्म है। ।



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

लेकिन बाद में लेख में मैं दिखाऊंगा कि बिटमैप इंडेक्स हाई कार्डिनैलिटी कॉलम के साथ भी काम करते हैं।

आइए एक बिटमैप इंडेक्स के सबसे सरल उदाहरण को देखें ...



कल्पना कीजिए कि हमारे पास बाइनरी विशेषताओं वाले मास्को रेस्तरां की एक सूची है:

• मेट्रो के पास
  
• निजी पार्किंग है
  
• छत है
  
• आरक्षण स्वीकार करता है
  
• शाकाहारी के अनुकूल
  
• महंगा
  

आइए प्रत्येक रेस्तरां को 0 से शुरू होने वाला एक सूचकांक दें और 6 बिटमैप (प्रत्येक विशेषता के लिए एक) आवंटित करें। फिर हम इन बिटमैप्स को भर देंगे कि रेस्तरां में कोई विशिष्ट विशेषता है या नहीं। यदि रेस्तरां नंबर 4 में छत है, तो "छत" बिटमैप में बिट नंबर 4 को 1 (0 नहीं तो) पर सेट किया जाएगा।



अब हमारे पास सबसे सरल बिटमैप इंडेक्स संभव है जिसका उपयोग हम प्रश्नों के उत्तर देने के लिए कर सकते हैं

• मुझे ऐसे रेस्तरां दें जो शाकाहारी हों
  
• मुझे एक छत के साथ रेस्तरां दें जो आरक्षण स्वीकार करते हैं, लेकिन महंगे नहीं हैं
  

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





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





यह थोड़ा सैद्धांतिक लग सकता है, लेकिन चिंता न करें, हम शीघ्र ही कोड पर पहुंच जाएंगे।

जहां बिटमैप इंडेक्स का उपयोग किया जाता है

यदि आप "बिटमैप इंडेक्स" को गूगल करते हैं, तो 90% परिणाम ओरेकल डीबी को इंगित करेंगे, जिसमें बेसिक बिटमैप इंडेक्स हैं। लेकिन, निश्चित रूप से, अन्य DBMS बिटमैप इंडेक्स का भी उपयोग करते हैं, है न? नहीं, वास्तव में, वे नहीं करते हैं। आइए एक के बाद एक सामान्य संदिग्धों के बारे में जानें।

• MySQL में अभी तक बिटमैप इंडेक्स नहीं हैं, लेकिन उन्हें जोड़ने के लिए एक प्रस्ताव है ( https://dev.mysql.com/worklog/task/?id=1524 )
  
• PostgreSQL में बिटमैप इंडेक्स नहीं होते हैं, लेकिन वे कई अलग-अलग इंडेक्स के परिणामों को संयोजित करने के लिए सरल बिटमैप और बिटवाइज़ ऑपरेशन का उपयोग करते हैं।
  
• टारेंटूल में बिटसेट इंडेक्स हैं और उनके साथ बहुत सरल खोज की अनुमति देता है।
  
• Redis में बिट फ़ील्ड हैं https://redis.io/commands/bitfiel d बिना खोज क्षमता के
  
• MongoDB उनके पास अभी तक नहीं है, लेकिन उन्हें जोड़ने के लिए एक प्रस्ताव भी है (https://jira.mongodb.org/browse/SERVER-1723)
  
• इलास्टिक्स खोज में बिटमैप्स का उपयोग करें https://www.elastic.co/blog/frame-of-reference-and-roaring-bitolapally
  

• लेकिन ब्लॉक पर एक नया लड़का है: पिलोसा। पिलोसा गो में लिखा गया एक नया डीबीएमएस है (नोटिस में कोई आर नहीं है, यह संबंधपरक नहीं है) जो कि बिटमैप इंडेक्स पर सब कुछ आधारित है। और हम बाद में पिलोसा के बारे में बात करेंगे।
  

जाने में कार्यान्वयन

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



बिटमैप को स्मृति के एक भाग के रूप में दर्शाया गया है। गो में चलो इसके लिए बाइट्स के स्लाइस का उपयोग करें।

हमारे पास प्रति रेस्तरां विशेषता में एक बिटमैप है। बिटमैप में प्रत्येक बिट यह दर्शाता है कि किसी विशेष रेस्तरां में यह विशेषता है या नहीं।



हमें दो सहायक कार्यों की आवश्यकता होगी। एक का उपयोग बिटमैप को यादृच्छिक रूप से भरने के लिए किया जाता है, लेकिन विशेषता होने की एक निर्दिष्ट संभावना के साथ। उदाहरण के लिए, मुझे लगता है कि बहुत कम रेस्तरां हैं जो आरक्षण को स्वीकार नहीं करते हैं और लगभग 20% शाकाहारी के अनुकूल हैं।

एक अन्य फ़ंक्शन हमें एक बिटमैप से रेस्तरां की सूची देगा।



प्रश्न का उत्तर देने के लिए "मुझे एक छत के साथ रेस्तरां दें जो आरक्षण स्वीकार करते हैं लेकिन महंगे नहीं हैं" हमें दो कार्यों की आवश्यकता होगी: नहीं और।

हम जटिल ऑपरेशन और नहीं शुरू करके कोड को थोड़ा सरल कर सकते हैं।

इनमें से प्रत्येक के लिए हमारे पास कार्य हैं। दोनों कार्य हमारे स्लाइस के माध्यम से प्रत्येक से संबंधित तत्व लेते हैं, ऑपरेशन करते हैं और परिणामी स्लाइस को लिखते हैं।



और अब हम उत्तर पाने के लिए अपने बिटमैप और हमारे कार्यों का उपयोग कर सकते हैं।



यहाँ प्रदर्शन इतना शानदार नहीं है, भले ही हमारे कार्य वास्तव में सरल हैं और हमने प्रत्येक फ़ंक्शन के आह्वान पर नए स्लाइस को वापस नहीं करके आवंटन पर बहुत बचत की।

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



आप देखते हैं, गो कंपाइलर स्लाइस के माध्यम से लूप से डरते हैं और किसी भी फ़ंक्शन को इनलाइन करने से मना करते हैं।



लेकिन मैं उनसे डरता नहीं हूं और अपने लूप के लिए गोटो का इस्तेमाल करके कंपाइलर को बेवकूफ बना सकता हूं।





जैसा कि आप देख सकते हैं, इनलाइनिंग ने हमें 2 माइक्रोसेकंड के बारे में बचाया। बुरा नहीं है!



जब आप असेंबली आउटपुट को करीब से देखते हैं तो एक और अड़चन हाजिर होती है। गो संकलक में हमारे लूप में रेंज चेक शामिल थे। गो एक सुरक्षित भाषा है और संकलक को डर है कि मेरे तीन बिटमैप अलग-अलग लंबाई के हो सकते हैं और एक बफर अतिप्रवाह हो सकता है।

चलो संकलक को शांत करें और यह दिखाएं कि मेरे सभी बिटमैप समान लंबाई हैं। ऐसा करने के लिए, हम फ़ंक्शन की शुरुआत में एक साधारण चेक जोड़ सकते हैं।



इस चेक के साथ, संकलक रेंज चेक को खुशी से छोड़ देगा और हम कुछ नैनोसेकंड बचाएंगे।

विधानसभा में क्रियान्वयन

ठीक है, इसलिए हम अपने सरल कार्यान्वयन द्वारा थोड़ा अधिक प्रदर्शन निचोड़ने में कामयाब रहे, लेकिन यह परिणाम वर्तमान हार्डवेयर की तुलना में कहीं अधिक खराब है।

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

दुर्भाग्य से, हम अपने सीपीयू को बहुत छोटे काम के साथ खिला रहे हैं। हमारा कार्य बाइट द्वारा संचालन करता है। हम आसानी से uint64 के स्लाइस का उपयोग करके 8-बाइट विखंडू के साथ काम करने के लिए हमारे कार्यान्वयन को घुमा सकते हैं।



जैसा कि आप यहां देख सकते हैं, हमने 8x बैच आकार के लिए लगभग 8x प्रदर्शन प्राप्त किया है, इसलिए प्रदर्शन लाभ बहुत अधिक रैखिक हैं।



लेकिन यह सड़क का अंत नहीं है। हमारे सीपीयू में 16-बाइट, 32-बाइट और यहां तक ​​कि 64-बाइट विखंडू के साथ काम करने की क्षमता है। इन ऑपरेशनों को SIMD (सिंगल इंस्ट्रक्शन मल्टीपल डेटा) कहा जाता है और इस तरह के सीपीयू ऑपरेशंस के उपयोग की प्रक्रिया को वैरिफिकेशन कहा जाता है।

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



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

इसके अतिरिक्त, गो एक असामान्य प्लान 9 प्रारूप का उपयोग करता है जो एटी एंड टी और इंटेल दोनों प्रारूपों के विपरीत है।



यह कहना सुरक्षित है कि गो विधानसभा कोड लिखना कोई मज़ा नहीं है।

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



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

हम इस पोस्ट के लिए परहेज का उपयोग करेंगे ताकि हमारे कार्यक्रम लगभग सामान्य गो कोड की तरह दिखें।



यह एवो कार्यक्रम का सबसे सरल उदाहरण है। हमारे पास एक मुख्य () फ़ंक्शन है जो Add () नामक एक फ़ंक्शन को परिभाषित करता है जो दो नंबर जोड़ता है। नाम से पैरामीटर प्राप्त करने और उपलब्ध सामान्य रजिस्टरों में से एक प्राप्त करने के लिए सहायक कार्य हैं। प्रत्येक विधानसभा संचालन के लिए फ़ंक्शन जैसे ADDQ यहां हैं, और परिणाम को एक रजिस्टर से परिणामी मान में सहेजने के लिए सहायक कार्य हैं।



कॉलिंग गो जनरेट इस एवो प्रोग्राम को निष्पादित करेगा और दो फाइलें बनाई जाएंगी

• उत्पन्न विधानसभा कोड के साथ add.s
  
• stub.go फ़ंक्शन हेडर के साथ जो हमारे गो और असेंबली कोड को जोड़ने के लिए आवश्यक हैं
  

अब जब हमने देखा है कि एवो क्या करता है, तो हमारे कार्यों को देखें। मैंने अपने कार्यों के स्केलर और SIMD (वेक्टर) दोनों संस्करणों को लागू किया है।

आइए देखें कि स्केलर संस्करण पहले कैसा दिखता है।



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



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



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



यह एक परिणामी asm कोड है जो हमें मिलता है। हमें ऑफ़सेट्स और आकारों (हरे रंग में) की गणना करने की आवश्यकता नहीं थी, हमें विशिष्ट रजिस्टरों (लाल रंग में) से निपटना नहीं था।



यदि हम विधानसभा में इस कार्यान्वयन की तुलना पिछले सर्वश्रेष्ठ में से करते हैं, तो हम देखते हैं कि प्रदर्शन उम्मीद के मुताबिक ही है। हमने कुछ अलग नहीं किया।

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

आइए अब हमारे कार्यों का वेक्टर संस्करण लिखें।



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



परिवर्तनों में से एक को इस तथ्य के साथ करना है कि वेक्टर ऑपरेशन विशिष्ट विस्तृत रजिस्टरों का उपयोग करते हैं। 32 बाइट्स के लिए उनके पास वाई उपसर्ग है, यही कारण है कि आप वहां वाईएमएम () देखते हैं। 64-बाइट के लिए उनके पास Z उपसर्ग होगा।

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



प्रदर्शन के लिए ... यह आश्चर्यजनक है। हमें पिछले सर्वश्रेष्ठ की तुलना में लगभग 7x सुधार मिला। बहुत प्रभावशाली, सही?



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

बिटमैप इंडेक्स समस्याएं

अब जब हमने मूल कार्यान्वयन और asm कार्यान्वयन की प्रभावशाली गति देखी है, तो इस तथ्य के बारे में बात करते हैं कि बिटमैप इंडेक्स बहुत व्यापक रूप से उपयोग नहीं किए जाते हैं। वह क्यों है?



पुराने प्रकाशन हमें ये तीन कारण देते हैं। लेकिन हाल के लोगों और मेरा तर्क है कि ये "निश्चित" हो चुके हैं या अब तक निपटा दिए गए हैं। मैं इस पर बहुत सारे विवरणों में नहीं जाऊँगा क्योंकि हमारे पास बहुत समय नहीं है, लेकिन यह निश्चित रूप से एक त्वरित नज़र के लायक है।

उच्च-हृदयता की समस्या

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




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



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

कुछ बड़े पैमाने पर उपयोग किए जाने वाले अनुप्रयोगों में रोमिंग बिटमैप पाए जा सकते हैं और कई भाषाओं के लिए कार्यान्वयन हैं, जिनमें गो के लिए कई कार्यान्वयन शामिल हैं।



एक और दृष्टिकोण जो उच्च कार्डिनलिटी फ़ील्ड के साथ मदद कर सकता है, उसे बिनिंग कहा जाता है। कल्पना कीजिए कि हमारे पास एक व्यक्ति की ऊंचाई का प्रतिनिधित्व करने वाला क्षेत्र है। ऊंचाई एक फ्लोट है, लेकिन हम इसे इस तरह से नहीं सोचते हैं। किसी को परवाह नहीं है अगर आपकी ऊंचाई 185.2 या 185.3 सेमी है। तो हम "आभासी डिब्बे" का उपयोग एक ही बिन में समान ऊंचाई को निचोड़ने के लिए कर सकते हैं: 1 सेमी बिन, इस मामले में। और यदि आप मानते हैं कि 50 सेमी से कम या 250 सेमी से अधिक की ऊंचाई वाले बहुत कम लोग हैं, तो हम लगभग असीम कार्डिनलिटी के बजाय, अपनी ऊंचाई को लगभग 200 तत्व कार्डिनैलिटी के साथ क्षेत्र में परिवर्तित कर सकते हैं। यदि आवश्यक हो, तो हम बाद में परिणामों पर अतिरिक्त फ़िल्टरिंग कर सकते हैं।

उच्च-थ्रूपुट समस्या

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



यह समस्या, यदि आपके पास है, तो अपने अनुक्रमणिका को शार्प करके या उपयुक्त होने पर, अनुक्रमणिका संस्करण होने से ठीक किया जा सकता है।

साझा करना सीधा है। जैसे ही आप एक डेटाबेस में उपयोगकर्ताओं को शार्क करेंगे और अब एक लॉक के बजाय, आपके पास कई ताले हैं, जो आपके लॉक नोटेशन को बहुत कम कर देता है।

एक और दृष्टिकोण जो कभी-कभी संभव होता है, संस्करणित अनुक्रमित होता है। आपके पास वह अनुक्रमणिका है जिसका उपयोग आप खोज के लिए करते हैं और आपके पास एक अनुक्रमणिका है जिसे आप अपडेट के लिए, अपडेट के लिए उपयोग करते हैं। और आप उन्हें कम आवृत्ति पर कॉपी और स्विच करते हैं, जैसे 100 या 500 एमएस।

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

गैर-तुच्छ प्रश्न

एक और बिटमैप इंडेक्स समस्या को श्रेणी क्वेरी के साथ बिटमैप सूचकांकों का उपयोग करना है। और पहली नजर में बिट एंड ऑपर जैसे बिट एंड ऑपरेशंस रेंज क्वैश्चंस के लिए बहुत उपयोगी प्रतीत होते हैं, जैसे "मुझे होटल के कमरे दें जिनकी कीमत 200 से 300 डॉलर प्रति रात है"।



एक भोले और बहुत ही अकुशल समाधान के लिए प्रत्येक मूल्य बिंदु के लिए 200 से 300 तक परिणाम प्राप्त करना होगा और परिणाम प्राप्त करना होगा।



थोड़ा बेहतर तरीका होगा कि आप बिंजिंग का उपयोग करें और हमारे होटलों को रेंज की चौड़ाई के साथ मूल्य सीमा में रखें, मान लें कि 50 डॉलर। यह दृष्टिकोण हमारे खोज खर्च को लगभग 50 गुना कम कर देगा।

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



सीमा-एन्कोडेड बिटमैप्स में, हम केवल 200 के लिए विशिष्ट बिट सेट नहीं करते हैं, मान लें कि 200 है, लेकिन सभी बिट्स को 200 और उच्चतर पर सेट करें। 300 के लिए समान।

तो, इस रेंज-एन्कोडेड बिटमैप प्रतिनिधित्व रेंज क्वेरी का उपयोग करके बिटमैप के माध्यम से केवल दो पास के साथ उत्तर दिया जा सकता है। हमें सभी होटल मिलते हैं, जिनकी लागत 300 डॉलर से कम या बराबर है, और परिणाम उन सभी होटलों से है जिनकी लागत 199 डॉलर से कम या बराबर है। हो गया।



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

तैयार समाधान

खैर, मुझे उम्मीद है कि मैंने आपकी रुचि को थोड़ा बढ़ा दिया है। अब आपके पास बेल्ट के नीचे एक और उपकरण है और अगर आपको कभी भी अपनी सेवा में ऐसा कुछ लागू करने की आवश्यकता है, तो आपको पता होगा कि कहाँ देखना है।

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

डर नहीं, दो खुले स्रोत उत्पाद हैं जो आपके प्रयास में आपकी सहायता कर सकते हैं।

गर्जन

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



दुर्भाग्य से, गो कार्यान्वयन SIMD का उपयोग नहीं करते हैं, इसलिए वे C कार्यान्वयन की तुलना में कुछ हद तक कम प्रदर्शन देते हैं।

Pilosa

एक अन्य उत्पाद पिलोसा नामक एक डीबीएमएस है जिसमें केवल बिटमैप इंडेक्स होते हैं। यह एक हालिया परियोजना है, लेकिन हाल ही में इसने बहुत अधिक कर्षण प्राप्त किया है।

E-d3BCvTn1CSSDr5Vj6W_9e5_GC1syQ9qSrwdS0 ">

पिलोसा नीचे की ओर गर्जन वाले बिटमैप्स का उपयोग करता है और लगभग सभी चीजें जो मैं आज आपको बता रहा हूं, को सरल करता है या समझाता है: बिनिंग, रेंज-एन्कोडेड बिटमैप्स, खेतों की धारणा आदि।

आइए संक्षेप में उपयोग में पिलोसा का एक उदाहरण देखें ...



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

परिणाम अपेक्षित है।



और अंत में, मैं उम्मीद कर रहा हूं कि भविष्य में कभी-कभी, mysql और postgresql जैसे डेटाबेस को एक नया सूचकांक प्रकार मिलेगा: बिटमैप इंडेक्स।

समापन शब्द

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

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

अपनी बातचीत के दौरान, हमने विभिन्न प्रदर्शन ट्रिक्स देखी हैं जिनका हम उपयोग कर सकते हैं और इस समय जो चीजें संघर्ष कर रही हैं। ये निश्चित रूप से ऐसी चीजें हैं जो हर गो प्रोग्रामर को जानने की जरूरत है।

और यह सब मैं तुम्हारे लिए अभी के लिए है। बहुत बहुत धन्यवाद!