การทำ Visualization ของดัชนี SQLite

 (mrsuh.com)
3 คะแนน โดย GN⁺ 2024-11-16 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • วิเคราะห์ โครงสร้าง B-Tree เพื่อดูว่าดัชนีของ SQLite ถูกจัดวางจริงบนดิสก์และในหน่วยความจำอย่างไร พร้อม dump ข้อมูลดัชนีออกมาเพื่อทำ visualization
  • ดัชนีประกอบด้วยหน่วย Page และ Cell โดย Page มีลิงก์ไปยังลูกฝั่งขวาและข้อมูล Cell ส่วน Cell มีข้อมูลดัชนี, rowId และลิงก์ไปยังลูกฝั่งซ้าย
  • ข้อมูลอย่างขนาด Page, จำนวน entry, ความลึกของ B-tree และจำนวน Page ที่ใช้ ซึ่ง sqlite3_analyzer ให้มา ยังไม่เพียงพอ จึงเพิ่ม ฟังก์ชัน debug ลงในซอร์สของ SQLite
  • การทดลองเปรียบเทียบจำนวน record, ASC/DESC, ดัชนีแบบอิง expression, UNIQUE ที่มี NULL, Partial Index, หลายคอลัมน์, ข้อความ·REAL·ชุดค่าจำนวนเต็ม+ข้อความ
  • สำหรับ record 1,000,000 รายการ หากสร้างดัชนีก่อน insert จะได้ 3,342 Pages แต่หากสร้างหลัง insert จะได้ 2,930 Pages และหลังทำ VACUUM หรือ REINDEX ก็ลดลงเหลือ 2,930 Pages เช่นกัน

เหตุผลที่ลองเจาะดูดัชนี SQLite ด้วยตัวเอง

  • เป็นการทดลองเพื่อดู โครงสร้างข้อมูล, อัลกอริทึม และวิธีจัดเก็บบนดิสก์จริง ๆ ไม่ใช่แค่โครงสร้างพื้นฐานของดัชนี
  • เป้าหมายคือดูว่า DBMS จัดเก็บดัชนีบนดิสก์และในหน่วยความจำอย่างไร และเข้าถึงมันอย่างไรระหว่างกระบวนการค้นหา
  • เหตุผลที่เลือก SQLite เป็นเป้าหมายการทดลองมีดังนี้
    • เป็น DBMS ที่ใช้กันแพร่หลายในเบราว์เซอร์ แอปมือถือ และระบบปฏิบัติการ
    • debug ได้ง่ายด้วยแอปพลิเคชันฝั่ง client เพียงอย่างเดียว โดยไม่ต้องมีเซิร์ฟเวอร์แยก
    • codebase เล็กกว่า MySQL หรือ PostgreSQL แต่ใช้โครงสร้างข้อมูลที่คล้ายกันสำหรับดัชนี
    • เป็นโอเพนซอร์ส

B-Tree ที่ประกอบด้วย Page และ Cell

  • ตาม เอกสาร ของ SQLite ดัชนีถูกจัดเก็บเป็น โครงสร้าง B-Tree
  • ใน SQLite หน่วยที่เทียบกับ Node คือ Page
    • Page เก็บข้อมูล Cell
    • Page มีลิงก์ไปยัง Page ลูกฝั่งขวา
  • Cell ประกอบด้วยข้อมูลดัชนี, rowId และลิงก์ไปยัง Page ลูกฝั่งซ้าย
  • แต่ละแถวในตาราง SQLite โดยพื้นฐานจะมี rowId ที่ไม่ซ้ำกัน และทำหน้าที่เหมือน primary key เมื่อไม่มี primary key ที่กำหนดไว้อย่างชัดเจน
  • แต่ละ Page มีขนาดคงที่ โดยช่วงขนาดคือ 512~65,536 bytes
  • header ของ Page และ Cell ใช้ 4 bytes สำหรับจัดเก็บลิงก์ลูก
    • ต้องอ่าน header แยกด้วยฟังก์ชัน get4byte(...) เพื่อรู้หมายเลข Page ลูก
  • ตัวอย่างโครงสร้างภายในของ SQLite มีดังนี้
    • MemPage: มีหมายเลข Page pgno, จำนวน Cell nCell, พื้นที่ดัชนีของ Cell aCellIdx, pointer ไปยัง disk image ของข้อมูล Page aData เป็นต้น
    • CellInfo: มี pPayload ที่ชี้ไปยังตำแหน่งเริ่มต้นของ payload เป็นต้น

