Trực quan hóa chỉ mục SQLite

 (mrsuh.com)
3 điểm bởi GN⁺ 2024-11-16 | 1 bình luận | Chia sẻ qua WhatsApp
  • Phân tích cấu trúc B-Tree để xem chỉ mục SQLite thực sự được bố trí trên đĩa và trong bộ nhớ như thế nào, rồi dump dữ liệu chỉ mục để trực quan hóa
  • Chỉ mục được cấu thành theo đơn vị Page và Cell; Page có liên kết tới con bên phải và dữ liệu Cell, còn Cell có dữ liệu chỉ mục, rowId và liên kết tới con bên trái
  • Chỉ các thông tin về kích thước Page, số entry, độ sâu B-tree, số Page sử dụng do sqlite3_analyzer cung cấp là chưa đủ, nên đã thêm hàm debug vào mã nguồn SQLite
  • Thử nghiệm so sánh số lượng record, ASC/DESC, chỉ mục dựa trên biểu thức, UNIQUE có NULL, Partial Index, nhiều cột, văn bản, REAL và tổ hợp số nguyên + văn bản
  • Với 1.000.000 record, nếu tạo chỉ mục trước khi chèn thì có 3.342 Pages; nếu tạo sau khi chèn thì có 2.930 Pages, và sau VACUUM hoặc REINDEX cũng giảm xuống 2.930 Pages

Vì sao tự mình xem bên trong chỉ mục SQLite

  • Đây là một thử nghiệm nhằm vượt ra ngoài cấu trúc cơ bản của chỉ mục để kiểm tra cấu trúc dữ liệu, thuật toán và cách lưu trữ trên đĩa thực tế
  • Mục tiêu là xem DBMS lưu chỉ mục trên đĩa và trong bộ nhớ như thế nào, cũng như truy cập chúng ra sao trong quá trình tìm kiếm
  • Lý do chọn SQLite làm đối tượng thử nghiệm như sau
    • Là DBMS được dùng rộng rãi trong trình duyệt, ứng dụng di động và hệ điều hành
    • Dễ debug chỉ bằng ứng dụng client, không cần server riêng
    • Codebase nhỏ hơn MySQL hay PostgreSQL nhưng sử dụng cấu trúc dữ liệu tương tự cho chỉ mục
    • Là mã nguồn mở

B-Tree được tạo từ Page và Cell

  • Theo tài liệu của SQLite, chỉ mục được lưu dưới dạng cấu trúc B-Tree
  • Trong SQLite, đơn vị tương ứng với Node là Page
    • Page lưu dữ liệu Cell
    • Page có liên kết tới Page con bên phải
  • Cell bao gồm dữ liệu chỉ mục, rowId và liên kết tới Page con bên trái
  • Mỗi hàng trong bảng SQLite mặc định có một rowId duy nhất, và khi không có khóa chính tường minh thì nó hoạt động như khóa chính
  • Mỗi Page có kích thước cố định, trong khoảng 512~65.536 bytes
  • Header của Page và Cell dùng 4 bytes để lưu liên kết con
    • Để biết số Page con, cần đọc riêng header bằng hàm get4byte(...)
  • Ví dụ về các struct nội bộ của SQLite như sau
    • MemPage: bao gồm số Page pgno, số Cell nCell, vùng chỉ mục Cell aCellIdx, con trỏ tới ảnh đĩa của dữ liệu Page aData, v.v.
    • CellInfo: bao gồm pPayload trỏ tới vị trí bắt đầu của payload, v.v.

Giới hạn của sqlite3_analyzer và hàm debug

  • Có thể xem thông tin chung về chỉ mục bằng sqlite3_analyzer
    • Ví dụ output bao gồm kích thước Page 4096, số entry 1000, độ sâu B-tree 2, số Page sử dụng 4, v.v.
  • Tuy nhiên, công cụ này chỉ dừng ở thông tin tổng quan, chưa đủ để trực tiếp xem Cell và payload bên trong chỉ mục
  • Sau vài tuần thử nghiệm, đã viết các hàm để phân tích chỉ mục
    • Mã: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Các hàm này đọc nội dung chỉ mục được chọn và xuất ra STDOUT
    • Luồng là SQL query -> selected index -> stdout
    • Output bao gồm số Page, số Page con bên phải, số Cell, số Page con bên trái, payload và rowId
  • Có thể chạy môi trường thử nghiệm bằng Docker
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

