SQLite İndeks Görselleştirmesi

 (mrsuh.com)
3 puan yazan GN⁺ 2024-11-16 | 1 yorum | WhatsApp'ta paylaş
  • SQLite indekslerinin gerçekte disk ve bellekte nasıl yerleştiğini görmek için B-Tree yapısı analiz edildi; indeks verileri dökülüp görselleştirildi
  • İndeksler Page ve Cell birimlerinden oluşur; Page sağ çocuk bağlantısını ve Cell verilerini, Cell ise indeks verisi·rowId·sol çocuk bağlantısını taşır
  • sqlite3_analyzer tarafından sağlanan Page boyutu, girdi sayısı, B-tree derinliği ve kullanılan Page sayısı tek başına yeterli olmadığından SQLite kaynak koduna debug fonksiyonları eklendi
  • Deneylerde kayıt sayısı, ASC/DESC, ifade tabanlı indeks, NULL içeren UNIQUE, Partial Index, çoklu sütun, metin·REAL·tamsayı+metin kombinasyonları karşılaştırıldı
  • 1.000.000 kayıtta indeks eklemeden önce oluşturulunca 3.342 Pages, eklemeden sonra oluşturulunca 2.930 Pages oldu; VACUUM veya REINDEX sonrasında da 2.930 Pages’a düştü

SQLite indeksini doğrudan inceleme nedeni

  • Bu, indeksin temel yapısının ötesine geçip gerçek veri yapısını, algoritmayı ve diskte saklanma biçimini doğrulamaya yönelik bir deneydir
  • Amaç, DBMS’in indeksi disk ve bellekte nasıl sakladığını ve arama sürecinde buna nasıl eriştiğini incelemektir
  • Deney hedefi olarak SQLite seçilmesinin nedenleri şunlardır
    • Tarayıcılarda, mobil uygulamalarda ve işletim sistemlerinde yaygın kullanılan bir DBMS’tir
    • Ayrı bir sunucu olmadan yalnızca istemci uygulamasıyla debug etmek kolaydır
    • MySQL veya PostgreSQL’e göre kod tabanı daha küçüktür, ancak indekslerde benzer veri yapıları kullanır
    • Açık kaynaktır

Page ve Cell’den oluşan B-Tree

  • SQLite dokümantasyonuna göre indeksler B-Tree yapısı olarak saklanır
  • SQLite’ta Node’a karşılık gelen birim Page’dir
    • Page, Cell verilerini saklar
    • Page, sağ çocuk Page’e giden bir bağlantıya sahiptir
  • Cell, indeks verisini, rowId’yi ve sol çocuk Page bağlantısını içerir
  • SQLite tablolarındaki her satır varsayılan olarak benzersiz bir rowId’ye sahiptir ve açık bir birincil anahtar olmadığında birincil anahtar gibi davranır
  • Her Page sabit bir boyuta sahiptir; boyut aralığı 512~65.536 bytes’tır
  • Page ve Cell başlıkları, çocuk bağlantısını saklamak için 4 bytes kullanır
    • Çocuk Page numarasını öğrenmek için başlığı get4byte(...) fonksiyonuyla ayrıca okumak gerekir
  • SQLite iç yapılarına örnekler şöyledir
    • MemPage: Page numarası pgno, Cell sayısı nCell, Cell indeks alanı aCellIdx, Page verisinin disk imajı işaretçisi aData vb. içerir
    • CellInfo: payload başlangıç konumunu gösteren pPayload vb. içerir

sqlite3_analyzer’ın sınırları ve debug fonksiyonları

  • sqlite3_analyzer ile indeksin genel bilgileri görülebilir
    • Örnek çıktıda Page boyutu 4096, girdi sayısı 1000, B-tree derinliği 2, kullanılan Page sayısı 4 vb. yer alır
  • Ancak bu araç, indeks içindeki Cell ve payload’u doğrudan incelemek için yalnızca özet bilgi düzeyinde kalır
  • Birkaç haftalık deneyden sonra indeks analizi için fonksiyonlar yazıldı
    • Kod: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Bu fonksiyonlar seçilen indeks içeriğini okuyup STDOUT’a yazdırır
    • Akış SQL query -> selected index -> stdout şeklindedir
    • Çıktıda Page numarası, sağ çocuk Page numarası, Cell numarası, sol çocuk Page numarası, payload ve rowId bulunur
  • Deney ortamı Docker ile çalıştırılabilir
    • 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

Görselleştirme yöntemindeki değişim

  • Başta indeks yapısını görselleştirmek için d3-org-tree kullanıldı
  • Ağaç derinleşip her seviyedeki Page sayısı arttıkça Page’ler arasındaki boşluğu ayarlamak zorlaştı; görüntü çok büyüdü ve okunması güçleşti
  • JavaScript ve CSS ile ayarlamaya çalışıldı ancak istenen uyum sağlanamayınca bir süre metin tabanlı yapı gösterimine geçildi
  • Metin çıktısı toplam Page sayısını, toplam Cell sayısını, seviye bazında Page·Cell sayılarını, Page bilgilerini, Cell bilgilerini ve payload’u gösterir
  • Daha sonra PHP’nin ImageMagick eklentisi kullanılarak tasarım ve boşlukların daha hassas kontrol edilebildiği görsel çıktıya geliştirildi
  • Nihai görsel şu bilgileri içerir
    • Sol üstte indeksin genel bilgilerini gösterir
    • Her seviyede toplam Page sayısını ve Cell sayısını gösterir
    • Her Page için Page numarasını, sağ çocuk bağlantısını, ilk Cell ve son Cell bilgilerini gösterir
    • Her seviyede Page’lerin yalnızca bir kısmını gösterir; ilk Page ve son Page dahildir
    • Kök Page ilk seviyede yer alır
  • Dökümden görsel üretme komutu şöyledir
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Kayıt sayısının indeks biçimini değiştirmesi

  • column1 INT NOT NULL tablosunda column1 ASC indeksi oluşturulup kayıt sayısı değiştirilerek yapı incelendi
  • 1 kayıtlık indeks 1 seviye, 1 Page ve 1 Cell’den oluşur
  • 1.000 kayıtlık indeks de aynı yöntemle oluşturulup görselleştirildi
  • 1.000.000 kayıtlık indeks şu yapıya sahiptir
    • 3 seviye
    • 2.930 Pages
    • 1.000.000 Cells
  • Veriler sırayla eklendiği için rowId = 1 olduğunda column1 = 1’dir

Sıralama yönü ve ifade indeksleri

  • Aynı veriler üzerinde idx_asc ve idx_desc oluşturularak ASC/DESC indeksleri karşılaştırıldı
  • ASC indeksinde varsayılan sıralama ASC olduğundan önceki indeksle aynıdır
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 olan öğe sağ uçtaki Page’in son Cell’inde bulunur
    • rowId=1, column1=1, payload=1 olan öğe sol uçtaki Page’in ilk Cell’inde bulunur
  • DESC indeksinde yerleşim tersinedir
    • rowId=1, column1=1, payload=1 olan öğe sağ uçtaki Page’in son Cell’inde bulunur
    • rowId=1,000,000, column1=1,000,000, payload=1,000,000 olan öğe sol uçtaki Page’in ilk Cell’inde bulunur
  • İfade tabanlı indeks ifadenin ürettiği dizeyi saklar
    • Örnekte JSON metninden $.timestamp çıkarılıp strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch') ile dönüştürülerek ASC indeks oluşturulur
    • Daha karmaşık ifadeler de kullanılabilir; indekste yalnızca sonuçları saklanır

