การเพิ่มประสิทธิภาพงาน Graph: ตั้งแต่การเลือก Algorithm จนถึงการจัดวาง Memory

Graph มีอยู่ทุกที่ในระบบ backend ไม่ว่าจะเป็นความสัมพันธ์ในโซเชียล เครือข่ายถนน dependency ของ package ลำดับชั้นของสิทธิ์การเข้าถึง หรือเครือข่ายธุรกรรมสำหรับตรวจจับการทุจริต และมันก็เป็นต้นเหตุของประสิทธิภาพที่ร่วงแบบหน้าผาด้วย query ที่รันได้ใน 5ms บนข้อมูลทดสอบ อาจใช้เวลาถึง 40 วินาทีบน production เพียงเพราะมี node "คนดัง" ตัวหนึ่งที่มี edge สองล้านเส้น

การเพิ่มประสิทธิภาพงาน graph เกิดขึ้นได้ในสามระดับ: การเลือก algorithm, การเก็บข้อมูล และ การจำกัดขอบเขตการค้นหา

ระดับที่ 1: เลือก algorithm ให้ตรงกับคำถาม

ฟีเจอร์ graph ที่ช้าจำนวนมากใช้ algorithm แบบอเนกประสงค์ ในจุดที่ algorithm เฉพาะทางซึ่งถูกกว่าก็ทำได้เหมือนกัน

ข้อสังเกตที่เจอบ่อย:

• อย่ารัน Dijkstra บน graph ที่ไม่มีน้ำหนัก BFS ธรรมดาให้คำตอบเดียวกันโดยไม่มี overhead ของ heap
• ค้นหาจากทั้งสองฝั่ง Bidirectional BFS หรือ Dijkstra จะขยายการค้นหาจากทั้งต้นทางและปลายทางพร้อมกัน แล้วหยุดเมื่อ frontier ของทั้งสองฝั่งมาบรรจบกัน เนื่องจาก frontier โตแบบ exponential ตามความลึก การค้นหาสองครั้งที่ลึก d/2 จึงถูกกว่าการค้นหาครั้งเดียวที่ลึก d อย่างมาก
• ใช้ A* เมื่อมีข้อมูลเชิงเรขาคณิต ในการหาเส้นทางบนถนนหรือ grid ระยะทางเส้นตรงเป็น admissible heuristic ที่ช่วยบังคับทิศการค้นหาให้มุ่งไปยังเป้าหมาย และข้ามส่วนใหญ่ของ graph ไปได้

A* แบบสั้น ๆ

import heapq

def a_star(graph, start, goal, h):
    open_heap = [(h(start), 0, start)]
    best = {start: 0}
    parent = {}
    while open_heap:
        _, g, node = heapq.heappop(open_heap)
        if node == goal:
            return reconstruct(parent, goal)
        if g > best.get(node, float("inf")):
            continue  # stale heap entry
        for nxt, w in graph[node]:
            ng = g + w
            if ng < best.get(nxt, float("inf")):
                best[nxt] = ng
                parent[nxt] = node
                heapq.heappush(open_heap, (ng + h(nxt), ng, nxt))
    return None

เงื่อนไข if g > best[...] มีความสำคัญ แทนที่จะ implement decrease-key เราใส่ entry ซ้ำลงไปใน heap แล้วข้ามตัวที่ล้าสมัยเมื่อ pop ออกมา วิธีนี้ง่ายกว่าและมักเร็วกว่า heap ที่รองรับการอัปเดตค่า

ระดับที่ 2: เก็บ graph ให้เหมาะกับลักษณะงาน

Adjacency matrix กับ adjacency list

• Adjacency matrix ใช้ memory O(V²) เหมาะเฉพาะกับ graph ขนาดเล็กที่หนาแน่น ซึ่งการเช็ก edge ได้ในเวลาคงที่คุ้มค่ากับพื้นที่ที่เสียไป
• Adjacency list ใช้ O(V + E) เป็นตัวเลือกเริ่มต้นสำหรับ graph ในโลกจริง ซึ่งแทบทั้งหมดเป็น graph แบบ sparse

