SQLite इंडेक्स विज़ुअलाइज़ेशन

 (mrsuh.com)
3 पॉइंट द्वारा GN⁺ 2024-11-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • SQLite इंडेक्स वास्तव में डिस्क और मेमोरी में कैसे व्यवस्थित होते हैं, यह देखने के लिए B-Tree संरचना का विश्लेषण किया गया और इंडेक्स डेटा को डंप करके विज़ुअलाइज़ किया गया
  • इंडेक्स Page और Cell इकाइयों से बने होते हैं; Page में दायाँ child link और Cell डेटा होता है, जबकि Cell में इंडेक्स डेटा, rowId, और बायाँ child link होता है
  • sqlite3_analyzer केवल Page size, entries की संख्या, B-tree depth, और उपयोग किए गए Pages जैसी जानकारी देता है, इसलिए SQLite source में debug functions जोड़े गए
  • प्रयोगों में records की संख्या, ASC/DESC, expression-based index, NULL सहित UNIQUE, Partial Index, multi-column, और text·REAL·integer+text संयोजनों की तुलना की गई
  • 1,000,000 records पर, insert से पहले इंडेक्स बनाने पर 3,342 Pages बने, जबकि insert के बाद बनाने पर 2,930 Pages बने; और VACUUM या REINDEX के बाद भी यह 2,930 Pages तक घट गया

SQLite इंडेक्स को सीधे देखने की वजह

  • यह प्रयोग इंडेक्स की बुनियादी संरचना से आगे बढ़कर वास्तविक data structure, algorithm, और disk storage format को समझने के लिए किया गया
  • लक्ष्य यह देखना था कि DBMS इंडेक्स को डिस्क और मेमोरी में कैसे स्टोर करता है, और खोज के दौरान उन तक कैसे पहुँचता है
  • प्रयोग के लिए SQLite चुनने के कारण ये थे
    • यह browser, mobile apps, और operating systems में व्यापक रूप से इस्तेमाल होने वाला DBMS है
    • अलग server के बिना केवल client application से इसे debug करना आसान है
    • MySQL या PostgreSQL की तुलना में इसका codebase छोटा है, लेकिन इंडेक्स के लिए मिलती-जुलती data structures का उपयोग करता है
    • यह open source है

Page और Cell से बना B-Tree

  • SQLite documentation के अनुसार इंडेक्स B-Tree संरचना में स्टोर होते हैं
  • SQLite में Node के समकक्ष इकाई Page है
    • Page, Cell डेटा स्टोर करता है
    • Page में दाएँ child Page का link होता है
  • Cell में इंडेक्स डेटा, rowId, और बाएँ child Page का link शामिल होता है
  • SQLite table की हर row के पास सामान्यतः एक unique rowId होता है, जो explicit primary key न होने पर primary key जैसा काम करता है
  • हर Page का आकार fixed होता है, और उसका size range 512~65,536 bytes है
  • Page और Cell headers child links स्टोर करने के लिए 4 bytes का उपयोग करते हैं
    • child Page number जानने के लिए header को अलग से get4byte(...) function से पढ़ना पड़ता है
  • SQLite की internal structures के उदाहरण इस प्रकार हैं
    • MemPage: इसमें Page number pgno, Cells की संख्या nCell, Cell index area aCellIdx, और Page data disk image pointer aData आदि शामिल हैं
    • CellInfo: इसमें payload की शुरुआत को दिखाने वाला pPayload आदि शामिल है

sqlite3_analyzer की सीमाएँ और debug functions

  • sqlite3_analyzer से इंडेक्स की सामान्य जानकारी देखी जा सकती है
    • उदाहरण output में Page size 4096, entries की संख्या 1000, B-tree depth 2, और उपयोग किए गए Pages 4 जैसी जानकारी शामिल होती है
  • लेकिन यह tool इंडेक्स के अंदर के Cell और payload को सीधे देखने के लिए केवल overview information देता है
  • कई हफ्तों के प्रयोगों के बाद इंडेक्स analysis के लिए functions लिखे गए
    • कोड: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • ये functions चुने गए इंडेक्स की सामग्री पढ़कर STDOUT पर प्रिंट करते हैं
    • flow है SQL query -> selected index -> stdout
    • output में Page number, right child Page number, Cell number, left child Page number, payload, और rowId शामिल होते हैं
  • Docker से experiment environment चलाया जा सकता है
    • 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

