ดัชนี SQL อธิบาย, Pt. 2

ในบทเรียนแรกของ SQL Indexes Explained เราได้เรียนรู้การใช้การเรียงลำดับเพื่อเพิ่มความเร็วในการดึงข้อมูล แม้ว่าการดำเนินการค้นหาของเราจะเร็วขึ้นหลังจากจัดเรียงแถวแล้ว การเรียงลำดับนั้นเกี่ยวข้องกับการอ่านทุกแถวอย่างน้อยหนึ่งครั้งและย้ายไปรอบๆ นั่นทำให้วิธีการทำงานช้าลงและมีประสิทธิภาพน้อยกว่าการอ่านทั้งตารางตามลำดับ

ข้อสรุปเชิงตรรกะดูเหมือนว่าเราควรรักษาสำเนาที่จัดเรียงไว้—ซึ่งเราจะเรียกอย่างเป็นทางการว่า ดัชนี SQL นำหน้าด้วย IX_ ของตารางที่กำหนด อัลกอริทึมการดึงข้อมูลจากบทความแรกจะนำไปใช้ได้ และเราไม่จำเป็นต้องจัดเรียงตารางก่อนเริ่มต้น

ดัชนีเป็นสำเนาที่เรียงลำดับของตาราง

มาดูการนำแนวคิดนั้นไปใช้จริงอีกครั้งโดยใช้ Google ชีต สเปรดชีตการจองของเรากลายเป็นชุดเอกสารห้าแผ่นที่มีข้อมูลเดียวกัน แต่ละแผ่นจะถูกจัดเรียงตามชุดของคอลัมน์ต่างๆ

แบบฝึกหัดนี้มีจุดมุ่งหมายเพื่อให้มีความเข้มงวดน้อยกว่าในบทความบทช่วยสอนดัชนี SQL ก่อนหน้านี้ ซึ่งสามารถทำได้โดยใช้ความรู้สึกมากกว่าการจับเวลาและการนับแถว แบบฝึกหัดบางอย่างอาจดูคล้ายกันมาก แต่คราวนี้ เรากำลังสำรวจ:

1. วิธีดึงข้อมูลอย่างมีประสิทธิภาพมากขึ้นเมื่อใช้ดัชนีแยกกันแทนที่จะจัดเรียงตารางหลัก
2. วิธี รักษาความ สงบเรียบร้อยในแต่ละดัชนีและตารางเมื่อแก้ไขข้อมูล

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

แบบฝึกหัดเบื้องต้น: ยกเลิกการจอง

เพื่อให้เข้าใจประสิทธิภาพของดัชนี SQL โดยใช้กลยุทธ์ตารางที่จัดเรียง งานของคุณคือลบการจองสำหรับไคลเอนต์ 12 ตั้งแต่วันที่ 22 สิงหาคม 2020 ในโรงแรม 4 โปรดทราบว่าคุณต้องลบแถวออกจากสำเนาทั้งหมด ตารางและรักษาการเรียงลำดับที่ถูกต้อง

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

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

ดัชนี SQL โดยใช้ที่อยู่แถว

สเปรดชีตนี้มีดัชนีที่ใช้แนวทางอื่น แถวดัชนียังคงจัดเรียงตามเกณฑ์เฉพาะ แต่เราไม่เก็บข้อมูลอื่นๆ ทั้งหมดในแถวดัชนี แต่เราเก็บเฉพาะ "ที่อยู่แถว" ซึ่งเป็นที่อยู่ของแถวในแผ่นงานการจอง ซึ่งเป็นตัวแทนของตารางเองในคอลัมน์ H

การใช้งาน RDBMS ทั้งหมดใช้ความสามารถระดับระบบปฏิบัติการเพื่อค้นหาบล็อกบนดิสก์อย่างรวดเร็วโดยใช้ที่อยู่จริง ที่อยู่แถวมักจะประกอบด้วยที่อยู่บล็อกบวกตำแหน่งของแถวภายในบล็อก

