B-tree และพื้นฐานของ index

บทเรียนก่อนหน้านี้แสดงให้เห็น ว่าทำไม index ถึงช่วยได้ บทนี้จะแสดงให้เห็น ว่าสร้างอย่างไร และชนิดไหนที่คุณแทบจะต้องใช้เสมอ PostgreSQL รองรับ index หลายชนิด แต่มีอยู่ชนิดหนึ่งที่เป็นค่าเริ่มต้นและเป็นคำตอบที่ถูกต้องสำหรับกรณีส่วนใหญ่อย่างท่วมท้น นั่นคือ B-tree

เราจะใช้ table books จากโมดูล CRUD ต่อไป

การสร้าง index

รูปแบบพื้นฐานคือระบุชื่อ table และ column หรือหลาย ๆ column ที่จะทำ index PostgreSQL จะเลือกชื่อให้คุณ หรือคุณจะตั้งชื่อเองก็ได้

psql

-- let PostgreSQL name it
CREATE INDEX ON books (title);

-- or name it yourself
CREATE INDEX books_title_idx ON books (title);

Node.js

await pool.query('CREATE INDEX books_title_idx ON books (title)');

Python

cur.execute("CREATE INDEX books_title_idx ON books (title)")

Go

_, err := conn.Exec(ctx, "CREATE INDEX books_title_idx ON books (title)")

Rust

sqlx::query("CREATE INDEX books_title_idx ON books (title)")
    .execute(&pool)
    .await?;

เนื่องจากไม่ได้ระบุชนิดของ index PostgreSQL จึงสร้าง B-tree การเขียน CREATE INDEX ... USING btree (title) ก็ให้ผลเทียบเท่ากันทุกประการ — USING btree คือค่าเริ่มต้นที่ถูกใช้อย่างเงียบ ๆ

ใน pgAdmin: ขยาย table ในแผนผัง (browser tree) คลิกขวาที่ Indexes แล้วเลือก Create กล่องโต้ตอบจะให้คุณเลือก column และ access method และแสดง SQL ที่ถูกสร้างขึ้นบนแท็บ SQL

B-tree ทำอะไรได้บ้าง

B-tree เก็บรายการทั้งหมดไว้ในลำดับที่เรียงแล้ว และนั่นเองที่ทำให้ใช้งานได้หลากหลาย เพราะค่าต่าง ๆ ถูกเรียงลำดับไว้ index จึงสามารถตอบ query ใด ๆ ที่ขึ้นอยู่กับลำดับนั้นได้:

รูปแบบ query	ตัวอย่าง	B-tree ช่วยไหม?
Equality	WHERE title = 'Quiet Harbors'	ใช่
Range	WHERE published > 2000	ใช่
Between	WHERE published BETWEEN 1990 AND 2000	ใช่
Sorting	ORDER BY published	ใช่
Prefix match	WHERE title LIKE 'The %'	ใช่
Leading wildcard	WHERE title LIKE '%orchard'	ไม่

สอง row สุดท้ายคือประเด็นสำคัญ B-tree สามารถจัดการ LIKE 'The %' ได้เพราะการค้นหายึดไว้ที่จุดเริ่มต้นของค่า แต่ช่วย LIKE '%orchard' ไม่ได้ เพราะ leading wildcard หมายความว่าค่าที่ตรงเงื่อนไขกระจัดกระจายอยู่ทั่วทั้งลำดับที่เรียงไว้ ไม่ได้ถูกจัดกลุ่มไว้ด้วยกัน

composite index และกฎ left-prefix

index หนึ่งตัวสามารถครอบคลุมได้มากกว่าหนึ่ง column index แบบ composite (หรือ multicolumn) เช่นนี้จะเรียงลำดับตาม column แรก จากนั้นจึงเรียงตาม column ที่สองภายในแต่ละค่าของ column แรก ไล่ไปเรื่อย ๆ

psql

CREATE INDEX books_author_published_idx
  ON books (author_id, published);

Node.js

await pool.query(
  'CREATE INDEX books_author_published_idx ON books (author_id, published)',
);

Python

cur.execute(
    "CREATE INDEX books_author_published_idx ON books (author_id, published)"
)

Go

_, err := conn.Exec(ctx,
    "CREATE INDEX books_author_published_idx ON books (author_id, published)")

Rust