विज़ुअलाइज़ेशन तरीके में बदलाव

  • शुरुआत में इंडेक्स संरचना को विज़ुअलाइज़ करने के लिए d3-org-tree का उपयोग किया गया
  • जैसे-जैसे tree गहरा हुआ और हर level पर Pages बढ़े, Pages के बीच spacing समायोजित करना मुश्किल हो गया, जिससे image बहुत बड़ी और पढ़ने में कठिन हो गई
  • JavaScript और CSS से इसे समायोजित करने की कोशिश की गई, लेकिन ठीक से काम नहीं किया, इसलिए कुछ समय के लिए text-based structure display पर स्विच किया गया
  • text output में कुल Pages, कुल Cells, level-wise Pages·Cells की संख्या, Page जानकारी, और Cell जानकारी के साथ payload दिखाया जाता है
  • बाद में PHP के ImageMagick extension का उपयोग करके design और spacing पर अधिक सूक्ष्म नियंत्रण वाली image rendering बनाई गई
  • अंतिम image में ये जानकारी शामिल होती है
    • ऊपर बाईं ओर इंडेक्स की general information
    • हर level पर कुल Pages और Cells की संख्या
    • हर Page पर Page number, right child link, first Cell और last Cell की जानकारी
    • हर level में केवल कुछ Pages दिखाए जाते हैं, जिनमें पहला और आखिरी Page शामिल होता है
    • root Page पहले level पर स्थित होता है
  • dump से image बनाने का command यह है
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

records की संख्या से बदलता इंडेक्स का रूप

  • column1 INT NOT NULL table पर column1 ASC इंडेक्स बनाकर और records की संख्या बदलकर संरचना देखी गई
  • 1 record वाला इंडेक्स 1 level, 1 Page, 1 Cell से बना होता है
  • 1,000 records वाला इंडेक्स भी इसी तरह बनाकर विज़ुअलाइज़ किया गया
  • 1,000,000 records वाले इंडेक्स की संरचना यह है
    • 3 levels
    • 2,930 Pages
    • 1,000,000 Cells
  • क्योंकि डेटा क्रम से जोड़ा गया था, इसलिए rowId = 1 होने पर column1 = 1 है

sort direction और expression indexes

  • समान डेटा पर idx_asc और idx_desc बनाकर ASC/DESC indexes की तुलना की गई
  • ASC इंडेक्स default sort order ASC होने के कारण पहले वाले इंडेक्स जैसा ही है
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 वाला item सबसे दाएँ Page के आखिरी Cell में है
    • rowId=1, column1=1, payload=1 वाला item सबसे बाएँ Page के पहले Cell में है
  • DESC इंडेक्स में व्यवस्था उलटी है
    • rowId=1, column1=1, payload=1 वाला item सबसे दाएँ Page के आखिरी Cell में है
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 वाला item सबसे बाएँ Page के पहले Cell में है
  • expression-based index expression द्वारा बनाई गई string को स्टोर करता है
    • उदाहरण में JSON text से $.timestamp निकाला गया, फिर strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') से बदलकर ASC इंडेक्स बनाया गया
    • इससे अधिक जटिल expressions भी उपयोग किए जा सकते हैं, और इंडेक्स में केवल उनका result स्टोर होता है

NULL, Partial Index, multi-column

  • SQLite NULL values सहित UNIQUE index को support करता है
    • उदाहरण में 1, कई NULL, और 1000000 values डालकर CREATE UNIQUE INDEX idx ON table_test (column1 ASC) चलाया गया
    • विज़ुअलाइज़ किया गया इंडेक्स ऐसा दिखता है मानो केवल non-NULL values स्टोर कर रहा हो
  • WHERE column1 IS NOT NULL शर्त वाला Partial Index NULL values को filter करता है
    • इस इंडेक्स में केवल एक Page शामिल है
    • यह पिछले UNIQUE उदाहरण की तुलना में तेज़ search तक ले जाता है
  • multi-column index Cell के अंदर सभी field data को क्रम से स्टोर करता है
    • उदाहरण (column1 ASC, column2 ASC) इंडेक्स का है
    • visualization में fields को colon : से अलग दिखाया गया है

