ParadeDB, ctid bölümleme, tersine çevrilmiş doküman haritaları ve bitmap'lerle Postgres arama COUNT maliyetini düşürüyor

ParadeDB, arama performansı üzerine teknik yazı dizisinin ikinci bölümünü yayımladı; bu kez odak noktası BM25 tam metin indeksleri üzerindeki COUNT sorguları. Ming Ying tarafından ParadeDB blogunda yazılan ve Hacker News'in ana sayfasında öne çıkan yazı, Wikipedia veri seti üzerinde beş dakikalık çalışmalarda sekiz eşzamanlı istemciyle ölçülen üç optimizasyonu ayrıntılarıyla anlatıyor; ardından karşılaştırmayı filtrelenmiş ve sıralı arama sorgularına genişletiyor ve ParadeDB bu alanda TIN'den 66 kata kadar daha hızlı olduğunu iddia ediyor.

Darboğaz: görünürlük kontrolleri

Bir terime uyan dokümanları saymak ucuz görünür, ancak Postgres yine de eşleşen her satırın mevcut transaction için görünür olduğunu doğrulamak zorundadır. ParadeDB hn_items tablosu üzerinde tek terimli bir COUNT'u profillediğinde, görünürlük haritası ve saklanan satır tanımlayıcıları (ctid'ler) toplam 1.382 sayfa erişiminin yaklaşık %81'ini oluştururken, geri kalan her şey — posting listeleri ve metadata dahil — kalan %19'u oluşturuyordu.

ParadeDB ve TIN indekslerini benzer şekilde LSM tarzı bir düzende saklıyor: boyut eşiklerine ulaştıkça birleşen değiştirilemez (immutable) segmentler. Düz bir boyut katmanlı birleştirme politikası altında, her segment tablonun fiilen rastgele bir örneklemini tutar; dolayısıyla bir segmentin minimum ve maksimum ctid'i heap'teki neredeyse her sayfayı kapsayabilir.

Segmentleri sayfa aralığına göre bölme

İlk düzeltme, Spooky LSM compaction makalesine dayanan ve segmentleri bir veya daha fazla sütunun değerlerine göre bölebilen yeni bir bölümleme ve birleştirme stratejisi. ctid'e göre bölümleme, her segmente çakışmayan bir Postgres sayfa numarası aralığı veriyor. Her segment zaten ctid minimum ve maksimumunu kaydettiği için, motor görünürlük haritasına önceden bakabiliyor ve aralıktaki her sayfa tümüyle görünür (all-visible) olarak işaretliyse, segmentin tamamı için satır bazlı görünürlük kontrollerini ve bunlarla ilişkili sayfa okumalarını atlayabiliyor.

Bu ayrıca güncellemelerin yarattığı hasarı sınırlıyor: Değiştirilen tek bir sayfa artık indeksin büyük bölümü için bu kısayolu etkisiz hale getiremiyor, yalnızca o sayfaları kapsayan tek bir segment için getirebiliyor. Benchmark'ta görünürlükle ilgili sayfa erişimleri 1.382'den 30'a düştü.

Tersine çevrilmiş bir doküman haritası

Yine de kontrol gerektiren sayfalar ctid çözümlemesini zorunlu kılıyor ve tablo son vacuum'undan ne kadar uzaklaşırsa bu olasılık o kadar artıyor. ParadeDB'nin önceki formatı doküman başına bir ctid saklıyor ve her eşleşme için bir tane alıyordu. Yeni format bu eşlemeyi tersine çeviriyor: Sıkıştırılmış bir sütun, her heap sayfa numarasını o sayfadaki ilk doküman kimliğine eşliyor; bu, segmentlerin ctid'e göre sıralı olması ve aynı sayfadaki dokümanların ardışık kimliklere sahip olmasını garanti etmesi sayesinde çalışıyor.

Bu düzenle motor önce görünürlük haritasını kontrol ediyor ve ctid'leri yalnızca gerçekten kontrol edilmesi gereken sayfalardaki dokümanlar için çözüyor. 1.000 satır güncellendikten sonraki bir test çalışmasında, buffer erişimleri 7.500'ün üzerindekinen azalan şekilde tam 400'ün hemen altına düştü; yazıya göre %95'lik bir azalma.

Sık terimler için bitmap'ler

Üçüncü değişiklik posting listesi kodlamasını hedefliyor. ParadeDB'nin üzerine inşa ettiği arama kütüphanesi Tantivy, posting'leri BP128 ile sıkıştırıyor; bu yöntem diziyi delta kodlamalı, bit paketli 128 kimliklik bloklara bölüyor. ParadeDB'ye göre bu çoğu terim için iyi çalışıyor ancak yoğun posting listelerine sahip çok yaygın terimler için maliyetli hale geliyor; çünkü büyük BP128 dizilerini kesiştirmek veya birleştirmek önemli bir ek yük getiriyor.

Dokümanların %10'undan fazlasıyla eşleşen terimler için ParadeDB artık posting'leri bitmap olarak saklıyor; böylece birleşimler ve kesişimler dizileri tek tek gezmek yerine işlem başına 64 doküman işleyebiliyor. Buradaki ödün bilinçli: Bitmap'ler nadir terimlerde emek harcar; iki 10 eşleşmeli posting birkaç karşıştırmayla kesişirken iki bitmap çoğunlukla sıfır bitleri taramak anlamına geliyor. Yalnızca bitmap'e geçiş, Wikipedia count benchmark'ında p99 gecikmesini yarıya indirdi.

TIN ile daha geniş karşılaştırma

Yazı, TIN'in kendisi için tasarlandığı sorgu biçimlerinde, yani Top K BM25 sıralaması ve count işlemlerinde çok hızlı olduğunu kabul ediyor. Kendisini Postgres üzerinde çalışan bir Elasticsearch alternatifi olarak konumlandıran ParadeDB, üretim ortamı aramasının çok daha fazlasını içerdiğini — filtreli count'lar ve çeşitli sıralama düzenleri dahil — savunuyor ve ParadeDB 66 kata kadar olan üstünlüğünü tam da bu sorgu biçimlerinde ölçüyor. Segment bölümlemesi üzerine teknik bir derinlemesine inceleme sözü verildi; şirket Top K ve join'ler için büyük ek kazanımlardan söz ediyor.

Neden önemli

Filtreli count'lar facet panellerini, sayfalama toplamlarını ve dashboard'ları besler ve büyük veri setlerinde çoğu zaman her istekte çalışırlar. Yazı üç açıdan değerli. Birincisi, bir arama indeksinin işinin ne kadarının gerçekte Postgres görünürlük defter tutması olduğunu sayısal olarak ortaya koyuyor ve heap sayfa aralıkları ile görünürlük haritasıyla hizalanmış indeks düzenlerinin bunun büyük kısmını ortadan kaldırabileceğini gösteriyor. İkincisi, sayfa anahtrlı doküman haritası ve uyarlanabilir posting kodlaması, her Postgres indeks geliştiricisinin öğrenebileceği somut teknikler. Üçüncüsü, benchmark sonuçlarının sorgu biçimine büyük ölçüde bağlı olduğunu hatırlatması açısından yararlı — ParadeDB'nin kendisinin de dile getirdiği ve arama motorları tek bir iş yükü üzerinde karşılaştırıldığında her zaman akılda tutulması gereken bir nokta.