जॉइन एल्गोरिदम: Nested Loop, Hash, Merge
प्रत्येक जॉइन कैसे निष्पादित होता है और किस परिस्थिति में कौन-सा सही विकल्प है
जॉइन एल्गोरिदम: Nested Loop, Hash, Merge, CoddyKit पर SQL साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह SQL साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। SQL साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
जॉइन केवल सिंटैक्स नहीं, एल्गोरिद्म हैं
आप INNER JOIN को सिंटैक्स के रूप में पहले से जानते हैं। वरिष्ठ-स्तर के साक्षात्कारों में आपसे पूछा जाता है कि डेटाबेस किसी जॉइन को वास्तव में कैसे निष्पादित करता है। तीन एल्गोरिद्म हैं:
- नेस्टेड लूप जॉइन
- हैश जॉइन
- मर्ज जॉइन (क्रमबद्ध-मर्ज)
तार्किक जॉइन प्रकार (INNER, LEFT) एल्गोरिद्म से स्वतंत्र होता है। प्लानर तालिकाओं के आकार, इंडेक्स और क्रमबद्ध क्रम के आधार पर एल्गोरिद्म चुनता है। प्रत्येक एल्गोरिद्म कब बेहतर होता है, यह जानना इस पाठ का मुख्य विषय है।
नेस्टेड लूप जॉइन
नेस्टेड लूप सबसे सरल होता है: बाहरी तालिका की प्रत्येक पंक्ति के लिए, मिलान खोजने हेतु आंतरिक तालिका को स्कैन करें। छद्म-कोड में यह एक-दूसरे के भीतर मौजूद दो लूप होते हैं।
साधारण रूप में इसकी जटिलता O(बाहरी * आंतरिक) होती है, इसलिए बड़ी तालिकाओं के लिए यह बहुत खराब है। लेकिन जब आंतरिक भाग में जॉइन कुंजी पर इंडेक्स हो, तो यह बहुत अच्छा हो जाता है: प्रत्येक बाहरी पंक्ति पूरे आंतरिक स्कैन के बजाय कम लागत वाली इंडेक्स खोज शुरू करती है।
जब बाहरी तालिका छोटी हो और आंतरिक जॉइन कॉलम पर इंडेक्स हो, तब यह प्लानर का पसंदीदा विकल्प होता है।
Nested Loop (cost=0.42..120.5 rows=15 width=72)
-> Seq Scan on customers c (rows=3)
-> Index Scan using idx_orders_cust on orders o
Index Cond: (o.customer_id = c.id)
(loops=3)नेस्टेड लूप में लूप पढ़ना
नेस्टेड लूप की पहचान आंतरिक नोड पर मौजूद loops से होती है। उदाहरण में loops=3 है, क्योंकि बाहरी भाग ने 3 पंक्तियाँ दीं और इसलिए आंतरिक इंडेक्स स्कैन 3 बार चला।
खतरा तब दिखाई देता है जब बाहरी भाग बड़ा हो। यदि बाहरी भाग 20 लाख पंक्तियाँ देता है, तो आंतरिक भाग 20 लाख बार चलेगा। 0.01ms की तेज़ खोज भी तब 20 सेकंड ले सकती है।
साक्षात्कार में ऐसे किसी नेस्टेड लूप को चिन्हित करें जिसमें बिना अच्छे इंडेक्स वाली आंतरिक तालिका पर loops का मान बहुत बड़ा हो; यही धीमी क्वेरी है।
हैश जॉइन
हैश जॉइन बड़ी, बिना क्रमबद्ध तालिकाओं के लिए अच्छा होता है। यह दो चरणों में चलता है:
- निर्माण: छोटी तालिका को पढ़कर जॉइन कॉलम की कुंजी के आधार पर उसे मेमोरी में मौजूद हैश तालिका में लोड करें।
- खोज: बड़ी तालिका को स्कैन करें; प्रत्येक पंक्ति के लिए जॉइन कुंजी का हैश निकालकर उसे हैश तालिका में खोजें।
प्रत्येक तालिका केवल एक बार पढ़ी जाती है, इसलिए जटिलता लगभग O(बाहरी + आंतरिक) होती है। इसके लिए न तो इंडेक्स चाहिए और न ही क्रमबद्ध इनपुट, इसलिए समानता वाली शर्तों पर बड़ी विश्लेषणात्मक जॉइन में यही अक्सर सबसे बेहतर होता है।
Hash Join (cost=18.0..520.0 rows=900 width=72)
Hash Cond: (o.customer_id = c.id)
-> Seq Scan on orders o (rows=100000)
-> Hash (rows=500)
-> Seq Scan on customers c (rows=500)हैश जॉइन की सीमाएँ
हैश जॉइन के बारे में आपको दो बातें अवश्य बतानी चाहिए:
- ये केवल समानता वाली जॉइन शर्तों पर काम करते हैं (
a.id = b.id)।a.x < b.yजैसी परास-शर्त हैश जॉइन का उपयोग नहीं कर सकती। - निर्माण वाला भाग work_mem में समा जाना चाहिए। यदि ऐसा नहीं होता, तो Postgres बैचों को डिस्क पर लिख देता है (आपको
Batches: > 1और डिस्क का उपयोग दिखाई देगा), जिससे जॉइन बहुत धीमा हो जाता है।
इसलिए बहुत बड़े निर्माण-भाग और बहुत छोटे work_mem वाला हैश जॉइन वास्तविक दुनिया की प्रदर्शन-संबंधी ऐसी त्रुटि है जिसे आपको अवश्य बताना चाहिए।
Hash (actual rows=2000000 loops=1)
Buckets: 65536 Batches: 16 Memory Usage: 4096kBमर्ज जॉइन
मर्ज जॉइन (क्रमबद्ध-मर्ज) के लिए दोनों इनपुट जॉइन कुंजी के आधार पर क्रमबद्ध होने चाहिए। इसके बाद यह दो क्रमबद्ध सूचियों को मिलाने की तरह, दोनों पर समान गति से आगे बढ़ता है और जो संकेतक पीछे है उसे आगे करता है।
जब इनपुट पहले से क्रमबद्ध हों, जैसे कुंजी-क्रम में सीधे इंडेक्स से आ रहे हों, तब यह कुशल होता है, क्योंकि उस स्थिति में अलग से क्रमबद्ध करने की आवश्यकता नहीं होती। हैश जॉइन के विपरीत, यह परास और असमानता वाले जॉइन का भी समर्थन करता है।
यदि इनपुट पहले से क्रमबद्ध नहीं हैं, तो प्लानर स्पष्ट Sort नोड जोड़ता है और उस क्रमबद्धता की लागत हैश जॉइन को अधिक सस्ता बना सकती है।
Merge Join (cost=0.85..210.0 rows=900 width=72)
Merge Cond: (o.customer_id = c.id)
-> Index Scan using idx_orders_cust on orders o
-> Index Scan using customers_pkey on customers cनिर्णय लेने की संक्षिप्त मार्गदर्शिका
याद रखें कि प्रत्येक एल्गोरिद्म कब बेहतर होता है:
- नेस्टेड लूप, जब बाहरी तालिका छोटी हो और आंतरिक जॉइन कुंजी पर इंडेक्स हो; बिना क्रमबद्ध इनपुट वाले असमानता-जॉइन के लिए यह एकमात्र विकल्प भी है।
- हैश जॉइन, जब बड़ी, बिना क्रमबद्ध तालिकाओं को समानता वाली शर्त पर जोड़ा जा रहा हो; इंडेक्स की आवश्यकता नहीं होती।
- मर्ज जॉइन, जब दोनों इनपुट कुंजी के आधार पर पहले से क्रमबद्ध हों (अक्सर इंडेक्स के माध्यम से), या परास-जॉइन के लिए; बहुत बड़े, पहले से क्रमबद्ध डेटा-समूहों के लिए यह शानदार होता है।
प्लानर पंक्तियों के अपने अनुमानों के आधार पर प्रत्येक विकल्प की लागत का अनुमान लगाता है और सबसे सस्ता विकल्प चुनता है।
मेमोरी और क्रमबद्धता की लागत
संसाधनों का उपयोग बहुत अलग-अलग होता है और साक्षात्कारकर्ता इस बारे में प्रश्न पूछते हैं:
- नेस्टेड लूप, बहुत कम मेमोरी चाहिए; इसकी लागत बार-बार होने वाली आंतरिक खोजों से निर्धारित होती है।
- हैश जॉइन, हैश तालिका के लिए मेमोरी चाहिए; बहुत बड़ी होने पर यह डिस्क पर लिखी जाती है।
- मर्ज जॉइन, मिलाना सस्ता होता है, लेकिन पहले क्रमबद्ध करना पड़े तो वह महँगा होता है; क्रमबद्ध करने की प्रक्रिया भी
work_memका उपयोग करती है और डिस्क पर लिखी जा सकती है।
इसलिए work_mem बढ़ाने से डिस्क पर लिखने वाले धीमे हैश या क्रमबद्धता को मेमोरी में होने वाली तेज़ प्रक्रिया में बदला जा सकता है। यह अनुकूलन का एक ठोस उत्तर है।
नेस्टेड लूप गलत क्यों हुआ
सामान्य स्थिति: डेवलपमेंट में क्वेरी तेज़ थी, लेकिन प्रोडक्शन में धीमी। प्लान में loops=3000000 वाला नेस्टेड लूप दिखाई देता है।
प्लानर ने बाहरी पंक्तियों की संख्या को कम आँका (पुराने आँकड़ों में 3 पंक्तियाँ थीं, जबकि वास्तविकता में 30 लाख थीं), इसलिए उसने नेस्टेड लूप चुना। सही आँकड़े होने पर वह हैश जॉइन चुनता।
साक्षात्कार में आपका उत्तर होना चाहिए: ANALYZE चलाएँ ताकि अनुमान सही हो जाए; इसके बाद प्लानर हैश जॉइन पर स्विच करेगा और क्वेरी बहुत तेज़ हो जाएगी।
Nested Loop (cost=0.42..50.0 rows=3 width=72)
-> Seq Scan on big_outer (actual rows=3000000 loops=1)
-> Index Scan on inner_t (actual rows=1 loops=3000000)चयन को प्रभावित करना
आमतौर पर आपको एल्गोरिद्म को जबरन नहीं चुनना चाहिए, लेकिन तुलना करने के लिए परीक्षण में ऐसा किया जा सकता है। Postgres प्रत्येक विधि के लिए टॉगल उपलब्ध कराता है:
SET enable_nestloop = off; और इसी तरह enable_hashjoin तथा enable_mergejoin के लिए भी। किसी एक को बंद करके EXPLAIN ANALYZE फिर चलाएँ और देखें कि वैकल्पिक तरीका वास्तव में तेज़ है या नहीं।
सही समाधान अब भी यही हैं: नए आँकड़े, सही इंडेक्स, पर्याप्त work_mem और चयनात्मक शर्तें। जबरन चयन केवल निदान के लिए है।
SET enable_nestloop = off;
EXPLAIN ANALYZE
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id;
SET enable_nestloop = on;बड़े पैमाने पर जॉइन का सारांश
दो बड़ी तथ्य और आयाम तालिकाओं को किसी पहचानकर्ता पर जोड़ने वाले विश्लेषणात्मक कार्यभार के लिए इसे एक साथ समझें:
- यदि आयाम तालिका मेमोरी में समा जाती है, तो हैश जॉइन की अपेक्षा करें; यह अक्सर सबसे अच्छा विकल्प होता है।
- यदि दोनों तालिकाएँ इंडेक्स से क्रमबद्ध रूप में आती हैं, तो मर्ज जॉइन हैश तालिका बनाने की आवश्यकता से बच सकता है।
- यहाँ नेस्टेड लूप एक चेतावनी संकेत होगा, जो आमतौर पर गलत अनुमान के कारण होता है।
प्लानर ने कौन-सा विकल्प चुना और उसे कौन-सा चुनना चाहिए था, यह पढ़ना ही वह वरिष्ठ-स्तर की समझ है जिसे इन प्रश्नों में जाँचा जाता है।
त्वरित जाँच
आप दो बड़ी, बिना क्रमबद्ध तालिकाओं को समानता वाली शर्त a.id = b.id पर जोड़ते हैं, दोनों में कोई उपयोगी इंडेक्स नहीं है और आँकड़े सही हैं। प्लानर सबसे अधिक संभावना से कौन-सा जॉइन एल्गोरिद्म चुनेगा?
पुनरावलोकन
तीन जॉइन एल्गोरिद्म:
- नेस्टेड लूप, बाहरी पंक्ति के लिए आंतरिक खोज; छोटी बाहरी तालिका और इंडेक्स वाली आंतरिक कुंजी के साथ शानदार, लेकिन
loopsबहुत बड़ा होने पर खतरनाक। - हैश जॉइन, निर्माण और खोज; बड़ी, बिना क्रमबद्ध समानता-जॉइन के लिए सर्वोत्तम, केवल समानता तक सीमित और
work_memसे नियंत्रित। - मर्ज जॉइन, क्रमबद्ध इनपुट पर समान गति से आगे बढ़ता है; डेटा पहले से क्रमबद्ध होने पर या परास-जॉइन के लिए आदर्श।
प्लानर लागत और आँकड़ों के आधार पर चुनाव करता है। बहुत बड़े loops वाला आश्चर्यजनक नेस्टेड लूप लगभग हमेशा पंक्तियों के गलत अनुमान का संकेत होता है; आँकड़े ठीक करें।
एआई शिक्षक के साथ SQL सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “जॉइन एल्गोरिदम: Nested Loop, Hash, Merge” पाठ निःशुल्क है?
हाँ—“जॉइन एल्गोरिदम: Nested Loop, Hash, Merge” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और SQL साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। SQL साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“जॉइन एल्गोरिदम: Nested Loop, Hash, Merge” में मैं क्या सीखूँगा?
प्रत्येक जॉइन कैसे निष्पादित होता है और किस परिस्थिति में कौन-सा सही विकल्प है आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ SQL साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या SQL साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर SQL साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“जॉइन एल्गोरिदम: Nested Loop, Hash, Merge” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस SQL साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर SQL साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- EXPLAIN प्लान पढ़ना
- Seq Scan बनाम Index Scan बनाम Index-Only
- जॉइन एल्गोरिदम: Nested Loop, Hash, Merge
- धीमी क्वेरी पहचानना और ठीक करना