Cách lưu trữ để tối ưu truy vấn Dữ liệu cấu trúc cây trong Cơ sở dữ liệu quan hệ

Phân tích cấu trúc lưu trữ dữ liệu tốt sẽ nâng cao performance cho việc sử dụng dữ liệu đó

1/ Vấn đề gặp phải

Lúc trước mình có làm freelance cho 1 công ty ở Canada, họ yêu cầu mình làm cái Search Engine bằng Elasticsearch để tìm kiếm tài liệu ở dạng PDF, dữ liệu gần 100,000 file PDF, trung bình mỗi file gần 100 trang, có file lên đến gần 1,000 trang. Khi user tìm kiếm theo nội dung và kết quả trả về: file đó, nội dung đó nằm ở trang nào,….

Khi làm xong cái search nó với performance khá tốt, họ yêu cầu mình làm thêm tính năng chia thư mục của tài liệu ở dạng cây.

Hình 1. Cây thư mục lưu trữ file theo ý tưởng của khách hàng

Vấn đề khó là họ đã tạo sẵn tính năng tạo thư mục và đã lưu vào PostgreSQL hơn 10 năm rồi (đến 7 level, gần 400 folders), nhưng chưa triển khai như hình 1 được vì phân cấp khá sâu, mỗi lần show lên rất tốn thời gian và rất chậm vì phải lấy path từ folder đó đến folder root. Dữ liệu này đã được lưu hơn 10 năm nhưng tới giờ vẫn chưa dùng vì vấn đề performance, team neo đơn không có dev improve.

Cách họ lưu trữ dữ liệu hiểu đơn giản là thế này:

Hình 2. Mô hình lưu trữ dữ liệu của version hiện tại

Tổ chức trong CSDL ở table path_tree nó dạng thế này (còn vài cột nữa, ở đây mình liệt kê vài cột thôi):

Hình 3. Bảng dữ liệu lưu trữ ở version hiện tại

Ở đây chỉ cần chú ý đến id (là id của folder/file đó), parent_id (là thư mục cha liền kề của nó).

Cách lưu trữ này rất dễ cho việc insert hay update, nhưng hiệu năng sẽ rất kém và khá phức tạp nếu retrieve nó ra ở dạng cây như hình 1, nếu lấy id join với cột parent_id của chính nó, hoặc dùng ngôn ngữ lập trình để xử lý.

2/ Phân tích vấn đề

Vì trong PostgreSQL có hỗ trợ recursive, khi dùng recursive để truy vấn ra kết quả liên quan đến 1 folder/file thì dùng SQL kiểu:

WITH RECURSIVE cursor_tmp AS (
    SELECT id, name, parent_id, type
    FROM path_tree
    WHERE id = 2
    UNION
    SELECT e.id, e.name, e.parent_id, e.type
    FROM path_tree e
            INNER JOIN cursor_tmp s
                ON s.parent_id = e.id
) 
SELECT *
FROM cursor_tmp;

Kết quả trả ra là danh sách các folders từ folder root đến item có id=2, nếu user ấn vào detail của folder đó thì sẽ hiển thị tiếp các items là con của folder đó.
Khi dùng đệ quy trên thì mỗi lần chạy phải tốn tầm hơn 30s, sau đó backend xử lý và trả ra UI tầm 35s, performance cực kém (ở đây chúng tôi không làm thế :D).
Mình không thể update structure của table path_tree được vì project này chạy hơn 10 năm rồi, giờ thay đổi thật rủi ro cho các services khác đang dùng nó. Cách tiếp cận của mình là tạo 1 table song song (tmp_path_tree) để flatten nó ra chứ không join với chính nó hay dùng recursive.

3/ Giải quyết vấn đề

Ở đây có nhiều các giải quyết vấn đề, mình chọn cách phân tích này

Hình 4. Phân tích depth của item có id=4 (Folder 4)

Với depth là khoảng cách của id hiện tại đến parent_id.

Sau đó dùng recursive để tạo ra bảng dữ liệu như sau:

Hình 5. Flatten bảng path_tree theo mô hình phân tích ở hình 4

Cách dùng: muốn tìm parent của item có id=8 thì chỉ cần query

SELECT * 
FROM tmp_path_tree 
WHERE id=8
ORDER BY depth DESC;

Nó sẽ trả về kết quả như mong đợi, và kèm thêm depth để backend dễ dàng parse đúng thứ tự folder/file ở path. Độ phức tạp khác thấp, thời gian data, backend, và frontend render trả về dưới 1s.

• Ưu điểm:
  + Search cho kết quả nhanh (cái mà khách hàng họ ưu tiên)
• Nhược điểm:
  + Khi bảng chính path_tree thay đổi cấu trúc thư mục thì phải tốn tầm 30s–60s để build lại bảng tmp_path_tree tuỳ vào dữ liệu của bảng path_tree (thời điểm này không bị downtime, services vẫn hoạt động bình thường, chỉ là UI chưa được cập nhật realtime thôi, đã được team tester đánh giá impact)

Đối với mình việc chọn cấu trúc lưu trữ sẽ ảnh hưởng rất nhiều đến hiệu năng sử dụng nó tuỳ vào mục đích của người dùng. Thường là sẽ đánh đổi giữa query và insert/update. Khó tìm được giải pháp tốt nhất, thường chỉ tìm được cách phù hợp nhất tại thời điểm ấy.

Các bạn có cách nào hay hơn, bình luận bên dưới để cùng học hỏi nhé!