ข้อจำกัดของ sqlite3_analyzer และฟังก์ชัน debug

  • สามารถดูข้อมูลทั่วไปของดัชนีได้ด้วย sqlite3_analyzer
    • ตัวอย่าง output มีขนาด Page 4096, จำนวน entry 1000, ความลึกของ B-tree 2, จำนวน Page ที่ใช้ 4 เป็นต้น
  • แต่เครื่องมือนี้ให้ได้เพียง ข้อมูลภาพรวม หากต้องการเจาะดู Cell และ payload ภายในดัชนีโดยตรง
  • หลังจากทดลองอยู่หลายสัปดาห์ จึงเขียนฟังก์ชันสำหรับวิเคราะห์ดัชนี
    • โค้ด: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • ฟังก์ชันนี้อ่านเนื้อหาของดัชนีที่เลือกแล้วพิมพ์ออกทาง STDOUT
    • flow คือ SQL query -> selected index -> stdout
    • output มีหมายเลข Page, หมายเลข Page ลูกฝั่งขวา, หมายเลข Cell, หมายเลข Page ลูกฝั่งซ้าย, payload และ rowId
  • สามารถรันสภาพแวดล้อมทดลองด้วย 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

การเปลี่ยนแปลงของวิธีทำ visualization

  • ตอนแรกใช้ d3-org-tree เพื่อทำ visualization โครงสร้างดัชนี
  • เมื่อ tree ลึกขึ้นและจำนวน Page ในแต่ละ level เพิ่มขึ้น การปรับระยะห่างระหว่าง Page ทำได้ยาก ภาพจึงใหญ่เกินไปและอ่านยาก
  • พยายามปรับด้วย JavaScript และ CSS แล้วแต่ไม่ลงตัว จึงเคยเปลี่ยนไปใช้ การแสดงโครงสร้างแบบข้อความ
  • output แบบข้อความแสดงจำนวน Page ทั้งหมด, จำนวน Cell ทั้งหมด, จำนวน Page·Cell ในแต่ละ level, ข้อมูล Page, ข้อมูล Cell และ payload
  • ต่อมาพัฒนาเป็น output ภาพที่ควบคุมดีไซน์และระยะห่างได้ละเอียดขึ้นโดยใช้ extension ImageMagick ของ PHP
  • ภาพสุดท้ายมีข้อมูลต่อไปนี้
    • แสดง ข้อมูลทั่วไป ของดัชนีที่มุมซ้ายบน
    • แสดงจำนวน Page และ Cell ทั้งหมดในแต่ละ level
    • แสดงหมายเลข Page, ลิงก์ลูกฝั่งขวา, ข้อมูล Cell แรกและ Cell สุดท้ายของแต่ละ Page
    • แสดงเฉพาะ Page บางส่วนในแต่ละ level โดยรวม Page แรกและ Page สุดท้ายไว้ด้วย
    • Root Page อยู่ที่ level แรก
  • คำสั่งสำหรับสร้างภาพจาก dump มีดังนี้
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

จำนวน record เปลี่ยนรูปทรงของดัชนี

  • สร้างดัชนี column1 ASC บนตาราง column1 INT NOT NULL แล้วเปลี่ยนจำนวน record เพื่อดูโครงสร้าง
  • ดัชนีที่มี 1 record ประกอบด้วย 1 level, 1 Page, 1 Cell
  • ดัชนีที่มี 1,000 records ก็สร้างและทำ visualization ด้วยวิธีเดียวกัน
  • ดัชนีที่มี 1,000,000 records มีโครงสร้างดังนี้
    • 3 levels
    • 2,930 Pages
    • 1,000,000 Cells
  • เนื่องจากเพิ่มข้อมูลตามลำดับ เมื่อ rowId = 1 ก็มี column1 = 1