ลองทำแบบฝึกหัดสองสามข้อเพื่อเรียนรู้ว่าการออกแบบดัชนีนี้ทำงานอย่างไร

แบบฝึกหัดที่ 1: การจองทั้งหมดของลูกค้า

เช่นเดียวกับในบทความแรก คุณจะจำลองการดำเนินการของแบบสอบถาม SQL ต่อไปนี้:

 SELECT * FROM Reservations WHERE ClientID = 12;

อีกครั้งมีสองวิธีที่สมเหตุสมผล รายการแรกเป็นเพียงการอ่านแถวทั้งหมดจากตารางการสำรองที่นั่งและดึงเฉพาะแถวที่ตรงกับเกณฑ์เท่านั้น:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

วิธีที่สองเกี่ยวข้องกับการอ่านข้อมูลจากชีต IX_ClientID และสำหรับรายการที่ตรงกับเกณฑ์ ให้ค้นหาแถวในตารางการสำรองตามค่า rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

ที่นี่นิพจน์ Get first row from ถูกนำมาใช้โดยลูปที่คล้ายกับที่เห็นในบทความก่อนหน้า:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

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

หากมีการส่งคืนการจองเพียงไม่กี่รายการ แนวทางที่ใช้ดัชนีจะดีกว่า อย่างไรก็ตาม ด้วยการส่งคืนแถวหลายร้อย—หรือบางครั้งอาจแค่สิบแถว—เพียงแค่ใช้ตารางการจองโดยตรงก็สามารถทำได้เร็วขึ้น

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

เราจะกลับไปที่ส่วนนั้นในภายหลังและนำเสนอวิธีแก้ปัญหาที่มีประสิทธิภาพ สำหรับตอนนี้ มาเน้นที่ส่วน นั้นหลังจากที่ คุณพบแถวแรกที่ตรงกับเกณฑ์ของเรา

การใช้สิทธิที่ 2: จำนวนการจองที่เริ่มในวันที่กำหนด

ภารกิจคือการนับจำนวนการเช็คอินในวันที่ 16 สิงหาคม 2020 โดยใช้การออกแบบดัชนีใหม่

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

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

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

โดยพื้นฐานแล้วอัลกอริทึมจะเหมือนกับอัลกอริทึมที่ใช้ตารางที่จัดเรียง อย่างไรก็ตาม แถวดัชนีสั้นกว่าแถวตารางมาก ดังนั้น RDBMS ของเราจึงต้องอ่านบล็อคข้อมูลจากดิสก์น้อยลง

การใช้สิทธิที่ 3: การสอบสวนทางอาญา (รายชื่อแขกระบุโรงแรมและช่วงวันที่)

มาเตรียมรายชื่อแขกที่มาถึง Hotel 3 ในวันที่ 13 และ 14 สิงหาคม 2020 กันครับ

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

เราสามารถอ่านแถวทั้งหมดจากตารางการสำรองที่นั่งหรือใช้ดัชนีที่มีอยู่ หลังจากทำแบบฝึกหัดเดียวกันกับตารางที่จัดเรียงตามเกณฑ์เฉพาะ เราพบว่าดัชนี IX_HotelID_DateFrom มีประสิทธิภาพมากที่สุด

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

เราสามารถออกแบบดัชนีที่มีประสิทธิภาพมากยิ่งขึ้นได้หรือไม่?

เราเข้าถึงตารางเนื่องจากค่า ClientID ซึ่งเป็นข้อมูลเดียวที่เราต้องการสำหรับรายชื่อแขกที่เรากำลังรายงาน ถ้าเรารวมค่านั้นไว้ในดัชนี SQL เราไม่ต้องเข้าถึงตารางเลย ลองเตรียมรายการที่อ่านได้จากดัชนีดังกล่าวเท่านั้น IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

เมื่อดัชนีประกอบด้วยข้อมูลที่จำเป็นทั้งหมดสำหรับการดำเนินการค้นหา เราบอกว่าดัชนี ครอบคลุม การสืบค้น