इंडेक्स बनाने का समय और rebuild का असर

  • डेटा डालने से पहले इंडेक्स बनाने और सारा डेटा डालने के बाद इंडेक्स बनाने की तुलना की गई
  • नया डेटा जुड़ने पर tree को खुद rebalance होना पड़ता है
  • मौजूदा डेटा पर इंडेक्स को एक बार में बनाना कहीं अधिक efficient हो सकता है
  • दोनों इंडेक्स देखने में समान लगते हैं, लेकिन कम Pages वाला दूसरा इंडेक्स तेज़ हो सकता है
  • 1,000,000 Cells के आधार पर तुलना का परिणाम यह है
वर्गीकरण Total Pages Total Cells
insert से पहले बनाया 3342 1000000
insert के बाद बनाया 2930 1000000
  • इसी तरह का optimization VACUUM या REINDEX से भी किया जा सकता है
    • VACUUM डेटा के साथ इंडेक्स और tables को फिर से बनाता है
    • REINDEX idx केवल इंडेक्स को फिर से बनाता है
  • उदाहरण में दोनों commands ने Page count को 3342 से 2930 तक घटा दिया

data type के अनुसार इंडेक्स storage

  • text data में छोटे strings सीधे इंडेक्स Cell में स्टोर हो जाते हैं, लेकिन लंबे text को अलग से स्टोर करना पड़ता है
    • उदाहरण में text-1 से text-1000000 तक values डालकर column1 ASC इंडेक्स बनाया गया
    • वास्तविक strings के सीधे इंडेक्स में स्टोर होने का रूप देखा जा सकता है
  • REAL data को भी इंडेक्स में स्टोर करके विज़ुअलाइज़ किया गया
    • उदाहरण में 1.14, 2.14, ..., 1000000.14 values का उपयोग किया गया
  • integer और text को साथ रखने वाला composite index भी देखा गया
    • उदाहरण में (column1 INT, column2 TEXT) table पर (column1 ASC, column2 ASC) इंडेक्स बनाया गया
    • integer और string, इंडेक्स बनाते समय दिए गए क्रम में उसी Cell में साथ स्टोर होते हैं

दोबारा प्रयोग करने का तरीका और आगे का काम

  • यह प्रयोग दिखाता है कि SQLite इंडेक्स कैसे संरचित होते हैं, record data मेमोरी में कैसे स्टोर होता है, और B-Tree डेटा को कैसे व्यवस्थित और access करता है
  • visualization का उपयोग अलग-अलग इंडेक्स का analysis और comparison करने के लिए किया गया
  • सभी उदाहरण निम्न command से दोबारा चलाए जा सकते हैं
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • कोड और उदाहरण mrsuh/sqlite-index में हैं
  • अगला काम index-based search visualization और कुछ SQL queries की पड़ताल है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-11-16