Compressed Sparse Row (CSR)

List ซ้อน list ([][]int ใน Go หรือ list ของ list ใน Python) ทำให้ edge กระจัดกระจายอยู่ทั่ว heap การ traverse จึง miss CPU cache อยู่ตลอด CSR จะอัด edge ทั้งหมดลงใน array แบนราบสองตัว:

offsets: [0, 2, 5, 6, 8]        # node i's edges live in edges[offsets[i]:offsets[i+1]]
edges:   [1, 2, 0, 2, 3, 3, 0, 1]
weights: [4, 1, 4, 2, 5, 1, 3, 2]

ข้อดี:

• Memory ต่อเนื่องกัน การ traverse จึงไหลผ่าน cache ได้ลื่น
• เล็กกว่าโครงสร้างที่ใช้ pointer อย่างมาก
• Memory-map จาก disk และแชร์ระหว่าง process ได้ง่าย

ข้อแลกเปลี่ยนคือ CSR แก้ไขได้แพง รูปแบบที่นิยมคือ rebuild snapshot ของ CSR เป็นระยะ และเก็บการเปลี่ยนแปลงล่าสุดไว้ในโครงสร้างเสริมขนาดเล็กที่ query ต้องเช็กควบคู่กันไปด้วย

เปลี่ยนเลข node ใหม่

ถ้า ID ของ node เป็น UUID หรือ string ให้ map เป็นจำนวนเต็มแบบต่อเนื่อง 0..V-1 ตอนโหลดข้อมูล ID ที่เป็นจำนวนเต็มทำให้ใช้ array indexing ได้ (แทนการ lookup ใน hash) และทำให้ทุก edge เล็กลง การเรียงลำดับ node ให้เพื่อนบ้านได้ ID ที่ใกล้กัน เช่น เรียงตามลำดับ BFS หรือเรียงตาม community จะช่วยให้ cache locality ดีขึ้นไปอีก

ระดับที่ 3: จำกัดพื้นที่การค้นหา

การ traverse ที่เร็วที่สุดคือการ traverse ที่ไปเยี่ยม node น้อยที่สุด

• จำกัดความลึก "เพื่อนของเพื่อน" หมายถึงความลึก 2 ให้บังคับขอบเขตนี้ไว้ใน query แทนการกรองผลลัพธ์ทีหลัง
• กรองตั้งแต่เนิ่น ๆ ใช้เงื่อนไขกับ edge และ node (ประเภทของ edge, ช่วงเวลา, สถานะ active) ระหว่าง การ traverse ไม่ใช่หลังจากนั้น
• จัดการ supernode Node ที่มี degree มหาศาล เช่น บัญชียอดนิยมหรือหมวดหมู่ค่าเริ่มต้น ทำให้ต้นทุนการ traverse พุ่งสูง ให้จำกัดจำนวนเพื่อนบ้านที่จะขยาย สุ่มตัวอย่าง หรือจัดการ node เหล่านี้เป็นกรณีพิเศษ
• คำนวณล่วงหน้าสิ่งที่ไม่ค่อยเปลี่ยน เครือข่ายถนนใช้ contraction hierarchies ซึ่งเพิ่ม edge ทางลัดไว้ล่วงหน้า ทำให้ตอบเส้นทางระดับทวีปได้ในระดับมิลลิวินาที ส่วนระบบแนะนำจะคำนวณชุด candidate แบบ offline แล้วค่อยจัดอันดับแบบ online
• Cache subgraph ที่ถูกใช้บ่อย ถ้า 80% ของ query แตะย่านเดิม ๆ ให้เก็บส่วนนั้นไว้ใน memory ใกล้กับแอปพลิเคชัน

