Sử dụng đệ quy và một số mẹo hay khi viết query PostgreSQL (phần 1)

Mở đầu

Đôi khi làm việc với cơ sở dữ liệu chúng ta cần tới các phép toán lặp (loop) nhằm phục vụ cho việc phân tích các cấu trúc phức tạp, PostgreSQL có hỗ trợ việc sử dụng CTEs (Common Table Expressions) như một giải pháp hiệu quả cho nhu cầu này, bài viết dưới đây mình sẽ mô tả ngắn gọn kịch bản, cách thức viết recursive query.

Bài toán

Giả sử đang xét tới CSDL của một trang web chuyên cung cấp các survey online, với các thực thể như sau: Survey bao gồm rất nhiều các câu hỏi khác nhau, các câu hỏi có thể cùng về một nhóm, chủ đề. Thực tế các câu hỏi có thể được chia nhỏ ra thành cấp nhỏ hơn bao gồm nhiều câu hỏi phụ, tuy nhiên để đơn giản ta chỉ xét trường hợp category bao gồm nhiều phân cấp (category lồng category) question sẽ nằm trong category có level cao nhất. Mỗi question và category đều có field order_number - một số nguyên thể hiện thứ tự tương đối của chính nó và các node có quan hệ (siblings) Ví dụ, trong trường hợp như hình vẽ dưới đây question Bar sẽ có order_number bé hơn order_number của Baz Điều này đảm bảo một category có thể fetch toàn bộ các câu hỏi nằm dưới nó theo đúng thứ tự.

# In category.rb
def sub_questions_in_order
  questions.order('order_number')
end

Trong thực tế, một survey có thể được lấy ra một cách hoàn chỉnh bằng cách visit từng category và gọi hàm sub_questions_in_oder ở mỗi phần từ của con của nó, kết quả thu được sẽ là 1 tree hoàn chỉnh. Có thể dự đoán trước được rằng với survey có khoảng từ 5 level trở lên và với hàng trăm câu hỏi thì việc build tree survey theo cách này sẽ rất chậm.

Recursive query

Theo tài liệu về CTEs của PostgreSQL, query đệ quy được viết theo cú pháp như sau:

WITH RECURSIVE temp_table AS (
    -- non-recursive term
    UNION (or UNION ALL)
    -- recursive term
    )
SELECT * FROM temp_table

Dạng thông thường của một query đệ quy WITH luôn bắt đầu bằng một mệnh đề không đệ quy (non-recursive) tiếp sau đó là phép toán UNION (hoặc UNION ALL), mệnh đề đệ quy - lưu trữ và truy vấn tới các kết quả sinh ra từ phép toán.

Đánh giá recursive query

1. Thực hiện đánh giá mệnh đề non-recursive, phép toán UNION (không phải UNION ALL) loại trừ các row bị trùng lặp, tất cả các row còn lại trong kết quả của query đệ quy sẽ được lưu trong một bảng tạm (temporary working table)
2. Sau khi nạp dữ liệu cho bảng tạm, lặp lại các bước sau: a. Đánh giá biểu thức đệ quy, thay thế nội dung hiện tại của bảng hiện hành bằng các bản ghi theo dạng đệ quy tự tham chiếu (self-reference). Đối với phép UNION (không phải UNION ALL) loại bỏ các row trùng lặp (so với tất cả các bản ghi đang tồn tại) các row còn lại trong kết quả truy vấn đệ quy sẽ được cập nhật lại trong bảng trung gian tạm thời. b. Thay thế nội dung của bảng hiện hành bằng bảng tạm thời trung gian, giải phóng dữ liệu ở bảng trung gian.

Áp dụng

Thực hiện bước 1, chúng ta cần xác định initial query (mệnh đề non-recursive) Trong ví dụ của chúng ta, đấy chính là query lấy ra các phần tử ở top level thỏa mãn điều kiện không có category cha hay nói cách khác trường dữ liệu của các phần tử này category_id is NULL. Giả sử survey đang xét có id = 2

(
  SELECT id, content, order_number, type, category_id FROM questions
  WHERE questions.survey_id = 2 AND questions.category_id IS NULL
)
UNION
(
  SELECT id, content, order_number, type, category_id FROM categories
  WHERE categories.survey_id = 2 AND categories.category_id IS NULL
)

Kết quả của query này là 2 bản ghi như sau Tiếp tục thực hiện bước thứ 2, tìm tất cả các bản ghi con trực tiếp từ 2 bản ghi thu được nêu trên

WITH RECURSIVE first_level_elements AS (
  -- Non-recursive term
  (
    (
      SELECT id, content, order_number, category_id FROM questions
      WHERE questions.survey_id = 2 AND questions.category_id IS NULL
    UNION
      SELECT id, content, order_number, category_id FROM categories
      WHERE categories.survey_id = 2 AND categories.category_id IS NULL
    )
  )
  UNION
  -- Recursive Term
  SELECT q.id, q.content, q.order_number, q.category_id
  FROM first_level_elements fle, questions q
  WHERE q.survey_id = 2 AND q.category_id = fle.id
)
SELECT * from first_level_elements;