แบบฝึกหัดที่ 4: รายชื่อแขกแทนบัตรประจำตัว

รายการ ID แขกจะไม่มีประโยชน์สำหรับเจ้าหน้าที่ตำรวจที่สืบสวนคดีอาชญากรรม เราจำเป็นต้องระบุชื่อ:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

ในการจัดทำรายการ นอกจากข้อมูลจากตารางการ Reservations แล้ว เรายังต้องการตาราง Clients ที่มีข้อมูลแขก ซึ่งสามารถพบได้ใน Google ชีตนี้

แบบฝึกหัดนี้คล้ายกับแบบฝึกหัดก่อนหน้า และแนวทางนี้ก็เช่นกัน

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

นิพจน์ Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID สามารถใช้งานได้โดยการสแกนตารางหรือใช้ดัชนีของเรา หากเราใช้การสแกนตาราง สำหรับแต่ละ ClientID จากลูป While เราจะต้องอ่านโดยเฉลี่ยครึ่งแถวจากตาราง Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

การใช้ดัชนีที่เราได้พิจารณามาจนถึงตอนนี้ เรียกว่าการใช้ดัชนีแบบ "คงที่" จะไม่ช่วยอะไรมากนัก เราจะต้องอ่านจำนวนแถวเท่ากัน (แม้ว่าจะเป็นแถวที่เล็กกว่า) จากดัชนี จากนั้นข้ามไปที่แถวใน Clients โดยใช้ RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

หมายเหตุ: ในที่นี้ PK หมายถึง "คีย์หลัก" ซึ่งเป็นคำที่เราจะมาสำรวจกันในซีรีส์นี้

มีวิธีทำให้สำเร็จโดยไม่ต้องอ่านหลายแถวหรือไม่? ใช่ นี่คือสิ่งที่ดัชนี B-tree มีไว้สำหรับ

ดัชนีต้นไม้สมดุล (B-tree)

มาแบ่งแถวจาก Clients_PK_Flat เป็นบล็อกสี่แถวและสร้างรายการที่มีค่าของ ClientID สุดท้ายจากบล็อกและที่อยู่ของการเริ่มต้นบล็อก (คอลัมน์ IndexRowAddress ) โครงสร้างข้อมูลดัชนีฐานข้อมูลผลลัพธ์—คุณจะพบได้ในชีต Clients_PK_2Levels ลองใช้โครงสร้างใหม่นี้เพื่อช่วยคุณค้นหาไคลเอ็นต์ที่มี ClientID เท่ากับ 28 อัลกอริทึมควรมีลักษณะดังนี้:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

คุณอาจพบว่าเราสามารถเพิ่มระดับอื่นได้ ระดับ 1 ประกอบด้วยสี่แถว ดังที่คุณเห็นในแท็บ IX_Clients_PK ในการค้นหาชื่อแขกที่มี ClientID เป็น 28 คุณต้องอ่านข้อมูลสามช่วงตึก (โหนด) หนึ่งบล็อกต่อระดับ จากโครงสร้างคีย์หลักและสุดท้ายข้ามไปยังแถวไคลเอ็นต์ที่มีที่อยู่ 42

โครงสร้างของดัชนี SQL นี้เรียกว่าต้นไม้ที่สมดุล ต้นไม้จะสมดุลเมื่อเส้นทางจากโหนดรากไปยังโหนดระดับลีฟแต่ละโหนดมีความยาวเท่ากัน เรียกว่าความลึกของต้นไม้บี ในกรณีของเรา ความลึกคือสาม

จากนี้ไป เราจะพิจารณาว่าดัชนีแต่ละรายการมีโครงสร้าง B-tree แม้ว่าสเปรดชีตของเราจะมีเฉพาะรายการระดับลีฟ ข้อเท็จจริงที่สำคัญที่สุดที่ควรทราบเกี่ยวกับบีทรีคือ:

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

แบบฝึกหัดที่ 5: การสอบสวนคดีอาญา ภาค II

