- SQL Engine เป็นชั้นเชิงตรรกะของฐานข้อมูลที่ทำงานอยู่ระหว่างไคลเอนต์กับสตอเรจ
- คำอธิบายอย่างละเอียดของกระบวนการหลักใน SQL Engine ได้แก่ การพาร์ส, การไบน์ดิง, การทำแผนให้ง่ายขึ้น, การสำรวจจอยน์และประเมินต้นทุน, การรันคำสั่ง, และ การสพูลผลลัพธ์
- การพาร์ส คือการแปลง SQL query ให้เป็น abstract syntax tree (AST) ที่มีโครงสร้าง
- การไบน์ดิง คือการจับคู่ฟิลด์ใน AST กับสัญลักษณ์ในแค็ตตาล็อกของฐานข้อมูลปัจจุบัน
- การทำแผนให้ง่ายขึ้น คือการนอร์มัลไลซ์ไวยากรณ์ SQL ที่ซับซ้อนให้อยู่ในรูปแบบที่เรียบง่ายขึ้นเพื่อเพิ่มความเร็วในการรัน
- การสำรวจแผน คือการสำรวจรูปแบบต่าง ๆ ของจอยน์ การรวมผล และ window function เพื่อหา execution plan ที่ดีที่สุด
- การรันและการสพูลผลลัพธ์ คือการแปลงแผนสุดท้ายให้อยู่ในรูปแบบที่รันได้จริงและส่งผลลัพธ์กลับไปยังไคลเอนต์
ภาพรวมของ SQL Engine
- SQL Engine เป็น ชั้นตัวกลางเชิงตรรกะ ระหว่างคำขอจากไคลเอนต์กับระบบจัดเก็บข้อมูล
- ขั้นตอนหลัก
- Parsing: แปลง query ให้เป็น AST (abstract syntax tree)
- Binding: เชื่อมตัวระบุใน AST เข้ากับสัญลักษณ์ในแค็ตตาล็อกของฐานข้อมูล
- Plan Simplification: ทำให้ไวยากรณ์ SQL ที่หลากหลายง่ายลงเป็นรูปแบบแผนมาตรฐาน
- Join Exploration & Costing: สำรวจลำดับการจอยน์แบบต่าง ๆ และประเมินต้นทุน
- Execution: รัน query โดยใช้ execution plan ที่เหมาะสมที่สุด
- Spooling Results: ส่งผลลัพธ์กลับไปยังไคลเอนต์
การพาร์ส (Parsing)
- การพาร์ส คือกระบวนการ tokenization ของ query ที่รับเข้ามาและแปลงให้เป็น AST
- right-recursive parser เข้าใจและดีบักได้ง่าย แต่ใช้หน่วยความจำสแตกมาก
- left-recursive parser (อิงกับ Yacc) มีประสิทธิภาพด้านหน่วยความจำมากกว่า แต่ต้องใช้ลอจิกที่ซับซ้อน
- Dolt ใช้ left-recursive parser เพื่อรองรับการพาร์สที่รวดเร็ว
- เมื่อพาร์สสำเร็จ โครงสร้าง AST จะสอดคล้องกับกฎของ Yacc
การไบน์ดิง (Binding)
- การไบน์ดิง คือกระบวนการเชื่อมฟิลด์ใน AST เข้ากับตารางจริงและสัญลักษณ์ของคอลัมน์ในฐานข้อมูล
- แนวคิดหลัก
- นิยามตาราง: ทำหน้าที่เป็นแหล่งข้อมูล
- นิยามคอลัมน์: อ้างอิงคอลัมน์เฉพาะจากแหล่งข้อมูลตาราง
- Alias: ใช้ค่าชนิดสเกลาร์ได้ทั้งในฐานะแหล่งข้อมูลและปลายทาง
- scalar subquery: ใช้สโคปร่วมกับ parent และทำ name binding
- ผลลัพธ์ของการไบน์ดิงคือการสร้างโหนด execution plan ในรูปแบบ sql.Node
การทำแผนให้ง่ายขึ้น (Plan Simplifications)
- เป็นกระบวนการแปลงรูปแบบ SQL ที่หลากหลายให้อยู่ใน รูปแบบที่นอร์มัลไลซ์แล้ว เพื่อช่วยให้การรันมีประสิทธิภาพขึ้น
- การเพิ่มประสิทธิภาพที่พบบ่อย
- Filter Pushdown: ตัดแถวที่ไม่จำเป็นออก
- Column Pruning: ตัดคอลัมน์ที่ไม่จำเป็นออก
- ยังทำ optimization ของแผนจอยน์ผ่านการแปลงอย่าง subquery decorrelation ด้วย
การบังคับแปลงชนิดข้อมูล (Type Coercion)
- การบังคับแปลงชนิดข้อมูล คือกระบวนการแปลงชนิดของ expression โดยอัตโนมัติตามบริบท
- ชนิดข้อมูลอาจเปลี่ยนไปตามบริบท เช่น WHERE, INSERT เป็นต้น
- Dolt กำลังจัดการการแปลงชนิดข้อมูลแบบค่อยเป็นค่อยไปในขั้นตอน binding
การสำรวจจอยน์ (Plan Exploration)
- การสำรวจจอยน์ คือกระบวนการสร้างและตรวจสอบลำดับการจอยน์แบบต่าง ๆ
- มีกลยุทธ์การสำรวจ 2 แบบ
- top-down backtracking: สำรวจเฉพาะลำดับการจอยน์ที่ใช้ได้
- bottom-up dynamic programming (DP): ลองทุกชุดผสมเพื่อหาลำดับการจอยน์ที่ดีที่สุด
- ใช้โครงสร้าง Memo เพื่อจัดการสถานะระหว่างทางอย่างมีประสิทธิภาพ
การขึ้นต่อกันเชิงฟังก์ชัน (Functional Dependencies)
- เมื่อต้องจอยน์ตารางตั้งแต่ 5 ตารางขึ้นไป ต้นทุนอาจเพิ่มสูงมาก
- หากใช้ประโยชน์จาก ความสัมพันธ์แบบ 1:1 เช่นการจอยน์ที่อิงกับ primary key (PK) ก็สามารถลดต้นทุนในการสำรวจได้
- มีการให้ความสำคัญกับ LOOKUP_JOIN ก่อนเพื่อการปรับแต่งประสิทธิภาพ
สรุป intermediate representation (IR Intermission)
- สรุป 3 ขั้นของ IR ที่กล่าวมาจนถึงตอนนี้
- AST: จัดระเบียบโทเคน
- scope binding: ตรวจสอบการอ้างอิงคอลัมน์
- Memo: ตัวแทนสำหรับการสำรวจจอยน์และการประเมินต้นทุน
การประเมินต้นทุนจอยน์ (Join Costing)
- การประเมินต้นทุนจอยน์ คือกระบวนการประมาณต้นทุนการรันของทุกแผนที่เป็นไปได้
- องค์ประกอบของต้นทุน
- ขนาดของตารางอินพุต
- ขนาดของตารางผลลัพธ์
- ชนิดของตัวดำเนินการจอยน์ (เช่น LOOKUP_JOIN, HASH_JOIN)
- Dolt ประเมินต้นทุนโดยอิงจากสถิติตารางที่แม่นยำ (histogram)
Join Hints
- ระบบจะพยายามใช้กลยุทธ์จอยน์ตาม hint ที่ผู้ใช้ระบุเป็นลำดับแรก
- hint ที่ขัดแย้งกันหรือไม่เหมาะสมจะถูกละเว้น
การรันคำสั่ง (Execution)
- แปลงแผนที่เหมาะสมที่สุดให้เป็นโครงสร้าง iterator (Volcano Iterator) ที่รันได้จริง
- คุณลักษณะ
- iterator แบบ non-materializing: คืนค่าแถวได้ทันที
- iterator แบบ materializing: รวบรวมทุกแถวก่อนแล้วจึงคืนค่า
- การอ้างอิงคอลัมน์จะถูกแมปตาม index offset ก่อนเริ่มรัน
I/O และการสพูลผลลัพธ์ (IO/Spooling)
- แปลงผลการรันให้อยู่ใน รูปแบบโปรโตคอล MySQL แล้วส่งต่อไปยังไคลเอนต์
- ในบางกรณีก็มีการ optimize โดยอ่านผลลัพธ์โดยตรงจากเลเยอร์ key-value (KV) storage
- ปรับปรุงความเร็วในการประมวลผลและประสิทธิภาพหน่วยความจำผ่านการประมวลผลแบบ batch และการใช้บัฟเฟอร์ซ้ำ
แผนในอนาคต (Future)
- โดยพื้นฐานแล้ว Dolt ใช้ row-based execution บน local server
- รองรับการวาง execution plan ที่เหมาะสมที่สุดด้วย 3-stage intermediate representation (IR) เช่น AST, scope-based binding, และ การสำรวจจอยน์ผ่านโครงสร้าง Memo
- ตัดสินใจกำหนดกลยุทธ์จอยน์ที่ดีที่สุดผ่าน Join Search และ Join Costing
- ในอนาคตมีแผนปรับปรุง ประสิทธิภาพ ผ่าน การรวม IR และ การปรับแต่งการใช้หน่วยความจำซ้ำ
ยังไม่มีความคิดเห็น