ทิศทางการ sort และ expression index

  • สร้าง idx_asc และ idx_desc บนข้อมูลเดียวกันเพื่อเปรียบเทียบ ดัชนี ASC/DESC
  • ดัชนี ASC เหมือนกับดัชนีก่อนหน้า เพราะการ sort พื้นฐานเป็น ASC
    • รายการที่ rowId=1,000,000, column1=1,000,000, payload=1,000,000 อยู่ใน Cell สุดท้ายของ Page ขวาสุด
    • รายการที่ rowId=1, column1=1, payload=1 อยู่ใน Cell แรกของ Page ซ้ายสุด
  • ดัชนี DESC ถูกจัดวางกลับกัน
    • รายการที่ rowId=1, column1=1, payload=1 อยู่ใน Cell สุดท้ายของ Page ขวาสุด
    • รายการที่ rowId=1,000,000, column1=1,000,000, payload=1,000,000 อยู่ใน Cell แรกของ Page ซ้ายสุด
  • ดัชนีแบบอิง expression จะเก็บสตริงที่ expression สร้างขึ้น
    • ตัวอย่างคือดึง $.timestamp จากข้อความ JSON แล้วแปลงด้วย strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') เพื่อสร้างดัชนี ASC
    • สามารถใช้ expression ที่ซับซ้อนกว่านี้ได้เช่นกัน และในดัชนีจะเก็บเฉพาะผลลัพธ์นั้น

NULL, Partial Index, หลายคอลัมน์

  • SQLite รองรับ ดัชนี UNIQUE ที่มีค่า NULL
    • ตัวอย่างคือใส่ค่า 1, ค่า NULL หลายรายการ, และ 1000000 แล้วรัน CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • ดัชนีที่ทำ visualization ดูเหมือนจะเก็บเฉพาะค่าที่ไม่ใช่ NULL
  • Partial Index ที่ใส่เงื่อนไข WHERE column1 IS NOT NULL จะกรองค่า NULL ออก
    • ดัชนีนี้มีเพียง Page เดียว
    • นำไปสู่การค้นหาที่เร็วกว่าเมื่อเทียบกับตัวอย่าง UNIQUE ก่อนหน้า
  • ดัชนีหลายคอลัมน์ จะเก็บข้อมูลทุก field ต่อกันภายใน Cell
    • ตัวอย่างคือดัชนี (column1 ASC, column2 ASC)
    • ใน visualization field ถูกคั่นด้วย colon :

ช่วงเวลาสร้างดัชนีและผลของการสร้างใหม่

  • เปรียบเทียบกรณีสร้างดัชนีก่อนใส่ข้อมูล กับกรณีสร้างดัชนีหลังใส่ข้อมูลทั้งหมดแล้ว
  • เมื่อมีการเพิ่มข้อมูลใหม่ tree ต้อง rebalance ตัวเอง
  • การสร้างดัชนีทีเดียวบนข้อมูลที่มีอยู่แล้วอาจมีประสิทธิภาพกว่ามาก
  • ดัชนีทั้งสองดูคล้ายกัน แต่ดัชนีแบบที่สองซึ่งมีจำนวน Page น้อยกว่าอาจเร็วกว่า
  • ผลเปรียบเทียบเมื่อมี 1,000,000 Cells เป็นดังนี้
ประเภท Total Pages Total Cells
สร้างก่อน insert 3342 1000000
สร้างหลัง insert 2930 1000000
  • สามารถทำ optimization แบบคล้ายกันได้ด้วย VACUUM หรือ REINDEX
    • VACUUM จะสร้างดัชนีและตารางขึ้นใหม่พร้อมกับข้อมูล
    • REINDEX idx จะสร้างใหม่เฉพาะดัชนี
  • ทั้งสองคำสั่งลดจำนวน Page จาก 3342 เป็น 2930 ในตัวอย่าง

