COUNT व्यंजक पर विधेय के लिए कार्डिनैलिटी अनुमान

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

एडवेंचरवर्क्स नमूना डेटाबेस का उपयोग करते हुए एक सरल उदाहरण:

व्यक्ति से A. शहर चुनें। 

 हम यह देखने में रुचि रखते हैं कि SQL सर्वर HAVING में काउंट एक्सप्रेशन पर विधेय के लिए एक अनुमान कैसे प्राप्त करता है खंड।
 

 बेशक HAVING खंड सिर्फ वाक्य रचना चीनी है। हम समान रूप से एक व्युत्पन्न तालिका, या सामान्य तालिका-अभिव्यक्ति का उपयोग करके क्वेरी लिख सकते थे:
 
-- व्युत्पन्न तालिका SQ1 चुनें। -- CTEWITH समूहीकृत AS (चयन A.City, Expr1001 =COUNT_BIG(*) व्यक्ति से। 

 सभी तीन क्वेरी फॉर्म समान निष्पादन योजना उत्पन्न करते हैं, समान क्वेरी योजना हैश मान के साथ।
 

 निष्पादन के बाद (वास्तविक) योजना कुल के लिए एक सही अनुमान दिखाती है; हालांकि, HAVING . के लिए अनुमान क्लॉज फ़िल्टर (या समकक्ष, अन्य क्वेरी रूपों में) खराब है:
 

 
 

 City . पर आंकड़े कॉलम शहर के विशिष्ट मूल्यों की संख्या के बारे में सटीक जानकारी प्रदान करता है:
 
DBCC SHOW_STATISTICS ([Person.Address], शहर) DENSITY_VECTOR के साथ;
 

 
 

 सभी घनत्व आकृति अद्वितीय मानों की संख्या का व्युत्क्रम है। बस गणना करना (1 / 0.00173913) =575 कुल के लिए कार्डिनैलिटी अनुमान देता है। शहर के अनुसार समूहीकरण स्पष्ट रूप से प्रत्येक विशिष्ट मूल्य के लिए एक पंक्ति उत्पन्न करता है।
 

 ध्यान दें कि सभी घनत्व घनत्व वेक्टर से आता है। सावधान रहें कि गलती से घनत्व . का उपयोग न करें DBCC SHOW_STATISTICS . के सांख्यिकी हेडर आउटपुट से मान . शीर्षलेख घनत्व केवल पश्चगामी संगतता के लिए बनाए रखा जाता है; इन दिनों कार्डिनैलिटी अनुमान के दौरान अनुकूलक द्वारा इसका उपयोग नहीं किया जाता है।
 
समस्या
 

 एग्रीगेट वर्कफ़्लो में एक नया कंप्यूटेड कॉलम पेश करता है, जिसे Expr1001 . लेबल किया जाता है निष्पादन योजना में। इसमें COUNT(*) . का मान होता है प्रत्येक समूहीकृत आउटपुट पंक्ति में:
 

 
 

 स्पष्ट रूप से इस नए परिकलित कॉलम के बारे में डेटाबेस में कोई सांख्यिकीय जानकारी नहीं है। जबकि अनुकूलक जानता है कि 575 पंक्तियाँ होंगी, वह वितरण . के बारे में कुछ नहीं जानता है उन पंक्तियों के भीतर गिनती मूल्यों की।
 

 खैर कुछ भी नहीं:अनुकूलक को पता है कि गिनती मान सकारात्मक पूर्णांक (1, 2, 3…) होंगे। फिर भी, यह 575 पंक्तियों के बीच इन पूर्णांक गणना मानों का वितरण है जो COUNT(*) = 1 की चयनात्मकता का सटीक अनुमान लगाने के लिए आवश्यक होगा। विधेय।
 

 कोई यह सोच सकता है कि किसी प्रकार की वितरण जानकारी हिस्टोग्राम से प्राप्त की जा सकती है, लेकिन हिस्टोग्राम केवल विशिष्ट गणना जानकारी प्रदान करता है (EQ_ROWS में) ) हिस्टोग्राम चरण मूल्यों के लिए। हिस्टोग्राम चरणों के बीच, हमारे पास केवल एक सारांश है:RANGE_ROWS पंक्तियों में DISTINCT_RANGE_ROWS है अलग मूल्य। उन तालिकाओं के लिए जो इतनी बड़ी हैं कि हम चयनात्मकता अनुमान की गुणवत्ता की परवाह करते हैं, यह बहुत संभव है कि अधिकांश तालिका इन इंट्रा-स्टेप सारांशों द्वारा दर्शायी जाती है।
 

 उदाहरण के लिए, City . की पहली दो पंक्तियाँ कॉलम हिस्टोग्राम हैं:
 