Graph database: การปรับแต่ง query

Graph database แบบ native เก็บ adjacency ไว้โดยตรง การเดินตาม edge จึงมีต้นทุนแค่การกระโดดตาม pointer แทนการ join แต่ก็ยังต้องปรับแต่งอยู่ดี

ยึดจุดเริ่ม traversal ด้วย index

Query ควรเริ่มจากชุด node ขนาดเล็กที่มี index:

// Slow: scans every Person node looking for a match
MATCH (p:Person)-[:FOLLOWS]->(f)
WHERE p.email = '[email protected]'
RETURN f

// Fix: create an index so the start node is found directly
CREATE INDEX person_email FOR (p:Person) ON (p.email);

กำหนดขอบเขตให้ path ที่มีความยาวแปรผัน

// Dangerous: unbounded, can explore the whole graph
MATCH path = (a:Account)-[:TRANSFER*]->(b:Account)

// Safe: explicit bounds plus early filtering
MATCH path = (a:Account {id: $id})-[t:TRANSFER*1..4]->(b:Account)
WHERE all(x IN t WHERE x.amount > 1000 AND x.at > $since)
RETURN path LIMIT 50

อ่าน plan

ใช้ผลลัพธ์จาก EXPLAIN หรือ PROFILE ของฐานข้อมูล แล้วมองหา:

• Full label scan ในจุดที่คุณคาดว่าจะเป็น index seek
• Cartesian product ที่เกิดจาก pattern ที่ไม่เชื่อมต่อกันภายใน MATCH เดียว
• "db hits" สูงมาก ในขั้น expand ซึ่งมักแปลว่ามี supernode หรือขาดตัวกรอง

ตั้งชื่อประเภท relationship ให้เจาะจง

[:RELATED_TO {kind: 'purchase'}] ทำให้ engine ต้องโหลดทุก relationship แล้วค่อยเช็ก property ขณะที่ [:PURCHASED] ทำให้ข้าม edge ที่ไม่เกี่ยวข้องไปได้ทั้งหมด ประเภท relationship ที่เจาะจงจึงทำหน้าที่เหมือน index ที่ได้มาฟรี ๆ

Relational database ก็ทำงาน graph ได้

สำหรับ graph ขนาดปานกลาง recursive CTE ใน PostgreSQL มักเพียงพอแล้ว:

WITH RECURSIVE reports AS (
    SELECT id, manager_id, 1 AS depth
    FROM employees WHERE id = $1
  UNION ALL
    SELECT e.id, e.manager_id, r.depth + 1
    FROM employees e
    JOIN reports r ON e.manager_id = r.id
    WHERE r.depth < 6
)
SELECT * FROM reports;

สร้าง index ให้คอลัมน์ที่ใช้ join (manager_id) ใส่ขีดจำกัดความลึกเสมอ และป้องกัน cycle ถ้าข้อมูลมีโอกาสวนกลับเป็นวงได้

สรุป

1. เลือก algorithm ให้ตรงกับคำถาม: BFS สำหรับนับ hop, Dijkstra หรือ A* สำหรับ graph ที่มีน้ำหนัก และ bidirectional search เมื่อรู้ทั้งสองปลาย
2. เก็บ graph ให้กะทัดรัด: ใช้ ID จำนวนเต็มแบบต่อเนื่องและ CSR สำหรับงานที่อ่านเป็นหลัก
3. ลดพื้นที่การค้นหา: จำกัดความลึก กรองระหว่าง traverse และจัดการ supernode อย่างตั้งใจ
4. ใน graph database ให้ยึดจุดเริ่มด้วย index จำกัดความยาว path และอ่าน plan

ปัญหาประสิทธิภาพของ graph ส่วนใหญ่มาจากการสำรวจ graph มากเกินกว่าที่คำถามต้องการ ขั้นตอนเหล่านี้จึงเน้นไปที่การจำกัดส่วนนั้น