SQL Interview Prep · درس

خوارزميات الربط: Nested Loop وHash وMerge

كيفية تنفيذ كل نوع من الربط ومتى يكون الخيار المناسب

خوارزميات الربط: Nested Loop وHash وMerge درس مجاني في SQL Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في SQL Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة SQL Interview Prep 4 دروس في المجموع.

عمليات الربط خوارزميات وليست مجرد صياغة

أنتم تعرفون INNER JOIN بوصفه صياغةً برمجية. لكن في مقابلات المستوى المتقدم، يسأل المحاورون عن كيفية تنفيذ قاعدة البيانات لعملية الربط فعليًا. توجد ثلاث خوارزميات:

الربط بالحلقات المتداخلة
الربط بالتجزئة
ربط الدمج (الفرز والدمج)

نوع الربط المنطقي (INNER، LEFT) مستقل عن الخوارزمية. يختار مخطط الاستعلام الخوارزمية بناءً على أحجام الجداول والفهارس وترتيب الفرز. ومعرفة متى تتفوق كل خوارزمية هي جوهر هذا الدرس.

الربط بالحلقات المتداخلة

تُعد الحلقات المتداخلة أبسط خوارزمية: إذ يجري فحص الجدول الداخلي بحثًا عن المطابقات لكل صف في الجدول الخارجي. وفي الشيفرة الوهمية، تكون هناك حلقتان، إحداهما داخل الأخرى.

بصورة ساذجة، يكون التعقيد O(outer * inner)، وهو سيئ جدًا مع الجداول الكبيرة. لكنه يصبح ممتازًا عندما يحتوي الجانب الداخلي على فهرس في مفتاح الربط؛ إذ يؤدي كل صف خارجي إلى عملية بحث رخيصة في الفهرس بدلًا من إجراء فحص كامل للجدول الداخلي.

ويفضّله مخطط الاستعلام عندما يكون الجدول الخارجي صغيرًا وعمود الربط في الجدول الداخلي مفهرسًا.

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 مرات.

يظهر الخطر عندما يكون الجانب الخارجي كبيرًا. فإذا أنتج الجانب الخارجي مليونَي صف، فستُنفّذ العملية الداخلية مليونَي مرة. وحتى عملية بحث سريعة تستغرق 0.01ms قد تستغرق 20 ثانية.

في المقابلات، أشيروا إلى أي حلقة متداخلة تكون فيها قيمة loops كبيرة فوق جدول داخلي لا يملك فهرسًا مناسبًا؛ فهذا هو الاستعلام البطيء.

الربط بالتجزئة

تتعامل خوارزمية الربط بالتجزئة جيدًا مع الجداول الكبيرة غير المرتبة. وتعمل على مرحلتين:

البناء: قراءة الجدول الأصغر وتحميله في جدول تجزئة داخل الذاكرة، باستخدام عمود الربط مفتاحًا.
الفحص: فحص الجدول الأكبر؛ ولكل صف، يجري حساب تجزئة مفتاح الربط والبحث عنه في جدول التجزئة.

تُقرأ كل من الجدولين مرة واحدة فقط، ما يعطي تعقيدًا تقريبيًا O(outer + inner). ولا تحتاج هذه الخوارزمية إلى فهارس أو إلى مدخلات مرتبة، ولذلك تتفوق في عمليات الربط التحليلية الكبيرة التي تعتمد على شروط المساواة.

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 صفوف، بينما الواقع 3 ملايين صف)، ولذلك اختار الحلقات المتداخلة. ولو كانت الإحصاءات دقيقة، لاختار ربطًا بالتجزئة.

إجابتكم في المقابلة: شغّلوا 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.
ربط الدمج، السير بالتزامن عبر مدخلات مرتبة؛ وهو مثالي عندما تكون البيانات مرتبة مسبقًا أو عند إجراء عمليات ربط النطاق.

يختار مخطط الاستعلام الخوارزمية بناءً على التكلفة والإحصاءات. وغالبًا ما يعني ظهور ربط متداخل مفاجئ مع عدد هائل من الحلقات أن تقدير عدد الصفوف خاطئ؛ لذا أصلحوا الإحصاءات.

الأسئلة الشائعة

هل درس «خوارزميات الربط: Nested Loop وHash وMerge» مجاني؟

نعم — نص درس «خوارزميات الربط: Nested Loop وHash وMerge» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة SQL Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة SQL Interview Prep 4 دروس في المجموع.

ماذا ستتعلم في «خوارزميات الربط: Nested Loop وHash وMerge»؟

كيفية تنفيذ كل نوع من الربط ومتى يكون الخيار المناسب تتمرن على SQL Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ SQL Interview Prep؟

لا تُشترط خبرة سابقة. SQL Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.

كم من الوقت يستغرق درس «خوارزميات الربط: Nested Loop وHash وMerge»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس SQL Interview Prep هذا؟

نعم. كل درس في SQL Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

قراءة خطة EXPLAIN
Seq Scan مقابل Index Scan مقابل Index-Only
خوارزميات الربط: Nested Loop وHash وMerge
اكتشاف الاستعلامات البطيئة وإصلاحها

← العودة إلى SQL Interview Prep