एक कार्य की समय जटिलता क्या है जैसे कि गिनती, योग, औसत या "गणित" में निर्मित किसी भी अन्य - MySQL, SQL सर्वर, ऑरैकल और अन्य में फ़ंक्शन?
एक सोचता है कि कॉलिंग योग (myColumn) रैखिक होगा।
लेकिन गिनती (1) नहीं है। टी कैसे आते हैं और वास्तविक समय-जटिलता क्या हैं?
एक परिपूर्ण दुनिया में मैं योग, एवीजी और ओ (1) होने के लिए गिनती चाहता हूं। लेकिन हम उनमें से किसी एक में नहीं रहते हैं, क्या हम?
उत्तर:
जवाब के लिए 2 № 1एसक्यूएल में गणित कार्य समेकन की जटिलतापूरी तरह से प्रासंगिक है। एकमात्र चीज जो वास्तव में मायने रखती है वह डेटा एसीस जटिलता है: किस एक्सेस पथ का चयन किया जाता है (टेबल स्कैन, इंडेक्स रेंज स्कैन, इंडेक्स सर्च इत्यादि) और कितने पेज पढ़े जाते हैं। प्रत्येक कुल के आंतरिक में थोड़ा अंतर हो सकता है, लेकिन वे सभी एक ही तरीके से काम करते हैं (चल रहे राज्य को रखें और प्रत्येक इनपुट मान के लिए चल रहे एकत्रीकरण की गणना करें) और बिल्कुल नहीं योग जो इनपुट को दो बार देखता है, इसलिए वे सभी ओ (एन) आंतरिक कार्यान्वयन के रूप में, जहां "एन" कुल को खिलाए गए रिकॉर्ड की संख्या है (तालिका में रिकॉर्ड की संख्या की संख्या नहीं है!)।
कुछ समेकित आंतरिक शॉर्टकट होते हैं, उदाहरण के लिए। COUNT (*) हो सकता है यदि संभव हो, तो कुछ सिस्टमों पर मेटाडेटा से गिनती वापस करें।
जवाब के लिए 3 № 2
एक कार्य की समय जटिलता क्या है जैसे कि गिनती, योग, औसत या "गणित" में निर्मित किसी भी अन्य - MySQL, SQL सर्वर, ऑरैकल और अन्य में फ़ंक्शन?
में
MySQLसाथ मेंMyISAM,COUNT(*)के बग़ैरGROUP BYहैO(1)(स्थिर)यह तालिका मेटाडेटा में संग्रहीत है।
सभी प्रणालियों में,
MAXतथाMINबिना अनुक्रमित अभिव्यक्तियों परGROUP BYकर रहे हैंO(log(n))(लघुगणक)।वे एक इंडेक्स खोज के साथ लाए जाते हैं।
कुल कार्य हैं
O(n)(रैखिक), जब बिना इस्तेमाल कियाGROUP BYयाGROUP BYका उपयोग करता हैHASHकुल कार्य हैं
O(n log(n))कबGROUP BYका उपयोग करता हैSORT.
सभी मानों को राज्य चर में प्राप्त, गणना और संग्रहीत किया जाना चाहिए (जिसे हैश तालिका में संग्रहीत किया जा सकता है)।
इसके अलावा, उपयोग करते समय SORT, उन्हें भी हल किया जाना चाहिए।
उत्तर № 3 के लिए 1
नोट: एसक्यूएल क्वेरी प्लानर्स कैसे काम करते हैं, इसकी समझ के आधार पर यह अनुमान लगाया गया है, और यह पूरी तरह सटीक नहीं हो सकता है।
मेरा मानना है कि सभी समग्र कार्यों, या कम से कम "गणित" जिन्हें आप उपरोक्त नाम देते हैं, ओ (एन) होना चाहिए। क्वेरी को लगभग निम्नानुसार निष्पादित किया जाएगा:
- जुड़ने वाली पंक्तियों को प्राप्त करने से मेल खाने वाली पंक्तियां प्राप्त करें और भविष्यवाणी करें (यानी "कहां खंड")
- ग्रुप बाय क्लॉज के अनुसार पंक्ति-समूह बनाएं। ग्रुप बाय के साथ पूछताछ के लिए एक एकल पंक्ति समूह बनाया गया है
- प्रत्येक पंक्ति समूह के लिए, कुल कार्य लागू करेंसमूह में पंक्तियों के लिए। एसयूएम, एवीजी, मिन, मैक्स और साथ ही गैर-संख्यात्मक कार्यों जैसे कि कंकैट जैसी चीजों के लिए सरल ओ (एन) एल्गोरिदम हैं, और मुझे संदेह है कि उनका उपयोग किया जाता है। चरण # 2 में बनाए गए प्रत्येक पंक्ति-समूह के आउटपुट सेट में एक पंक्ति बनाएं
- यदि एक हैविंग भविष्यवाणी मौजूद है, तो इस predicate का उपयोग कर आउटपुट पंक्तियों को फ़िल्टर करें
नोट, हालांकि, हालांकि कुल मिलाकरकार्य ओ (एन) हैं, ऑपरेशन नहीं हो सकता है। यदि आप एक क्वेरी बनाते हैं जो कार्टेशियन स्वयं तालिका में शामिल हो जाता है, तो आप प्रारंभिक पंक्ति सेट (चरण # 1) बनाने के लिए न्यूनतम (ओ * एन) न्यूनतम देखेंगे। पंक्ति-समूह बनाने के लिए सॉर्टिंग (चरण # 2) ओ (एन एलजी एन) हो सकता है, और सॉर्ट ऑपरेशन के लिए डिस्क संग्रहण की आवश्यकता हो सकती है (केवल इन-मेमोरी ऑपरेशन के विपरीत), इसलिए यदि आप हैं तो आपकी क्वेरी खराब प्रदर्शन कर सकती है कई पंक्तियों में हेरफेर करना।
जवाब के लिए 0 № 4
बड़े डेटा-गोदाम शैली के प्रश्नों के लिए, प्रमुखडेटाबेस कार्य को समानांतर कर सकते हैं, इसलिए इसमें कई CPUs काम कर रहे हैं। ऐसे में थ्रेसहोल्ड पॉइंट होंगे जहां यह कई सीपीयू का उपयोग करने के लाभ के विपरीत समानांतर धागे को समन्वयित करने की लागत के रूप में काफी रैखिक नहीं है।