Sự thay đổi trong cách trực quan hóa

  • Ban đầu sử dụng d3-org-tree để trực quan hóa cấu trúc chỉ mục
  • Khi cây sâu hơn và số Page ở mỗi level tăng lên, việc điều chỉnh khoảng cách giữa các Page trở nên khó khăn, khiến hình ảnh quá lớn và khó đọc
  • Đã thử điều chỉnh bằng JavaScript và CSS nhưng không phù hợp, nên từng chuyển sang hiển thị cấu trúc dạng văn bản
  • Output dạng văn bản hiển thị tổng số Page, tổng số Cell, số Page/Cell theo từng level, thông tin Page, thông tin Cell và payload
  • Sau đó phát triển thành output hình ảnh với khả năng kiểm soát thiết kế và khoảng cách chi tiết hơn bằng extension ImageMagick của PHP
  • Hình ảnh cuối cùng bao gồm các thông tin sau
    • Hiển thị thông tin chung của chỉ mục ở góc trên bên trái
    • Hiển thị tổng số Page và Cell ở mỗi level
    • Hiển thị số Page, liên kết con bên phải, thông tin Cell đầu tiên và Cell cuối cùng cho từng Page
    • Chỉ hiển thị một số Page ở mỗi level, bao gồm Page đầu tiên và Page cuối cùng
    • Root Page nằm ở level đầu tiên
  • Lệnh tạo hình ảnh từ dump như sau
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Số lượng record làm thay đổi hình dạng chỉ mục

  • Tạo chỉ mục column1 ASC trên bảng column1 INT NOT NULL và thay đổi số lượng record để kiểm tra cấu trúc
  • Chỉ mục với 1 record gồm 1 level, 1 Page, 1 Cell
  • Chỉ mục với 1.000 record cũng được tạo và trực quan hóa theo cách tương tự
  • Chỉ mục với 1.000.000 record có cấu trúc như sau
    • 3 level
    • 2.930 Pages
    • 1.000.000 Cells
  • Vì dữ liệu được thêm theo thứ tự, khi rowId = 1 thì column1 = 1

Hướng sắp xếp và chỉ mục biểu thức

  • Tạo idx_asc và idx_desc trên cùng dữ liệu để so sánh chỉ mục ASC/DESC
  • Chỉ mục ASC giống với chỉ mục trước đó vì thứ tự mặc định là ASC
    • Entry có rowId=1.000.000, column1=1.000.000, payload=1.000.000 nằm ở Cell cuối của Page ngoài cùng bên phải
    • Entry có rowId=1, column1=1, payload=1 nằm ở Cell đầu của Page ngoài cùng bên trái
  • Chỉ mục DESC được bố trí ngược lại
    • Entry có rowId=1, column1=1, payload=1 nằm ở Cell cuối của Page ngoài cùng bên phải
    • Entry có rowId=1.000.000, column1=1.000.000, payload=1.000.000 nằm ở Cell đầu của Page ngoài cùng bên trái
  • Chỉ mục dựa trên biểu thức lưu chuỗi do biểu thức tạo ra
    • Ví dụ trích xuất $.timestamp từ văn bản JSON, rồi chuyển đổi bằng strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') để tạo chỉ mục ASC
    • Cũng có thể dùng các biểu thức phức tạp hơn; chỉ kết quả của chúng được lưu trong chỉ mục

NULL, Partial Index, nhiều cột

  • SQLite hỗ trợ chỉ mục UNIQUE có chứa giá trị NULL
    • Ví dụ chèn các giá trị 1, nhiều NULL, 1000000 rồi chạy CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • Chỉ mục được trực quan hóa trông như chỉ lưu các giá trị không phải NULL
  • Partial Index có điều kiện WHERE column1 IS NOT NULL lọc bỏ các giá trị NULL
    • Chỉ mục này chỉ gồm một Page
    • Dẫn tới tìm kiếm nhanh hơn so với ví dụ UNIQUE trước đó
  • Chỉ mục nhiều cột lưu tuần tự dữ liệu của tất cả field trong Cell
    • Ví dụ là chỉ mục (column1 ASC, column2 ASC)
    • Trong phần trực quan hóa, các field được phân tách bằng dấu hai chấm :