sqlx::query(
    "CREATE INDEX books_author_published_idx ON books (author_id, published)",
)
.execute(&pool)
.await?;

ลำดับของ column มีความสำคัญเพราะ กฎ left-prefix: composite index สามารถถูกใช้ได้กับ query ที่กรองด้วย prefix นำหน้า ของ column ในนั้น index บน (author_id, published) ช่วย query เหล่านี้:

-- uses the index: filters on the leading column
SELECT * FROM books WHERE author_id = 4;

-- uses the index: filters on both columns
SELECT * FROM books WHERE author_id = 4 AND published > 2000;

แต่ index ตัวนี้ ไม่ ช่วย query ข้างล่างอย่างมีประสิทธิภาพ เพราะ published ไม่ใช่ column นำหน้า:

-- the index cannot be used as a simple lookup here
SELECT * FROM books WHERE published > 2000;

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

unique index

การเพิ่ม UNIQUE ทำให้ index บังคับด้วยว่าจะไม่มีสอง row ที่มีค่าเดียวกัน นี่เป็นทั้งโครงสร้างเพื่อประสิทธิภาพและกฎความถูกต้องของข้อมูล (data integrity)

psql

CREATE UNIQUE INDEX books_isbn_idx ON books (isbn);

Node.js

await pool.query('CREATE UNIQUE INDEX books_isbn_idx ON books (isbn)');

Python

cur.execute("CREATE UNIQUE INDEX books_isbn_idx ON books (isbn)")

Go

_, err := conn.Exec(ctx, "CREATE UNIQUE INDEX books_isbn_idx ON books (isbn)")

Rust

sqlx::query("CREATE UNIQUE INDEX books_isbn_idx ON books (isbn)")
    .execute(&pool)
    .await?;

หลังจากนี้ INSERT หรือ UPDATE ที่จะสร้าง isbn ซ้ำกันจะล้มเหลวด้วย error การละเมิดความเป็น unique การกำหนด column เป็น PRIMARY KEY หรือ UNIQUE ในการนิยาม table จะสร้าง index แบบนี้ให้อัตโนมัติอยู่แล้ว จึงเป็นเหตุผลที่การค้นหาด้วย primary key เร็วตั้งแต่แรกโดยคุณไม่ต้องทำอะไรเลย

คุณสามารถยืนยันว่า index เหล่านี้มีอยู่ได้ด้วย \d books ใน psql ซึ่งจะแสดงรายการ column ของตามด้วย index ของ table

Indexes:
    "books_pkey" PRIMARY KEY, btree (id)
    "books_author_published_idx" btree (author_id, published)
    "books_isbn_idx" UNIQUE, btree (isbn)
    "books_title_idx" btree (title)

เคล็ดลับและข้อควรระวัง

• B-tree คือค่าเริ่มต้นและเป็นตัวเลือกที่ถูกต้องสำหรับเกือบทุกอย่าง ทั้ง equality, range, การ sort และ prefix match จงหันไปใช้ชนิดอื่นเฉพาะเมื่อ B-tree ทำงานนั้นไม่ได้จริง ๆ เท่านั้น
• index ทุกตัวทำให้การเขียนช้าลงและใช้พื้นที่ดิสก์ เพราะแต่ละ INSERT, UPDATE และ DELETE ต้องคอยดูแล index ทุกตัว อย่าสร้าง index ให้ทุก column
• สำหรับ composite index จงวาง column ที่เลือกเฉพาะเจาะจงที่สุดและถูกกรองบ่อยที่สุดไว้ก่อน และอย่าลืมกฎ left-prefix เมื่อตัดสินใจเรื่องลำดับของ column
• composite index ที่ถูกเลือกมาอย่างดีเพียงตัวเดียวสามารถแทนที่ index column เดียวหลาย ๆ ตัวได้ แต่ก็ทดแทนไม่ได้เมื่อ query ของคุณกรองด้วย column ที่ตามหลังเพียงอย่างเดียว
• การสร้าง index บน table ขนาดใหญ่ที่มีงานคึกคักจะ lock table นั้นไม่ให้เขียน จงใช้ CREATE INDEX CONCURRENTLY ในงาน production เพื่อหลีกเลี่ยงการบล็อก โดยแลกกับการสร้างที่ช้าลง

🐘 ทำ index ให้กับ query ที่คุณใช้งานจริง

