SQL Query ในการดึงข้อมูลที่มีโครงสร้างเป็นแบบ hierarchy

สำหรับข้อมูลที่มีโครงสร้างเป็นแบบ hierarchy หรือโครงสร้างต้นไม้ เช่นผังองค์กร, สายบังคับบัญชา มักจะมีการตั้งคำถามว่า หน่วยงานนี้อยู่ในสังกัดหน่วยงานอะไรบ้าง หรือมีพนักงานคนใดอยู่ภายใต้การบังคับบัญชาของผู้จัดการคนนี้บ้าง เทคนิคการ query เพื่อหาคำตอบสำหรับข้อมูลแบบนี้ต้องใช้การเวียนเกิดหรือ recursion

ปกติแล้วฐานข้อมูล RDBMS จะเก็บข้อมูลซึ่งมีโครงสร้างแบบ hierarchy โดยทำตารางให้มีคอลัมน์ที่สำคัญสองตัวคือ ID ของบรรทัดนั้นๆ และ ID ของบรรทัด parent ตัวอย่างด้านล่างแสดงผังองค์กรและวิธีเก็บข้อมูลในตาราง

sample-org-chart
sample-org-table

สมมติว่าตารางนี้ชื่อว่า Org, คอลัมน์ org_id เป็น Primary key หรือ identity ของตาราง, ส่วนคอลัมน์ org_parent_id คือตัวสำคัญที่ใช้บอกว่าบรรทัดใดเป็น parent ของบรรทัดนั้นๆ ตัวอย่างเช่น org_id 104 นั้น อยู่ภายใต้ org_id 102 ซึ่งฟิลด์ org_parent_id ของบรรทัดนี้ก็จะเก็บเลข 102 เป็นต้น, คอลัมน์ org_parent_id นี้ถ้าจะให้ดี(แต่อาจจะไม่ยืดหยุ่นนัก) ควรทำเป็น foreign key เข้าหา org_id ของตารางตัวเอง แต่สิ่งที่ควรทำแน่ๆ คือต้องทำ index ที่คอลัมน์นี้ เพื่อประสิทธิภาพในการ join หาโหนดลูกๆ ในโครงสร้างต้นไม้, สำหรับคอลัมน์ org_name หรืออื่นๆ จะไม่มีบทบาทอะไรนักในโครงสร้างต้นไม้ แต่เป็นตัวข้อมูลที่สุดท้าย user ต้องการนำไปใช้
 

สถานการณ์ที่ 1: ค้นหาบรรพบุรุษ

โจทย์มีอยู่ว่า หน่วยงาน “บัญชี 1” หรือ org_id 110 อยู่ภายใต้สังกัดอะไร คำตอบที่ต้องการคือ “การบัญชี, Contoso Holdings, Contoso Group”

วิธีทำแบบที่ 1 ทำ recursion ด้วย CTE (Common Table Expressions)

DECLARE @org_id INT; SET @org_id=110;

WITH Recurr(org_parent_id, depth) AS
(
    SELECT org_parent_id, 1 depth
    FROM Org
    WHERE org_id = @org_id
    UNION ALL
    SELECT Parent.org_parent_id, Recurr.depth+1 depth
    FROM Recurr
    INNER JOIN Org Parent ON Parent.org_id=Recurr.org_parent_id
)

SELECT Org.*, depth
FROM Recurr
INNER JOIN Org ON Org.org_id=Recurr.org_parent_id

ผลลัพธ์
hierarchy-qresult2
 

วิธีทำแบบที่ 2 เขียนโปรแกรมวนลูปและเก็บค่าใส่ table ชั่วคราว

DECLARE @org_id INT; SET @org_id=110;

DECLARE @recurr TABLE(
	row_id INT IDENTITY(1, 1) PRIMARY KEY, 
	org_parent_id INT,
	depth INT)

INSERT INTO @recurr(org_parent_id, depth)
SELECT org_parent_id, 1 depth
FROM Org
WHERE org_id = @org_id;

DECLARE @row_count INT
DECLARE @last_row_id INT
SET @row_count = @@ROWCOUNT
SET @last_row_id = 0
WHILE (@row_count != 0)
BEGIN
    INSERT INTO @recurr(org_parent_id, depth)
    SELECT Parent.org_parent_id, depth+1 depth
    FROM @recurr Recurr
    INNER JOIN Org Parent ON Parent.org_id=Recurr.org_parent_id
    WHERE row_id > @last_row_id

    SET @row_count = @@ROWCOUNT
    SET @last_row_id = @@IDENTITY - @row_count
END