NULL, Partial Index, çoklu sütun

  • SQLite, NULL değerleri içeren UNIQUE indeksleri destekler
    • Örnekte 1, çok sayıda NULL, 1000000 değeri eklenip CREATE UNIQUE INDEX idx ON table_test (column1 ASC) çalıştırılır
    • Görselleştirilen indeks yalnızca NULL olmayan değerleri saklıyor gibi görünür
  • WHERE column1 IS NOT NULL koşulu eklenen Partial Index, NULL değerlerini filtreler
    • Bu indeks yalnızca bir Page içerir
    • Önceki UNIQUE örneğine göre daha hızlı arama sağlar
  • Çoklu sütun indeksi, tüm alan verilerini Cell içinde sırayla saklar
    • Örnek (column1 ASC, column2 ASC) indeksidir
    • Görselleştirmede alanlar iki nokta : ile ayrılır

İndeks oluşturma zamanı ve yeniden yapılandırmanın etkisi

  • İndeksi verileri eklemeden önce oluşturma ile tüm veriler eklendikten sonra oluşturma karşılaştırıldı
  • Yeni veri eklendiğinde ağaç kendi kendini yeniden dengelemek zorundadır
  • Mevcut veriler için indeksi tek seferde oluşturmak çok daha verimli olabilir
  • İki indeks benzer görünse de Page sayısı daha az olan ikinci indeks daha hızlı olabilir
  • 1.000.000 Cells bazında karşılaştırma sonucu şöyledir
Tür Total Pages Total Cells
Eklemeden önce oluşturma 3342 1000000
Eklemeden sonra oluşturma 2930 1000000
  • Benzer optimizasyon VACUUM veya REINDEX ile yapılabilir
    • VACUUM, indeksleri ve tabloları verilerle birlikte yeniden oluşturur
    • REINDEX idx, yalnızca indeksi yeniden oluşturur
  • Her iki komut da örnekte Page sayısını 3342’den 2930’a düşürdü

Veri tipine göre indeks saklama

  • Metin verileri için kısa dizeler doğrudan indeks Cell’inde saklanır, ancak uzun metinlerin ayrı saklanması gerekir
    • Örnekte text-1den text-1000000e kadar değerler eklenip column1 ASC indeksi oluşturulur
    • Gerçek dizelerin doğrudan indekste saklandığı görülebilir
  • REAL verileri de indekste saklanıp görselleştirildi
    • Örnek 1.14, 2.14, ..., 1000000.14 değerlerini kullanır
  • Tamsayı ve metni birlikte kullanan bileşik indeks de incelendi
    • Örnekte (column1 INT, column2 TEXT) tablosunda (column1 ASC, column2 ASC) indeksi oluşturulur
    • Tamsayı ve dize, indeks oluşturulurken belirtildiği şekilde aynı Cell içinde birlikte saklanır

Yeniden üretme yöntemi ve sonraki işler

  • Deney, SQLite indekslerinin nasıl yapılandırıldığını, kayıt verilerinin bellekte nasıl saklandığını ve B-Tree’nin verileri nasıl organize edip eriştiğini gösterir
  • Görselleştirme, farklı indeksleri analiz etmek ve karşılaştırmak için kullanılır
  • Tüm örnekler şu komutla yeniden üretilebilir
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • Kod ve örnekler mrsuh/sqlite-index içinde bulunur
  • Sonraki işler indeks tabanlı arama görselleştirmesi ve birkaç SQL sorgusunu incelemektir

İlgili okumalar

