เมื่อใช้อย่างถูกต้องดัชนีฐานข้อมูล SQL จะมีประสิทธิภาพมากจนอาจดูเหมือนเวทมนตร์ แต่ชุดแบบฝึกหัดต่อไปนี้จะแสดงให้เห็นว่าด้านล่างตรรกะของดัชนี SQL ส่วนใหญ่และ การกวัดแกว่งอย่างถูกต้อง - ค่อนข้างตรงไปตรงมา
ในซีรีส์นี้ คำอธิบายดัชนี SQL เราจะอธิบายถึงแรงจูงใจในการใช้ดัชนีเพื่อเข้าถึงข้อมูลและสำหรับการออกแบบดัชนีในแบบที่ RDBMS ยุคใหม่ทั้งหมดทำ จากนั้นเราจะดูอัลกอริทึมที่ใช้ในการส่งคืนข้อมูลสำหรับรูปแบบการสืบค้นเฉพาะ
คุณไม่จำเป็นต้องรู้เกี่ยวกับดัชนีมากนักก็สามารถติดตามได้ คำอธิบายดัชนี SQL . มีเพียงสองเงื่อนไขเบื้องต้น:
หัวข้อหลัก คำอธิบายดัชนี SQL จะได้รับคือ:
นี่ไม่ใช่แค่บทแนะนำเกี่ยวกับดัชนี SQL แต่เป็นการเจาะลึกในการทำความเข้าใจกลไกพื้นฐานของดัชนี
เราจะหาวิธีที่ RDBMS ใช้ดัชนีโดยทำแบบฝึกหัดและวิเคราะห์วิธีการแก้ปัญหาของเรา เอกสารแบบฝึกหัดของเราประกอบด้วย Google ชีตแบบอ่านอย่างเดียว หากต้องการทำแบบฝึกหัดคุณสามารถคัดลอก Google ชีต ( ไฟล์→ทำสำเนา ) หรือคัดลอกเนื้อหาลงใน Google Sheet ของคุณเอง
ในการออกกำลังกายทุกครั้งเราจะแสดงไฟล์ SQL แบบสอบถามที่ใช้ไวยากรณ์ Oracle สำหรับวันที่เราจะใช้รูปแบบ ISO 8601, YYYY-MM-DD
งานแรกอย่าเพิ่งทำไป - คือการค้นหาแถวทั้งหมดจาก สเปรดชีตการจอง สำหรับลูกค้าเฉพาะของระบบการจองโรงแรมและคัดลอกลงในสเปรดชีตของคุณเองโดยจำลองการดำเนินการของแบบสอบถามต่อไปนี้:
SELECT * FROM Reservations WHERE ClientID = 12;
แต่เราต้องการทำตามวิธีการเฉพาะ
ในการลองครั้งแรกอย่าใช้คุณลักษณะการเรียงลำดับหรือการกรองใด ๆ กรุณาบันทึกเวลาที่ใช้ แผ่นงานที่ได้ควรมี 73 แถว
pseudocode นี้แสดงให้เห็นถึงอัลกอริทึมสำหรับการทำงานให้สำเร็จโดยไม่ต้องเรียงลำดับ:
For each row from Reservations If Reservations.ClientID = 12 then fetch Reservations.*
ในกรณีนี้เราต้องตรวจสอบแถวทั้งหมด 841 แถวเพื่อส่งคืนและคัดลอก 73 แถวที่ตรงตามเงื่อนไข
สำหรับการลองครั้งที่สองให้จัดเรียงแผ่นงานตามค่าของ ClientID
คอลัมน์. อย่าใช้ฟิลเตอร์ บันทึกเวลาและเปรียบเทียบกับเวลาที่ใช้ในการทำงานให้เสร็จโดยไม่ต้องเรียงลำดับข้อมูล
หลังจากเรียงลำดับแนวทางจะมีลักษณะดังนี้:
For each row from Reservations If ClientID = 12 then fetch Reservations.* Else if ClientID > 12 exit
คราวนี้เราต้องตรวจสอบ 'เฉพาะ' 780 แถว หากเราสามารถข้ามไปยังแถวแรกได้ก็จะใช้เวลาน้อยลง
แต่ถ้าเราจะต้องพัฒนาโปรแกรมสำหรับงานการแก้ปัญหานี้จะช้ากว่าโปรแกรมแรกด้วยซ้ำ นั่นเป็นเพราะเราจะต้องเรียงลำดับข้อมูลทั้งหมดก่อนซึ่งหมายความว่าแต่ละแถวจะต้องเข้าถึงอย่างน้อยหนึ่งครั้ง วิธีนี้จะดีก็ต่อเมื่อจัดเรียงแผ่นงานตามลำดับที่ต้องการแล้ว
ตอนนี้ภารกิจคือการนับจำนวนการเช็คอินในวันที่ 16 สิงหาคม 2020:
SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16', 'YYYY-MM-DD')
ใช้สเปรดชีตจากแบบฝึกหัด 1 วัดและเปรียบเทียบเวลาที่ใช้ในการทำภารกิจให้เสร็จโดยไม่เรียงลำดับ จำนวนที่ถูกต้องคือ 91
สำหรับวิธีการที่ไม่มีการเรียงลำดับอัลกอริทึมนั้นโดยพื้นฐานแล้วจะเหมือนกับวิธีการออกกำลังกายที่ 1
วิธีการเรียงลำดับยังคล้ายกับวิธีการออกกำลังกายครั้งก่อน เราจะแบ่งลูปออกเป็นสองส่วน:
-- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 16th of August 2020. Repeat Read next row Until DateFrom = '2020-08-16' -- Calculate the count While DateFrom = '2020-08-16' Increase the count Read the next row
เจ้าหน้าที่ตำรวจขอดูรายชื่อแขกที่มาถึงโรงแรมในวันที่ 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;
ผู้ตรวจต้องการให้รายการเร็ว เรารู้อยู่แล้วว่าเราควรจัดเรียงตาราง / สเปรดชีตให้ดีขึ้นตามวันที่มาถึง ถ้าเราเพิ่งออกกำลังกาย 2 เสร็จถือว่าเราโชคดีที่ตารางเรียงลำดับเรียบร้อยแล้ว ดังนั้นเราจึงใช้แนวทางที่คล้ายกับแบบฝึกหัดที่ 2
โปรดลองบันทึกเวลาจำนวนแถวที่คุณต้องอ่านและจำนวนรายการในรายการ
-- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 13th of August 2020. Repeat Read next row Until DateFrom >= '2020-08-13' -- Prepare the list While DateFrom <'2020-08-15' If HotelID = 3 then write down the ClientID Read the next row
ด้วยวิธีนี้เราต้องอ่าน 511 แถวเพื่อรวบรวมรายชื่อแขก 46 คน หากเราสามารถเลื่อนลงได้อย่างแม่นยำเราไม่จำเป็นต้องทำการอ่าน 324 ครั้งจากรอบการทำซ้ำเพียงเพื่อค้นหาการมาถึงครั้งแรกในวันที่ 13 สิงหาคม อย่างไรก็ตามเรายังคงต้องอ่านมากกว่า 100 แถวเพื่อตรวจสอบว่าแขกมาถึงโรงแรมด้วย HotelID
หรือไม่ ของ 3
.
เจ้าหน้าที่ตรวจสอบรอตลอดเวลา แต่คงไม่มีความสุข: แทนที่จะเป็นชื่อแขกและข้อมูลอื่น ๆ ที่เกี่ยวข้องเราส่งเฉพาะรายการ ID ที่ไม่มีความหมาย
เราจะกลับไปที่แง่มุมนั้นในภายหลังในซีรีส์ ก่อนอื่นเรามาหาวิธีเตรียมรายการให้เร็วขึ้น
เพื่อจัดเรียงแถวตาม HotelID
จากนั้น DateFrom
เราสามารถเลือกคอลัมน์ทั้งหมดจากนั้นใช้ตัวเลือกเมนู Google ชีต ข้อมูล→จัดเรียงช่วง .
-- Assumption: Sorted according to HotelID and DateFrom -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Find the first arrival at the hotel on 13th of August While HotelID = 3 and DateFrom <'2020-08-13' Read the next row -- Prepare the list While HotelID = 3 and DateFrom < '2020-08-15' Write down the ClientID Read the next row
เราต้องข้ามผู้มาถึง 338 คนแรกก่อนที่จะหาคนแรกไปที่โรงแรมของเรา หลังจากนั้นเราก็เดินทางมาถึงก่อนหน้านี้กว่า 103 คนเพื่อค้นหาคนแรกในวันที่ 13 สิงหาคม สุดท้ายเราคัดลอก 46 ค่าต่อเนื่องของ ClientID
ช่วยเราว่าในขั้นตอนที่สามเราสามารถคัดลอกบล็อกของ ID ที่ติดต่อกันได้ น่าเสียดายที่เราไม่สามารถข้ามไปยังแถวแรกจากบล็อกนั้นได้
ลองทำแบบฝึกหัดเดียวกันโดยใช้สเปรดชีตเรียงลำดับโดย HotelID
เท่านั้น.
อัลกอริทึมที่ใช้กับตารางเรียงลำดับโดย HotelID
มีประสิทธิภาพน้อยกว่าเมื่อเราเรียงลำดับตาม HotelID
และ DateFrom
(เพื่อให้):
-- Assumption: Sorted according to HotelID -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Prepare the list While HotelID = 3 If DateFrom between '2020-08-13' and '2020-08-14' Write down the ClientID Read the next row
ในกรณีนี้เราต้องอ่านจำนวนผู้โดยสารที่มาถึงโรงแรมทั้งหมด 166 คนด้วย a HotelID
ของ 3
และสำหรับแต่ละรายการเพื่อตรวจสอบว่า DateFrom
เป็นของช่วงเวลาที่ร้องขอ
มันสำคัญหรือไม่ว่าเราจะเรียงลำดับก่อนโดย HotelID
แล้ว DateFrom
หรือในทางกลับกัน? มาดูกันว่า: ลองเรียงลำดับก่อนโดย DateFrom
จากนั้นตาม HotelID
-- Assumption: Sorted according to DateFrom and HotelID -- Find the first arrival on 13th of August While DateFrom <'2020-08-13' Read the next row --Find the first arrival at the Hotel While HotelID < 3 and DateFrom '2020-08-14' or (DateFrom = '2020-08-14' and HotelID> 3)
เราค้นหาแถวแรกพร้อมวันที่ที่เกี่ยวข้องจากนั้นอ่านเพิ่มเติมจนกว่าเราจะพบการมาถึงโรงแรมครั้งแรก หลังจากนั้นสำหรับแถวจำนวนหนึ่งเงื่อนไขทั้งสองก็เป็นไปตามวันที่ที่ถูกต้องและโรงแรมที่เหมาะสม อย่างไรก็ตามหลังจากมาถึงโรงแรม 3 เราก็มาถึงโรงแรม 4, 5 และอื่น ๆ ในวันเดียวกัน หลังจากนั้นเราต้องอ่านแถวในวันถัดไปสำหรับโรงแรม 1 และ 2 อีกครั้งจนกว่าเราจะสามารถอ่านการมาถึงโรงแรมที่เราสนใจติดต่อกันได้
อย่างที่เราเห็นวิธีการทั้งหมดมีบล็อกข้อมูลที่ติดต่อกันเพียงชุดเดียวอยู่ตรงกลางของชุดแถวทั้งหมดซึ่งแสดงถึงข้อมูลที่ตรงกันบางส่วน แนวทางที่ 2 และ 4 เป็นแนวทางเดียวที่ตรรกะอนุญาตให้เราหยุดอัลกอริทึมทั้งหมดก่อนที่เราจะถึงจุดสิ้นสุดของการแข่งขันบางส่วน
Approach 4 มีข้อมูลที่ตรงกันทั้งหมดในสองบล็อก แต่ Approach 2 เป็นเพียงบล็อกเดียวที่ข้อมูลเป้าหมายอยู่ในบล็อกเดียวติดต่อกัน
โค้ชเปรียวคืออะไร
แนวทาง 1 | แนวทาง 2 | แนวทาง 3 | แนวทาง 4 | |
---|---|---|---|---|
แถวเริ่มต้นที่ข้ามได้ | 324 | 338 + 103 = 441 | 342 | 324 |
แถวผู้สมัครที่จะตรวจสอบ | 188 | 46 | 166 | 159 |
แถวที่ข้ามได้หลังจากหยุดอัลกอริทึม | 328 | 353 | 332 | 357 |
แถวที่ข้ามได้ทั้งหมด | 652 | 794 | 674 | 681 |
จากตัวเลขเป็นที่ชัดเจนว่าแนวทาง 2 มีข้อดีที่สุดในกรณีนี้
การทำแบบฝึกหัดเหล่านี้ควรทำให้ประเด็นต่อไปนี้ชัดเจน:
ตอนนี้สำเนาของตารางที่เรียงลำดับจะดูเหมือนดัชนีฐานข้อมูล บทความถัดไปใน คำอธิบายดัชนี SQL ปก การใช้ดัชนีพื้นฐาน . ขอบคุณที่อ่าน!
ดัชนีฐานข้อมูลเป็นโครงสร้างข้อมูลเสริมที่สำคัญซึ่งช่วยเร่งความเร็วในการดึงข้อมูล จำนวนข้อมูลที่เข้าถึงเพื่อดำเนินการสืบค้น SQL เป็นปัจจัยหลักที่ทำให้เวลาดำเนินการ การใช้ดัชนีที่ออกแบบมาอย่างดีช่วยลดปริมาณข้อมูลที่เข้าถึง
กรณีการใช้งานหลักคือแบบสอบถามที่ส่งคืนข้อมูลตามเงื่อนไขของประเภท 'ค่าคอลัมน์ระหว่าง X และ Y' ดัชนีบนคอลัมน์ช่วยให้ RDBMS ค้นหาแถวแรกที่ตรงตามเงื่อนไขได้อย่างรวดเร็วอ่านแถวต่อเนื่องจากช่วงที่กำหนดและหยุดโดยไม่จำเป็นต้องอ่านข้อมูลอื่น ๆ
ดัชนีสามารถแบ่งออกเป็นประเภทได้หลายวิธี: โครงสร้าง (B-tree, ตารางแฮช, ไบนารี, ที่เก็บคอลัมน์, ข้อความเต็ม ฯลฯ ) ไม่ว่าจะเป็นแบบคลัสเตอร์หรือไม่และแบ่งพาร์ติชันหรือไม่ (ในเครื่องทั่วโลกหรือ ไม่ใช่เลย). บางคนเก็บทั้งแถวบางส่วนเก็บค่าอนุพันธ์บางรายการเก็บสำเนาคอลัมน์แบบตรง
ดัชนีทั่วไปถูกนำมาใช้โดยใช้โครงสร้างต้นไม้ที่สมดุล ระดับลีฟของดัชนีจะเรียงตามค่าคอลัมน์ ดังนั้นเมื่อเราต้องการค้นหาแถวทั้งหมดที่มีค่าเฉพาะของคอลัมน์ที่จัดทำดัชนีเราสามารถค้นหาแถวแรกได้อย่างรวดเร็วและอ่านแถวที่ติดต่อกันตราบเท่าที่ตรงกับค่า
ดัชนีที่เหมาะสมสามารถลดปริมาณข้อมูลที่เข้าถึงโดยคำสั่ง SELECT ซึ่งเป็นปัจจัยหลักที่ทำให้เวลาดำเนินการสืบค้น
ฐานข้อมูลสมัยใหม่มักเก็บและเผยแพร่ข้อมูลจำนวนมาก เมื่อผู้ใช้พยายามดึงข้อมูลเพียงชิ้นเล็ก ๆ โดยไม่มีดัชนีที่เหมาะสมการดึงข้อมูล (จากเข็มในกองหญ้า) อาจใช้เวลาหลายชั่วโมง