SELECT Org.*, depth
FROM @recurr Recurr
INNER JOIN Org on Org.org_id=Recurr.org_parent_id

ผลลัพธ์เหมือนกัน
hierarchy-qresult2

 
สถานการณ์ที่ 2: ค้นหาลูกหลาน

โจทย์มีอยู่ว่า หน่วยงาน “Contoso Holdings” หรือ org_id 102 มีหน่วยงานอะไรอยู่ในสังกัดบ้าง คำตอบที่ต้องการคือ “การบุคคล, บุคคล 1, บุคคล 2, การบัญชี, บัญชี 1, บัญชี 2”

วิธีทำแบบที่ 1 ทำ recursion ด้วย CTE (Common Table Expressions)

DECLARE @org_id INT; SET @org_id=102;

WITH Recurr(org_id, depth) AS
(
    SELECT org_id, 1 depth
    FROM Org
    WHERE org_parent_id = @org_id
    UNION ALL
    SELECT Child.org_id, Recurr.depth+1 depth
    FROM Recurr
    INNER JOIN Org Child ON Child.org_parent_id=Recurr.org_id
)

SELECT Org.*, depth
FROM Recurr
INNER JOIN Org ON Org.org_id=Recurr.org_id

ผลลัพธ์
hierarchy-qresult3
 

วิธีทำแบบที่ 2 เขียนโปรแกรมวนลูปและเก็บค่าใส่ table ชั่วคราว

DECLARE @org_id INT; SET @org_id=102;
 
DECLARE @recurr TABLE(
    row_id INT IDENTITY(1, 1) PRIMARY KEY, 
    org_id INT,
    depth INT)
 
INSERT INTO @recurr(org_id, depth)
SELECT org_id, 1 depth
FROM Org
WHERE org_parent_id = @org_id;
 
DECLARE @row_count INT
DECLARE @last_row_id INT
SET @row_count = @@ROWCOUNT
SET @last_row_id = 0
WHILE (@row_count != 0)
BEGIN
    INSERT INTO @recurr(org_id, depth)
    SELECT Child.org_id, depth+1 depth
    FROM @recurr Recurr
    INNER JOIN Org Child ON Child.org_parent_id=Recurr.org_id
    WHERE row_id > @last_row_id
 
    SET @row_count = @@ROWCOUNT
    SET @last_row_id = @@IDENTITY - @row_count
END
 
SELECT Org.*, depth
FROM @recurr Recurr
INNER JOIN Org on Org.org_id=Recurr.org_id

ผลลัพธ์เหมือนกัน
hierarchy-qresult3

 
แล้วควรเลือกวิธีไหน?
จากตัวอย่างจะเห็นได้ว่าเราสามารถเขียน query ได้สองวิธี วิธีแรกใช้ recursion ด้วย CTE วิธีที่สองเขียนโปรแกรมวนลูปใส่ค่าลงใน table ชั่วคราว
ตรงนี้ขอบอกว่า จากการทดสอบกับฐานข้อมูล SQL Server วิธีที่สองกลับมีประสิทธิภาพดีกว่า ความจริงแล้วหลักการทำงานมันน่าจะเหมือนๆ กันทั้งสองวิธี แต่ด้วย implementation ของ SQL Server ผลลัพธ์ชั่วคราวของแต่ละชั้นที่ recurr น่าจะเก็บอยู่คนละที่ ต่างจากวิธีวนลูปที่นำผลทั้งหมดมารวมลงในตารางเดียว ทำให้ความเร็วของ query ต่างกัน โดยเฉพาะคำตอบที่ต้องวนหลายชั้นหรือข้อมูลมีปริมาณมากๆ แบบแรกจะทำงานช้ากว่าอย่างเห็นได้ชัด แม้จะกำหนด index ไว้แล้ว
อย่างไรก็ตาม CTE นั้นเป็นคอนเซปท์ตามมาตรฐาน SQL:1999 ขณะที่แบบเขียนโปรแกรมต้องปรับแต่ง syntax ตาม DB แต่ละยี่ห้อ ดังนั้นผมแนะนำว่าถ้าต้องการเขียน query แบบอ่านง่ายๆ ไว้ใช้กับ DB ทั่วไป เขียนแบบ CTE จะดีกว่า แต่ถ้ารู้ว่าใช้ SQL Server แน่ๆ หรือ DB ที่ใช้ไม่สนับสนุน CTE ก็ควรใช้วิธีที่สองครับ

2 Responses to “SQL Query ในการดึงข้อมูลที่มีโครงสร้างเป็นแบบ hierarchy”

  1. toro Says:

    ตัวอย่างนี้ data จิงเก็บกี่ table ครับ


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: