SQL सर्वर हिस्टोग्राम मोटे संरेखण का उपयोग करके अनुमान में शामिल हों

SQL सर्वर 2014 रिलीज़ के साथ शुरू होने वाले कार्डिनैलिटी अनुमान में किए गए प्राथमिक परिवर्तनों का वर्णन Microsoft श्वेत पत्र में SQL सर्वर 2014 कार्डिनैलिटी एस्टिमेटर के साथ आपकी क्वेरी योजनाओं को अनुकूलित करने में किया गया है जो जो सैक, यी फेंग और वासिलिस पापडिमोस द्वारा किया गया है।

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

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

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

मोटे हिस्टोग्राम संरेखण उदाहरण

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

जिस क्वेरी में हम रुचि रखते हैं वह FactResellerSales . से जुड़ती है और FactCurrencyRate टेबल.

FRS.ProductKey, FRS.OrderDateKey, FRS.DueDateKey, FRS.ShipDateKey, FCR.DateKey, FCR.AverageRate, FCR.EndOfDayRate, FCR चुनें। .CurrencyKey =FRS.CurrencyKey;

यह एक एकल कॉलम पर साधारण इक्विजॉइन . है इसलिए यह हिस्टोग्राम मोटे संरेखण का उपयोग करके कार्डिनैलिटी और चयनात्मकता अनुमान में शामिल होने के योग्य है।

हिस्टोग्राम

हमें जिन हिस्टोग्रामों की आवश्यकता है, वे CurrencyKey . से संबद्ध हैं प्रत्येक सम्मिलित तालिका पर स्तंभ। AdventureWorksDW डेटाबेस की एक नई कॉपी पर, बड़े FactResellerSales के लिए पहले से मौजूद आंकड़े तालिका एक नमूने पर आधारित है। प्रतिलिपि प्रस्तुत करने योग्यता को अधिकतम करने के लिए और विस्तृत गणनाओं को पालन करने के लिए जितना संभव हो सके (स्केलिंग से परहेज) करने के लिए, सबसे पहले हम एक पूर्ण स्कैन का उपयोग करके आँकड़ों को ताज़ा करने के लिए करेंगे:

अद्यतन सांख्यिकी dbo.FULLSCAN के साथFactCurrencyRate;अद्यतन सांख्यिकी dbo.FactResellerFulscan के साथ बिक्री;

इन तालिकाओं में छोटे और सरल maxdiff . बनाने का प्रदर्शन-अनुकूल लाभ है हिस्टोग्राम:

DBCC SHOW_STATISTICS (FactResellerSales, CurrencyKey)HISTOGRAM के साथ; डीबीसीसी SHOW_STATISTICS (FactCurrencyRate, [PK_FactCurrencyRate_CurrencyKey_DateKey]) हिस्टोग्राम के साथ;

न्यूनतम मिलान हिस्टोग्राम चरणों का संयोजन

मोटे संरेखण . में पहला चरण गणना सबसे कम मिलान वाले हिस्टोग्राम चरण द्वारा प्रदान की गई कार्डिनैलिटी में शामिल होने में योगदान को खोजने के लिए है। हमारे उदाहरण हिस्टोग्राम के लिए, न्यूनतम मिलान चरण मान RANGE_HI_KEY = 6 पर है :

इस हाइलाइट किए गए चरण के लिए अनुमानित इक्विजॉइन कार्डिनैलिटी 1,713 * 1,158 =1,983,654 पंक्तियां है ।

शेष मिलान चरण

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

ये दो श्रेणियां शेष पंक्तियों का प्रतिनिधित्व करती हैं जिनसे कार्डिनैलिटी को समान करने में योगदान करने की उम्मीद की जा सकती है।

मोटे आवृत्ति-आधारित अनुमान

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

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

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

• C - कार्डिनैलिटी (पंक्तियों की संख्या)
• D - विशिष्ट मानों की संख्या
• F - प्रत्येक विशिष्ट मान के लिए आवृत्ति (पंक्तियों की संख्या)
• नोट सी =डी * एफ परिभाषा के अनुसार

इनमें से प्रत्येक गुण पर संबंध R1 और R2 के एक समयुग्मन का प्रभाव नीचे दिखाया गया है:

• F' =F1 * F2
• D' =MIN(D1; D2) - कंटेनमेंट मानकर
• C' =D' * F' (फिर से, परिभाषा के अनुसार)

हम सी के बाद हैं, इक्विजॉइन की कार्डिनैलिटी। सूत्र में D' और F' को प्रतिस्थापित करना और विस्तार करना:

• सी' =डी' * एफ'
• C' =मिन (D1; D2) * F1 * F2
• C' =मिन (D1 * F1 * F2; D2 * F1 * F2)
• अब, चूंकि C1 =D1 * F1, और C2 =D2 * F2:
• C' =मिन (C1 * F2, C2 * F1)
• आखिरकार, चूंकि F =C/D (परिभाषा के अनुसार भी):
• C' =MIN(C1 * C2 / D2; C2 * C1 / D1)

यह देखते हुए कि C1 * C2 दो इनपुट कार्डिनैलिटी (कार्टेशियन जॉइन) का उत्पाद है, यह स्पष्ट है कि उन अभिव्यक्तियों में से न्यूनतम अलग-अलग मानों की उच्च संख्या वाला होगा:

• C' =(C1 * C2) / MAX(D1; D2)

यदि यह सब थोड़ा सारगर्भित लगता है, तो आवृत्ति-आधारित इक्विजॉइन अनुमान के बारे में सोचने का एक सहज तरीका यह विचार करना है कि एक संबंध से प्रत्येक विशिष्ट मूल्य दूसरे संबंध में कई पंक्तियों (औसत आवृत्ति) के साथ जुड़ जाएगा। यदि हमारे पास एक तरफ 5 अलग-अलग मान हैं, और दूसरी तरफ प्रत्येक विशिष्ट मान औसतन 3 बार दिखाई देता है, तो एक समझदार (लेकिन मोटे) समयुग्मन अनुमान 5 * 3 =15 है।

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

