डेटा पुनर्प्राप्ति के लिए एक क्वेरी का अनुकूलन करने के लिए द्विआधारी खोज का उपयोग करना

परिचय

अब यह विभिन्न DBMS के साथ काम के अनुकूलन के संदर्भ में बहुत लोकप्रिय है। "दुनिया में सबसे अच्छा DBMS" के बारे में कई मंचों पर चर्चा होती है, लेकिन अक्सर यह सब अनुचित रोता है कि "मैंने जीवन का अर्थ समझा और महसूस किया कि सबसे अच्छा डेटा गोदाम एक्स है"।

हां, अब, हम NoSQL समाधानों के सक्रिय विकास का निरीक्षण कर सकते हैं जो आपको बहुत कुछ करने की अनुमति देते हैं। लेकिन यह लेख उनके बारे में नहीं है। यह पता चला कि मैंने अपना काम बदल दिया है और भार में मुझे php + MySQL के एक समूह में एक बहुत ही दिलचस्प परियोजना मिली है। इसके कई अच्छे फैसले हैं, लेकिन इसे बड़े दर्शकों पर ध्यान दिए बिना लिखा गया। अस्तित्व के कई वर्षों में, सक्रिय उपयोगकर्ताओं की संख्या 7 शून्य के साथ संख्याओं को प्राप्त करने के लिए शुरू हो गई है। चूंकि परियोजना खेल तत्वों के साथ एक सामाजिक नेटवर्क का एक हिस्सा है, इसलिए उपयोगकर्ताओं के साथ तालिका सभी का सबसे "मुश्किल" नहीं थी। मुझे लाखों उपयोगकर्ता आइटम, निजी संदेश, बिलिंग रिकॉर्ड आदि के साथ तालिकाएँ विरासत में मिलीं। परियोजना ने रिफलेक्टर, कई सर्वरों में विभाजन और महत्वपूर्ण परिणाम प्राप्त किए। अब सब कुछ स्थिर है।

लेकिन हाल ही में एक नया कार्य मेरे मेल पर भेजा गया था। लब्बोलुआब यह था कि आंकड़े एकत्र किए जाएं। आवश्यकताओं का विश्लेषण करने के बाद, मुझे एहसास हुआ कि निष्पादित करने के लिए यह एक एकल क्वेरी लिखने के लिए पर्याप्त है जो तालिकाओं पर 3 INNER JOIN को निष्पादित करता है जिनके आयाम प्रभावशाली थे। प्रत्येक तालिका ने औसतन 40 मिलियन रिकॉर्ड बनाए। यह पता चला है कि अस्थायी तालिका में 4 * 4 * 4 * 10 ^ 21 = 64 * 10 ^ 21 प्रविष्टियां शामिल होंगी। यह एक विशाल आंकड़ा है। और आँकड़े एकत्र करने के लिए इस तरह की क्वेरी के साथ DBMS को लोड करना एक दुर्गम विलासिता है।

इसके अलावा, वास्तव में, मैं इस अमूर्त समस्या का समाधान प्रस्तुत करना चाहता हूं, जो मुझे तब हुआ जब मैंने विश्वविद्यालय में अपने पहले वर्ष में कंप्यूटर विज्ञान की कक्षाओं को याद किया।



(परियोजना MySQL DBMS का उपयोग करता है, लेकिन एल्गोरिथ्म में कोई विशिष्ट विशेषताएं नहीं हैं)

बाइनरी सर्च क्या है?

मुझे लगता है कि आप में से कई ने एक बाइनरी एल्गोरिथ्म का उपयोग करके सरणी में एक तत्व खोजने के लिए समर्पित प्रयोगशालाओं को लिखा था। मैं इसके सार को संक्षेप में बताने की कोशिश करूंगा।

मान लें कि हमारे पास n तत्वों की एक क्रमबद्ध सरणी है:

सरणी का पहला तत्व = 1
अंतिम सरणी तत्व = एन

हमें मूल्य एफ के साथ तत्व के सूचकांक को खोजने की आवश्यकता है।

प्रत्येक चरण यह है कि हम सरणी के मध्य की गणना करते हैं:

मध्य-ऐरे = गोल (पहला तत्व + अंतिम तत्व) / 2

फिर हम इस तत्व के मूल्य की गणना करते हैं और वांछित एफ की तुलना में अधिक या कम प्राप्त मूल्य की जांच करते हैं। खोज सीमा 2 गुना कम हो गई है:

यदि <midpoint >> f, तब
अंतिम सरणी तत्व = मध्य मान
अन्यथा
सरणी का पहला तत्व = मध्य मान

इन चरणों को तब तक दोहराया जाता है जब तक कि कोई एक स्थिति न हो:

• माध्य और f मानों में अंतर का मापांक कुछ एप्सिलॉन (जहां एप्सिलॉन, कुछ त्रुटि) से कम है
• पुनरावृत्तियों की संख्या log2 के मान को पार कर गई (सरणी में तत्वों की संख्या)

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

अभ्यास के लिए आगे बढ़ते हैं

तो, मान लें कि हमें 3 टेबल में एक INNER JOIN करने की आवश्यकता है, और फिर "कॉलम x को 10 और 20 के बीच की सीमा में" सेट करें। इसके अलावा, कॉलम x का कोई इंडेक्स नहीं है। यह बहुत लंबा होगा। यह वह जगह है जहाँ बचाव का आसान तरीका आता है।

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

यह कहने योग्य है कि द्विआधारी खोज का उपयोग एक तत्व को खोजने के लिए किया जाता है, एक सीमा नहीं, लेकिन कोई भी हमें 10 के मान के साथ पहला तत्व खोजने में परेशान नहीं करता है और 20 के मान के साथ अंतिम तत्व है। उनकी प्राथमिक कुंजियाँ सीमाओं की सीमाएं होंगी।

इस श्रेणी के साथ, हम अपनी क्वेरी पर वापस जाते हैं, लेकिन अब WHERE x> = 10 और x <= 20 स्थिति के बजाय, हम WHERE id_x BETWEEN min_id_x और max_id_x लिखते हैं , जहां min_id_x और max_id_x श्रेणी के निचले और ऊपरी किनारों के मान हैं जो स्थिति को संतुष्ट करते हैं।

हमें क्या मिलता है: अब हम कुछ कॉलम x के अनुसार चयन नहीं करते हैं, लेकिन प्राथमिक कुंजी के अनुसार। एक टेबल पर रेंगने में लगने वाला समय बच जाता है। अनुरोध में अन्य शर्तों के साथ एक समान प्रक्रिया को अंजाम दिया जा सकता है।

मैं यहां कोड लाने की बात नहीं देखता, क्योंकि बाइनरी खोज कोड विकिपीडिया पर पाया जा सकता है, और अनुरोध स्वयं कुछ अलौकिक नहीं है।

निष्कर्ष

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

सबसे पहले , सभी अनुरोधों के लिए एक सार्वभौमिक समाधान तैयार करना मुश्किल है। किसी भी मामले में, किसी विशेष तालिका के कार्यान्वयन के विवरण को ध्यान में रखना आवश्यक होगा और परिणामस्वरूप, हर बार अनुकूलन करने में समय व्यतीत करें।

दूसरे , यह विधि सभी समाधानों के लिए उपयुक्त नहीं है, क्योंकि तालिका में पंक्तियों को किसी क्रम में क्रमबद्ध किया जाना चाहिए।