लागत-आधारित क्वेरी अनुकूलन

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

Definition

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

Scope

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

Core questions

• समतुल्य निष्पादन योजनाओं का स्थान कैसे उत्पन्न और छाँटा जाता है?
• अनुकूलक संचालन की कार्डिनैलिटी और चयनात्मकता का अनुमान कैसे लगाता है?
• गतिशील प्रोग्रामिंग जॉइन ऑर्डर को कुशलतापूर्वक कैसे सूचीबद्ध करती है?
• लागत मॉडल में क्या शामिल है, और I/O और CPU लागतों को कैसे संयोजित किया जाता है?
• कार्डिनैलिटी-अनुमान त्रुटियों के कारण खराब योजना विकल्प क्यों होते हैं?

Key concepts

• योजना खोज स्थान
• लागत मॉडल (I/O और CPU)
• चयनात्मकता और कार्डिनैलिटी अनुमान
• हिस्टोग्राम और सांख्यिकी
• जॉइन-ऑर्डर गणना
• गतिशील प्रोग्रामिंग
• दिलचस्प ऑर्डर
• परिवर्तन-आधारित अनुकूलन

Key theories

सिस्टम R गतिशील-प्रोग्रामिंग अनुकूलन

सेलिंगर का अनुकूलक गतिशील प्रोग्रामिंग के साथ जॉइन ऑर्डर को नीचे से ऊपर की ओर सूचीबद्ध करता है, संबंधों के प्रत्येक उपसमूह (और प्रत्येक दिलचस्प सॉर्ट ऑर्डर) के लिए सबसे सस्ती योजना रखता है, जो बड़े जॉइन-ऑर्डर स्थान की खोज को व्यवहार्य बनाता है।

कार्डिनैलिटी और चयनात्मकता अनुमान

अनुकूलक तालिका सांख्यिकी, हिस्टोग्राम और चयनात्मकता सूत्रों का उपयोग करके प्रत्येक ऑपरेशन द्वारा उत्पादित टुपल्स की संख्या का अनुमान लगाता है; ये अनुमान लागत मॉडल को संचालित करते हैं और अनुकूलन त्रुटि का मुख्य स्रोत हैं।

लागत मॉडल और खोज रणनीतियाँ

योजनाओं को I/O, CPU और मेमोरी प्रभावों को संयोजित करने वाले लागत मॉडल द्वारा स्कोर किया जाता है; सिस्टम R की गतिशील प्रोग्रामिंग से परे, परिवर्तन-आधारित अनुकूलक समृद्ध ऑपरेटरों और वितरित सेटिंग्स के लिए अनुकूलन का विस्तार करने के लिए पुनर्लेखन नियमों के माध्यम से योजनाओं का अन्वेषण करते हैं।

Clinical relevance

अनुकूलक वह घटक है जो उपयोगकर्ताओं को यह निर्दिष्ट किए बिना घोषणात्मक SQL लिखने देता है कि इसे कैसे निष्पादित किया जाए; इसके लागत अनुमानों और खोज की गुणवत्ता सीधे नियंत्रित करती है कि बड़े डेटाबेस पर क्वेरीज़ तेज़ हैं या नहीं, इसलिए लागत-आधारित अनुकूलन डेटाबेस सिस्टम के सबसे अधिक अध्ययन किए गए और व्यावसायिक रूप से महत्वपूर्ण हिस्सों में से एक है।

History

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

Debates

कार्डिनैलिटी अनुमान बनाम अनुकूली निष्पादन

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

Key figures

• Patricia Selinger
• Goetz Graefe
• Surajit Chaudhuri

Seminal works

• selinger1979
• graefe1993

Frequently asked questions

एक अनुकूलक कभी-कभी खराब योजना क्यों चुनता है?

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

जॉइन ऑर्डरिंग के लिए गतिशील प्रोग्रामिंग का उपयोग क्यों करें?

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