อย่าทำ index แบบคาดเดา จงดูที่ส่วน WHERE, JOIN และ ORDER BY ที่แอปพลิเคชันของคุณใช้งานจริง ๆ แล้วจึงเพิ่ม B-tree index ที่รองรับสิ่งเหล่านั้น index ที่ไม่มีใครใช้คือภาระล้วน ๆ เพราะเสียต้นทุนทุกครั้งที่เขียน แต่ไม่ได้คืนอะไรให้เลยตอนอ่าน

ข้อแลกเปลี่ยน

ตัวเลือก	Benefit	Cost
เพิ่ม index ใหม่	SELECT/WHERE/JOIN ที่ตรงกับ column นั้นเร็วขึ้นมาก	ทุก INSERT, UPDATE, DELETE ต้อง update index ด้วย เขียนช้าลงและใช้พื้นที่ดิสก์เพิ่ม
ไม่เพิ่ม index (พึ่ง seq scan)	เขียนเร็ว ไม่มี index ให้ดูแล	อ่านช้าลงเมื่อ table โตขึ้น โดยเฉพาะ query ที่เลือกเฉพาะเจาะจง
CREATE INDEX ธรรมดา	สร้างเร็วกว่า	lock table ไม่ให้เขียนระหว่างสร้าง
CREATE INDEX CONCURRENTLY	ไม่ lock การเขียนระหว่างสร้าง	สร้างช้ากว่าและใช้ทรัพยากรมากกว่า อาจล้มเหลวและทิ้ง index ที่ invalid ไว้

ข้อผิดพลาดที่พบบ่อย

• ทำ index ให้ทุก column “เผื่อไว้” — ทุก index ที่ไม่ถูกใช้งานจริงยังคงสร้างต้นทุนกับทุกการเขียน จงดูที่ WHERE, JOIN และ ORDER BY ที่แอปพลิเคชันใช้งานจริงก่อนเพิ่ม index
• ไม่เคยลบ index ที่ไม่ได้ใช้ — index เก่าที่ไม่มี query ไหนพึ่งพาแล้วยังคงกินพื้นที่และทำให้การเขียนช้าลงต่อไปเรื่อย ๆ จงตรวจสอบด้วย pg_stat_user_indexes เป็นระยะแล้วพิจารณา drop ตัวที่ไม่ถูกใช้
• สร้าง index บน table ขนาดใหญ่ที่ใช้งานจริงโดยไม่ใช้ CONCURRENTLY — CREATE INDEX ธรรมดาจับ lock ที่บล็อกการเขียนตลอดการสร้าง บน table ใหญ่นั่นอาจหมายถึงดาวน์ไทม์ยาวนาน ใน production จงใช้ CREATE INDEX CONCURRENTLY เสมอ

💡 ตัวอย่างจากของจริง

GitLab — ทีม database ของ GitLab มีกระบวนการ review index อย่างเป็นทางการก่อน merge index ใหม่เข้า production เพราะ index ที่ไม่ถูกใช้งานสร้างต้นทุนต่อการเขียนและพื้นที่เก็บข้อมูลอย่างเงียบ ๆ โดยไม่มีใครสังเกต

pganalyze — เครื่องมือ monitoring อย่าง pganalyze ถูกสร้างขึ้นมาเพื่อช่วยหาปัญหา index bloat และ index ที่ไม่ถูกใช้งานโดยเฉพาะ ทำให้ทีมเห็นได้ชัดว่า index ตัวไหนควรเก็บไว้และตัวไหนควร drop

CREATE INDEX สร้าง index ชนิดใดเมื่อคุณไม่ได้ระบุชนิด?

Hash GIN B-tree BRIN

index บน (author_id, published) สามารถรองรับ query ใดได้อย่างมีประสิทธิภาพ?

WHERE published > 2000 WHERE author_id = 4 WHERE title LIKE '%orchard' ไม่มีข้อใดเลย

การเพิ่ม UNIQUE ให้ index ทำอะไรเพิ่มเติมนอกเหนือจากการเร่งความเร็วการค้นหา?

บีบอัด index ป้องกันไม่ให้สอง row มีค่าที่ทำ index เดียวกัน ทำให้การเขียนเร็วขึ้น ทำให้ค้นหา LIKE แบบ leading-wildcard ได้

Submit

Mark as complete