Beyond Rails Abstractions: A Dive into Database Internals

Trừu tượng là một điều rất tuyệt vời. Đối với Rails: chúng ta có thể thi hành một chức năng lớn với một vài dòng code được viết. Chúng ta không cần thiết biết một thỏa thuật tuyệt vời về làm thế nào để dữ liệu của chúng ta được thi hành theo thứ tự để có thể chạy đúng và nhanh chóng. Nhược điểm khi code ở level này đó là chúng ta có thể không lường trước được tất cả mọi thứ đằng sau các hàm viết sẵn. Một vấn để rất hay xảy ra đó là query rất chậm khi dữ liệu không được đánh index mà chúng ta sẽ đi tìm hiểu dưới đây.

How do Indexes Work?

Chúng ta đều mong đợi các query trở nên nhanh chóng nhất có thể khi truy xuất dữ liệu. Nếu bạn đã từng thi hành một chức năng lấy về mọi giá trị trong khoảng nào đó giữa hai số, bạn có thể sẽ so sánh từng giá trị của mỗi bản ghi với khoảng so sánh, nhưng đây là một cách không hiệu quả khi tập dữ liệu so sánh là cực lớn và bạn có thể thấy ngay được đó là query tuyến tính giữa thời gian và dữ liệu (O(n)). Điều bạn cần trong trường hợp này là lưu lại các bản ghi theo thứ tự quy định rõ ràng để tạo điều kiện giảm thời gian lấy dữ liệu data. Một cách sắp xếp theo cây tìm kiếm nhị phân (Binary Search Tree - BST) làm chính xác điều này. bởi chắc chắn rằng bất kỳ bản ghi nào có giá trị so sánh lớn hơn sẽ nằm ở nhánh bên trái và các giá trị so sánh nhỏ hơn nằm ở bên phải cây nhị phân. Điều này sẽ giảm độ phức tạp tìm kiếm đáng kể từ tuyến tính O(n) trở thành O(log n), và điều này chính xác là xướng sống của database index. BST không phù hợp lắm khi chúng ta chỉ tìm kiếm một bản ghi, thay vì đó hiệu quả trong trường hợp tìm kiếm trong một khoảng điều kiện. Khi đó độ phức tạp tìm kiếm trở về O(n/2) vẫn là tuyến tính. Trong trường hợp này chúng ta có thể sử dụng cây tìm kiếm B+ với độ phức tạp tìm kiếm là O(m + log n).

Why Is Using Too Many Indexes a Bad Idea?

Hãy tưởng tượng khi chúng ta xóa đi một bản ghi trong database. Điều này có nghĩa là chúng ta sẽ xóa đi một nút trong cầy tìm kiếm B+. Chúng ta không thể xóa ngay được mà sẽ phải sắp xếp lại cây tìm kiếm. Để làm điều này chúng ta có thể sử dụng các hàm được viết sẵn như chèn thêm hay xóa đi nhưng nó sẽ có thể mất thời gian với độ phức tạp tương ứng là O(log n). Điều quan trọng là bất kể trường nào được đánh index sẽ phải tự cân bằng lại cây tìm kiếm mỗi khi chúng ta thêm vào hay xóa đi.

Query Parser

Hãy xem với một query rất đơn giản

SELECT id, email, admin, credits FROM users WHERE credits > 2 + 3;

Kết quả của phân tích query cho thấy

>>> SELECT email, admin, credits FROM users WHERE credits > 2 + 3                                                         
LOG:  parse tree:
DETAIL:     {QUERY
  :commandType 1
  :querySource 0
  :canSetTag true
  :utilityStmt <>
  :resultRelation 0
  :hasAggs false
  :hasWindowFuncs false
  :hasSubLinks false
  :hasDistinctOn false
  :hasRecursive false
  :hasModifyingCTE false
  :hasForUpdate false
  :hasRowSecurity false
  :cteList <>
  :rtable (
    {RTE
    :alias <>
    :eref
      {ALIAS
      :aliasname users
      :colnames ("id" "created_at" "updated_at" "email" "encrypted_password
      " "confirmation_token" "remember_token" "admin" "" "credits")
      }
    :rtekind 0
    :relid 27043
    :relkind r
    :tablesample <>
    :lateral false
    :inh true
    :inFromCl true
    :requiredPerms 2
    :checkAsUser 0
    :selectedCols (b 12 16 18)
    :insertedCols (b)
    :updatedCols (b)
    :securityQuals <>
  Time: 0.001s

Khi query là đúng và hợp lệ, chúng ta sẽ tới bước sau

Query Rewriter

Giờ là lúc mà query sẽ được tối ưu và viết lại. Ví dụ như bạn lựa chọn DISTINCT đối với một trường đã được đặt rằng buộc duy nhất unique, khi đó DISTINCT sẽ bị bỏ đi.

Statistics

Một database tốt sẽ tự lưu lại thống kê truy xuất và sẽ được lưu lại cũng giống như các bảng để phục vụ việc tối ưu, và đó là lý do tại sao truy xuất của bạn có thể trở nên nhanh hơn. Ví dụ nếu bạn muốn join một bảng với hàng triệu bản ghi với một bảng có khoảng một trăm bản ghi. Khi đó sẽ tính toán lại lịch sử query để chỉ phải join số lượng ít hơn chứ không cần join toàn bộ các bản ghi.

Query Executor

Cuối cùng sau khi tối ưu, query sẽ được thực thi để lấy ra dữ liệu cần truy xuất. Bộ xử lý query sẽ kiểm tra có đủ tài nguyên (bộ nhớ và CPU), và nếu đủ thì mới thi hành query.

Wrapping Up

Có rất nhiều tài liệu để chúng ta có thể hiểu hơn về database, và nhiều thứ chưa được nhắc tới trong bài viết này. Nhưng nó có thể sẽ có ích cung cấp đầy đủ cái nhìn định hình về database xử lý query bên trong, và cuối cùng là nên cẩn trọng khi thêm index cho database.

Refs

Beyond Rails Abstractions: A Dive into Database Internals