Index และการจัดเรียงการ์ด

สิ่งที่จะสร้าง

TaskFlow ให้ผู้ใช้ลากการ์ดขึ้นลงในคอลัมน์ และลากคอลัมน์ซ้ายขวา ทุกการเคลื่อนไหวนั้นต้องบันทึก ลำดับ ลงฐานข้อมูลที่คงอยู่หลังรีโหลดและคงเส้นคงวาข้ามทุก client ที่เชื่อมต่ออยู่ บทเรียนนี้อธิบายกลยุทธ์ที่เราเลือก — คอลัมน์ position double precision — วิธีคำนวณตำแหน่งใหม่ตอน insert และ reorder กลยุทธ์นี้เสื่อมลงได้อย่างไรในที่สุด วิธีแก้ และ index สองตัวที่ทำให้ทั้งระบบเร็ว

ทำไม

วิธีที่ตรงไปตรงมาที่สุดคือเก็บ position เป็นเลขจำนวนเต็ม 0, 1, 2, 3 บนแต่ละการ์ด อ่านดูสวยดี แต่พังลงกับปฏิบัติการที่ Kanban ทำบ่อยที่สุด: การจัดเรียงใหม่ (reorder) ลองวางการ์ดไว้ระหว่างตำแหน่ง 1 กับ 2 ดู จะเห็นว่าไม่มีจำนวนเต็มระหว่างสองค่านั้น — คุณต้องไล่เลขลำดับใหม่ให้ทุกการ์ดที่อยู่ข้างใต้ แล้วเขียนแถวเหล่านั้นกลับทั้งหมด บนบอร์ดที่คึกคัก การลากครั้งเดียวกลายเป็นพายุของการอัปเดต และในแอปเรียลไทม์ ทุกอัปเดตนั้นกระจายออกไปยังทุก client ที่เชื่อมต่ออยู่

เราต้องการสิ่งตรงกันข้าม: การ reorder ควรแตะ แถวเดียว เคล็ดลับคือหยุดคิดว่าตำแหน่งเป็นจำนวนเต็มต่อเนื่อง แล้วเริ่มมองเป็นจุดบนเส้นจำนวนแทน ระหว่างจำนวนจริงสองค่าที่ต่างกันมีจำนวนจริงอีกค่าเสมอ ดังนั้นจึงมีที่ว่างให้เสียบการ์ดระหว่างเพื่อนบ้านสองตัวเสมอโดยไม่รบกวนใคร นั่นคือเหตุผลที่ columns.position และ cards.position เป็น double precision (float 64 บิต) ไม่ใช่จำนวนเต็ม

ข้อดีข้อเสีย

ตำแหน่งเศษส่วน double precision (สิ่งที่เราใช้)

• ข้อดี: การ reorder หรือ insert เขียนแค่แถวเดียว; ไม่มี cascade การเลขลำดับใหม่; คิวรีง่ายมาก (order by position); ใช้ได้เหมือนกันทั้งคอลัมน์และการ์ด
• ข้อเสีย: float มีความละเอียดจำกัด ดังนั้นการ insert ระหว่างเพื่อนบ้าน คู่เดิม ซ้ำ ๆ ในที่สุดจะหมดค่าที่แทนได้และบังคับให้ต้อง renormalize; ตำแหน่งไม่ใช่สิ่งที่มนุษย์อ่านได้; และ client สองตัวที่ insert ที่จุดเดียวกันพร้อมกันอาจลงเอยใกล้กันมาก

ตำแหน่งแบบเว้นช่องจำนวนเต็ม (เว้นช่อง: 10, 20, 30…)

• ข้อดี: มนุษย์อ่านได้ และคุณได้การแทรกฟรีสองสามครั้งระหว่างรายการก่อนต้องเลขลำดับใหม่
• ข้อเสีย: ช่องว่างมีจำกัด — พอใช้หมดระหว่างสองรายการ ก็ต้องกลับไปไล่เลขลำดับใหม่ให้ทั้งช่วงอยู่ดี วิธีนี้แค่เลื่อนปัญหาที่ตำแหน่งเศษส่วนเลี่ยงได้ทั้งหมดออกไปเท่านั้น