Thời điểm tạo chỉ mục và hiệu quả tái cấu trúc

  • So sánh trường hợp tạo chỉ mục trước khi đưa dữ liệu vào và trường hợp tạo chỉ mục sau khi đã đưa toàn bộ dữ liệu vào
  • Khi dữ liệu mới được thêm, cây phải tự tái cân bằng
  • Cách tạo chỉ mục một lần trên dữ liệu hiện có có thể hiệu quả hơn nhiều
  • Hai chỉ mục trông tương tự nhau, nhưng chỉ mục thứ hai có số Page ít hơn có thể nhanh hơn
  • Kết quả so sánh với 1.000.000 Cells như sau
Phân loại Total Pages Total Cells
Tạo trước khi chèn 3342 1000000
Tạo sau khi chèn 2930 1000000
  • Có thể thực hiện tối ưu hóa tương tự bằng VACUUM hoặc REINDEX
    • VACUUM tạo lại chỉ mục và bảng cùng với dữ liệu
    • REINDEX idx chỉ tạo lại chỉ mục
  • Trong ví dụ, cả hai lệnh đều giảm số Page từ 3342 xuống 2930

Lưu trữ chỉ mục theo kiểu dữ liệu

  • Dữ liệu văn bản: chuỗi ngắn được lưu trực tiếp trong Cell của chỉ mục, nhưng văn bản dài phải được lưu riêng
    • Ví dụ đưa vào các giá trị từ text-1 đến text-1000000 rồi tạo chỉ mục column1 ASC
    • Có thể xác nhận rằng chuỗi thực tế được lưu trực tiếp trong chỉ mục
  • Dữ liệu REAL cũng được lưu trong chỉ mục và trực quan hóa
    • Ví dụ sử dụng các giá trị 1.14, 2.14, ..., 1000000.14
  • Cũng kiểm tra chỉ mục phức hợp dùng đồng thời số nguyên và văn bản
    • Ví dụ tạo chỉ mục (column1 ASC, column2 ASC) trên bảng (column1 INT, column2 TEXT)
    • Số nguyên và chuỗi được lưu cùng nhau trong cùng một Cell theo đúng thứ tự chỉ định khi tạo chỉ mục