Hacker News टिप्पणियाँ

  • कहा गया कि SQLite table की हर row में डिफ़ॉल्ट रूप से एक unique rowId होता है, और अगर explicit primary key न हो तो वह primary key की तरह काम करता है, लेकिन असल में primary key होने पर भी rowid का इस्तेमाल होता है
    WITHOUT ROWID table के primary key index को visualize करके देखना अच्छा रहेगा। ऐसे index खास तौर पर दिलचस्प होते हैं
    भले ही दो index एक जैसे दिखें, दूसरे index में page count कम है इसका तुरंत यह मतलब नहीं कि वह तेज़ होगा। अहम चीज़ tree की height है, और उसके बाद यह कि index में value ढूँढने के बाद बाकी data अलग table (rowid) से पढ़ना पड़ता है या WITHOUT ROWID की तरह data वहीं मौजूद होता है। खासकर where 50 <= col <= 100 जैसी range query में फर्क बड़ा होता है

    • अगर सिर्फ single access को देखें तो tree height सही पैमाना है, लेकिन अगर index को अक्सर access किया जाता है तो कुल size भी cache hit rate के लिए बहुत महत्वपूर्ण हो सकता है
    • primary key होने पर भी rowid इस्तेमाल होता है, इसमें एक exception है। अगर आप INTEGER PRIMARY KEY बनाते हैं तो SQLite इसके बजाय उसी का इस्तेमाल करता है [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite अपने लगभग हर processing तरीके में काफी अलग है, और खासकर query processing में तो और भी
    SQLite performance की बजाय simplicity को प्राथमिकता देता है, इसलिए मैंने जिन दूसरे databases के साथ काम किया है उनसे अलग तरीके से चीज़ें implement करता है। SQLite दूसरे databases से मुकाबला करने के बजाय persistent storage के लिए JSON/XML files से मुकाबला करता है। इसलिए SQLite की implementation देखकर यह जानने को बहुत कुछ नहीं मिलता कि असली databases वही काम कैसे करते हैं

    • यह दोनों से मुकाबला करता है। SQLite का local persistent storage के रूप में इस्तेमाल होना साफ है, लेकिन जहाँ अलग server process की जरूरत नहीं होती, वहाँ यह दूसरे relational database management systems से भी मुकाबला करता है
      इसका मतलब है कि requirements काफी अलग हैं, लेकिन इसका उपयोग सिर्फ JSON/XML file replacement तक सीमित नहीं है
    • SQLite एक वास्तविक database engine है। शायद आपका मतलब यह है कि यह database servers से मुकाबला नहीं करता
    • दूसरे database management system servers storage और indexes को जिस तरह handle करते हैं, उससे यह बहुत दूर नहीं है। principles लगभग वही हैं, खासकर जब SQLite WAL mode में चल रहा हो

  • Website इतनी पढ़ने लायक है कि सच में पढ़ने का मन करता है

    • iPhone पर देखने पर body text का font size बहुत बड़ा है। diagram के अंदर का महत्वपूर्ण text काफी छोटा है, इसलिए body पढ़ने के लिए phone को चेहरे से दूर करना पड़ता है और diagram पढ़ने के लिए फिर पास लाना पड़ता है, जो अटपटा लगता है
    • घने-भरे ads के बिना content देख पाना सचमुच आरामदायक है। लेख भी बहुत अच्छा है

  • “indexes” verb “to index” का third-person singular present form भी है और “index” का plural noun form भी। वहीं “indices” पारंपरिक plural form है, और खासकर math/science context में ज्यादा इस्तेमाल होता है
    सामान्य English में “indexes” आम है, लेकिन tech field में linguistic precision के लिए indices को प्राथमिकता देने के मामले मिलते हैं। ऐसे context में “indices” इस्तेमाल करने से indexing action और index के plural form में फर्क साफ होता है, जिससे clarity बढ़ती है

    • दोनों ठीक हैं(https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). SQLite और PostgreSQL docs भी प्रमुख उदाहरणों के तौर पर indexes का इस्तेमाल करते हैं
    • “time series” को plural बनाने की कोशिश करें तो आसान नहीं है
      Finland में मैंने देखा है कि plural के लिए “time series” और singular के लिए “time serie” इस्तेमाल किया जाता है
    • समझ नहीं आता कि आप किस authority से ऐसा कह रहे हैं
      सभी प्रमुख relational database management systems indexes शब्द का इस्तेमाल करते हैं
    • यह target audience पर निर्भर करता है। अगर academic audience है तो indices इस्तेमाल करें, और general readers के लिए “indices” दिखावटी लग सकता है

  • अच्छा होगा अगर यह भी देखा जाए कि PostgreSQL वही काम कैसे करता है। तुलना करके सीखने लायक बहुत कुछ होगा

  • कम मेहनत में अलग-अलग layouts देखने के लिए yEd के लिए TGF output करवाना भी अच्छा रहेगा