डेटाबेस में तार्किक क्षेत्र, क्या कोई मारक है?

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

SQL में, लॉजिकल फ़ील्ड्स को मुख्य रूप से दो मामलों में उपयोग किया जाता है। सबसे पहले, जब आपको वास्तव में एक बाइनरी विशेषता की आवश्यकता होती है, उदाहरण के लिए, लेन-देन तालिका में 'खरीद / बिक्री' करें। समय के साथ ऐसी विशेषताएँ शायद ही कभी बदलती हैं।

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

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


झंडा लगाने का मतलब है कि न केवल संबंधित प्रकार के क्षेत्र को जोड़ना, बल्कि ऑटोमेटन के संचालन में इसे ध्यान में रखना, यह बताता है कि यह किस स्थिति को प्रभावित करता है, जिसमें यह भाग लेता है। व्यवहार में, यह इस तरह दिखता है:

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

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

सबसे पहले, कई बूलियन फ़ील्ड हो सकते हैं, उन सभी को अनुक्रमण करना बहुत बेकार होगा।

दूसरी बात यह है कि यह बेकार हो सकता है प्रत्येक क्षेत्र के लिए चयनात्मकता कम होगी, और संयुक्त संभावना SQL प्रोसेसर के आंकड़ों द्वारा कवर नहीं की जाती है।

मान लें कि तालिका T1: F1 & F2, और क्वेरी में दो बूलियन फ़ील्ड हैं

select F1, F2, count(1) from T1 group by F1, F2 

बाहर देता है

यानी हालांकि, एफ 1 और एफ 2 के अनुसार, सच्चे और झूठे समान रूप से संभावित हैं, संयोजन (सच्चे, झूठे) एक हजार में से केवल एक बार बाहर निकलता है। परिणामस्वरूप, यदि हम F1 और F2 को अलग-अलग अनुक्रमित करते हैं और उन्हें क्वेरी में उपयोग करने के लिए बाध्य करते हैं , तो SQL प्रोसेसर को दोनों सूचकांकों के आधे हिस्से को पढ़ना होगा और परिणामों को पार करना होगा। संपूर्ण तालिका को पढ़ना और प्रत्येक पंक्ति के लिए अभिव्यक्ति की गणना करना सस्ता हो सकता है।

और यहां तक ​​कि अगर आप पूर्ण अनुरोधों पर आंकड़े एकत्र करते हैं, तो यह बहुत अधिक उपयोग नहीं होगा। विशेष रूप से मशीन की स्थिति के लिए जिम्मेदार क्षेत्रों के लिए आंकड़े बहुत अधिक तैरते हैं। वास्तव में, किसी भी समय "हैंडलर" आ सकता है और राज्य S1 से S2 तक की आधी लाइनों को स्थानांतरित कर सकता है।

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

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

विघटनकारी सामान्य रूप

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

इस तरह के सूचकांक में एक खोज क्वेरी & (संयोजन) की एक श्रृंखला है, उदाहरण के लिए, अभिव्यक्ति: v1 और v2 & 3 (& V4), v1 के बराबर: [1,1], v2: [1,1], v3: 1; 1], v4: [0,0]। और अन्य सभी क्षेत्रों में एक सीमा होती है: [0,1]।

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

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

एक BUT है। कुछ मामलों में इस तरह के परिवर्तन से अभिव्यक्ति के आकार में तेजी से वृद्धि हो सकती है। उदाहरण के लिए, से रूपांतरण



2 ** n शब्दों की अभिव्यक्ति की ओर जाता है। ऐसे मामलों में, एप्लिकेशन डेवलपर को सोचना चाहिए कि वह क्या कर रहा है, और SQL प्रोसेसर की ओर से, आप हमेशा तार्किक सूचकांक का उपयोग करने से इनकार कर सकते हैं यदि कंजंप्शन की संख्या उचित सीमा से अधिक है।

बहुआयामी अनुक्रमण एल्गोरिथ्म

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


चित्र 1 द्वि-आयामी जेड-वक्र, 3 और 6 पुनरावृत्तियों


चित्रा 2 दो आयामी हिल्बर्ट वक्र, 3 और 6 पुनरावृत्तियों