Cách tái hiện và công việc tiếp theo

  • Thử nghiệm cho thấy chỉ mục SQLite được cấu trúc ra sao, dữ liệu record được lưu trong bộ nhớ như thế nào, và B-Tree tổ chức cũng như truy cập dữ liệu ra sao
  • Phần trực quan hóa được dùng để phân tích và so sánh các chỉ mục khác nhau
  • Có thể tái hiện mọi ví dụ bằng các lệnh sau
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • Mã và ví dụ nằm tại mrsuh/sqlite-index
  • Công việc tiếp theo là trực quan hóa tìm kiếm dựa trên chỉ mục và khám phá một số SQL query

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-11-16
Ý kiến trên Hacker News

  • Mỗi hàng trong bảng SQLite về cơ bản có một rowId duy nhất, và nếu không có khóa chính tường minh thì nó hoạt động như khóa chính; nhưng thực tế là ngay cả khi có khóa chính, SQLite vẫn dùng rowid
    Sẽ hay nếu trực quan hóa chỉ mục khóa chính của bảng WITHOUT ROWID. Những chỉ mục như vậy đặc biệt thú vị
    Dù hai chỉ mục trông có vẻ giống nhau, việc chỉ mục thứ hai có ít trang hơn không đồng nghĩa ngay là nó nhanh hơn. Điều quan trọng là chiều cao của cây, sau đó là sau khi tìm được giá trị trong chỉ mục, có phải đọc phần dữ liệu còn lại từ một bảng riêng (rowid) hay không, hay dữ liệu đã nằm ngay đó như với WITHOUT ROWID. Khác biệt đặc biệt lớn trong các truy vấn phạm vi như where 50 <= col <= 100

    • Nếu chỉ xét một lần truy cập đơn lẻ thì đúng là chiều cao cây quan trọng, nhưng nếu truy cập chỉ mục thường xuyên thì kích thước tổng thể cũng có thể rất quan trọng đối với tỷ lệ cache hit
    • Việc vẫn dùng rowid ngay cả khi có khóa chính có một ngoại lệ. Nếu tạo INTEGER PRIMARY KEY, SQLite sẽ dùng nó thay thế [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite khá đặc biệt trong hầu như mọi cách xử lý, và tôi cho là đặc biệt hơn nữa ở xử lý truy vấn
    SQLite có xu hướng ưu tiên sự đơn giản hơn hiệu năng, nên thường triển khai theo cách khác với các cơ sở dữ liệu khác mà tôi từng làm việc. SQLite cạnh tranh với tệp JSON/XML dùng cho lưu trữ bền vững hơn là cạnh tranh với các cơ sở dữ liệu khác. Vì vậy, nhìn vào cách triển khai của SQLite không hẳn cho bạn biết nhiều về việc một cơ sở dữ liệu thực thụ sẽ làm cùng việc đó như thế nào

    • Nó cạnh tranh với cả hai. Rõ ràng SQLite được dùng làm lưu trữ bền vững cục bộ, nhưng trong những tình huống không cần một tiến trình máy chủ riêng, nó cũng cạnh tranh với các hệ quản trị cơ sở dữ liệu quan hệ khác
      Điều đó đúng là có nghĩa yêu cầu rất khác nhau, nhưng phạm vi sử dụng của nó không chỉ dừng ở việc thay thế tệp JSON/XML
    • SQLite là một database engine thực thụ. Có lẽ ý gần hơn là nó không cạnh tranh với database server
    • Cách các máy chủ hệ quản trị cơ sở dữ liệu khác xử lý lưu trữ và chỉ mục không quá xa lạ với cách này. Nguyên lý gần như giống nhau, đặc biệt là khi SQLite hoạt động ở chế độ WAL

  • Trang web dễ đọc đến mức thực sự khiến tôi muốn đọc

    • Xem trên iPhone thì cỡ chữ phần nội dung quá lớn. Văn bản quan trọng trong biểu đồ lại nhỏ hơn nhiều, nên muốn đọc nội dung thì phải đẩy điện thoại ra xa mặt, còn muốn đọc biểu đồ thì lại phải đưa gần vào, khá gượng gạo
    • Thật sự dễ chịu khi có thể xem nội dung mà không bị quảng cáo dày đặc. Bài viết cũng rất hay

  • “indexes” vừa là ngôi thứ ba số ít hiện tại của động từ “to index”, vừa là danh từ số nhiều của “index”. Trong khi đó “indices” là dạng số nhiều truyền thống, đặc biệt hay dùng trong ngữ cảnh toán học và khoa học
    Trong tiếng Anh thông dụng, “indexes” phổ biến hơn, nhưng trong lĩnh vực kỹ thuật đôi khi người ta thích dùng indices để chính xác hơn về mặt ngôn ngữ. Trong ngữ cảnh này, dùng “indices” giúp phân biệt thao tác lập chỉ mục với dạng số nhiều của chỉ mục, qua đó rõ ràng hơn

    • Cả hai đều ổn (https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). Tài liệu SQLite và PostgreSQL cũng dùng indexes như ví dụ tiêu biểu
    • Thử biến “time series” thành số nhiều thì không dễ
      Ở Phần Lan, tôi từng thấy người ta dùng “time series” cho số nhiều và “time serie” cho số ít
    • Không biết bạn nói vậy dựa trên thẩm quyền nào
      Tất cả các hệ quản trị cơ sở dữ liệu quan hệ lớn đều dùng thuật ngữ indexes
    • Tùy đối tượng độc giả. Nếu nhắm đến giới học thuật thì dùng indices, còn nếu nhắm đến độc giả phổ thông thì “indices” có thể trông như làm màu

  • Sẽ hay nếu được xem PostgreSQL làm cùng việc này như thế nào. Có lẽ sẽ học được nhiều điều khi so sánh

  • Để xem nhiều bố cục khác nhau với ít công sức hơn, cũng có thể cho xuất TGF dành cho yEd