0Pricing
SQL Interview Prep · บทเรียน

อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน

วิธีดำเนินการเชื่อมตารางแต่ละแบบ และสถานการณ์ที่ควรเลือกใช้

อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน เป็นบทเรียน SQL Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 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 ครั้ง

อันตรายจะเกิดขึ้นเมื่อด้านนอกมีขนาดใหญ่ หากด้านนอกสร้างผลลัพธ์ 2 ล้านแถว ด้านในจะทำงาน 2 ล้านครั้ง แม้การค้นหาแต่ละครั้งจะรวดเร็วเพียง 0.01 มิลลิวินาที ก็ยังใช้เวลา 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;

สรุปการเชื่อมตารางเมื่อมีข้อมูลขนาดใหญ่

ลองนำทุกอย่างมารวมกันสำหรับงานวิเคราะห์ที่เชื่อมตารางข้อเท็จจริงขนาดใหญ่สองตารางกับตารางมิติด้วย id:

  • หากตารางมิติมีขนาดพอดีกับหน่วยความจำ ให้คาดว่าจะได้การเชื่อมตารางแบบแฮช ซึ่งมักเป็นตัวเลือกที่ดีที่สุด
  • หากทั้งสองตารางมาจากดัชนีโดยเรียงลำดับไว้แล้ว การเชื่อมตารางแบบผสานอาจหลีกเลี่ยงการสร้างตารางแฮชได้
  • การวนซ้อน ในกรณีนี้ควรถือเป็นสัญญาณเตือน มักเกิดจากค่าประมาณที่ไม่ถูกต้อง

การอ่านว่าตัววางแผนเลือกแบบใด และพิจารณาว่าควรเลือกแบบนั้นหรือไม่ คือทักษะระดับอาวุโสที่คำถามเหล่านี้ต้องการทดสอบโดยตรง

ตรวจสอบอย่างรวดเร็ว

คุณเชื่อมตารางขนาดใหญ่สองตารางที่ไม่ได้เรียงลำดับด้วยเงื่อนไขความเท่ากัน a.id = b.id ทั้งสองตารางไม่มีดัชนีที่เป็นประโยชน์ และสถิติถูกต้อง ตัววางแผนน่าจะเลือกอัลกอริทึมการเชื่อมตารางแบบใดมากที่สุด

ทบทวน

อัลกอริทึมการเชื่อมตารางทั้งสามแบบ:

  • การวนซ้อน จำนวนแถวด้านนอกคูณด้วยการค้นหาด้านใน เหมาะอย่างยิ่งเมื่อตารางด้านนอกมีขนาดเล็กและคีย์ด้านในมีดัชนี แต่อันตรายเมื่อค่า loops สูงมาก
  • การเชื่อมตารางแบบแฮช สร้างตารางแล้วค้นหา เหมาะที่สุดกับการเชื่อมตารางขนาดใหญ่ที่ไม่ได้เรียงลำดับและใช้ความเท่ากัน จำกัดให้ใช้ได้กับความเท่ากันเท่านั้น และอยู่ภายใต้ข้อจำกัดของ work_mem
  • การเชื่อมตารางแบบผสาน เดินผ่านข้อมูลนำเข้าที่เรียงลำดับไปพร้อมกัน เหมาะเมื่อข้อมูลเรียงลำดับอยู่แล้วหรือใช้กับการเชื่อมตารางตามช่วง

ตัววางแผนเลือกตามต้นทุนและสถิติ การวนซ้อนที่น่าประหลาดใจและมีค่า loops สูงมากแทบจะหมายถึงค่าประมาณจำนวนแถวไม่ถูกต้องเสมอ ให้แก้ไขสถิติ

คำถามที่พบบ่อย

บทเรียน “อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส SQL Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส SQL Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน”

วิธีดำเนินการเชื่อมตารางแต่ละแบบ และสถานการณ์ที่ควรเลือกใช้ คุณปฏิบัติ SQL Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน SQL Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน SQL Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน SQL Interview Prep นี้ได้ไหม

ได้ บทเรียน SQL Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. อ่านแผน EXPLAIN
  2. การสแกนตามลำดับเทียบกับการสแกนดัชนีและการสแกนเฉพาะดัชนี
  3. อัลกอริทึมการเชื่อมตาราง: ลูปซ้อน แฮช และผสาน
  4. ค้นหาและแก้ไขคำสั่งค้นหาที่ช้า
← กลับไปที่ SQL Interview Prep