การจัดเก็บดัชนีตามชนิดข้อมูล

  • ข้อมูลข้อความ: สตริงสั้นจะถูกเก็บไว้ใน Cell ของดัชนีโดยตรง แต่ข้อความยาวต้องถูกเก็บแยกต่างหาก
    • ตัวอย่างคือใส่ค่าตั้งแต่ text-1 ถึง text-1000000 แล้วสร้างดัชนี column1 ASC
    • สามารถเห็นได้ว่าสตริงจริงถูกเก็บในดัชนีโดยตรง
  • ข้อมูล REAL ก็ถูกเก็บในดัชนีและนำมาทำ visualization
    • ตัวอย่างใช้ค่า 1.14, 2.14, ..., 1000000.14
  • ตรวจสอบ composite index ที่ใช้จำนวนเต็มร่วมกับข้อความด้วย
    • ตัวอย่างคือสร้างดัชนี (column1 ASC, column2 ASC) บนตาราง (column1 INT, column2 TEXT)
    • จำนวนเต็มและสตริงถูกเก็บร่วมกันใน Cell เดียวตามที่ระบุไว้ตอนสร้างดัชนี

วิธีทำซ้ำและงานถัดไป

  • การทดลองนี้แสดงให้เห็นว่าดัชนี SQLite ถูกจัดโครงสร้างอย่างไร, ข้อมูล record ถูกเก็บในหน่วยความจำอย่างไร และ B-Tree จัดระเบียบและเข้าถึงข้อมูลอย่างไร
  • visualization ใช้สำหรับวิเคราะห์และเปรียบเทียบดัชนีต่าง ๆ
  • ตัวอย่างทั้งหมดสามารถทำซ้ำได้ด้วยคำสั่งต่อไปนี้
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • โค้ดและตัวอย่างอยู่ที่ mrsuh/sqlite-index
  • งานถัดไปคือ visualization การค้นหาโดยใช้ดัชนี และการสำรวจ SQL query บางรายการ

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-11-16
ความคิดเห็นบน Hacker News

  • มีการบอกว่าแต่ละแถวในตาราง SQLite โดยค่าเริ่มต้นจะมี rowId ที่ไม่ซ้ำกัน และถ้าไม่มีคีย์หลักที่ระบุชัดเจนก็จะทำงานเหมือนคีย์หลัก แต่ในความเป็นจริง แม้จะมีคีย์หลักก็ยังใช้ rowid
    ถ้าได้เห็นการแสดงผลเชิงภาพของดัชนีคีย์หลักในตาราง WITHOUT ROWID ก็น่าจะดี ดัชนีแบบนั้นน่าสนใจเป็นพิเศษ
    แม้ดัชนีสองตัวจะดูคล้ายกัน ก็ไม่ได้แปลทันทีว่าดัชนีตัวที่สองจะเร็วกว่าเพียงเพราะมีจำนวนหน้าน้อยกว่า สิ่งสำคัญคือ ความสูงของต้นไม้ และถัดมาคือหลังจากค้นหาค่าในดัชนีแล้วต้องไปอ่านข้อมูลที่เหลือจากตารางแยกต่างหาก (rowid) หรือข้อมูลอยู่ตรงนั้นเลยเหมือน WITHOUT ROWID โดยเฉพาะกับคิวรีแบบช่วงอย่าง where 50 <= col <= 100 ความต่างจะมาก

    • ถ้าดูแค่การเข้าถึงครั้งเดียว ความสูงของต้นไม้ก็ถูกต้อง แต่ถ้าเข้าถึงดัชนีบ่อย ขนาดโดยรวมก็อาจสำคัญมากต่อ อัตราการเจอในแคช
    • เรื่องที่ว่าแม้มีคีย์หลักก็ยังใช้ rowid มีข้อยกเว้นอย่างหนึ่ง ถ้าสร้าง INTEGER PRIMARY KEY แล้ว SQLite จะใช้สิ่งนี้แทน [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite ค่อนข้างพิเศษในแทบทุกวิธีการประมวลผล และผมคิดว่าโดยเฉพาะในเรื่อง การประมวลผลคิวรี ยิ่งเป็นเช่นนั้น
    SQLite มีแนวโน้มชอบความเรียบง่ายมากกว่าประสิทธิภาพ จึงมัก implement ในวิธีที่ต่างจากฐานข้อมูลอื่น ๆ ที่ผมเคยจัดการ SQLite ไม่ได้แข่งกับฐานข้อมูลอื่นมากนัก แต่แข่งกับ ไฟล์ JSON/XML สำหรับการจัดเก็บถาวรมากกว่า ดังนั้นการดูการ implement ของ SQLite ไม่ได้ทำให้รู้ได้มากนักว่าฐานข้อมูลจริง ๆ ทำสิ่งเดียวกันอย่างไร

    • แข่งกับทั้งสองอย่างนั่นแหละ ชัดเจนว่า SQLite ถูกใช้เป็นที่เก็บข้อมูลถาวรในเครื่อง แต่ในสถานการณ์ที่ไม่ต้องมีโปรเซสเซิร์ฟเวอร์แยกต่างหาก ก็แข่งกับ ระบบจัดการฐานข้อมูลเชิงสัมพันธ์ อื่น ๆ ด้วย
      แม้จะหมายความว่าข้อกำหนดแตกต่างกันมาก แต่การใช้งานไม่ได้หยุดอยู่แค่การแทนที่ไฟล์ JSON/XML
    • SQLite เป็น เอนจินฐานข้อมูล จริง ๆ น่าจะหมายถึงว่าไม่ได้แข่งกับเซิร์ฟเวอร์ฐานข้อมูลมากกว่า
    • วิธีที่เซิร์ฟเวอร์ระบบจัดการฐานข้อมูลอื่นจัดการสตอเรจและดัชนีไม่ได้ห่างไกลกันมากนัก หลักการแทบเหมือนกัน โดยเฉพาะเมื่อ SQLite ทำงานใน โหมด WAL

  • เว็บไซต์อ่านง่ายมากจนทำให้อยากอ่านจริง ๆ

    • ดูบน iPhone แล้ว ขนาดตัวอักษร ของเนื้อหาใหญ่เกินไปมาก ข้อความสำคัญในแผนภาพกลับเล็กกว่ามาก ทำให้ถ้าจะอ่านเนื้อหาต้องยื่นโทรศัพท์ให้ห่างจากหน้า แต่ถ้าจะอ่านแผนภาพต้องดึงกลับมาใกล้ ๆ อีก รู้สึกไม่ค่อยลงตัว
    • สบายมากที่ได้ดูคอนเทนต์โดยไม่มีโฆษณาแน่น ๆ บทความก็ดีมาก

  • “indexes” เป็นได้ทั้งกริยาปัจจุบันกาลบุรุษที่สามเอกพจน์ของ “to index” และรูปพหูพจน์ของคำนาม “index” ส่วน “indices” เป็นรูปพหูพจน์แบบดั้งเดิม และใช้มากโดยเฉพาะในบริบทคณิตศาสตร์และวิทยาศาสตร์
    ในภาษาอังกฤษทั่วไป “indexes” พบได้บ่อย แต่ในสายเทคนิคบางครั้งนิยมใช้ indices เพื่อความถูกต้องทางภาษา ในบริบทแบบนี้ การใช้ “indices” ช่วยแยกให้ชัดระหว่างงานทำดัชนีกับรูปพหูพจน์ของอินเด็กซ์ ทำให้ความชัดเจนดีขึ้น

    • ใช้ได้ทั้งคู่ (https://www.nasdaq.com/articles/indexes-or-indices-whats-the...) เอกสารของ SQLite และ PostgreSQL ก็เป็นตัวอย่างเด่นที่ใช้ indexes
    • ถ้าลองทำ “time series” ให้เป็นพหูพจน์ก็ไม่ง่าย
      ในฟินแลนด์เคยเห็นใช้ “time series” เป็นพหูพจน์ และใช้ “time serie” เป็นเอกพจน์
    • ไม่รู้ว่าใช้สิทธิอำนาจอะไรถึงพูดแบบนั้น
      ระบบจัดการฐานข้อมูลเชิงสัมพันธ์หลัก ๆ ทั้งหมดใช้คำว่า indexes
    • ขึ้นอยู่กับผู้อ่านเป้าหมาย ถ้าเขียนให้วงวิชาการก็ใช้ indices แต่ถ้าเขียนให้ผู้อ่านทั่วไป “indices” อาจดูเหมือนอวดภูมิได้

  • อยากเห็นด้วยว่า PostgreSQL ทำสิ่งเดียวกันอย่างไร น่าจะมีอะไรให้เรียนรู้มากจากการเปรียบเทียบ

  • ถ้าอยากดูการจัดวางหลากหลายแบบโดยใช้แรงน้อยลง ให้เอาต์พุตเป็น TGF สำหรับ yEd ก็ได้