DBCC SHOW_STATISTICS ([व्यक्ति.पता], शहर) हिस्टोग्राम के साथ;
 

 
 

 यह हमें बताता है कि "एबिंगडन" के लिए बिल्कुल एक पंक्ति है, और "एबिंगडन" के बाद 29 अन्य पंक्तियां हैं, लेकिन "बल्लार्ड" से पहले, उस 29-पंक्ति श्रेणी में 19 अलग-अलग मान हैं। निम्न क्वेरी उस 29-पंक्ति इंट्रा-स्टेप श्रेणी में अद्वितीय मानों के बीच पंक्तियों का वास्तविक वितरण दिखाती है:
 
चुनें A.City, NumRows =COUNT_BIG(*)F From Person.[Address] A.A.City> N'Abingdon' and A.City  

 
 

 जैसा कि हिस्टोग्राम में कहा गया है, 19 अलग-अलग मानों वाली 29 पंक्तियाँ हैं। फिर भी, यह स्पष्ट है कि हमारे पास उस क्वेरी में गिनती कॉलम पर एक विधेय की चयनात्मकता का मूल्यांकन करने का कोई आधार नहीं है। उदाहरण के लिए, HAVING COUNT_BIG(*) = 2 5 पंक्तियाँ लौटाएगा (अलेक्जेंड्रिया, अल्ताडेना, अटलांटा, ऑग्सबर्ग और ऑस्टिन के लिए) लेकिन हमारे पास इसे हिस्टोग्राम से निर्धारित करने का कोई तरीका नहीं है।
 
एक शिक्षित अनुमान
 

 SQL सर्वर का दृष्टिकोण यह मान लेना है कि प्रत्येक समूह सबसे अधिक संभावना है पंक्तियों की कुल माध्य (औसत) संख्या समाहित करने के लिए। यह केवल अद्वितीय मूल्यों की संख्या से विभाजित कार्डिनैलिटी है। उदाहरण के लिए, 20 अद्वितीय मानों वाली 1000 पंक्तियों के लिए, SQL सर्वर मान लेगा कि (1000 / 20) =50 पंक्तियाँ प्रति समूह सबसे संभावित मान है।
 

 हमारे मूल उदाहरण की ओर मुड़ते हुए, इसका अर्थ है कि गणना किए गए गणना कॉलम में "सबसे अधिक संभावना" है कि इसमें लगभग (19614/575) का मान हो ~=34.1113 . चूंकि घनत्व अद्वितीय मूल्यों की संख्या का पारस्परिक है, हम इसे कार्डिनैलिटी * घनत्व के रूप में भी व्यक्त कर सकते हैं =(19614 * 0.00173913), एक बहुत ही समान परिणाम दे रहा है।
 
वितरण
 

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

 SQL सर्वर सामान्य वितरण मानकर इसे संभालता है। इसमें विशिष्ट घंटी का आकार है जिससे आप पहले से परिचित हो सकते हैं (लिंक की गई विकिपीडिया प्रविष्टि से छवि):
 

 
 

 सामान्य वितरण का सटीक आकार दो पैरामीटर . पर निर्भर करता है :माध्य (μ ) और मानक विचलन (σ ) माध्य शिखर का स्थान निर्धारित करता है। मानक विचलन निर्दिष्ट करता है कि घंटी वक्र कैसे "चपटा" है। वक्र जितना समतल होगा, शिखर उतना ही कम होगा, और अन्य मानों पर प्रायिकता घनत्व का वितरण उतना ही अधिक होगा।
 

 SQL सर्वर सांख्यिकीय जानकारी से माध्य प्राप्त कर सकता है जैसा कि पहले ही उल्लेख किया गया है। मानक विचलन परिकलित गणना स्तंभ मानों का अज्ञात है। SQL सर्वर इसका अनुमान वर्गमूल . के रूप में लगाता है माध्य का (थोड़ा समायोजन बाद में विस्तृत किया गया है)। हमारे उदाहरण में, इसका मतलब है कि सामान्य वितरण के दो पैरामीटर मोटे तौर पर 34.1113 और 5.84 (वर्गमूल) हैं।
 

 मानक सामान्य वितरण (उपरोक्त चित्र में लाल वक्र) एक उल्लेखनीय विशेष मामला है। यह तब होता है जब माध्य शून्य होता है, और मानक विचलन 1 होता है। किसी भी सामान्य वितरण को मानक विचलन से घटाकर और मानक विचलन से विभाजित करके मानक सामान्य वितरण में परिवर्तित किया जा सकता है।
 