आवृत्ति गणना

हम इनमें से प्रत्येक पैरामीटर को हाइलाइट किए गए हिस्टोग्राम चरणों से प्राप्त कर सकते हैं।

• कार्डिनैलिटी सी EQ_ROWS . का योग है और RANGE_ROWS .
• विभिन्न मानों की संख्या D DISTINCT_RANGE_ROWS . का योग है प्रत्येक चरण के लिए प्लस वन।

FactResellerSales . से मेल खाने की कार्डिनैलिटी C1 चरण हाइलाइट किए गए कक्षों का योग है:

यह देता है C1 =59,142 पंक्तियाँ।

कोई विशिष्ट श्रेणी पंक्तियाँ नहीं हैं, इसलिए केवल विशिष्ट मान चार चरण की सीमाओं से ही आते हैं, जो D1 =4 देते हैं। ।

दूसरी तालिका के लिए:

यह देता है C2 =9,632 . फिर से कोई विशिष्ट श्रेणी पंक्तियाँ नहीं हैं, इसलिए विशिष्ट मान दस चरण की सीमाओं से आते हैं, D2 =10.

इक्विजॉइन अनुमान को पूरा करना

अब हमारे पास इक्विजॉइन फॉर्मूला के लिए आवश्यक सभी नंबर हैं:

• C' =(C1 * C2) / MAX (D1; D2)
• सी' =(59142 * 9632) / मैक्स(4; 10)
• सी' =569655744 / 10
• सी' =56,965,574.4

याद रखें, यह न्यूनतम मिलान सीमा से ऊपर के हिस्टोग्राम चरणों का योगदान है। जॉइन कार्डिनैलिटी अनुमान को पूरा करने के लिए हमें न्यूनतम मिलान चरण मानों से योगदान जोड़ना होगा, जो कि 1,713 * 1,158 =1,983,654 पंक्तियाँ थीं।

इसलिए अंतिम इक्विजॉइन अनुमान 56,965,574.4 + 1,983,654 =58,949,228.4 पंक्तियाँ या 58,949,200 है छह महत्वपूर्ण आंकड़ों तक।

स्रोत क्वेरी के लिए अनुमानित निष्पादन योजना में इस परिणाम की पुष्टि की गई है:

जैसा कि श्वेत पत्र में उल्लेख किया गया है, यह एक महान अनुमान नहीं है। इस क्वेरी द्वारा लौटाई गई पंक्तियों की वास्तविक संख्या 70,470,090 . है . मूल ("विरासत") कार्डिनैलिटी अनुमानक द्वारा उत्पादित अनुमान - चरण-दर-चरण हिस्टोग्राम संरेखण का उपयोग करके - 70,470,100 पंक्तियाँ हैं।

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

दूसरा उदाहरण

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

ड्रॉप टेबल अगर मौजूद है dbo.R1, dbo.R2; तालिका dbo.R1 बनाएं (n पूर्णांक शून्य नहीं); तालिका बनाएं dbo.R2 (एन पूर्णांक शून्य नहीं); INSERT dbo.R1 (n) मान (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (6) ), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), (6); INSERT dbo.R2 (n) VALUES (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15) ), (10), (10); FULLSCAN के साथ dbo.R1 (n) पर आँकड़ों के आँकड़े बनाएँ; dbo पर आँकड़े बनाएँ। R2 (n) FULLSCAN के साथ;

मिलान किए गए न्यूनतम चरणों को दर्शाने वाले हिस्टोग्राम हैं:

सबसे कम RANGE_HI_KEY जो मेल खाता है 5. EQ_ROWS . का मान दोनों में 1 है, इसलिए अनुमानित इक्विजॉइन कार्डिनैलिटी 1 * 1 =1 पंक्ति . है ।

उच्चतम मिलान RANGE_HI_KEY 10 है। मोटे आवृत्ति-आधारित अनुमान के लिए R1 हिस्टोग्राम पंक्तियों को हाइलाइट करना:

सारांश EQ_ROWS और RANGE_ROWS देता है C1 =24 . अलग-अलग पंक्तियों की संख्या 2 है DISTINCT_RANGE_ROWS (चरणों के बीच विशिष्ट मान) प्लस 3 प्रत्येक चरण सीमा से संबद्ध विशिष्ट मानों के लिए, D1 =5 देते हुए ।

R2 के लिए, संक्षेप EQ_ROWS और RANGE_ROWS देता है C2 =7 . अलग-अलग पंक्तियों की संख्या 2 है DISTINCT_RANGE_ROWS (चरणों के बीच अलग मान) प्लस 3 प्रत्येक चरण सीमा से जुड़े अलग-अलग मानों के लिए, D2 =5 देते हुए ।

इक्विजॉइन अनुमान सी' है:

• C' =(C1 * C2) / MAX (D1; D2)
• सी' =(24 * 7)/5
• सी' =33.6

1 पंक्ति . में जोड़ना न्यूनतम चरण मिलान से 34.6 पंक्तियों . का कुल अनुमान मिलता है इक्विजॉइन के लिए:

R1.n, R2.nFROM से चुनें। 

 अनुमानित निष्पादन योजना हमारी गणना से मेल खाने वाला अनुमान दिखाती है:
 

 
 

 यह बिल्कुल सही नहीं है, लेकिन "विरासत" कार्डिनैलिटी अनुमानक बेहतर नहीं है, अनुमान है कि 15.25 पंक्तियों बनाम 27 वास्तविक:
 

 
 

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

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