ทำไมการใช้ index จึงทำให้ query ข้อมูลได้ไวขึ้น?

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

ในฐานข้อมูลการทำ index ก็จะทำให้กับ field หรือคอลัมน์ที่เรามีเงื่อนไขในการ query บ่อยๆ การดึงข้อมูลก็จะไปดูที่ index แล้วกระโดดไปยังตำแหน่งที่เก็บข้อมูลเลยโดยไม่ต้องค้นหาทุกแถวในตาราง

ตัวอย่างเช่น การทำ index ให้กับตาราง employees ที่คอลัมน์ emp_id

1	rowid
2	rowid
3	rowid
.	.
.	.
.	.

เมื่อมีการ query

SELECT *
FROM employees
WHERE emp_id = 3;

Database ก็จะวิ่งไปดึงข้อมูลยังตำแหน่งที่เก็บข้อมูลของ emp003 มาแสดง โดยที่ไม่ต้องวิ่งไปหาทุกๆ แถวในตาราง employees

Oracle Database มี Index อยู่หลายประเภทแต่ที่ถูกใช้กันทั่วไปคือ B-Tree Indexes

(รูปภาพจาก www.oracle.com)

จากรูปจะเห็นว่า B-tree Index นั้นมี block อยู่สองประเภทด้วยกันคือ Branch blocks ไว้สำหรับการค้นหา และ leaf blocks สำหรับเก็บค่า ในการค้นหาก็จะแบ่งเป็นช่วงๆ ตามขอบเขตแต่ละ block ทำให้การค้นหานั้นมีประสิทธิภาพ

ซึ่ง การใช้ index นั้น ยังมีรายละเอียดเสริมเพื่อเพิ่มความเข้าใจอีก โดย คุณ Siamnobita ได้อธิบายเกี่ยวกับ index ด้วยกัน 5 ข้อดังต่อไปนี้

1. สิ่งที่ทำให้เราสามารถค้นหาใน index ได้เร็วนั้นเนื่องจากมีการ sort ตามค่าในคอลัมน์ด้วย เคยมีคนตั้งคำถามใน narisa ประมาณว่าทำไม oracle ถึงไม่เรียงลำดับข้อมูลในตารางซะเลย จะได้ไม่ต้องใช้ index คำตอบก็คือการจัดเก็บแบบเรียงลำดับนั้นทำได้ยากกว่าและเกิดต้นทุนตามมาเช่น เวลาที่ใช้เมื่อมีการเพิ่ม record ใหม่ พื้นที่ว่างเมื่อเกิดการ split block เป็นต้น อย่างไรก็ดีหากเราไม่มีปัญหากับต้นทุนเหล่านี้ เราก็สามารถจัดเก็บข้อมูลในตารางแบบเรียงลำดับได้เลย นั่นคือใช้ index-organized table (IOT) ซึ่งถือเป็นวิธีที่เร็วที่สุดในการค้นหาข้อมูลตาม primary key

2. ปกติเวลา oracle อ่านข้อมูลจะอ่านทีละ block ไม่ใช่ทีละแถว ดังนั้นจะดูว่าเร็วหรือช้า จะนับจากว่า oracle ต้อง access ข้อมูลจำนวนกี่ block เช่น

ถ้าดูจากรูปด้านบน index มี 3 level
เมื่อเรา select * from ... where index_column = ??
oracle จะอ่านข้อมูลทั้งสิ้น 4 block คือ root block ตัวบนสุด, branch block ตัวกลาง, leaf block ตัวล่างสุด, table block ซึ่งรู้ได้ทันทีเมื่อรู้ค่า rowid จำนวน level ที่น้อยที่สุดที่เป็นไปได้คือ 1 level คือเก็บ rowid ไว้ใน root block เลย ซึ่งจะเกิดในกรณีที่ข้อมูลมีจำนวนไม่มาก ( โดย default ขนาดของ block ประมาณ 8K )

3. คำถามคือ หากข้อมูลมีขนาดเล็ก ๆ เช่น ตารางมีขนาดแค่ block เดียว การใช้ index ยังมีประโยชน์อยู่หรือไม่ เดิมผมเคยเข้าใจว่าไม่มีประโยชน์เหมือนกัน แต่เมื่อได้อ่าน blog ของคุณ richard foote ซึ่งทำการทดสอบให้เห็นชัด ๆ ไปเลย พบว่า index ก็ยังมีประโยชน์อยู่ดี เนื่องจาก

3.1 ในการ full table scan นอกจากตัว block ที่เก็บ data แล้วยังต้องอ่าน header block ด้วยจึงมี cost ที่เกิดขึ้นไม่ใช่แค่ 1 I/O เมื่อเทียบกับ index ที่ใช้ 2 I/O (root block + data block) ก็พอ ๆ กัน

3.2 ในการ full table scan จะเก็บ data ที่อ่านมาบน buffer cache ด้าน LRU ซึ่งจะอยู่ใน memory ได้ไม่นาน ขณะที่ index scan จะวางไว้ด้าน MRU ทำให้มีโอกาสใช้ประโยชน์จากการอ่านจาก memory โดยตรงได้มากกว่า โดยเฉพาะเมื่อมีการเรียกใช้ข้อมูลจาก table บ่อย ๆ

4. ในข้อ 3 เขาทดสอบเฉพาะกรณี index unique scan เช่นค้นตาม primary key เท่านั้น หากเป็น index range scan จะเป็นอีกกรณีหนึ่ง ซึ่งทุก rowid ที่เจอใน index ก็จะต้องมีการ access table block หนึ่งครั้ง แม้ว่า block นั้นจะอยู่บน memory แล้วก็ยังเป็น cost อยู่ดี ดังนั้น full table scan ก็อาจจะคุ้มกว่าขึ้นกับจำนวนแถวที่ต้องการ

5. ประโยชน์ของ index อีกข้อ คือโดยปกติจำนวน column ใน index จะน้อยกว่า column ใน table มาก ๆ ดังนั้นขนาดของ index ก็จะเล็กกว่า table มาก ๆ ด้วย หากเราต้องการดูเฉพาะข้อมูลที่อยู่ใน index อยู่แล้ว เราก็อาจ full scan ที่ index แทน table ไปเลยก็ได้ ซึ่งกรณีนี้จะเป็นการ fast full scan ซึ่งอ่าน index แบบ multi block เหมือน table scan ( full scan ใน index มี 2 แบบ full scan เฉย ๆ กับ fast full scan แบบแรกอ่านทีละ block ซึ่งช้ากว่า แต่ข้อดีคือ ผลลัพธ์มีการ sort ตาม index แบบหลังจะไม่มีการเรียงลำดับ

ปล. ต้องขอบคุณคำอธิบายดี ๆ จาก คุณ Siamnobita มาก ๆ ครับ

Credit by Paley (@ratipong)

อ้างอิง