क्षेत्र और अंतराल
 

 हम चयनात्मकता का अनुमान लगाने में रुचि रखते हैं, इसलिए हम इस संभावना की तलाश कर रहे हैं कि गणना किए गए कॉलम का एक निश्चित मान (x) हो। यह प्रायिकता उपरोक्त y-अक्ष मान से नहीं, बल्कि वक्र के अंतर्गत क्षेत्र द्वारा दी गई है x के बाईं ओर।
 

 माध्य 34.1113 और मानक विचलन 5.84 के साथ सामान्य वितरण के लिए, x =30 के बाईं ओर वक्र के नीचे का क्षेत्र लगभग 0.2406 है:
 

 
 

 यह इस संभावना से मेल खाता है कि परिकलित गणना स्तंभ इससे कम या उसके बराबर . है 30 हमारी उदाहरण क्वेरी के लिए।
 

 यह अच्छी तरह से इस विचार की ओर ले जाता है कि सामान्य तौर पर, हम एक विशिष्ट मूल्य की संभावना की तलाश नहीं कर रहे हैं, लेकिन एक अंतराल के लिए . संभवत:यह पता लगाने के लिए कि गिनती बराबर है एक पूर्णांक मान, हमें इस तथ्य पर ध्यान देने की आवश्यकता है कि पूर्णांक आकार 1 के अंतराल को फैलाते हैं। हम एक पूर्णांक को अंतराल में कैसे परिवर्तित करते हैं, यह कुछ हद तक मनमाना है। SQL सर्वर 0.5 . जोड़कर और घटाकर इसे हैंडल करता है अंतराल की निचली और ऊपरी सीमा देने के लिए।
 

 उदाहरण के लिए, परिकलित गणना मान 30 के बराबर होने की प्रायिकता ज्ञात करने के लिए, हमें घटाना की आवश्यकता है (x =29.5) के लिए (x =30.5) के क्षेत्र से सामान्य वितरण वक्र के तहत क्षेत्र। परिणाम नीचे दिए गए आरेख में (29.5  

 
 

 लाल टुकड़े का क्षेत्रफल लगभग 0.0533 . है . एक अच्छे पहले सन्निकटन के लिए, यह हमारी परीक्षण क्वेरी में एक गिनती =30 विधेय की चयनात्मकता है।
 
संचयी वितरण फ़ंक्शन
 

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

 चूंकि सभी सामान्य वितरण आसानी से मानक सामान्य वितरण (माध्य =0, मानक विचलन =1) में परिवर्तित किए जा सकते हैं, सन्निकटन सभी मानक सामान्य का अनुमान लगाने के लिए काम करते हैं। इसका मतलब है कि हमें रूपांतरण . करने की आवश्यकता है क्वेरी के लिए उपयुक्त विशेष सामान्य वितरण से लेकर मानक सामान्य वितरण तक हमारी अंतराल सीमाएं। यह, जैसा कि पहले उल्लेख किया गया है, माध्य घटाकर और मानक विचलन से विभाजित करके किया जाता है।
 

 यदि आप एक्सेल से परिचित हैं, तो आप NORM.DIST और NORM.S.DIST के कार्यों से अवगत हो सकते हैं जो किसी विशेष सामान्य वितरण या मानक सामान्य वितरण के लिए CDF (संख्यात्मक सन्निकटन विधियों का उपयोग करके) की गणना कर सकते हैं।
 

 SQL सर्वर में कोई CDF कैलकुलेटर नहीं बनाया गया है, लेकिन हम इसे आसानी से बना सकते हैं। यह देखते हुए कि मानक सामान्य वितरण के लिए सीडीएफ है:
 

 
 

 ...जहां erf त्रुटि फ़ंक्शन है:
 

 
 

 मानक सामान्य वितरण के लिए सीडीएफ प्राप्त करने के लिए एक टी-एसक्यूएल कार्यान्वयन नीचे दिखाया गया है। यह त्रुटि फ़ंक्शन . के लिए एक संख्यात्मक सन्निकटन का उपयोग करता है जो आंतरिक रूप से उपयोग किए जाने वाले SQL सर्वर के बहुत करीब है:
 
CREATE PROCEDURE dbo.GetStandardNormalCDF(@x float, @cdf float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON; डिक्लेयर @ साइन फ्लोट, @erf फ्लोट; सेट @ साइन =साइन (@x); SET @x =ABS(@x) / SQRT(2); सेट @erf =1; सेट @erf =@erf + (0.0705230784 * @x); सेट @erf =@erf + (0.0422820123 * पावर(@x, 2)); सेट @erf =@erf + (0.0092705272 * पावर (@x, 3)); सेट @erf =@erf + (0.0001520143 * पावर (@x, 4)); सेट @erf =@erf + (0.0002765672 * पावर (@x, 5)); सेट @erf =@erf + (0.0000430638 * पावर(@x, 6)); सेट @erf =पावर (@erf, -16); सेट @erf =1 - @erf; सेट @erf =@erf * @ साइन; SET @cdf =0.5 * (1 + @erf);END;
 

 एक उदाहरण, हमारी परीक्षण क्वेरी के लिए सामान्य वितरण का उपयोग करके x =30 के लिए CDF की गणना करने के लिए:
 
DECLARE @cdf float;DECLARE @x float;-- COUNT_BIG(*) =xSET @x =30;-- 30 को नॉर्मलाइज करने के लिए माध्य घटाना-- और स्टैंडर्ड डिवएशनसेट @x =(@x - 34.1113/5.84; निष्पादित dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf OUTPUT; चयन CDF =@cdf;
 

 मानक सामान्य वितरण में बदलने के लिए सामान्यीकरण चरण पर ध्यान दें। प्रक्रिया मान 0.2407196… लौटाती है, जो संबंधित एक्सेल परिणाम से सात दशमलव स्थानों से मेल खाता है।
 
अंतिम विवरण और उदाहरण
 

 निम्न कोड फ़िल्टर के लिए एक बड़ा अनुमान बनाने के लिए हमारी उदाहरण क्वेरी को संशोधित करता है (तुलना अब मान 32 के साथ है, जो पहले की तुलना में माध्य के बहुत करीब है):
 
व्यक्ति से A.CityFrom चुनें।[पता] A.CityHAVING COUNT_BIG(*) =32 द्वारा समूह के रूप में;
 

 
 

 अनुकूलक का अनुमान अब 36.7807 . है ।
 

 मैन्युअल रूप से अनुमान की गणना करने के लिए, हमें पहले कुछ अंतिम विवरणों को संबोधित करना होगा:
 
 
मानक विचलन (वर्गमूल के माध्यम से) प्राप्त करने के लिए उपयोग किया जाने वाला माध्य ((अलग मान -1) / (अलग मान) के एक कारक द्वारा बढ़ाया जाता है . उदाहरण में, अलग-अलग मानों की संख्या 575 है, इसलिए स्केलिंग फ़ैक्टर (574/575) ~=0.99826 है। 
यदि (पूर्णांक) अंतराल की निचली सीमा 1 है, तो SQL सर्वर अंतराल को अनबाउंड मानता है निचली तरफ। चयनात्मकता अकेले अंतराल (1.5) की ऊपरी सीमा के सीडीएफ के बराबर है। निचली सीमा (जो 0.5 होगी) का उपयोग नहीं किया जाता है। 
विरासत कार्डिनैलिटी अनुमानक (सीई) के पास COUNT(*) = 1 के लिए जटिल तर्क है , जो यहाँ विस्तृत नहीं है। 
COUNT(*) = 1 . के अलावा मामले में, लीगेसी सीई नए सीई (एसक्यूएल सर्वर 2014 में उपलब्ध) के समान तर्क का उपयोग करती है।
 
 

 निम्नलिखित प्रक्रिया इस आलेख में सभी विवरणों को शामिल करती है। इसके लिए पहले दी गई सीडीएफ प्रक्रिया की आवश्यकता है:
 
प्रक्रिया बनाएं dbo.GetCountPredicateEstimate (@ पूर्णांक से, @ पूर्णांक तक, @ कार्डिनैलिटी फ्लोट, @ घनत्व फ्लोट, @ चयन फ्लोट आउटपुट, @ एस्टीमेट फ्लोट आउटपुट) ASBEGIN SET NOCOUNT, XACT_ABORT ON; शुरू करने की कोशिश करें @ फ्लोट शुरू करें, @ अंत फ्लोट, @ अलग फ्लोट, @ मीन फ्लोट, @ मीनएडज फ्लोट, @Stdev फ्लोट, @ नॉर्मस्टार्ट फ्लोट, @ नॉर्मएंड फ्लोट, @ सीडीएफस्टार्ट फ्लोट, @ सीडीएफएंड फ्लोट; -- इनपुट मान्य करें और डिफ़ॉल्ट लागू करें यदि ISNULL(@From, 0) =0 SET @From =1; अगर @ से <1 रेज़र ('@ से होना चाहिए>=1', 16, 1); IF ISNULL(@Cardinality, -1) <=0 RAISERROR('@Cardinality is be पॉजिटिव', 16, 1); अगर ISNULL(@Density, -1) <=0 RAISERROR('@Density is be पॉजिटिव', 16, 1); अगर ISNULL(@To, 0) =0 SET @To =CEILING(1 / @Density); अगर @To <@RAISERROR से('@To होना चाहिए>=@From', 16, 1); - पूर्णांक श्रेणी को अंतराल में बदलें SET @Start =@From - 0.5; SET @End =@To + 0.5; - अलग-अलग मानों की संख्या प्राप्त करें SET @Distinct =1 / @Density; - माध्य SET @Mean =@Cardinality * @Density की गणना करें; - माध्य समायोजित करें; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); - मानक विचलन (अनुमान) प्राप्त करें SET @Stdev =SQRT(@MeanAdj); - अंतराल को सामान्य करें SET @NormStart =(@Start - @Mean) / @Stdev; सेट @NormEnd =(@End - @Mean) / @Stdev; -- CDF की गणना करें dbo निष्पादित करें। GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart OUTPUT; निष्पादित dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd OUTPUT; - चयनात्मकता सेट @ चयनात्मकता =मामला - असीमित प्रारंभ जब @ से =1 तब @CDFEnd - असीमित अंत जब @To>=@ विशिष्ट तब 1 - @CDFStart - सामान्य अंतराल ELSE @CDFEnd - @CDFStart END; -- वापसी पंक्ति अनुमान SET @Estimate =@Selectivity * @Distinct; END TRY BEGIN DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); अगर @@ ट्रांज़ैक्शन> 0 रोलबैक ट्रांज़ैक्शन; रायसरर (@EM, 16, 1); वापसी; END CATCH;END;
 

 अब हम अपनी नई परीक्षण क्वेरी के लिए अनुमान उत्पन्न करने के लिए इस प्रक्रिया का उपयोग कर सकते हैं:
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; चयन चयन =@ चयन, अनुमान =@ अनुमान, गोल =गोल (@ अनुमान, 4); 
 

 आउटपुट है:
 

 
 

 यह ऑप्टिमाइज़र के 36.7807 के कार्डिनैलिटी अनुमान के साथ बहुत अच्छी तरह से तुलना करता है। 
 
असमानता अंतराल के उदाहरण
 

 प्रक्रिया का उपयोग समानता परीक्षणों के अलावा अन्य गणना अंतरालों के लिए किया जा सकता है। बस जरूरत है @From . सेट करने की और @To पूर्णांक अंतराल सीमाओं के पैरामीटर। असीमित निर्दिष्ट करने के लिए, शून्य पास करें या NULL जैसा आप पसंद करते हैं।
 
व्यक्ति से A.CityFROM चुनें।[पता] A.CityHAVING COUNT_BIG(*) <50;
 

 
 

 हमारी प्रक्रिया के साथ इसका उपयोग करने के लिए, हम सेट करते हैं @From = NULL और @To = 49 (क्योंकि 50 को इससे कम से बाहर रखा गया है):
 
DECLARE @Selectivity फ्लोट, @Estimate फ्लोट; EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT; चयन चयन =@ चयन, अनुमान =@ अनुमान, गोल =गोल (@ अनुमान, 4); 
 

 परिणाम 572.5964 है:
 

 
 

 BETWEEN . का उपयोग करते हुए एक अंतिम उदाहरण :
 
एक व्यक्ति से चुनें। 

 अनुकूलक अनुमान है 
 

 
 

 चूंकि BETWEEN समावेशी है, हम प्रक्रिया पास करते हैं @From = 25 और @To = 30 . नतीजा यह है:
 

 
 

 फिर से, यह अनुकूलक अनुमान से सहमत है।