ตอนนี้ สารวัตรตำรวจกำลังมองหารายชื่อแขก วันที่เดินทางมาถึง และชื่อโรงแรมจากโรงแรมทั้งหมดในเมือง A

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

แนวทาง 1

หากเราใช้ดัชนี IX_DateFrom_HotelID_ClientID สำหรับแต่ละแถวจากช่วงวันที่ เราจะต้องเข้าถึงตาราง Hotels และตรวจสอบว่าโรงแรมมาจากเมือง A หรือไม่ หากใช่ เราจะต้องเข้าถึงตาราง Clients ด้วย เพื่อ อ่านชื่อลูกค้า

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

วิธีที่ 2

การใช้ IX_HotelID_DateFrom_ClientID ทำให้เรามีแผนการดำเนินการที่มีประสิทธิภาพมากขึ้น

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

จากตาราง Hotels เราพบโรงแรมทั้งหมดจากเมือง A เมื่อทราบ ID ของโรงแรมเหล่านี้แล้ว เราสามารถอ่านรายการถัดไปได้จากดัชนี IX_HotelID_DateFrom_ClientID ด้วยวิธีนี้ หลังจากที่หาแถวแรกในระดับใบไม้ B สำหรับแต่ละโรงแรมและวันที่แล้ว เราจะไม่อ่านการจองจากโรงแรมนอกเมือง A

ในที่นี้ เราจะเห็นว่าเมื่อเรามีดัชนีฐานข้อมูลที่เหมาะสมกับเป้าหมายของเรา การรวมเพิ่มเติมจะทำให้การสืบค้นเร็วขึ้น

โครงสร้าง B-tree และวิธีอัปเดตทุกครั้งที่มีการแทรก อัปเดต หรือลบแถวจะมีรายละเอียดเพิ่มเติมเมื่อฉันอธิบายแรงจูงใจในการแบ่งพาร์ติชันและผลกระทบ ประเด็นคือเราสามารถพิจารณาการดำเนินการนี้อย่างรวดเร็วทุกครั้งที่เราใช้ดัชนี

การสืบค้นดัชนีใน SQL: รายละเอียดสร้างความแตกต่าง

เมื่อพูดถึงดัชนีและฐานข้อมูล การทำงานในระดับภาษา SQL จะซ่อนรายละเอียดการใช้งานในระดับหนึ่ง แบบฝึกหัดเหล่านี้มีขึ้นเพื่อช่วยให้คุณเข้าใจว่าแผนการดำเนินการทำงานอย่างไรเมื่อใช้ดัชนี SQL ที่แตกต่างกัน หลังจากอ่านบทความนี้แล้ว ฉันหวังว่าคุณจะสามารถเดาแผนการดำเนินการที่ดีที่สุดได้จากดัชนีที่มีอยู่และดัชนีการออกแบบซึ่งจะทำให้การสืบค้นรวดเร็วและมีประสิทธิภาพมากที่สุด

ในส่วนถัดไปของชุดข้อมูลนี้ เราจะใช้และขยายทักษะที่ได้รับใหม่เพื่อตรวจสอบและทำความเข้าใจ แนวทางปฏิบัติที่ดีที่สุดและการต่อต้านรูปแบบที่พบบ่อยที่สุด ในการใช้ดัชนีใน SQL ฉันมีรายการแนวทางปฏิบัติที่ดีและดีที่สุดที่ฉันต้องการจะกล่าวถึงในส่วนถัดไป แต่เพื่อให้บทความถัดไปมีความเกี่ยวข้องกับความต้องการและประสบการณ์ของคุณมากขึ้น โปรด โพสต์คำถามของคุณเองที่คุณต้องการรับคำตอบ

ในส่วนสุดท้ายของ SQL Indexes Explained เราจะเรียนรู้เกี่ยวกับการแบ่งพาร์ติชั่นตารางและดัชนี แรงจูงใจที่ถูกต้องและไม่ถูกต้องในการใช้งาน และผลกระทบต่อประสิทธิภาพการสืบค้นและการบำรุงรักษาฐานข้อมูล