ลำดับแบบ array / linked-list (เก็บลำดับทั้งหมดไว้ที่เดียว)

• ข้อดี: ลำดับชัดเจนไม่กำกวม; array board.column_order เดียวหรือ pointer next_card_id นิยามลำดับได้เป๊ะ
• ข้อเสีย: array ลำดับเป็นจุด contention — ทุกการ reorder เขียนแถวใหญ่หนึ่งแถวใหม่ ซึ่งทำให้การแก้ไขพร้อมกันเป็นแบบอนุกรมและขัดกับโมเดลเรียลไทม์; linked list ต้องอัปเดตหลายแถวต่อการย้ายและ sort ใน SQL ยาก ทั้งคู่ไม่เหมาะกับบอร์ดที่ทำงานร่วมกันซึ่งหลายคน reorder พร้อมกัน

ตำแหน่งเศษส่วนให้เราการเขียนแถวเดียวและการ sort ที่ง่าย แลกกับการทำความสะอาดเป็นครั้งคราว สำหรับบอร์ดเรียลไทม์ นั่นคือการแลกที่คุ้ม

ลงมือสร้าง

กฎเหมือนเดิมเสมอ: ตำแหน่งใหม่ของการ์ดคือจำนวนที่จัดเรียงการ์ดไว้ตรงจุดที่ผู้ใช้ปล่อย มีสามกรณี

แทรกระหว่างการ์ดสองใบ

เฉลี่ยตำแหน่งของการ์ดที่อยู่เหนือและการ์ดที่อยู่ใต้จุดปล่อย:

new_position = (before.position + after.position) / 2

ถ้าการ์ดด้านบนมี position = 2.0 และการ์ดด้านล่างมี position = 3.0 การ์ดที่ปล่อยลงจะได้ 2.5 ปล่อยการ์ดอีกใบระหว่าง 2.0 กับ 2.5 ค่าก็จะเป็น 2.25 และมีเพียงแถวของการ์ดใบนั้นใบเดียวที่ต้องเขียน

แทรกที่ปลายสุด

ไม่มีเพื่อนบ้านด้านหนึ่ง จึงก้าวข้ามค่าสุดขั้วที่มีอยู่ไปด้วยจำนวนคงที่

ปล่อยที่ ด้านบน ของคอลัมน์ ก่อนการ์ดใบแรกปัจจุบัน:

new_position = first.position - 1.0

ปล่อยที่ ด้านล่าง หลังการ์ดใบสุดท้ายปัจจุบัน:

new_position = last.position + 1.0

การ์ดใบแรกของคอลัมน์ว่างเปล่ารับ position = 1.0 ไปได้เลย คอลัมน์บนบอร์ดทำงานเหมือนกันเป๊ะ จัดเรียงจากซ้ายไปขวาด้วย columns.position

ข้อควรระวังเรื่อง float-precision หมด

float 64 บิตมีเลขนัยสำคัญราว 15–17 หลักฐานสิบ ทุกครั้งที่คุณ insert ระหว่างเพื่อนบ้าน คู่เดิม ช่องว่างจะลดครึ่ง: 2.5, 2.25, 2.125, 2.0625… หลังจากราว 50 ครั้งของการ insert ต่อเนื่องเข้าไปในช่องว่างที่หดเดิม ตำแหน่งเพื่อนบ้านสองค่าจะใกล้กันมากจน float แทนค่าที่อยู่ระหว่างกลางไม่ได้อีก — ค่าเฉลี่ยปัดไปเท่ากับปลายด้านหนึ่ง และลำดับของการ์ดใหม่ก็กำกวม ในการใช้งานประจำวันไม่มีใครลากเข้าจุดเดียวกัน 50 ครั้งติด แต่ schema ที่คุณไม่ต้องคอยดูแลก็คุ้มค่าที่จะออกแบบเผื่อ

การ renormalize เป็นระยะ