Có thể thấy mệnh đề đệ quy ở trên mới chỉ lấy các question trong khi ở level 1 của một category có thể là một question hoặc một category khác. Mặc dù Postgre không cho phép tham chiếu tới mệnh đề non-recursive nhiều hơn một lần tuy nhiên chúng ta có thể sử dụng phép toán UNION để lấy thứ mình cần

WITH RECURSIVE first_level_elements AS (
  (
    (
      SELECT id, content, order_number, category_id FROM questions
      WHERE questions.survey_id = 2 AND questions.category_id IS NULL
    UNION
      SELECT id, content, order_number, category_id FROM categories
      WHERE categories.survey_id = 2 AND categories.category_id IS NULL
    )
  )
  UNION
  (
      SELECT e.id, e.content, e.order_number, e.category_id
      FROM
      (
        -- Fetch questions AND categories
        SELECT id, content, order_number, category_id FROM questions WHERE survey_id = 2
        UNION
        SELECT id, content, order_number, category_id FROM categories WHERE survey_id = 2
      ) e, first_level_elements fle
      WHERE e.category_id = fle.id
  )
)
SELECT * from first_level_elements;

Điểm mấu chốt ở đây đó là thực hiện phép toán category UNION question trong mệnh đề đệ quy trước khi thực hiện kết hợp với mệnh đề non-recursive. Kết quả thu được là toàn bộ các phần tử có trong survey tương ứng với id = 2 Nhìn vào kết quả có thể thấy các bản ghi được lấy ra không còn đúng với thứ tự sắp xếp mong muốn.

Sắp xếp thứ tự trong recursive query

Vấn đề xuất hiện khi chúng ta tìm cách chèn thêm các phần tử ở level 2 vào các phần tử ở level đầu, thay vì thực hiện kìm kiếm theo chiều sâu chúng ta đã sử dụng tìm kiếm theo chiều rộng - điều này có vẻ không đúng dưới góc độ hiệu năng. Để khắc phục vấn đề này ta có thể sử dụng kiểu dữ liệu mảng array built in của Postgres. Mảng chúng ta gần bao gồm order number của các phần tử, hay còn gọi là path (theo cách nói khi thực hiện duyệt tree). Path được định nghĩa là

path của cha phần tử đó (nếu tồn tại) + order_number của chính nó.

Thực hiện lại query nêu trên và sort kết quả cuối cùng theo path, ta thu được phép tìm kiếm theo chiều sâu đúng như mong muốn. Chú ý giả định ban đầu, chỉ có category mới có con do đó ta không cần xét đệ quy cho trường hợp phần tử đang xét là câu hỏi.

WITH RECURSIVE first_level_elements AS (
  (
    (
      SELECT id, content, category_id, 'questions' as type, array[id] AS path FROM questions
      WHERE questions.survey_id = 2 AND questions.category_id IS NULL
    UNION
      SELECT id, content, category_id, 'categories' as type, array[id] AS path FROM categories
      WHERE categories.survey_id = 2 AND categories.category_id IS NULL
    )
  )
  UNION
  (
      SELECT e.id, e.content, e.category_id, e.type, (fle.path || e.id)
      FROM
      (
        SELECT id, content, category_id, 'questions' as type, order_number FROM questions WHERE survey_id = 2
        UNION
        SELECT id, content, category_id, 'categories' as type, order_number FROM categories WHERE survey_id = 2
      ) e, first_level_elements fle
      -- Look for children only if the type is 'categories'
      WHERE e.category_id = fle.id AND fle.type = 'categories'
  )
)
SELECT * from first_level_elements ORDER BY path;

Tree tương ứng với survey_id=2 được tạo ra có cấu trúc như sau

Hiệu năng

Kiểm tra thử hiệu năng của phương pháp query truyền thống và sử dụng đệ quy, lần lượt test với bộ dữ liệu survey gồm 10 category, mỗi category có 6 level

survey = Survey.find(9)
10.times do
  category = FactoryGirl.create(:category, :survey => survey)
  6.times do
    category = FactoryGirl.create(:category, :category => category, :survey => survey)
  end
  FactoryGirl.create(:single_line_question, :category_id => category.id, :survey_id => survey.id)
end

Kết quả thu được thực tế như sau

pry(main)> Benchmark.ms { 5.times { Survey.find(9).sub_questions_using_recursive_queries }}
=> 36.839999999999996

pry(main)> Benchmark.ms { 5.times { Survey.find(9).sub_questions_in_order } }
=> 1145.1309999999999

Sử dụng recursive query cho kết quả nhanh hơn 31 lần, rất đáng kể.

Kết luận

Recursive query thông thường được sử dụng cho các tình huống cần thao tác mô hình hóa cấu trúc dữ liệu thừa kế dạng tree. Sử dụng linh hoạt kiểu query này sẽ giúp chúng ta tiết kiệm được thời gian tìm kiếm, truy xuất dữ liệu cũng như update một cách tối ưu nhất.

Link tham khảo

1. https://www.postgresql.org/docs/9.1/static/queries-with.html
2. http://blog.timothyandrew.net/blog/2013/06/24/recursive-postgres-queries/