• साइड 2 के साथ एक एन-डायमेंशनल सिम्प्लेक्स में उनके बीच 2 ** n कोने और (2 ** n-1) संक्रमण होते हैं।
• एक सिम्प्लेक्स का एक प्राथमिक पुनरावृत्ति एक सिम्प्लेक्स के प्रत्येक शीर्ष को निचले स्तर के सिम्प्लेक्स में बदल देता है।
• पुनरावृत्तियों की आवश्यक संख्या करने के बाद, हम किसी भी आकार के हाइपर-क्यूबिक जाली का निर्माण कर सकते हैं।
• इसके अलावा, इस जाली के प्रत्येक नोड की अपनी अनूठी संख्या होगी - इसकी शुरुआत से नंबरिंग वक्र के साथ लिया गया पथ। इसके अलावा, इस जाली के प्रत्येक नोड में प्रत्येक निर्देशांक में एक मूल्य है। वास्तव में, नंबरिंग वक्र एक नियमित बी-ट्री के साथ अनुक्रमण के लिए उपयुक्त एक आयामी मूल्य में बहुआयामी बिंदु का अनुवाद करता है ।
• किसी भी स्तर के एक सिम्प्लेक्स के अंदर स्थित सभी नोड्स एक ही अंतराल के भीतर हैं और यह अंतराल समान स्तर के किसी भी सिम्प्लेक्स के साथ प्रतिच्छेद नहीं करता है।
• इसलिए, किसी भी खोज आयत (बॉक्स) को हाइपर-क्यूबिक सबक्वेरी की एक छोटी संख्या में विभाजित किया जा सकता है, जिनमें से प्रत्येक के भीतर सूचकांक को एक खोज / ट्रैवर्स द्वारा पढ़ा जा सकता है।
  
• इसके लिए हम बी-ट्री के साथ निचले स्तर के काम का जादू जोड़ते हैं ताकि बेकार अनुरोध न हो और ... एल्गोरिथ्म तैयार हो।

यहाँ बताया गया है कि यह कैसे काम करता है:


चित्र 3 दो आयामी सूचकांक (जेड-वक्र) में उदाहरण खोज

चित्र 3 मूल खोज की सीमा को उप-प्रश्नों और पाए गए बिंदुओं में दर्शाता है। एक दो-आयामी सूचकांक का उपयोग किया गया था, जो 100,000, 000,000 अंकों के समान रूप से वितरित [यादृच्छिक, समान रूप से वितरित] पर बनाया गया था।

तार्किक बहुआयामी सूचकांक

चूंकि हम बहुआयामी अनुक्रमण के बारे में बात कर रहे हैं, यह सोचने का समय है कि यह कितना बहुआयामी हो सकता है? क्या कोई उद्देश्य सीमाएं हैं?

बेशक, क्योंकि बी-ट्री में एक पेज संगठन है और एक पेड़ होने के लिए, पेज पर फिट होने के लिए कम से कम दो तत्वों की गारंटी होनी चाहिए। यदि आप 8K के लिए पेज लेते हैं, तो एक आइटम को संग्रहीत करना 4K से अधिक नहीं जा सकता है। बिना संपीड़न के 4K में, लगभग 1000 32-बिट मान फिट होते हैं। यह काफी है, किसी भी उचित अनुप्रयोग की सीमा से परे, हम कह सकते हैं कि भौतिक सीमा व्यावहारिक रूप से उपलब्ध नहीं है।

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

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

सच है, वहाँ बारीकियों हैं:

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

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

संख्यात्मक प्रयोग

एक सूचकांक का निर्माण:

• इंडेक्स 128-बिट होगा यानी 128 तार्किक क्षेत्रों पर बनाया गया
• और 2 ** 30 तत्व शामिल होंगे
• सूचकांक तत्व का मान 0 से 2 ** 30 तक की संख्या होगी
• सूचकांक तत्व की कुंजी समान संख्या में बाईं ओर 48 बिट्स स्थानांतरित हो जाएगी, अर्थात। तार्किक क्षेत्र 48 से 78 उसी क्रम में संख्या के अंकों से भरे जाएंगे
• नतीजतन, हमें कुंजी के बीच में 30 महत्वपूर्ण तार्किक फ़ील्ड मिलते हैं, शेष बिट 0 भरे जाएंगे
  
• बूलियन क्षेत्रों में से प्रत्येक में समान आँकड़े सही / गलत हैं
• सभी सांख्यिकीय रूप से स्वतंत्र हैं।

खोज:

• प्रत्येक प्रयोग कई लगातार तार्किक क्षेत्रों के चयन और उनके लिए खोज मूल्यों के असाइनमेंट से मेल खाता है। इसलिए नहीं कि एल्गोरिथम केवल धारियों में खोज कर सकता है, बल्कि इसलिए क्योंकि प्रयोग के परिणामों को अधिक स्पष्ट रूप से देखना संभव है, हमारे पास केवल दो आयाम हैं - पट्टी की चौड़ाई और उसकी स्थिति
• प्रयोगों की कुल 24 श्रृंखला। प्रत्येक श्रृंखला में हम उन मानों की तलाश करेंगे जहाँ संगत चौड़ाई N (1 से 24 बिट्स) के तार्किक क्षेत्रों की पट्टी मान को सही मानती है।
• प्रत्येक श्रृंखला में प्रयोगों की एक उप-प्रजाति होगी जिसमें एक चयनित चौड़ाई के तार्किक क्षेत्रों की एक पट्टी अलग-अलग पारियों के साथ पट्टी की शुरुआत से 30 महत्वपूर्ण तार्किक क्षेत्रों में स्थित होती है। कुल (30-N) प्रयोग उप-प्रजाति में।
• प्रत्येक प्रयोग में, सूचकांक के सभी तत्वों के लिए एक खोज की जाती है जो स्थिति को संतुष्ट करते हैं, अर्थात्। अंतराल में संख्या वाले क्षेत्र [48 + S, 48 + S + N -1] अंतराल में खोजे जाएंगे [1,1], अंतराल में शेष [0,1]
  
• खोज ठंडी शुरुआत से की जाती है
• परिणाम डिस्क पृष्ठों की संख्या है, जिसमें कैशिंग (4096 पेज कैश) शामिल है
• सही संचालन का नियंत्रण दो तरीकों से किया जाता है - पाए जाने वाले तत्वों की संख्या 2 ** (30-N) के बराबर होनी चाहिए और पाए गए मानों में आप संबंधित अंकों की जांच कर सकते हैं
  

इस प्रकार,


चित्र 4 परिणाम, विभिन्न श्रृंखलाओं में पढ़े गए पृष्ठों की संख्या

Y द्वारा - पढ़े गए पृष्ठों की संख्या को स्थगित कर दिया जाता है।
एक्स पर - सबसे कम उम्र (48) श्रेणी से स्ट्रिप्स को वरिष्ठ में स्थानांतरित करना। विभिन्न चौड़ाई के पट्टियों पर हस्ताक्षर किए जाते हैं और विभिन्न रंगों में चिह्नित किए जाते हैं।


चित्रा 5 चित्रा 4 के रूप में एक ही डेटा, एक और दृश्य

एक्स - बैंड शिफ्ट
वाई - बैंडविड्थ

क्या ध्यान दिया जाना चाहिए:

• हालाँकि यह चित्रों में प्रत्यक्ष रूप से दिखाई नहीं देता है, सूचकांक सही ढंग से काम करता है, यह दोनों तत्वों की संख्या और स्वयं तत्वों की सामग्री में दिखाई देता है
• 0 की एक पारी के साथ 10 से अधिक नहीं की चौड़ाई के साथ सभी धारियों को सूचकांक के निरंतर पढ़ने की आवश्यकता होती है
• पारी में वृद्धि के साथ 1 से 18 की चौड़ाई वाली धारियां पूरे सूचकांक के आकार के 2 ~ (- N) तक पहुंच जाती हैं, जो तार्किक है
• विषमता के व्यापक बैंड के लिए - पेड़ की ऊंचाई, कम रीडिंग नहीं हो सकती
• इंडेक्स शीट पेज पर 1000 से अधिक तत्वों को रखा गया है, इसे चौड़ाई 10 की पट्टी में देखा जा सकता है, जब 0 को शिफ्ट करने के लिए पूरे इंडेक्स को पढ़ने की आवश्यकता नहीं होती है, तो कुछ पेजों को छोड़ दिया जा सकता है
• निम्न-स्तरीय फ़िल्टरिंग आश्चर्यजनक रूप से अच्छी तरह से काम करता है। 10. की चौड़ाई के साथ एक पट्टी पर विचार करें। एक आदर्श खोज विकल्प 20 (कुल 30 महत्वपूर्ण क्षेत्रों) की पारी के साथ है, जब उपसर्ग में कोई अपरिभाषित क्षेत्र नहीं होते हैं, तो डेटा को एक एकल बीम के साथ पाया जा सकता है। इस स्थिति में, खोज के दौरान सूचकांक का लगभग 1/1000 भाग - 779 पृष्ठों पर पढ़ा जाता है।
  मध्यवर्ती मामला 10 की पारी है, हमारे पास 10 अज्ञात क्षेत्रों का एक उपसर्ग और एक प्रत्यय है। पृष्ठों की संख्या 2484 है, आदर्श मामले में केवल तीन गुना बदतर है।
  और यहां तक ​​कि सबसे खराब स्थिति में, 0 (20 अज्ञात क्षेत्रों के एक उपसर्ग) के बदलाव के साथ, आप कुछ पृष्ठों को छोड़ सकते हैं।

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

वास्तविक डेटा पर प्रयोग

ट्रेड्स टेबल, कुल 278,479,918 पंक्तियाँ, परीक्षण छोरों में से एक से डेटा।
नीचे दी गई तालिका में कुछ प्रश्नों के परिणाम:


एक पृष्ठ को पढ़ने / संसाधित करने में औसतन processing. processing एमएस लगता है।

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

लेकिन इससे पहले कि इस तकनीक का व्यावहारिक उपयोग हो सके, बहुत कुछ किया जाना बाकी है। तो, जारी रखा जाए।