query planner guide

[صاحب نائب]

مقدمة

يعد مخطط الاستعلام مكونًا لنظام إدارة قاعدة البيانات (DBMS) المسؤول عن إنشاء خطة لتنفيذ استعلام قاعدة البيانات. تحدد خطة الاستعلام الخطوات التي ستتخذها DBMS لاسترداد البيانات المطلوبة بواسطة الاستعلام. الهدف من مخطط الاستعلام هو إنشاء خطة فعالة قدر الإمكان ، مما يعني أنه سيعيد البيانات إلى المستخدم في أسرع وقت ممكن.

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

كتبه الذكاء الاصطناعى ، حرره الإنسان

الجماهير المستهدفة

هذا الدليل مكتوب لـ:

• الذين اعتادوا العمل مع محركات الاستعلام
• من فضولي ، يريدون صنع أغراضهم الخاصة
• من يريد أن يتعلم مواد ديسيبل ولكن الرياضيات الكراهية

الأهداف:

• قادرة على فهم أساسي تخطيط الاستعلام
• قادر على كتابة مخطط الاستعلام الخاص بك

الهندسة المعمارية الأساسية لمحرك الاستعلام

 الرسم البياني TD
    المستخدم ((المستخدم))
    محلل [Query Parser]
    مخطط [مخطط الاستعلام]
    المنفذ [معالج الاستعلام]
    المستخدم -استعلام نص -> محلل
    محلل -AST -> مخطط
    مخطط -الخطة المادية -> المنفذ

تتكون الهندسة المعمارية الأساسية لمحرك الاستعلام من تلك المكونات:

• محلل الاستعلام: يستخدم لتحليل إدخال استعلام المستخدم ، عادة بتنسيق نص قابل للقراءة البشرية (مثل SQL)
• مخطط الاستعلام: يستخدم لإنشاء الخطة/الاستراتيجية لتنفيذ الاستعلام. عادةً ما يختار مخطط الاستعلام أفضل خطة بين العديد من الخطط التي تم إنشاؤها من استعلام واحد
• معالج الاستعلام: يستخدم لتنفيذ خطة الاستعلام ، والتي يتم إخراجها بواسطة مخطط الاستعلام

أنواع مخططي الاستعلام

عادة ، يتم تقسيم مخططو الاستعلام إلى نوعين:

• مخطط مجريات الأمور
• مخطط قائم على التكلفة

المخطط الإرشادي هو مخطط الاستعلام الذي استخدم القواعد المحددة مسبقًا لإنشاء خطة استعلام.

المخطط القائم على التكلفة هو مخطط الاستعلام الذي يستند إلى تكلفة توليد الاستعلام ، ويحاول العثور على الخطة المثلى بناءً على تكلفة استعلام المدخلات.

على الرغم من أن المخطط الإرشادي عادة ما يجد أفضل خطة من خلال تطبيق قواعد التحويل إذا عرفت أن الخطة المحولة أفضل ، فإن المخطط القائم على التكلفة يجد أفضل خطة من خلال تعداد الخطط المكافئة ومحاولة العثور على أفضل خطة بينها.

مخطط الاستعلام القائم على التكلفة

في مخطط الاستعلام القائم على التكاليف ، يتكون عادة من مراحل:

• خطة تعداد
• تحسين الاستعلام

في مرحلة تعداد الخطة ، سيعدد المخطط الخطط المكافئة المحتملة.

بعد ذلك ، في مرحلة تحسين الاستعلام ، سيبحث المخطط عن أفضل خطة من قائمة الخطط المذكورة. أفضل خطة هي الخطة التي لها أدنى تكلفة ، والتي يتم تعريف نموذج التكلفة (أو وظيفة التكلفة).

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

• البحث الشامل ، مثل البرمجة الديناميكية الحتمية. ستقوم الخوارزمية بالبحث عن أفضل خطة حتى ظروف إنهاء البحث
• البحث العشوائي ، مثل البحث عن الأشجار العشوائية. ستقوم الخوارزمية بالبحث عن أفضل خطة حتى ظروف إنهاء البحث

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

ملاحظات: عادة ما تكون شروط إنهاء البحث:

• استنفاد البحث (عندما لا توجد خطط للزيارة)
• عتبة التكلفة (عندما يتم العثور على خطة أن التكلفة أقل من عتبة التكلفة المحددة)
• الوقت (عندما تعمل مرحلة البحث لفترة طويلة)

مخطط الاستعلام البركاني

مخطط استعلام Volcano (أو مولد محسن Volcano) هو مخطط استعلام يعتمد على التكلفة

يستخدم Volcano Planner نهج البرمجة الديناميكية للعثور على أفضل خطة استعلام من قائمة الخطط المذكورة.

التفاصيل: https://ieeexplore.ieee.org/document/344061 (أنا كسول جدًا لشرح الورقة هنا)

إليكم تفسيرًا رائعًا: https://15721.courses.cs.cmu.edu/spring2017/slides/15-optimizer2.pdf#page=9

صياغة مخطط الاستعلام القائم على التكاليف

مخطط الاستعلام الخاص بنا ، هو مخطط استعلام يعتمد على التكاليف ، في أعقاب الفكرة الأساسية لمخطط الاستعلام البركاني ، سيكون مخططنا يتألف من مرحلتين رئيسيتين:

• مرحلة الاستكشاف/البحث
• مرحلة التنفيذ/التحسين

 الرسم البياني LR
    AST ((AST))
    logical_plan [خطة]
    explored_plans ["`
        الخطة رقم 1
        ...
        خطة #n
    `"]
    APPERANTITATION_PLAN ["Plan #X (أفضل خطة)"]
    AST -تحويل إلى خطة منطقية -> logical_plan
    logical_plan -مرحلة الاستكشاف -> explored_plans
    explored_plans -مرحلة التحسين -> تطبيق _Plan
    LinkStyle 1،2 اللون: البرتقال ، السكتة الدماغية: البرتقالي ، السكتة الدماغية: 5 بكسل

مسرد

خطة منطقية

الخطة المنطقية هي أن هيكل البيانات الذي يحتفظ بتجريد خطوة التحول المطلوبة لتنفيذ الاستعلام.

فيما يلي مثال على خطة منطقية:

 الرسم البياني TD
    1 ["Project tbl1.id ، tbl1.field1 ، tbl2.field1 ، tbl2.field2 ، tbl3.id ، tbl3.field2 ، tbl3.field2"] ؛
    2 ["انضم"] ؛
    3 ["مسح TBL1"] ؛
    4 ["انضم"] ؛
    5 ["مسح TBL2"] ؛
    6 ["مسح TBL3"] ؛
    1 -> 2 ؛
    2 -> 3 ؛
    2 -> 4 ؛
    4 -> 5 ؛
    4 -> 6 ؛

الخطة المادية

في حين أن الخطة المنطقية تحمل فقط التجريد ، فإن الخطة المادية هي بنية البيانات التي تحتفظ بتفاصيل التنفيذ. سيكون لكل خطة منطقية خطط مادية متعددة. على سبيل المثال ، قد يكون للانضمام المنطقي العديد من الخطط المادية مثل Hash Join و Merge Join و Broadcast Join ، إلخ.

مجموعة مكافئة

المجموعة المكافئة هي مجموعة من التعبيرات المكافئة (والتي لكل تعبير ، خطتها المنطقية مكافئة منطقيا)

على سبيل المثال

 الرسم البياني TD
    مجموعة فرعية#8
        expr#8 ["مسح TBL2 (Field1 ، Field2 ، id)"]
    نهاية
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#11
        expr#11 ["Join"]
    نهاية
    Expr#11 -> المجموعة رقم 7
    Expr#11 -> المجموعة رقم 10
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7 ["مسح TBL1 (ID ، Field1)"]
    نهاية
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#10
        expr#10 ["Join"]
    نهاية
    Expr#10 -> المجموعة رقم 8
    Expr#10 -> المجموعة رقم 9
    مجموعة فرعية#9
        expr#9 ["مسح TBL3 (ID ، Field2)"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#12 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    Expr#12 -> المجموعة رقم 11
    expr#6 -> المجموعة رقم 5

هنا يمكننا أن نرى Group#6 لها تعبيرين مكافئين ، كلاهما يمثل الاستعلام نفسه (أحدهما يقوم بالمسح الضوئي من الجدول ثم المشروع ، يقوم أحدهما بإسقاط الإسقاط لأسفل إلى عقدة المسح الضوئي).

قاعدة التحول

قاعدة التحول هي قاعدة التحول من خطة منطقية إلى خطة منطقية معادلة أخرى

على سبيل المثال ، الخطة:

 الرسم البياني TD
    1 ["Project tbl1.id ، tbl1.field1 ، tbl2.field1 ، tbl2.field2 ، tbl3.id ، tbl3.field2 ، tbl3.field2"] ؛
    2 ["انضم"] ؛
    3 ["مسح TBL1"] ؛
    4 ["انضم"] ؛
    5 ["مسح TBL2"] ؛
    6 ["مسح TBL3"] ؛
    1 -> 2 ؛
    2 -> 3 ؛
    2 -> 4 ؛
    4 -> 5 ؛
    4 -> 6 ؛

عند تطبيق تحول Pushdown الإسقاط ، يتم تحويله إلى:

 الرسم البياني TD
    1 ["Project *. *"] ؛
    2 ["انضم"] ؛
    3 ["مسح TBL1 (ID ، field1)"] ؛
    4 ["انضم"] ؛
    5 ["مسح TBL2 (Field1 ، Field2)"] ؛
    6 ["مسح TBL3 (ID ، Field2 ، Field2)"] ؛
    1 -> 2 ؛
    2 -> 3 ؛
    2 -> 4 ؛
    4 -> 5 ؛
    4 -> 6 ؛

يمكن أن تؤثر قاعدة التحول من خلال السمات/الخصائص المنطقية مثل مخطط الجدول ، وإحصائيات البيانات ، إلخ.

قاعدة التنفيذ

قاعدة التنفيذ هي القاعدة لإعادة الخطط المادية المعطاة للخطة المنطقية.

يمكن أن تؤثر قاعدة التنفيذ من خلال السمات/الخصائص المادية مثل تخطيط البيانات (مرتبة أم لا) ، إلخ.

مرحلة الاستكشاف

في مرحلة الاستكشاف ، سيطبق المخطط قواعد التحول ، مما يولد خططًا منطقية مكافئة

على سبيل المثال ، الخطة:

 الرسم البياني TD
    1326583549 ["Project tbl1.id ، tbl1.field1 ، tbl2.id ، tbl2.field1 ، tbl2.field2 ، tbl3.id ، tbl3.field2 ، tbl3.field2"] ؛
    -425111028 ["Join"] ؛
    -349388609 ["SCAR TBL1"] ؛
    1343755644 ["Join"] ؛
    -1043437086 ["مسح TBL2"] ؛
    -1402686787 ["مسح TBL3"] ؛
    1326583549 -> -425111028 ؛
    -425111028 -> -349388609 ؛
    -425111028 -> 1343755644 ؛
    1343755644 -> -1043437086 ؛
    1343755644 -> -1402686787 ؛

بعد تطبيق قواعد التحول ، مما أدى إلى الرسم البياني التالي:

 الرسم البياني TD
    مجموعة فرعية#8
        expr#8 ["مسح TBL2 (ID ، Field1 ، Field2)"]
    نهاية
    مجموعة فرعية#11
        expr#11 ["Join"]
        expr#14 ["Join"]
    نهاية
    Expr#11 -> المجموعة رقم 7
    Expr#11 -> المجموعة رقم 10
    Expr#14 -> المجموعة رقم 8
    Expr#14 -> المجموعة رقم 12
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
        expr#16 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    Expr#16 -> المجموعة رقم 2
    Expr#16 -> المجموعة رقم 13
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#13
        expr#15 ["Join"]
    نهاية
    expr#15 -> المجموعة رقم 1
    Expr#15 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7 ["مسح TBL1 (ID ، Field1)"]
    نهاية
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#10
        expr#10 ["Join"]
    نهاية
    Expr#10 -> المجموعة رقم 8
    Expr#10 -> المجموعة رقم 9
    مجموعة فرعية#9
        expr#9 ["مسح TBL3 (ID ، Field2)"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#12
        expr#13 ["Join"]
    نهاية
    Expr#13 -> المجموعة رقم 7
    Expr#13 -> المجموعة رقم 9
    مجموعة فرعية#6
        Expr#12 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    Expr#12 -> المجموعة رقم 11
    expr#6 -> المجموعة رقم 5

هنا يمكننا أن نرى أن قاعدة pushdown الإسقاط والانضمام يتم تطبيق قاعدة إعادة الترتيب.

مرحلة التحسين

تتمثل مرحلة التحسين ، في اجتياز الشجرة الموسعة في مرحلة الاستكشاف ، لإيجاد أفضل خطة لاستعلامنا.

هذا "في الواقع" هو تحسين البحث عن الأشجار ، بحيث يمكنك استخدام أي خوارزمية بحث الأشجار التي يمكنك تخيلها (ولكن عليك التأكد من أنها صحيحة).

فيما يلي مثال الخطة المادية المتولدة بعد مرحلة التحسين:

 الرسم البياني TD
    المجموعة رقم 6 ["
    المجموعة رقم 6
محدد: Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2
المشغل: ProjectOperator
التكلفة: التكلفة (وحدة المعالجة المركزية = 641400.00 ، MEM = 1020400012.00 ، الوقت = 1000000.00)
"]
المجموعة رقم 6 -> المجموعة رقم 11
المجموعة رقم 11 ["
المجموعة رقم 11
محدد: انضم
المشغل: Hashjoinoperator
التكلفة: التكلفة (وحدة المعالجة المركزية = 641400.00 ، MEM = 1020400012.00 ، الوقت = 1000000.00)
"]
المجموعة رقم 11 -> المجموعة رقم 7
المجموعة رقم 11 -> المجموعة رقم 10
المجموعة رقم 7 ["
المجموعة رقم 7
محدد: مسح TBL1 (ID ، Field1)
المشغل: NormalmCanoperator
التكلفة: التكلفة (وحدة المعالجة المركزية = 400.00 ، MEM = 400000.00 ، الوقت = 1000.00)
"]
المجموعة رقم 10 ["
المجموعة رقم 10
محدد: انضم
المشغل: mergejoinoperator
السمات: فرز
التكلفة: التكلفة (وحدة المعالجة المركزية = 640000.00 ، MEM = 20000012.00 ، الوقت = 1100000.00)
"]
المجموعة رقم 10 -> المجموعة رقم 8
المجموعة رقم 10 -> المجموعة رقم 9
المجموعة رقم 8 ["
المجموعة رقم 8
محدد: مسح TBL2 (ID ، Field1 ، Field2)
المشغل: NormalmCanoperator
السمات: فرز
التكلفة: التكلفة (وحدة المعالجة المركزية = 600000.00 ، MEM = 12.00 ، الوقت = 1000000.00)
"]
المجموعة رقم 9 ["
المجموعة رقم 9
محدد: مسح TBL3 (ID ، Field2)
المشغل: NormalmCanoperator
السمات: فرز
التكلفة: التكلفة (وحدة المعالجة المركزية = 40000.00 ، MEM = 20000000.00 ، الوقت = 100000.00)
"]

أظهرت الخطة التي تم إنشاؤها الخطة المنطقية المحددة والتكلفة المقدرة والمشغل الفيزيائي

تحسين/إنهاء البحث

سوف يقوم مخططنا بإجراء بحث استنفاد للعثور على أفضل خطة

الغوص في الرموز

نظرًا لأن رمز المخطط كبير ، فلن أكتب دليلًا خطوة بخطوة ، لكنني سأشرح كل قطعة من الكود بدلاً من ذلك

لغة الاستعلام

سنحدد هنا لغة الاستعلام التي استخدمت هذا البرنامج التعليمي تمامًا

 SELECT emp . id ,
       emp . code ,
       dept . dept_name ,
       emp_info . name ,
       emp_info . origin
FROM emp
         JOIN dept ON emp . id = dept . emp_id
         JOIN emp_info ON dept . emp_id = emp_info . id

لغة الاستعلام التي سننفذها هي لغة تشبه SQL. ومع ذلك ، من أجل البساطة ، سنقوم بتقييد وظائفها وبناء الجملة.

ظهرت اللغة في شكل

 SELECT tbl . field , [...]
FROM tbl JOIN [...]

سيتم دعمه فقط SELECT JOIN ، وأيضًا يجب أن يكون الحقل في بيان محدد مؤهلاً بالكامل (في شكل table.field ) ، لن يتم دعم جميع الوظائف الأخرى

AST

أولاً ، علينا أن نحدد AST للغة لدينا. AST (أو شجرة بناء الجملة المجردة) هي شجرة تستخدم لتمثيل التركيب النحوي للنص.

نظرًا لأن لغتنا بسيطة للغاية ، يمكننا فقط تحديد بنية AST في عدة رموز:

 sealed trait Identifier

case class TableID ( id : String ) extends Identifier

case class FieldID ( table : TableID , id : String ) extends Identifier

sealed trait Statement

case class Table ( table : TableID ) extends Statement

case class Join ( left : Statement , right : Statement , on : Seq [( FieldID , FieldID )]) extends Statement

case class Select ( fields : Seq [ FieldID ], from : Statement ) extends Statement

على سبيل المثال ، استعلام

 SELECT tbl1 . id ,
       tbl1 . field1 ,
       tbl2 . id ,
       tbl2 . field1 ,
       tbl2 . field2 ,
       tbl3 . id ,
       tbl3 . field2 ,
       tbl3 . field2
FROM tbl1
         JOIN tbl2 ON tbl1 . id = tbl2 . id
         JOIN tbl3 ON tbl2 . id = tbl3 . id

يمكن تمثيل

 Select (
  Seq (
    FieldID ( TableID ( " tbl1 " ), " id " ),
    FieldID ( TableID ( " tbl1 " ), " field1 " ),
    FieldID ( TableID ( " tbl2 " ), " id " ),
    FieldID ( TableID ( " tbl2 " ), " field1 " ),
    FieldID ( TableID ( " tbl2 " ), " field2 " ),
    FieldID ( TableID ( " tbl3 " ), " id " ),
    FieldID ( TableID ( " tbl3 " ), " field2 " ),
    FieldID ( TableID ( " tbl3 " ), " field2 " )
  ),
  Join (
    Table ( TableID ( " tbl1 " )),
    Join (
      Table ( TableID ( " tbl2 " )),
      Table ( TableID ( " tbl3 " )),
      Seq (
        FieldID ( TableID ( " tbl2 " ), " id " ) -> FieldID ( TableID ( " tbl3 " ), " id " )
      )
    ),
    Seq (
      FieldID ( TableID ( " tbl1 " ), " id " ) -> FieldID ( TableID ( " tbl2 " ), " id " )
    )
  )
)

محلل استعلام بسيط

بعد تحديد بنية AST ، سيتعين علينا كتابة محلل الاستعلام ، والذي يستخدم لتحويل استعلام النص إلى نموذج AST.

نظرًا لأن هذا الدليل يستخدم Scala للتنفيذ ، فسوف نختار المقياس المقرن الرئيسي لإنشاء محلل الاستعلام الخاص بنا.

فئة محلل الاستعلام:

 object QueryParser extends ParserWithCtx [ QueryExecutionContext , Statement ] with RegexParsers {

  override def parse ( in : String )( implicit ctx : QueryExecutionContext ) : Either [ Throwable , Statement ] = {
    Try (parseAll(statement, in) match {
      case Success (result, _) => Right (result)
      case NoSuccess (msg, _) => Left ( new Exception (msg))
    }) match {
      case util. Failure (ex) => Left (ex)
      case util. Success (value) => value
    }
  }

  private def select : Parser [ Select ] = ??? // we will implement it in later section

  private def statement : Parser [ Statement ] = select
}

ثم حدد بعض قواعد التحليل:

 // common
private def str : Parser [ String ] = """ [a-zA-Z0-9_]+ """ .r
private def fqdnStr : Parser [ String ] = """ [a-zA-Z0-9_]+.[a-zA-Z0-9_]+ """ .r

// identifier
private def tableId : Parser [ TableID ] = str ^^ (s => TableID (s))

private def fieldId : Parser [ FieldID ] = fqdnStr ^^ { s =>
  val identifiers = s.split( '.' )
  if (identifiers.length != 2 ) {
    throw new Exception ( " should never happen " )
  } else {
    val table = identifiers.head
    val field = identifiers( 1 )
    FieldID ( TableID (table), field)
  }
}

فيما يلي قاعدتان تستخدمان لتحليل المعرفات: TableID و FieldID .

عادةً ما يحتوي معرف الجدول (أو اسم الجدول) فقط على أحرف وأرقام ورسومات أسطورية ( _ ) ، لذلك سنستخدم إعادة صياغة بسيطة [a-zA-Z0-9_]+ لتحديد اسم الجدول.

من ناحية أخرى ، فإن معرف الحقل (بالنسبة إلى مؤهل الميدان) بلغتنا هو اسم المجال المؤهل بالكامل. عادةً ما يكون في شكل table.field ، وعادة ما يحتوي اسم الحقل أيضًا على أحرف وأرقام ورسومات سوية ، لذلك سنستخدم Regex [a-zA-Z0-9_]+.[a-zA-Z0-9_]+

بعد تحديد قواعد تحليل المعرفات ، يمكننا الآن تحديد قواعد لتحليل بيان الاستعلام:

 // statement
private def table : Parser [ Table ] = tableId ^^ (t => Table (t))
private def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "

قاعدة table هي قاعدة بسيطة ، فهي تنشئ عقدة Table باستخدام TableID المحلية من قاعدة tableId .

subQuery ، هي القاعدة لتحليل المساع الفرعي. في SQL ، يمكننا كتابة استعلام يبدو هكذا:

 SELECT a
FROM ( SELECT b FROM c) d

SELECT b FROM c هو السبع الفرعي في البيان أعلاه. هنا ، بلغة الاستعلام البسيطة لدينا ، سوف نوضح أن البيان هو مسابقة فرعية إذا تم إرفاقها بزوج من الأقواس ( () ). نظرًا لأن لغتنا تحتوي فقط على بيان محدد ، يمكننا كتابة قاعدة التحليل على النحو التالي:

 def subQuery : Parser [ Statement ] = " ( " ~> select <~ " ) "

الآن سنحدد قواعد التحليل لبيان محدد:

 private def fromSource : Parser [ Statement ] = table ||| subQuery

private def select : Parser [ Select ] =
  " SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep(
    " JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)
  ) ^^ {
    case _ ~ fields ~ _ ~ src ~ joins =>
      val p = if (joins.nonEmpty) {
        def chain ( left : Statement , right : Seq [( Statement , Seq [( FieldID , FieldID )])]) : Join = {
          if (right.isEmpty) {
            throw new Exception ( " should never happen " )
          } else if (right.length == 1 ) {
            val next = right.head
            Join (left, next._1, next._2)
          } else {
            val next = right.head
            Join (left, chain(next._1, right.tail), next._2)
          }
        }

        val temp = joins.map { join =>
          val statement = join._1._1._2
          val joinOn = join._2.map(on => on._1._1 -> on._2)
          statement -> joinOn
        }
        chain(src, temp)
      } else {
        src
      }
      Select (fields, p)
  }

في SQL ، يمكننا استخدام المساع الفرعي كمصدر للانضمام. على سبيل المثال:

 SELECT * . *
FROM tbl1
    JOIN ( SELECT * . * FROM tbl2)
    JOIN tbl3

لذلك سيقوم المحللون أيضًا بتنفيذ قواعد لتحليل المساع الفرعي في جزء من البيان ، ولهذا السبب لدينا قاعدة تحليل:

 " SELECT " ~ rep1sep(fieldId, " , " ) ~ " FROM " ~ fromSource ~ rep( " JOIN " ~ fromSource ~ " ON " ~ rep1(fieldId ~ " = " ~ fieldId)

انظر queryparser.scala للتنفيذ الكامل

اختبار محلل الاستعلام لدينا

انظر QueryParserspec.Scala

خطة منطقية

بعد إنشاء AST من استعلام النص ، يمكننا تحويله مباشرة إلى الخطة المنطقية

أولاً ، دعنا نحدد الواجهة لخطتنا المنطقية:

 sealed trait LogicalPlan {
  def children () : Seq [ LogicalPlan ]
}

children هي قائمة الخطة المنطقية للأطفال. على سبيل المثال:

 الرسم البياني TD
    1326583549 ["Project tbl1.id ، tbl1.field1 ، tbl2.id ، tbl2.field1 ، tbl2.field2 ، tbl3.id ، tbl3.field2 ، tbl3.field2"] ؛
    -425111028 ["Join"] ؛
    -349388609 ["SCAR TBL1"] ؛
    1343755644 ["Join"] ؛
    -1043437086 ["مسح TBL2"] ؛
    -1402686787 ["مسح TBL3"] ؛
    1326583549 -> -425111028 ؛
    -425111028 -> -349388609 ؛
    -425111028 -> 1343755644 ؛
    1343755644 -> -1043437086 ؛
    1343755644 -> -1402686787 ؛

العقد الفرعية لعقدة PROJECT هي أول عقدة JOIN . تحتوي عقدة JOIN الأولى على طفلان ، وهما العقدة الثانية JOIN SCAN tbl1 . قريباً، ...

نظرًا لأن لغة الاستعلام الخاصة بنا بسيطة ، نحتاج فقط إلى 3 أنواع من العقدة المنطقية:

• المشروع: تمثل مشغل الإسقاط فيما يتعلق بالجبر
• الانضمام: تمثل الصلة المنطقية
• المسح الضوئي: تمثل مسح الجدول

 case class Scan ( table : ql. TableID , projection : Seq [ String ]) extends LogicalPlan {
  override def children () : Seq [ LogicalPlan ] = Seq .empty
}

case class Project ( fields : Seq [ql. FieldID ], child : LogicalPlan ) extends LogicalPlan {
  override def children () : Seq [ LogicalPlan ] = Seq (child)
}

case class Join ( left : LogicalPlan , right : LogicalPlan , on : Seq [(ql. FieldID , ql. FieldID )]) extends LogicalPlan {
  override def children () : Seq [ LogicalPlan ] = Seq (left, right)
}

ثم يمكننا كتابة الوظيفة لتحويل AST إلى خطة منطقية:

 def toPlan ( node : ql. Statement ) : LogicalPlan = {
  node match {
    case ql. Table (table) => Scan (table, Seq .empty)
    case ql. Join (left, right, on) => Join (toPlan(left), toPlan(right), on)
    case ql. Select (fields, from) => Project (fields, toPlan(from))
  }
}

انظر logicalplan.scala للتنفيذ الكامل

المجموعات المكافئة

مجموعة

يمكننا تحديد فصول المجموعة على النحو التالي:

 case class Group (
                  id : Long ,
                  equivalents : mutable. HashSet [ GroupExpression ]
                ) {
  val explorationMark : ExplorationMark = new ExplorationMark
  var implementation : Option [ GroupImplementation ] = None
}

case class GroupExpression (
                            id : Long ,
                            plan : LogicalPlan ,
                            children : mutable. MutableList [ Group ]
                          ) {
  val explorationMark : ExplorationMark = new ExplorationMark
  val appliedTransformations : mutable. HashSet [ TransformationRule ] = mutable. HashSet ()
}

Group هي مجموعة من الخطط التي تعادل منطقيا.

يمثل كل GroupExpression عقدة خطة منطقية. نظرًا لأننا حددنا أن عقدة خطة منطقية ستحتوي على قائمة بالعقد الفرعية (في القسم السابق) ، ويمثل GroupExpression عقدة خطة منطقية ، وتمثل Group مجموعة من الخطط المكافئة ، وبالتالي فإن أطفال GroupExpression هو قائمة Group

على سبيل المثال

 الرسم البياني TD
    مجموعة فرعية#8
        expr#8
    نهاية
    مجموعة فرعية#2
        expr#2
    نهاية
    مجموعة فرعية#11
        Expr#11
    نهاية
    Expr#11 -> المجموعة رقم 7
    Expr#11 -> المجموعة رقم 10
    مجموعة فرعية#5
        expr#5
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7
    نهاية
    مجموعة فرعية#1
        expr#1
    نهاية
    مجموعة فرعية#10
        expr#10
    نهاية
    Expr#10 -> المجموعة رقم 8
    Expr#10 -> المجموعة رقم 9
    مجموعة فرعية#9
        expr#9
    نهاية
    مجموعة فرعية#3
        expr#3
    نهاية
    مجموعة فرعية#6
        expr#12
        expr#6
    نهاية
    Expr#12 -> المجموعة رقم 11
    expr#6 -> المجموعة رقم 5

كما نرى هنا ، لدى Group#6 تعبيرات مكافئة: Expr#12 و Expr#6 ، وأطفال Expr#12 هو Group#11

ملاحظات: سنقوم بتنفيذ تحويل متعدد الجولة في مرحلة الاستكشاف ، لذلك لكل Group و GroupExpression ، لدينا إشارة ExplorationMark إلى حالة الاستكشاف.

 class ExplorationMark {
  private var bits : Long = 0

  def get : Long = bits

  def isExplored ( round : Int ) : Boolean = BitUtils .getBit(bits, round)

  def markExplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = true )

  def markUnexplored ( round : Int ) : Unit = bits = BitUtils .setBit(bits, round, on = false )
}

ExplorationMark هو مجرد فئة غلاف bitset ، وسيحتفل بيتي إلى 1 إذا تم استكشاف الجولة i-th ، مارك على أنها 0 خلاف ذلك.

يمكن أيضًا استخدام ExplorationMark لتصور التحول الدقيق ، راجع التصور لمزيد من التفاصيل

مذكرة

المذكرة هي مجموعة من المساعدين للمساعدة في بناء المجموعات المكافئة. تتكون المذكرة من العديد من hashmap لتخريب التعبير الجماعي والجماعي ، كما توفر طرقًا لتسجيل مجموعة جديدة أو تعبير جماعي جديد.

 class Memo (
            groupIdGenerator : Generator [ Long ] = new LongGenerator ,
            groupExpressionIdGenerator : Generator [ Long ] = new LongGenerator
          ) {
  val groups : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]()
  val parents : mutable. HashMap [ Long , Group ] = mutable. HashMap [ Long , Group ]() // lookup group from group expression ID
  val groupExpressions : mutable. HashMap [ LogicalPlan , GroupExpression ] = mutable. HashMap [ LogicalPlan , GroupExpression ]()

  def getOrCreateGroupExpression ( plan : LogicalPlan ) : GroupExpression = {
    val children = plan.children()
    val childGroups = children.map(child => getOrCreateGroup(child))
    groupExpressions.get(plan) match {
      case Some (found) => found
      case None =>
        val id = groupExpressionIdGenerator.generate()
        val children = mutable. MutableList () ++ childGroups
        val expression = GroupExpression (
          id = id,
          plan = plan,
          children = children
        )
        groupExpressions += plan -> expression
        expression
    }
  }

  def getOrCreateGroup ( plan : LogicalPlan ) : Group = {
    val exprGroup = getOrCreateGroupExpression(plan)
    val group = parents.get(exprGroup.id) match {
      case Some (group) =>
        group.equivalents += exprGroup
        group
      case None =>
        val id = groupIdGenerator.generate()
        val equivalents = mutable. HashSet () + exprGroup
        val group = Group (
          id = id,
          equivalents = equivalents
        )
        groups.put(id, group)
        group
    }
    parents += exprGroup.id -> group
    group
  }
}

انظر Memo.Scala للتنفيذ الكامل

التهيئة

الخطوة الأولى داخل المخطط ، هي التهيئة

 الرسم البياني LR
    الاستعلام ((استعلام))
    AST ((AST))
    root_plan ((Rootplan))
    ROOT_GROUP ((ROOTGROUP))
    استعلام -"QueryParser.parse (استعلام)" -> AST
    AST -"logicalplan.toplan (AST)" -> ROOT_PLAN
    ROOT_PLAN -"memo.getorcreategroup (Rootplan)" -> ROOT_GROUP

أولاً ، سيتم تحليل الاستعلام في AST. ثم تحويلها إلى خطة منطقية ، تسمى root plan ، ثم تهيئة المجموعة من root plan ، تسمى root group .

 def initialize ( query : Statement )( implicit ctx : VolcanoPlannerContext ) : Unit = {
  ctx.query = query
  ctx.rootPlan = LogicalPlan .toPlan(ctx.query)
  ctx.rootGroup = ctx.memo.getOrCreateGroup(ctx.rootPlan)
  // assuming this is first the exploration round,
  // by marking the initialRound(0) as explored,
  // it will be easier to visualize the different between rounds (added nodes, add connections)
  ctx.memo.groups.values.foreach(_.explorationMark.markExplored(initialRound))
  ctx.memo.groupExpressions.values.foreach(_.explorationMark.markExplored(initialRound))
}

انظر Volcanoplanner.scala لمزيد من التفاصيل

على سبيل المثال ، الاستعلام:

 SELECT tbl1 . id ,
       tbl1 . field1 ,
       tbl2 . id ,
       tbl2 . field1 ,
       tbl2 . field2 ,
       tbl3 . id ,
       tbl3 . field2 ,
       tbl3 . field2
FROM tbl1
         JOIN tbl2 ON tbl1 . id = tbl2 . id
         JOIN tbl3 ON tbl2 . id = tbl3 . id

بعد التهيئة ، ستبدو المجموعات هكذا:

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    expr#6 -> المجموعة رقم 5

هنا يمكنك أن ترى ذلك ، كل مجموعة لديها تعبير واحد مكافئ بالضبط

مرحلة الاستكشاف

بعد التهيئة ، أصبحت الآن مرحلة الاستكشاف ، والتي ستستكشف جميع الخطط المكافئة الممكنة.

طريقة الاستكشاف بسيطة للغاية:

• لكل مجموعة ، قم بتطبيق قواعد التحول للعثور على جميع تعبير مجموعة مكافئة وإضافة إلى مجموعة مكافئة حتى لا نتمكن من العثور على أي خطة مكافئة جديدة
• لكل تعبير جماعي ، استكشف جميع مجموعات الأطفال

قاعدة التحول

قبل الغوص في رمز الاستكشاف ، دعنا نتحدث عن قاعدة التحول أولاً.

قاعدة التحول هي قاعدة تستخدم لتحويل خطة منطقية إلى خطة منطقية مكافئة أخرى إذا كانت مطابقة شرط القاعدة.

فيما يلي واجهة قاعدة التحول:

 trait TransformationRule {
  def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean

  def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression
}

نظرًا لأن الخطة المنطقية عبارة عن بنية بيانات تشبه الأشجار ، وبالتالي فإن match قواعد التحول هو مطابقة النمط على الشجرة.

على سبيل المثال ، إليك match التي يتم استخدامها لمطابقة عقدة المشروع بينما تحقق أيضًا مما إذا كانت أحفادها تحتوي على انضمام ومسح ضوئي فقط:

 override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
  val plan = expression.plan
  plan match {
    case Project (_, child) => check(child)
    case _ => false
  }
}

// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
  node match {
    case Scan (_, _) => true
    case Join (left, right, _) => check(left) && check(right)
    case _ => false
  }
}

هذه الخطة "متطابقة":

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["Scan"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["Scan"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["Scan"]
    نهاية
    مجموعة فرعية#6
        expr#6 ["Project"]
    نهاية
    expr#6 -> المجموعة رقم 5

في حين أن هذه الخطة ليست:

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["Scan"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 3
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Scan"]
    نهاية
    مجموعة فرعية#7
        expr#7 ["المشروع"]
    نهاية
    Expr#7 -> المجموعة رقم 6
    مجموعة فرعية#1
        expr#1 ["Scan"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["Project"]
    نهاية
    Expr#3 -> المجموعة رقم 2
    مجموعة فرعية#6
        expr#6 ["Join"]
    نهاية
    expr#6 -> المجموعة رقم 1
    expr#6 -> المجموعة رقم 5

خطة تعداد

كما قلنا من قبل ، طريقة الاستكشاف هي:

• لكل مجموعة ، قم بتطبيق قواعد التحول للعثور على جميع تعبير مجموعة مكافئة وإضافة إلى مجموعة مكافئة حتى لا نتمكن من العثور على أي خطة مكافئة جديدة
• لكل تعبير جماعي ، استكشف جميع مجموعات الأطفال

وهنا رمز الاستكشاف (بسيط للغاية ، هاه):

 private def exploreGroup (
                          group : Group ,
                          rules : Seq [ TransformationRule ],
                          round : Int
                        )( implicit ctx : VolcanoPlannerContext ) : Unit = {
  while ( ! group.explorationMark.isExplored(round)) {
    group.explorationMark.markExplored(round)
    // explore all child groups
    group.equivalents.foreach { equivalent =>
      if ( ! equivalent.explorationMark.isExplored(round)) {
        equivalent.explorationMark.markExplored(round)
        equivalent.children.foreach { child =>
          exploreGroup(child, rules, round)
          if (equivalent.explorationMark.isExplored(round) && child.explorationMark.isExplored(round)) {
            equivalent.explorationMark.markExplored(round)
          } else {
            equivalent.explorationMark.markUnexplored(round)
          }
        }
      }
      // fire transformation rules to explore all the possible transformations
      rules.foreach { rule =>
        if ( ! equivalent.appliedTransformations.contains(rule) && rule.`match`(equivalent)) {
          val transformed = rule.transform(equivalent)
          if ( ! group.equivalents.contains(transformed)) {
            group.equivalents += transformed
            transformed.explorationMark.markUnexplored(round)
            group.explorationMark.markUnexplored(round)
          }
        }
      }
      if (group.explorationMark.isExplored(round) && equivalent.explorationMark.isExplored(round)) {
        group.explorationMark.markExplored(round)
      } else {
        group.explorationMark.markUnexplored(round)
      }
    }
  }
}

انظر Volcanoplanner.scala لمزيد من التفاصيل

تنفيذ بعض قواعد التحول

حان الوقت الآن لتنفيذ بعض قواعد التحول

الإسقاط pushdown

Pushdence Pushdown هو قاعدة تحويل بسيطة ، وتستخدم لدفع الإسقاط لأسفل إلى طبقة التخزين.

على سبيل المثال ، الاستعلام

 SELECT field1, field2
from tbl

لديه الخطة

 الرسم البياني LR
    Project [Project Field1 ، Field2]
    مسح [مسح TBL]
    المشروع -> المسح

من خلال هذه الخطة ، عند التنفيذ ، سيتم إحضار صفوف من طبقة التخزين (تحت المسح) بالكامل ، ثم سيتم إسقاط الحقول غير الضرورية (المشروع). لا يزال يتعين على البيانات غير الضرورية الانتقال من عقدة المسح إلى عقدة المشروع ، لذلك هناك بعض الجهود الضائعة هنا.

يمكننا أن نجعلها أفضل بمجرد إخبار طبقة التخزين فقط التي تجلب الحقول اللازمة. الآن سيتم تحويل الخطة إلى:

 الرسم البياني LR
    Project [Project Field1 ، Field2]
    Scan ["مسح TBL (Field1 ، Field2)"]
    المشروع -> المسح

دعنا نذهب إلى الكود:

 override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
  val plan = expression.plan
  plan match {
    case Project (_, child) => check(child)
    case _ => false
  }
}

// check if the tree only contains SCAN and JOIN nodes
private def check ( node : LogicalPlan ) : Boolean = {
  node match {
    case Scan (_, _) => true
    case Join (left, right, _) => check(left) && check(right)
    case _ => false
  }
}

سوف تتطابق قاعدة Pushdown الخاصة بنا هنا ، عندما تكون عقدة المشروع ، وجميع أحفادها يتم فحصها والانضمام إلى العقدة فقط.

ملاحظات: في الواقع ، تكون مطابقة الإسقاط الحقيقية أكثر تعقيدًا ، ولكن من أجل البساطة ، فإن قاعدة المطابقة هنا هي مجرد عقدة المشروع مع المسح والانضمام إلى أحفاد

وهنا رمز التحويل:

 override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
  val plan = expression.plan. asInstanceOf [ Project ]
  val pushDownProjection = mutable. ListBuffer [ FieldID ]()
  extractProjections(plan, pushDownProjection)
  val newPlan = Project (plan.fields, pushDown(pushDownProjection.distinct, plan.child))
  ctx.memo.getOrCreateGroupExpression(newPlan)
}

private def extractProjections ( node : LogicalPlan , buffer : mutable. ListBuffer [ FieldID ]) : Unit = {
  node match {
    case Scan (_, _) => () : Unit
    case Project (fields, parent) =>
      buffer ++= fields
      extractProjections(parent, buffer)
    case Join (left, right, on) =>
      buffer ++= on.map(_._1) ++ on.map(_._2)
      extractProjections(left, buffer)
      extractProjections(right, buffer)
  }
}

private def pushDown ( pushDownProjection : Seq [ FieldID ], node : LogicalPlan ) : LogicalPlan = {
  node match {
    case Scan (table, tableProjection) =>
      val filteredPushDownProjection = pushDownProjection.filter(_.table == table).map(_.id)
      val updatedProjection =
        if (filteredPushDownProjection.contains( " * " ) || filteredPushDownProjection.contains( " *.* " )) {
          Seq .empty
        } else {
          (tableProjection ++ filteredPushDownProjection).distinct
        }
      Scan (table, updatedProjection)
    case Join (left, right, on) => Join (pushDown(pushDownProjection, left), pushDown(pushDownProjection, right), on)
    case _ => throw new Exception ( " should never happen " )
  }
}

سيجد رمز التحويل أولاً جميع التوقعات من عقدة مشروع الجذر ، ثم دفعها لأسفل إلى جميع عقد المسح الضوئي تحتها.

تصور قاعدتنا ، على سبيل المثال ، الخطة

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    expr#6 -> المجموعة رقم 5

بعد تطبيق تحويل Pushdown Transformation ، سيؤدي إلى خطة مكافئة جديدة مع التوقعات يتم دفعها إلى عمليات المسح (الخطة الجديدة هي الشجرة ذات العقد الحدودية البرتقالية).

 الرسم البياني TD
    مجموعة فرعية#8
        expr#8 ["مسح TBL2 (ID ، Field1 ، Field2)"]
    نهاية
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#11
        expr#11 ["Join"]
    نهاية
    Expr#11 -> المجموعة رقم 7
    Expr#11 -> المجموعة رقم 10
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7 ["مسح TBL1 (ID ، Field1)"]
    نهاية
    مجموعة فرعية#10
        expr#10 ["Join"]
    نهاية
    Expr#10 -> المجموعة رقم 8
    Expr#10 -> المجموعة رقم 9
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#9
        expr#9 ["مسح TBL3 (ID ، Field2)"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#12 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    Expr#12 -> المجموعة رقم 11
    expr#6 -> المجموعة رقم 5
    نمط expr#12 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: البرتقالي
    نمط expr#8 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#10 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#9 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#11 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: البرتقالي
    Linkstyle 0 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    LinkStyle 1 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 6 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 8 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange

انظر DespectionPushdown.scala للتنفيذ الكامل

انضم إلى إعادة ترتيب

يعد Join Reorder أيضًا أحد أكثر التحول المعترف به في عالم مخطط الاستعلام. مخططنا ، سوف ينفذ أيضًا قاعدة تحويل إعادة ترتيب.

نظرًا لأن الانضمام إلى Reorder in Real World ليس قطعة سهلة للتنفيذ. لذلك سنقوم بتنفيذ نسخة بسيطة ومطفأة من قاعدة REDRORD RELD هنا.

أولاً ، match القاعدة:

 // check if the tree only contains SCAN and JOIN nodes, and also extract all SCAN nodes and JOIN conditions
private def checkAndExtract (
                             node : LogicalPlan ,
                             buffer : mutable. ListBuffer [ Scan ],
                             joinCondBuffer : mutable. ListBuffer [(ql. FieldID , ql. FieldID )]
                           ) : Boolean = {
  node match {
    case node @ Scan (_, _) =>
      buffer += node
      true
    case Join (left, right, on) =>
      joinCondBuffer ++= on
      checkAndExtract(left, buffer, joinCondBuffer) && checkAndExtract(right, buffer, joinCondBuffer)
    case _ => false
  }
}

private def buildInterchangeableJoinCond ( conditions : Seq [(ql. FieldID , ql. FieldID )]) : Seq [ Seq [ql. FieldID ]] = {
  val buffer = mutable. ListBuffer [mutable. Set [ql. FieldID ]]()
  conditions.foreach { cond =>
    val set = buffer.find { set =>
      set.contains(cond._1) || set.contains(cond._2)
    } match {
      case Some (set) => set
      case None =>
        val set = mutable. Set [ql. FieldID ]()
        buffer += set
        set
    }
    set += cond._1
    set += cond._2
  }
  buffer.map(_.toSeq)
}

override def `match` ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Boolean = {
  val plan = expression.plan
  plan match {
    case node @ Join (_, _, _) =>
      val buffer = mutable. ListBuffer [ Scan ]()
      val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
      if (checkAndExtract(node, buffer, joinCondBuffer)) {
        // only match if the join is 3 tables join
        if (buffer.size == 3 ) {
          var check = true
          val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
          interChangeableCond.foreach { c =>
            check &= c.size == 3
          }
          check
        } else {
          false
        }
      } else {
        false
      }
    case _ => false
  }
}

سيتم مطابقة قاعدةنا فقط ، إذا قمنا بتطابق الانضمام الثالث (يجب أن يكون عدد الجدول المعني 3 ، ويجب أن يكون شرط الانضمام ثلاثي الاتجاه ، مثل tbl1.field1 = tbl2.field2 = tbl3.field3 )

على سبيل المثال،

tbl1
    JOIN tbl2 ON tbl1 . field1 = tbl2 . field2
    JOIN tbl3 ON tbl1 . field1 = tbl3 . field3

سيتم "مطابقة" بيان الانضمام هنا منذ انضمامه إلى 3 اتجاهات (إنه الانضمام بين tbl1 و tbl2 و tbl3 والشرط هو tbl1.field1 = tbl2.field2 = tbl3.field3 )

بعد ذلك ، هو رمز التحويل:

 override def transform ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : GroupExpression = {
  val plan = expression.plan. asInstanceOf [ Join ]
  val buffer = mutable. ListBuffer [ Scan ]()
  val joinCondBuffer = mutable. ListBuffer [(ql. FieldID , ql. FieldID )]()
  checkAndExtract(plan, buffer, joinCondBuffer)
  val interChangeableCond = buildInterchangeableJoinCond(joinCondBuffer)
  //
  val scans = buffer.toList
  implicit val ord : Ordering [ Scan ] = new Ordering [ Scan ] {
    override def compare ( x : Scan , y : Scan ) : Int = {
      val xStats = ctx.statsProvider.tableStats(x.table.id)
      val yStats = ctx.statsProvider.tableStats(y.table.id)
      xStats.estimatedTableSize.compareTo(yStats.estimatedTableSize)
    }
  }

  def getJoinCond ( left : Scan , right : Scan ) : Seq [(ql. FieldID , ql. FieldID )] = {
    val leftFields = interChangeableCond.flatMap { c =>
      c.filter(p => p.table == left.table)
    }
    val rightFields = interChangeableCond.flatMap { c =>
      c.filter(p => p.table == right.table)
    }
    if (leftFields.length != rightFields.length) {
      throw new Exception ( s " leftFields.length( ${leftFields.length} ) != rightFields.length( ${rightFields.length} ) " )
    } else {
      leftFields zip rightFields
    }
  }

  val sorted = scans.sorted
  val newPlan = Join (
    sorted( 0 ),
    Join (
      sorted( 1 ),
      sorted( 2 ),
      getJoinCond(sorted( 1 ), sorted( 2 ))
    ),
    getJoinCond(sorted( 0 ), sorted( 1 ))
  )
  ctx.memo.getOrCreateGroupExpression(newPlan)
}

سوف يعيد رمز التحويل هنا ترتيب الجداول حسب حجمه المقدر.

على سبيل المثال ، إذا كان لدينا 3 جداول A ، B ، C مع حجم تقديري قدره 300B ، 100B ، 200B وبيان Join A JOIN B JOIN C ، فسيتم تحويله إلى B JOIN C JOIN A

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

تصور قاعدتنا ، على سبيل المثال ، الخطة

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    expr#6 -> المجموعة رقم 5

بعد الانضمام إلى إعادة ترتيب تحول ، مما أدى

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
        expr#8 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    Expr#8 -> المجموعة رقم 2
    Expr#8 -> المجموعة رقم 7
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7 ["Join"]
    نهاية
    Expr#7 -> المجموعة رقم 1
    Expr#7 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    expr#6 -> المجموعة رقم 5
    نمط expr#8 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: البرتقالي
    Linkstyle 2 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 6 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 3 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange

يمكننا أن نرى أن tbl2 JOIN tbl1 JOIN tbl3 من tbl1 JOIN tbl2 JOIN tbl3 تم إنشاؤه بواسطة التحول (يتم الإشارة إلى العقد والحواف المضافة حديثًا بواسطة خطوط برتقالية)

انظر X3TableJoInreOrderBysize.scala للتنفيذ الكامل

جمع جميع التحولات معًا

الآن يمكننا وضع قواعد التحول لدينا في مكان واحد

 private val transformationRules : Seq [ Seq [ TransformationRule ]] = Seq (
  Seq ( new ProjectionPushDown ),
  Seq ( new X3TableJoinReorderBySize )
)

وركضهم لاستكشاف المجموعات المكافئة

 for (r <- transformationRules.indices) {
  exploreGroup(ctx.rootGroup, transformationRules(r), r + 1 )
}

على سبيل المثال ، الخطة

 الرسم البياني TD
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#6
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    expr#6 -> المجموعة رقم 5

بعد استكشافها ، سوف يؤدي إلى هذا الرسم البياني

 الرسم البياني TD
    مجموعة فرعية#8
        expr#8 ["مسح TBL2 (ID ، Field1 ، Field2)"]
    نهاية
    مجموعة فرعية#11
        expr#11 ["Join"]
        expr#14 ["Join"]
    نهاية
    Expr#11 -> المجموعة رقم 7
    Expr#11 -> المجموعة رقم 10
    Expr#14 -> المجموعة رقم 8
    Expr#14 -> المجموعة رقم 12
    مجموعة فرعية#2
        expr#2 ["مسح TBL2"]
    نهاية
    مجموعة فرعية#5
        expr#5 ["Join"]
        expr#16 ["Join"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    Expr#16 -> المجموعة رقم 2
    Expr#16 -> المجموعة رقم 13
    مجموعة فرعية#4
        expr#4 ["Join"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة فرعية#13
        expr#15 ["Join"]
    نهاية
    expr#15 -> المجموعة رقم 1
    Expr#15 -> المجموعة رقم 3
    مجموعة فرعية#7
        expr#7 ["مسح TBL1 (ID ، Field1)"]
    نهاية
    مجموعة فرعية#1
        expr#1 ["مسح TBL1"]
    نهاية
    مجموعة فرعية#10
        expr#10 ["Join"]
    نهاية
    Expr#10 -> المجموعة رقم 8
    Expr#10 -> المجموعة رقم 9
    مجموعة فرعية#9
        expr#9 ["مسح TBL3 (ID ، Field2)"]
    نهاية
    مجموعة فرعية#3
        expr#3 ["مسح TBL3"]
    نهاية
    مجموعة فرعية#12
        expr#13 ["Join"]
    نهاية
    Expr#13 -> المجموعة رقم 7
    Expr#13 -> المجموعة رقم 9
    مجموعة فرعية#6
        Expr#12 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
        Expr#6 ["Project TBL1.ID ، TBL1.Field1 ، TBL2.ID ، TBL2.Field1 ، TBL2.Field2 ، TBL3.ID ، TBL3.Field2 ، TBL3.Field2"]
    نهاية
    Expr#12 -> المجموعة رقم 11
    expr#6 -> المجموعة رقم 5
    نمط expr#12 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: البرتقالي
    نمط expr#8 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#10 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#13 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#14 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#11 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#9 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#15 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    نمط expr#7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: البرتقالي
    نمط expr#16 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: برتقالي
    Linkstyle 0 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 15 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 12 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    LinkStyle 1 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 16 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 13 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 2 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 6 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 3 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 10 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 7 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 14 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange
    Linkstyle 11 عرض السكتة الدماغية: 4 بكسل ، السكتة الدماغية: Orange

انظر Volcanoplanner.scala لمزيد من التفاصيل

مرحلة التحسين

بعد مرحلة الاستكشاف ، لدينا الآن شجرة موسعة بالكامل تحتوي على جميع الخطط الممكنة ، والآن هي مرحلة التحسين.

في هذه المرحلة ، سنجد أفضل خطة لمجموعة الجذر لدينا. تم وصف عملية التحسين على النحو التالي:

• لكل مجموعة ، سنجد أفضل تنفيذ من خلال اختيار المجموعة التي تعبر بأقل تكلفة
• لكل تعبير جماعي ، سنقوم أولاً بتعداد التطبيقات المادية من الخطة المنطقية. ثم لكل تطبيق مادي ، سنحسب تكلفته باستخدام تكاليف مجموعة الأطفال.

هنا مثال

 الرسم البياني TD
    مجموعة Subgraph#2 ["المجموعة رقم 2 (التكلفة = 1)"]
        expr#2 ["Expr#2 (Cost = 1)"]
    نهاية
    مجموعة Subgraph#5 ["المجموعة رقم 5 (التكلفة = 3)"]
        expr#5 ["expr#5 (COST = MAX (3،2) = 3"]
    نهاية
    Expr#5 -> المجموعة رقم 1
    Expr#5 -> المجموعة رقم 4
    مجموعة Subgraph#4 ["المجموعة رقم 4 (التكلفة = 2)"]
        expr#4 ["Expr#4 (COST = MAX (1،2) = 2)"]
        expr#7 ["Expr#7 (COST = 1+2 = 3)"]
    نهاية
    Expr#4 -> المجموعة رقم 2
    Expr#4 -> المجموعة رقم 3
    مجموعة Subgraph#1 ["المجموعة رقم 1 (التكلفة = 3)"]
        expr#1 ["Expr#1 (Cost = 3)"]
    نهاية
    مجموعة Subgraph#3 ["المجموعة رقم 3 (التكلفة = 2)"]
        expr#3 ["Expr#3 (Cost = 2)"]
    نهاية
    مجموعة Subgraph#6 ["المجموعة رقم 6 (التكلفة = 4.5)"]
        expr#6 ["Expr#6 (COST = 3*1.5 = 4.5)"]
    نهاية
    expr#6 -> المجموعة رقم 5
    مجموعة Subgraph#8 ["المجموعة رقم 8 (التكلفة = 1)"]
        expr#8 ["Expr#8 (Cost = 1)"]
    نهاية
    مجموعة Subgraph#9 ["المجموعة رقم 9 (التكلفة = 2)"]
        expr#9 ["Expr#9 (Cost = 2)"]
    نهاية
    Expr#7 -> المجموعة رقم 8
    Expr#7 -> المجموعة رقم 9

على سبيل المثال ، يتم حساب التكلفة Expr#4 من خلال تكاليف المجموعة الفرعية ( Group#2 والمجموعة Group#3 ) باستخدام وظيفة max . مثال آخر ، هو Group#4 ، يتم حساب تكلفتها عن طريق حساب قيمة MIN بين تكاليف تعبيراتها المكافئة.

الخطة المادية

نظرًا لأن هدف مرحلة التحسين هو إنتاج أفضل خطة مادية بالنظر إلى تعبيرات المجموعة التي تم استكشافها. يمكننا تحديد الخطة المادية على النحو التالي:

 sealed trait PhysicalPlan {
  def operator () : Operator

  def children () : Seq [ PhysicalPlan ]

  def cost () : Cost

  def estimations () : Estimations

  def traits () : Set [ String ]
}

operator هو المشغل الفيزيائي ، الذي يستخدم لتنفيذ الخطة ، سنغطيها في القسم اللاحق. عندها children هي قائمة عقد خطة الأطفال ، وهم معتادون على المشاركة في عملية حساب التكلفة. السمة الثالثة هي cost ، cost هي معلومات تكلفة احتجاز الكائن (مثل تكلفة وحدة المعالجة المركزية ، تكلفة الذاكرة ، تكلفة IO ، إلخ). estimations هي العقار الذي يحمل الإحصائيات المقدرة حول الخطة (مثل عدد الصفوف ، وحجم الصف ، وما إلى ذلك) ، كما أنها تشارك في حساب التكلفة. أخيرًا ، traits هي مجموعة من السمات المادية ، والتي تؤثر على قاعدة التنفيذ للتأثير على عملية توليد الخطة المادية.

بعد ذلك ، يمكننا تنفيذ فئات العقدة المادية:

 case class Scan (
                 operator : Operator ,
                 cost : Cost ,
                 estimations : Estimations ,
                 traits : Set [ String ] = Set .empty
               ) extends PhysicalPlan {
  override def children () : Seq [ PhysicalPlan ] = Seq .empty // scan do not receive any child
}

case class Project (
                    operator : Operator ,
                    child : PhysicalPlan ,
                    cost : Cost ,
                    estimations : Estimations ,
                    traits : Set [ String ] = Set .empty
                  ) extends PhysicalPlan {
  override def children () : Seq [ PhysicalPlan ] = Seq (child)
}

case class Join (
                 operator : Operator ,
                 leftChild : PhysicalPlan ,
                 rightChild : PhysicalPlan ,
                 cost : Cost ,
                 estimations : Estimations ,
                 traits : Set [ String ] = Set .empty
               ) extends PhysicalPlan {
  override def children () : Seq [ PhysicalPlan ] = Seq (leftChild, rightChild)
}

انظر Physicalplan.scala للتنفيذ الكامل

قاعدة التنفيذ

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

نظرًا لأننا لا ننفذ مباشرة الخطة المادية في المخطط ، لذلك سنعيد منشئ الخطة المادية بدلاً من ذلك ، من الأسهل أيضًا تخصيص وظيفة التكلفة لكل عقدة.

فيما يلي واجهة قاعدة التنفيذ:

 trait PhysicalPlanBuilder {
  def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ]
}

trait ImplementationRule {
  def physicalPlanBuilders ( expression : GroupExpression )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ]
}

هنا هو PhysicalPlanBuilder هو الواجهة المستخدمة لبناء الخطة المادية ، بالنظر إلى الخطط المادية للطفل.

على سبيل المثال ، يحتوي Joinal المنطقي على تطبيقان ماديان هجمة ودمج الانضمام

 الرسم البياني TD
    الطفل#1 ["الطفل#1"]
    الطفل رقم 2 ["الطفل#2"]
    الطفل رقم 3 ["الطفل#3"]
    الطفل رقم 4 ["الطفل#4"]
    hash_join ["` hash Join 
    التكلفة = F (التكلفة (الطفل رقم 1) ، التكلفة (الطفل#2))
    `"]
    merge_join ["` merge join
    cost=g(cost(child#3),cost(child#4))
    `"]
    hash_join --> child#1
    hash_join --> child#2
    merge_join --> child#3
    merge_join --> child#4

the HASH JOIN cost is using function f() to calculate cost, and MERGE JOIN is using function g() to calculate cost, both are using its children as function parameters. So it's easier to code if we're returning just the phyiscal plan builder from the implementation rule instead of the physical plan.

Finding the best plan

As we've said before, the optimization process is described as following:

• For each group, we will find the best implementation by choosing the group expressing with the lowest cost
• For each group expression, first we will enumerate the physical implementations from the logical plan. Then for each physical implementation, we will calculate its cost using its child group costs.

And here is the code:

 private def implementGroup ( group : Group , combinedRule : ImplementationRule )(
  implicit ctx : VolcanoPlannerContext
) : GroupImplementation = {
  group.implementation match {
    case Some (implementation) => implementation
    case None =>
      var bestImplementation = Option .empty[ GroupImplementation ]
      group.equivalents.foreach { equivalent =>
        val physicalPlanBuilders = combinedRule.physicalPlanBuilders(equivalent)
        val childPhysicalPlans = equivalent.children.map { child =>
          val childImplementation = implementGroup(child, combinedRule)
          child.implementation = Option (childImplementation)
          childImplementation.physicalPlan
        }
        // calculate the implementation, and update the best cost for group
        physicalPlanBuilders.flatMap(_.build(childPhysicalPlans)).foreach { physicalPlan =>
          val cost = physicalPlan.cost()
          bestImplementation match {
            case Some (currentBest) =>
              if (ctx.costModel.isBetter(currentBest.cost, cost)) {
                bestImplementation = Option (
                  GroupImplementation (
                    physicalPlan = physicalPlan,
                    cost = cost,
                    selectedEquivalentExpression = equivalent
                  )
                )
              }
            case None =>
              bestImplementation = Option (
                GroupImplementation (
                  physicalPlan = physicalPlan,
                  cost = cost,
                  selectedEquivalentExpression = equivalent
                )
              )
          }
        }
      }
      bestImplementation.get
  }
}

This code is an exhaustive search code, which is using recursive function to traverse all nodes. At each node (group), the function is called once to get its best plan while also calculate the optimal cost of that group.

Finally, the best plan for our query is the best plan of the root group

 val implementationRules = new ImplementationRule {

  override def physicalPlanBuilders (
                                     expression : GroupExpression
                                   )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
    expression.plan match {
      case node @ Scan (_, _) => implement. Scan (node)
      case node @ Project (_, _) => implement. Project (node)
      case node @ Join (_, _, _) => implement. Join (node)
    }
  }
}

ctx.rootGroup.implementation = Option (implementGroup(ctx.rootGroup, implementationRules))

See VolcanoPlanner.scala for full implementation

Here is an example of the plan after optimization, it's shown the selected logical node, the selected physical operator, and the estimated cost

 graph TD
    Group#6["
    Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
"]
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
"]
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
"]
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
"]

Implement the implementation rules

Next, we will implement some implementation rules.

مشروع

The first, easiest one is the implementation rule of logical PROJECT

 object Project {

  def apply ( node : logicalplan. Project )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
    Seq (
      new ProjectionImpl (node.fields)
    )
  }
}

class ProjectionImpl ( projection : Seq [ql. FieldID ]) extends PhysicalPlanBuilder {

  override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
    val child = children.head
    val selfCost = Cost (
      estimatedCpuCost = 0 ,
      estimatedMemoryCost = 0 ,
      estimatedTimeCost = 0
    ) // assuming the cost of projection is 0
    val cost = Cost (
      estimatedCpuCost = selfCost.estimatedCpuCost + child.cost().estimatedCpuCost,
      estimatedMemoryCost = selfCost.estimatedMemoryCost + child.cost().estimatedMemoryCost,
      estimatedTimeCost = selfCost.estimatedTimeCost + child.cost().estimatedTimeCost
    )
    val estimations = Estimations (
      estimatedLoopIterations = child.estimations().estimatedLoopIterations,
      estimatedRowSize = child.estimations().estimatedRowSize // just guessing the value
    )
    Some (
      Project (
        operator = ProjectOperator (projection, child.operator()),
        child = child,
        cost = cost,
        estimations = estimations,
        traits = child.traits()
      )
    )
  }
}

The implementation rule for logical PROJECT, is returning one physical plan builder ProjectionImpl . ProjectionImpl cost calculation is simple, it just inherits the cost from the child node (because the projection is actually not doing any intensive operation). Beside that, it also updates the estimation (in this code, estimation is also inherit from the child node)

See Project.scala for full implementation

ينضم

Writing implementation rule for logical JOIN is way harder than PROJECTION.

One first reason is, a logical JOIN has many physical implementation, such as HASH JOIN, MERGE JOIN, BROADCAST JOIN, etc.

The second reason is, estimating cost for physical JOIN is also hard, because it depends on lots of factors such as row count, row size, data histogram, indexes, data layout, etc.

So, to keep everything simple in this guide, I will only implement 2 physical JOIN: HASH JOIN and MERGE JOIN. The cost estimation functions are fictional (just to show how it works, I'm not trying to correct it). And in the MERGE JOIN, all data is assuming to be sorted by join key.

ها هو الرمز:

 object Join {

  def apply ( node : logicalplan. Join )( implicit ctx : VolcanoPlannerContext ) : Seq [ PhysicalPlanBuilder ] = {
    val leftFields = node.on.map(_._1).map(f => s " ${f.table.id} . ${f.id} " )
    val rightFields = node.on.map(_._2).map(f => s " ${f.table.id} . ${f.id} " )
    Seq (
      new HashJoinImpl (leftFields, rightFields),
      new MergeJoinImpl (leftFields, rightFields)
    )
  }
}

The HASH JOIN:

 class HashJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {

  private def viewSize ( plan : PhysicalPlan ) : Long = {
    plan.estimations().estimatedLoopIterations * plan.estimations().estimatedRowSize
  }

  // noinspection ZeroIndexToHead,DuplicatedCode
  override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
    // reorder the child nodes, the left child is the child with smaller view size (smaller than the right child if we're store all of them in memory)
    val (leftChild, rightChild) = if (viewSize(children( 0 )) < viewSize(children( 1 ))) {
      (children( 0 ), children( 1 ))
    } else {
      (children( 1 ), children( 0 ))
    }
    val estimatedLoopIterations = Math .max(
      leftChild.estimations().estimatedLoopIterations,
      rightChild.estimations().estimatedLoopIterations
    ) // just guessing the value
    val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
    val selfCost = Cost (
      estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
      estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
      estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
    )
    val childCosts = Cost (
      estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
      estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
      estimatedTimeCost = 0
    )
    val estimations = Estimations (
      estimatedLoopIterations = estimatedLoopIterations,
      estimatedRowSize = estimatedOutRowSize
    )
    val cost = Cost (
      estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
      estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
      estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
    )
    Some (
      Join (
        operator = HashJoinOperator (
          leftChild.operator(),
          rightChild.operator(),
          leftFields,
          rightFields
        ),
        leftChild = leftChild,
        rightChild = rightChild,
        cost = cost,
        estimations = estimations,
        traits = Set .empty // don't inherit trait from children since we're hash join
      )
    )
  }
}

We can see that the cost function of HASH JOIN is composed of its children costs and estimations

 val selfCost = Cost (
  estimatedCpuCost = leftChild.estimations().estimatedLoopIterations, // cost to hash all record from the smaller view
  estimatedMemoryCost = viewSize(leftChild), // hash the smaller view, we need to hold the hash table in memory
  estimatedTimeCost = rightChild.estimations().estimatedLoopIterations
)

val childCosts = Cost (
  estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
  estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
  estimatedTimeCost = 0
)

val estimations = Estimations (
  estimatedLoopIterations = estimatedLoopIterations,
  estimatedRowSize = estimatedOutRowSize
)

val cost = Cost (
  estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
  estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
  estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)

Next, the MERGE JOIN:

 class MergeJoinImpl ( leftFields : Seq [ String ], rightFields : Seq [ String ]) extends PhysicalPlanBuilder {

  // noinspection ZeroIndexToHead,DuplicatedCode
  override def build ( children : Seq [ PhysicalPlan ]) : Option [ PhysicalPlan ] = {
    val (leftChild, rightChild) = (children( 0 ), children( 1 ))
    if (leftChild.traits().contains( " SORTED " ) && rightChild.traits().contains( " SORTED " )) {
      val estimatedTotalRowCount =
        leftChild.estimations().estimatedLoopIterations +
          rightChild.estimations().estimatedLoopIterations
      val estimatedLoopIterations = Math .max(
        leftChild.estimations().estimatedLoopIterations,
        rightChild.estimations().estimatedLoopIterations
      ) // just guessing the value
      val estimatedOutRowSize = leftChild.estimations().estimatedRowSize + rightChild.estimations().estimatedRowSize
      val selfCost = Cost (
        estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
        estimatedMemoryCost = 0 , // no additional memory cost
        estimatedTimeCost = estimatedTotalRowCount
      )
      val childCosts = Cost (
        estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
        estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
        estimatedTimeCost = 0
      )
      val estimations = Estimations (
        estimatedLoopIterations = estimatedLoopIterations,
        estimatedRowSize = estimatedOutRowSize
      )
      val cost = Cost (
        estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
        estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
        estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
      )
      Some (
        Join (
          operator = MergeJoinOperator (
            leftChild.operator(),
            rightChild.operator(),
            leftFields,
            rightFields
          ),
          leftChild = leftChild,
          rightChild = rightChild,
          cost = cost,
          estimations = estimations,
          traits = leftChild.traits() ++ rightChild.traits()
        )
      )
    } else {
      None
    }
  }
}

Same with HASH JOIN, MERGE JOIN also uses its children costs and estimations to calculate its cost, but with different formulla:

 val selfCost = Cost (
  estimatedCpuCost = 0 , // no additional cpu cost, just scan from child iterator
  estimatedMemoryCost = 0 , // no additional memory cost
  estimatedTimeCost = estimatedTotalRowCount
)

val childCosts = Cost (
  estimatedCpuCost = leftChild.cost().estimatedCpuCost + rightChild.cost().estimatedCpuCost,
  estimatedMemoryCost = leftChild.cost().estimatedMemoryCost + rightChild.cost().estimatedMemoryCost,
  estimatedTimeCost = 0
)

val estimations = Estimations (
  estimatedLoopIterations = estimatedLoopIterations,
  estimatedRowSize = estimatedOutRowSize
)

val cost = Cost (
  estimatedCpuCost = selfCost.estimatedCpuCost + childCosts.estimatedCpuCost,
  estimatedMemoryCost = selfCost.estimatedMemoryCost + childCosts.estimatedMemoryCost,
  estimatedTimeCost = selfCost.estimatedTimeCost + childCosts.estimatedTimeCost
)

See HashJoinImpl.scala and MergeJoinImpl.scala for full implementation

آحرون

You can see other rules and physical plan builders here:

• ينفذ
• builder

Putting all pieces together

Now, after done implementing the implementation rules, now we can find our best plan. Let's start over from the user query

 SELECT tbl1 . id ,
       tbl1 . field1 ,
       tbl2 . id ,
       tbl2 . field1 ,
       tbl2 . field2 ,
       tbl3 . id ,
       tbl3 . field2 ,
       tbl3 . field2
FROM tbl1
         JOIN tbl2 ON tbl1 . id = tbl2 . id
         JOIN tbl3 ON tbl2 . id = tbl3 . id

will be converted to the logical plan

 graph TD
    1326583549["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"];
    -425111028["JOIN"];
    -349388609["SCAN tbl1"];
    1343755644["JOIN"];
    -1043437086["SCAN tbl2"];
    -1402686787["SCAN tbl3"];
    1326583549 --> -425111028;
    -425111028 --> -349388609;
    -425111028 --> 1343755644;
    1343755644 --> -1043437086;
    1343755644 --> -1402686787;

After exploration phase, it will generate lots of equivalent plans

 graph TD
    subgraph Group#8
        Expr#8["SCAN tbl2 (id, field1, field2)"]
    نهاية
    subgraph Group#11
        Expr#11["JOIN"]
        Expr#14["JOIN"]
    نهاية
    Expr#11 --> Group#7
    Expr#11 --> Group#10
    Expr#14 --> Group#8
    Expr#14 --> Group#12
    subgraph Group#2
        Expr#2["SCAN tbl2"]
    نهاية
    subgraph Group#5
        Expr#5["JOIN"]
        Expr#16["JOIN"]
    نهاية
    Expr#5 --> Group#1
    Expr#5 --> Group#4
    Expr#16 --> Group#2
    Expr#16 --> Group#13
    subgraph Group#4
        Expr#4["JOIN"]
    نهاية
    Expr#4 --> Group#2
    Expr#4 --> Group#3
    subgraph Group#13
        Expr#15["JOIN"]
    نهاية
    Expr#15 --> Group#1
    Expr#15 --> Group#3
    subgraph Group#7
        Expr#7["SCAN tbl1 (id, field1)"]
    نهاية
    subgraph Group#1
        Expr#1["SCAN tbl1"]
    نهاية
    subgraph Group#10
        Expr#10["JOIN"]
    نهاية
    Expr#10 --> Group#8
    Expr#10 --> Group#9
    subgraph Group#9
        Expr#9["SCAN tbl3 (id, field2)"]
    نهاية
    subgraph Group#3
        Expr#3["SCAN tbl3"]
    نهاية
    subgraph Group#12
        Expr#13["JOIN"]
    نهاية
    Expr#13 --> Group#7
    Expr#13 --> Group#9
    subgraph Group#6
        Expr#12["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
        Expr#6["PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2"]
    نهاية
    Expr#12 --> Group#11
    Expr#6 --> Group#5
    style Expr#12 stroke-width: 4px, stroke: orange
    style Expr#8 stroke-width: 4px, stroke: orange
    style Expr#10 stroke-width: 4px, stroke: orange
    style Expr#13 stroke-width: 4px, stroke: orange
    style Expr#14 stroke-width: 4px, stroke: orange
    style Expr#11 stroke-width: 4px, stroke: orange
    style Expr#9 stroke-width: 4px, stroke: orange
    style Expr#15 stroke-width: 4px, stroke: orange
    style Expr#7 stroke-width: 4px, stroke: orange
    style Expr#16 stroke-width: 4px, stroke: orange
    linkStyle 0 stroke-width: 4px, stroke: orange
    linkStyle 15 stroke-width: 4px, stroke: orange
    linkStyle 12 stroke-width: 4px, stroke: orange
    linkStyle 1 stroke-width: 4px, stroke: orange
    linkStyle 16 stroke-width: 4px, stroke: orange
    linkStyle 13 stroke-width: 4px, stroke: orange
    linkStyle 2 stroke-width: 4px, stroke: orange
    linkStyle 6 stroke-width: 4px, stroke: orange
    linkStyle 3 stroke-width: 4px, stroke: orange
    linkStyle 10 stroke-width: 4px, stroke: orange
    linkStyle 7 stroke-width: 4px, stroke: orange
    linkStyle 14 stroke-width: 4px, stroke: orange
    linkStyle 11 stroke-width: 4px, stroke: orange

And the at optimization phase, a final best plan is chose

 graph TD
    Group#6["
    Group #6
Selected: PROJECT tbl1.id, tbl1.field1, tbl2.id, tbl2.field1, tbl2.field2, tbl3.id, tbl3.field2, tbl3.field2
Operator: ProjectOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#6 --> Group#11
Group#11["
Group #11
Selected: JOIN
Operator: HashJoinOperator
Cost: Cost(cpu=641400.00, mem=1020400012.00, time=1000000.00)
"]
Group#11 --> Group#7
Group#11 --> Group#10
Group#7["
Group #7
Selected: SCAN tbl1 (id, field1)
Operator: NormalScanOperator
Cost: Cost(cpu=400.00, mem=400000.00, time=1000.00)
"]
Group#10["
Group #10
Selected: JOIN
Operator: MergeJoinOperator
Traits: SORTED
Cost: Cost(cpu=640000.00, mem=20000012.00, time=1100000.00)
"]
Group#10 --> Group#8
Group#10 --> Group#9
Group#8["
Group #8
Selected: SCAN tbl2 (id, field1, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=600000.00, mem=12.00, time=1000000.00)
"]
Group#9["
Group #9
Selected: SCAN tbl3 (id, field2)
Operator: NormalScanOperator
Traits: SORTED
Cost: Cost(cpu=40000.00, mem=20000000.00, time=100000.00)
"]

Bonus: query execution

Now we've done building a functional query planner which can optimize the query from user, but our query plan could not run by itself. So it's the reason why now we will implement the query processor to test out our query plan.

Basically the query process receive input from the query planner, and execute them

 graph LR
    plan(("Physical Plan"))
    storage[("Storage Layer")]
    processor["Query Processor"]
    plan -- execute --> processor
    storage -- fetch --> processor

Volcano/Iterator model

Volcano/iterator model is the query processing model that is widely used in many DBMS. It is a pipeline architecture, which means that the data is processed in stages, with each stage passing the output of the previous stage to the next stage.

Each stage in the pipeline is represented by an operator. Operators are functions that perform a specific operation on the data, such as selecting rows, filtering rows, or aggregating rows.

Usually, operator can be formed directly from the query plan. For example, the query

 SELECT field_1
FROM tbl
WHERE field = 1

will have the plan

 graph TD
  project["PROJECT: field_1"]
  scan["SCAN: tbl"]
  filter["FILTER: field = 1"]
  project --> scan
  filter --> project

will create a chain of operators like this:

 scan = {
    next() // fetch next row from table "tbl"
}

project = {
    next() = {
        next_row = scan.next() // fetch next row from scan operator
        projected = next_row["field_1"]
        return projected
    }
}

filter = {
    next() = {
        next_row = {}
        do {
            next_row = project.next() // fetch next row from project operator
        } while (next_row["field"] != 1)
        return next_row
    }
}

results = []
while (row = filter.next()) {
    results.append(row)
}

notes : this pseudo code did not handle for end of result stream

The operators

The basic interface of an operator is described as following:

 trait Operator {
  def next () : Option [ Seq [ Any ]]
}

See Operator.scala for full implementation of all operators

Testing a simple query

Let's define a query

 SELECT emp . id ,
       emp . code ,
       dept . dept_name ,
       emp_info . name ,
       emp_info . origin
FROM emp
         JOIN dept ON emp . id = dept . emp_id
         JOIN emp_info ON dept . emp_id = emp_info . id

with some data and stats

 val table1 : Datasource = Datasource (
  table = " emp " ,
  catalog = TableCatalog (
    Seq (
      " id " -> classOf [ String ],
      " code " -> classOf [ String ]
    ),
    metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id
  ),
  rows = Seq (
    Seq ( " 1 " , " Emp A " ),
    Seq ( " 2 " , " Emp B " ),
    Seq ( " 3 " , " Emp C " )
  ),
  stats = TableStats (
    estimatedRowCount = 3 ,
    avgColumnSize = Map ( " id " -> 10 , " code " -> 32 )
  )
)

val table2 : Datasource = Datasource (
  table = " dept " ,
  catalog = TableCatalog (
    Seq (
      " emp_id " -> classOf [ String ],
      " dept_name " -> classOf [ String ]
    ),
    metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by emp_id (this is just a fake trait to demonstrate how trait works)
  ),
  rows = Seq (
    Seq ( " 1 " , " Dept 1 " ),
    Seq ( " 1 " , " Dept 2 " ),
    Seq ( " 2 " , " Dept 3 " ),
    Seq ( " 3 " , " Dept 3 " )
  ),
  stats = TableStats (
    estimatedRowCount = 4 ,
    avgColumnSize = Map ( " emp_id " -> 10 , " dept_name " -> 255 )
  )
)

val table3 : Datasource = Datasource (
  table = " emp_info " ,
  catalog = TableCatalog (
    Seq (
      " id " -> classOf [ String ],
      " name " -> classOf [ String ],
      " origin " -> classOf [ String ]
    ),
    metadata = Map ( " sorted " -> " true " ) // assumes rows are already sorted by id (this is just a fake trait to demonstrate how trait works)
  ),
  rows = Seq (
    Seq ( " 1 " , " AAAAA " , " Country A " ),
    Seq ( " 2 " , " BBBBB " , " Country A " ),
    Seq ( " 3 " , " CCCCC " , " Country B " )
  ),
  stats = TableStats (
    estimatedRowCount = 3 ,
    avgColumnSize = Map ( " id " -> 10 , " name " -> 255 , " origin " -> 255 )
  )
)

The cost model is optimized for CPU

 val costModel : CostModel = ( currentCost : Cost , newCost : Cost ) => {
  currentCost.estimatedCpuCost > newCost.estimatedCpuCost
}

Now, executing the query by running this code:

 val planner = new VolcanoPlanner
QueryParser .parse(query) match {
  case Left (err) => throw err
  case Right (parsed) =>
    val operator = planner.getPlan(parsed)
    val result = Utils .execute(operator)
    // print result
    println(result._1.mkString( " , " ))
    result._2.foreach(row => println(row.mkString( " , " )))
}

it will print:

 emp.id,emp.code,dept.dept_name,emp_info.name,emp_info.origin
1,Emp A,Dept 1,AAAAA,Country A
1,Emp A,Dept 2,AAAAA,Country A
2,Emp B,Dept 3,BBBBB,Country A
3,Emp C,Dept 3,CCCCC,Country B

Voila, We've done building a fully functional query planner and query engine :). You can start writing one for your own, good luck

See Demo.scala for full demo code

شكرًا

Thanks for reading this, this guide is quite long, and not fully correct, but I've tried my best to write it as understandably as possible ?