1 yorum

 
GN⁺ 2024-11-16
Hacker News yorumları

  • SQLite tablolarındaki her satırın varsayılan olarak benzersiz bir rowId’si olduğu ve açıkça tanımlanmış bir birincil anahtar yoksa birincil anahtar gibi davrandığı söylenmiş; ama pratikte birincil anahtar olsa bile rowid kullanılır
    WITHOUT ROWID tablolarının birincil anahtar indeksini görselleştirmek güzel olurdu. Bu tür indeksler özellikle ilginç
    İki indeks benzer görünse bile ikinci indeksin daha az sayfası olması, doğrudan daha hızlı olduğu anlamına gelmez. Önemli olan ağacın yüksekliğidir; ardından da indekste değeri bulduktan sonra kalan verilerin ayrı bir tablodan (rowid) okunmasının gerekip gerekmediği ya da WITHOUT ROWID’de olduğu gibi verinin doğrudan orada bulunup bulunmadığı gelir. Özellikle where 50 <= col <= 100 gibi aralık sorgularında fark büyüktür

    • Tekil erişim açısından bakıldığında ağaç yüksekliği doğru ölçüttür; ancak indekse sık erişiliyorsa toplam boyut da önbellek isabet oranı için çok önemli olabilir
    • Birincil anahtar olsa bile rowid kullanılması konusunda bir istisna var. INTEGER PRIMARY KEY oluşturursanız SQLite onun yerine bunu kullanır [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite, neredeyse tüm işleme biçimlerinde oldukça kendine özgü; özellikle de sorgu işleme konusunda böyle olduğunu düşünüyorum
    SQLite performanstan çok sadeliği tercih etme eğiliminde olduğundan, çalıştığım diğer veritabanlarından farklı şekillerde uygulanmış çok şey var. SQLite diğer veritabanlarıyla rekabet etmekten ziyade kalıcı depolama için kullanılan JSON/XML dosyalarıyla rekabet eder. Bu yüzden SQLite’ın uygulamasına bakmak, gerçek veritabanlarının aynı işleri nasıl yaptığı hakkında çok fazla şey öğretmez

    • İkisiyle de rekabet eder. SQLite’ın yerel kalıcı depolama olarak kullanıldığı açık; ancak ayrı bir sunucu sürecinin gerekmediği durumlarda diğer ilişkisel veritabanı yönetim sistemleriyle de rekabet eder
      Bu, gereksinimlerin epey farklı olduğu anlamına gelse de kullanım alanı yalnızca JSON/XML dosyalarının yerine geçmekle sınırlı değildir
    • SQLite gerçek bir veritabanı motorudur. Muhtemelen veritabanı sunucularıyla rekabet etmediği kastediliyor
    • Diğer veritabanı yönetim sistemi sunucularının depolama ve indeksleri ele alış biçiminden çok da uzak değildir. İlkeler neredeyse aynıdır; özellikle SQLite WAL modunda çalışırken bu daha da böyledir

  • Web sitesi o kadar okunaklı ki gerçekten okumak isteği uyandırıyor

    • iPhone’da bakınca gövde metninin yazı boyutu çok büyük. Diyagramlardaki önemli metin ise çok daha küçük; bu yüzden gövdeyi okumak için telefonu yüzümden uzaklaştırmam, diyagramı okumak içinse yeniden yaklaştırmam gerekiyor; garip hissettiriyor
    • Yoğun reklamlar olmadan içeriği görebilmek gerçekten rahat. Yazı da çok iyi

  • “indexes”, “to index” fiilinin üçüncü tekil şahıs geniş zaman biçimi olduğu gibi “index”in çoğul isim biçimi de olabilir. Buna karşılık “indices” geleneksel çoğul biçimdir ve özellikle matematik ve bilim bağlamlarında sık kullanılır
    Genel İngilizcede “indexes” yaygındır; ancak teknik alanlarda dilsel doğruluk adına indices tercih edilebiliyor. Bu bağlamda “indices” kullanmak, indeksleme işlemiyle indeksin çoğulunu ayırarak açıklığı artırır

    • İkisi de kabul edilebilir(https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). SQLite ve PostgreSQL belgeleri de tipik örnekler olarak indexes kullanır
    • “time series”i çoğul yapmaya çalışınca iş kolay değil
      Finlandiya’da çoğul olarak “time series”, tekil olarak “time serie” kullanıldığını gördüm
    • Bunu hangi otoriteye dayanarak söylüyorsun bilmiyorum
      Başlıca ilişkisel veritabanı yönetim sistemlerinin hepsi indexes terimini kullanır
    • Hedef okura göre değişir. Akademiye yönelikse indices kullanılır; genel okura yönelikse “indices” gösteriş gibi görünebilir

  • PostgreSQL’in aynı işi nasıl yaptığını da görmek güzel olurdu. Karşılaştırarak öğrenilecek çok şey var gibi

  • Daha az işle farklı yerleşimleri görmek için yEd’e yönelik TGF çıktısı üretmesi de iyi olabilir