วิธีแก้คือ pass ทำความสะอาดที่กระจายทุกอย่างกลับออกไป เป็นระยะ — เช่น เมื่อช่องว่างที่เล็กที่สุดในคอลัมน์ต่ำกว่าเกณฑ์ หรือในงานตอนกลางคืน — กำหนดตำแหน่งที่สะอาดและเว้นระยะเท่ากันใหม่ในลำดับที่มองเห็นปัจจุบัน:

-- Renormalize one column's cards to 1.0, 2.0, 3.0, ...
with ordered as (
    select id,
           row_number() over (order by position) as rn
    from cards
    where column_id = $1
)
update cards
set position = ordered.rn
from ordered
where cards.id = ordered.id;

หลังคำสั่งนี้รัน การ์ดกลับเป็น 1.0, 2.0, 3.0, … อีกครั้ง ดังนั้นทุกช่องว่างกว้างเต็ม 1.0 และงบการหารครึ่งรีเซ็ต ลำดับที่มองเห็นไม่เปลี่ยน — เปลี่ยนแค่ตัวเลขเบื้องหลัง ทำแบบเดียวกันต่อบอร์ดสำหรับ columns.position เมื่อจำเป็น

ตรวจสอบผล

คิวรีที่ทำให้การจัดเรียงรู้สึกทันใจพึ่ง index สองตัวจาก 0001_init.sql

cards(column_id, position)

create index on cards(column_id, position);

การเรนเดอร์คอลัมน์คือ “ขอการ์ดทุกใบในคอลัมน์นี้ ตามลำดับ” พอดี:

select * from cards where column_id = $1 order by position;

composite index นี้รองรับทั้งสองครึ่งของคิวรีนั้นพร้อมกัน: column_id นำหน้าจำกัดให้เหลือคอลัมน์เดียว และ position ตามหลังทำให้แถวกลับมาเรียงไว้แล้ว — PostgreSQL อ่านตรงจาก index ได้เลย โดยไม่มีขั้นตอน sort แยก ยืนยันด้วย:

psql "$DATABASE_URL" -c 'explain select * from cards where column_id = gen_random_uuid() order by position;'

บนตารางที่มีข้อมูล แผนจะใช้ Index Scan บน cards_column_id_position_idx และไม่แสดง node Sort

board_members(user_id)

create index on board_members(user_id);

เส้นทาง authorization ถามคำถามกลับด้าน: “ผู้ใช้คนนี้เป็นสมาชิกบอร์ดไหนบ้าง” — ใช้ในเกือบทุก API request เพื่อตรวจสิทธิ์การเข้าถึง

select board_id from board_members where user_id = $1;

composite primary key (board_id, user_id) จัดเรียงเอา board ก่อน จึงตอบการค้นหาที่มีแค่ user_id อย่างมีประสิทธิภาพไม่ได้ index เฉพาะบน user_id นี้ทำให้การตรวจสมาชิกต่อ request เป็น index scan แทนที่จะเป็นการสแกนทั้งตาราง

สรุป

คุณได้เรียนรู้ว่าทำไม TaskFlow เก็บลำดับเป็น position แบบ double precision แทนจำนวนเต็มต่อเนื่อง: การ reorder เขียนแถวเดียว คุณคำนวณตำแหน่งใหม่ด้วยการเฉลี่ยเพื่อนบ้าน หรือก้าว ±1.0 ข้ามปลายสุด คุณเข้าใจว่าการแบ่งครึ่งช่องว่างเดิมซ้ำ ๆ ทำให้ float precision หมดในที่สุด และแก้ได้ด้วยการ renormalize เป็นระยะกลับไปเป็น 1.0, 2.0, 3.0… คุณยังได้เห็นว่าทำไม cards(column_id, position) รองรับการอ่านคอลัมน์แบบเรียงลำดับโดยไม่มีขั้นตอน sort และทำไม board_members(user_id) ขับเคลื่อนการตรวจสมาชิกต่อ request สิ่งนี้จบโมดูลฐานข้อมูล — ต่อไป Backend Foundations เชื่อม schema นี้เข้ากับ Rust