COUNTs en de rest van de zoekfunctie echt snel maken (Deel II)

In Deel I hebben we de Top K BM25-prestaties van ParadeDB met meerdere grootteordes verbeterd. Aan het eind beloofden we een Deel II te publiceren met de focus op COUNT. Dit artikel bespreekt de optimalisaties die onze COUNT-query's veel sneller hebben gemaakt. Hier is het eindresultaat, gebruikmakend van dezelfde Wikipedia-dataset en benchmark-omgeving als het oorspronkelijke TIN-bericht:

Wikipedia COUNT-zoekopdracht (8 gelijktijdige clients · run van 5 minuten)

SysteemDoorvoersnelheid (Throughput)
ParadeDB (2,0x sneller)5353,3 QPS
TIN2645,8 QPS

Opmerking: Hogere waarden zijn beter. De gegevens zijn gebaseerd op gereconstrueerde buckets van één seconde uit de ruwe query-timings van elke worker.

Eerst leggen we uit hoe we de COUNT-prestaties hebben verbeterd. In het tweede deel gaan we verder dan ongefilterde BM25- en eenvoudige COUNT-query's om zoekopdrachten met verschillende filters en sorteervolgordes te testen, waarbij ParadeDB tot 66 keer sneller is. We zullen uitleggen waarom dit zo is en wat deze verschillen betekenen bij het vergelijken van benchmarks en het kiezen van een zoekmachine voor uw applicatie.

Maar eerst: hoe maken we COUNT sneller?

Optimalisatie 1: Segmentpartitiering

Hieronder staat de eenvoudige query waar we mee begonnen: tel het aantal documenten dat overeenkomt met de term 'database'.

EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*)
FROM hn_items
WHERE text === 'database';

Bij het profileren van deze query bleek dat het controleren van de zichtbaarheid (visibility checking) verantwoordelijk was voor meer dan 80% van onze paginatoegangen. Dit is logisch, want voor elke match moeten we de ctid-waarde ophalen en decoderen (iets wat TIN kan overslaan omdat zijn documentindex ctid is).

Aandeel paginatoegangen:

  • Zichtbaarheidskaart + opgeslagen CTID's: 1382 (81%)
  • Overig (postings, metadata, etc.): 325 (19%)

Tijdens het analyseren van de query realiseerden we ons dat we gebruik konden maken van een nieuwe functie waar we aan werken: segmentpartitiering.

Zowel ParadeDB als TIN slaan gegevens op in een structuur die lijkt op een LSM-boom. In grote lijnen betekent dit dat gegevens zijn verdeeld in onveranderlijke segmenten die worden samengevoegd wanneer ze een bepaalde drempelwaarde bereiken. Een eenvoudige, naïeve samenvoegingsstrategie houdt geen rekening met de gegevens in het segment, waardoor we kunnen aannemen dat elk segment in feite een willekeurige steekproef van de dataset bevat.

Onze nieuwe segmentpartitiering- en samenvoegingsstrategie, gebaseerd op het Spooky LSM compaction paper, stelt ons in staat om segmenten op te splitsen op basis van de waarden van één of meer kolommen. Voor deze query is het nuttige aspect dat we kunnen partitioneren op ctid (de interne rij-identificatoren van Postgres), wat elk segment een uniek bereik van Postgres-paginanummers geeft.

Zonder partitiering (overlappende min/max paginabereiken): Postgres pagina's: 0----------2999 0----------2999 0----------2999 [ Segment A ] [ Segment B ] [ Segment C ]

Met partitiering (disjuncte paginabereiken): Postgres pagina's: 0-----------999 1000-------1999 2000-------2999 [ Segment A ] [ Segment B ] [ Segment C ]

Elk segment slaat al het minimum en maximum ctid op. Met deze indeling kunnen we dat bereik vooraf controleren tegen de zichtbaarheidskaart. Als elke pagina in het bereik is gemarkeerd als 'volledig zichtbaar' (all-visible), kunnen we de zichtbaarheidscontrole (en alle bijbehorende paginalezingen) voor dat gehele segment volledig overslaan.

Bij pure size-tiered compaction kunnen die ctid min/max-bereiken bijna de hele tabel beslaan. Eén bijgewerkte pagina kan de shortcut voor de meeste segmenten onbruikbaar maken. Partitiering op ctid beperkt dit effect tot het segment dat de betreffende pagina's bevat, zodat andere segmenten de per-rij-controles kunnen blijven overslaan.

Voor onze benchmark-query bracht dit de paginatoegangen gerelateerd aan zichtbaarheid terug van 1382 naar slechts 30.

Optimalisatie 2: Het omkeren van onze DocId-map

Maar wat gebeurt er als er ten minste één pagina in het ctid-bereik van een segment moet worden gecontroleerd op zichtbaarheid? Dit wordt waarschijnlijker naarmate we verder komen vanaf de laatste (auto)vacuum. We willen niet dat een paar gewijzigde pagina's ctid-uitlezingen forceren voor elke match.

De TIN-blog legt uit dat het converteren van DocId's naar ctid-waarden overhead introduceert, en dat klopt. Wat echter niet wordt vermeld, is hoe efficiënt een DocId-naar-ctid-map kan zijn.

Onze bestaande aanpak sloeg een ctid op voor elk document en haalde deze op voor elke match. Het tellen van n matches betekende n ctid-lookups:

Doc ID: 0 1 2 3 4 5 6 CTID: (10,1) (10,2) (11,1) (11,2) (11,3) (15,1) (15,2)

Een veel efficiëntere representatie is om de map in feite om te keren: een gecomprimeerde kolom die Postgres-paginanummers (het eerste getal in de ctid-tuple) koppelt aan het eerste DocId dat op die pagina is gevonden. Dit werkt omdat onze segmenten al gesorteerd zijn op ctid, waardoor documenten op dezelfde pagina opeenvolgende DocId's hebben.

Na: documentgrenzen geïndexeerd per pagina Heap pagina: 10 11 12 13 14 15 eind Start DocId: 0 2 - - - 5 7 Pagina 11 --> doc ID's [2, 5)

Met dit nieuwe formaat kunnen we de zichtbaarheidskaart vooraf controleren en vervolgens alleen documentbereiken opzoeken voor pagina's die gecontroleerd moeten worden:

  1. Pagina die controle nodig heeft: 11
  2. DocID's die controle nodig hebben: [2, 5)
  3. Query matches: [0, 3, 6]
  4. → Voer alleen een CTID-lookup uit voor DocId's in [2, 5) → Doc 3.

Voor de bovenstaande single-term count query, na het bijwerken van 1.000 rijen, verminderde dit de buffer-toegangen van meer dan 7.500 naar net onder de 400: een reductie van 95%.

Optimalisatie 3: Bitmaps zijn geweldig voor veelvoorkomende termen

Tantivy gebruikt BP128-codering voor zijn postinglijsten. BP128 betekent dat de postings-array is verdeeld in blokken van 128, waarbij elk blok bitpacked en delta-encoded is. Deze blokken bevatten ook de scoregrenzen waarmee het blockmax-algoritme niet-competitieve blokken kan overslaan tijdens BM25-ranking.

Bij het profileren ontdekten we dat deze representatie goed werkt voor de meeste termen, met uitzondering van zeer veelvoorkomende termen met dichte postinglijsten. Voor deze termen merkten we dat het kruisen (intersecting) of samenvoegen (unioning) van grote BP128-arrays aanzienlijke overhead veroorzaakte, en dat het representeren van postings als bitmaps deze bewerkingen veel goedkoper maakte.

Voorbeeld:

  • Document ID's: [1, 3, 4, 7]
  • Bitmap: één bit per mogelijk document ID (0 1 0 1 1 0 0 1)
  • BP128: slaat gaten tussen document ID's op, vervolgens bitpacked (Gaps: 1, 2, 1, 3)

Om de afweging tussen BP128 en bitmaps te illustreren, kijken we naar twee scenario's:

  1. Zeldzame termen: Twee termen die elk 10 van de miljoen documenten matchen. Het kruisen van hun BP128-encoded arrays vereist slechts een handvol vergelijkingen. Het scannen van twee equivalente bitmaps zou echter betekenen dat er een miljoen bits per stuk verwerkt moeten worden, waarvan de meeste nullen zijn (verspilde arbeid).
  2. Veelvoorkomende termen: Twee termen die elk ongeveer 500.000 van de miljoen documenten matchen. In dit geval kunnen bitmaps efficiënter zijn, omdat bitwise AND/OR 64 documenten tegelijk kan verwerken, in plaats van de arrays één voor één te doorlopen.

We hebben een bitmap-representatie van postings geïntroduceerd voor termen die voldoende dicht zijn (meer dan 10% van de documenten matchen). Deze wijziging alleen al halveerde de p99-latentie in onze Wikipedia count-benchmark.

De rest van de zoekfunctie

TIN is zeer snel in de query-vormen waarvoor het is geoptimaliseerd: Top K via BM25 en counts. ParadeDB streeft ernaar een Elasticsearch-alternatief op Postgres te zijn. Vanuit dat perspectief zijn BM25 en counts slechts het topje van de ijsberg.

Beschouw bijvoorbeeld de volgende zoekopdrachten over de Hacker News-dataset:

1. Gefilterde count

Vraag: Hoeveel berichten bevatten de term "database" EN hebben meer dan 10 Hacker News-punten ontvangen?

SysteemQueryResultaat
ParadeDB`SELECT COUNT(*) FROM hn_items WHERE text \\\'database' AND score > 10;`777,3 QPS
TINSELECT COUNT(*) FROM hn_items WHERE text ==> 'database' AND score > 10;77,6 QPS

Resultaat: ParadeDB is 10,0x sneller.

2. Gefilterde Top K op basis van BM25-relevantie

Vraag: Geef me de Top 10 meest relevante berichten die de term "database" bevatten EN meer dan 10 Hacker News-punten hebben ontvangen.

SysteemQueryResultaat
ParadeDB`SELECT id, text, "by", score, pdb.score(id) AS relevance FROM hn_items WHERE text \\\'database' AND score > 10 ORDER BY relevance DESC LIMIT 10;`820,4 QPS
TINSELECT id, text, "by", score, tin.score(ctid, denseratio => 0.1) AS relevance FROM hnitems WHERE text ==> 'database' AND score > 10 ORDER BY relevance DESC LIMIT 10;70,5 QPS

Resultaat: ParadeDB is 11,6x sneller.

3. Top K zoekopdracht gesorteerd op tijd

Vraag: Geef me de Top 10 meest recente berichten die de term "database" bevatten.

SysteemQueryResultaat
ParadeDB`SELECT id, text, "by", score, "time" FROM hn_items WHERE text \\\'database' ORDER BY "time" DESC NULLS LAST LIMIT 10;`377,8 QPS
TINSELECT id, text, "by", score, "time" FROM hn_items WHERE text ==> 'database' ORDER BY "time" DESC NULLS LAST LIMIT 10;17,4 QPS

Resultaat: ParadeDB is 21,7x sneller.

PlanetScale is het ermee eens dat deze query's belangrijk zijn. In hun eigen blogpost schrijven ze: "Een goede tekstindex in Postgres moet al deze zaken ondersteunen, terwijl hij ook joins en ingewikkelde WHERE-clausules over full-text en andere kolomtypes afhandelt."

TIN is momenteel niet erg snel in deze gefilterde en op tijd gesorteerde query's. Omdat hun Wikipedia- en StackExchange-workloads slechts één geïndexeerde tekstkolom bevatten, wordt dit gat niet zichtbaar. Echte applicatietabellen zijn breder: zoekresultaten worden vaak gefilterd op metadata-waarden of gesorteerd op velden zoals tijdstempels of numerieke waarden.

Dit brengt ons bij een breder punt: de workload die u kiest, bepaalt vaak het verhaal dat u vertelt. Toen we onze benchmarker introduceerden, legden we uit dat we een tool hadden gebouwd die elke workload kon accommoderen. PlanetScale ontwierp er een waarin TIN uitblonk. We stelden dat dit blinde vlekken in onze BM25- en count-prestaties blootlegde en hebben dit rigoureus geoptimaliseerd.

Toch geloven we niet dat dit ParadeDB bestempelt als de "snelste zoekmachine", op Postgres of anders. Geen enkele benchmark kan dat, zeker niet een die is ontworpen door hetzelfde team dat het product bouwt. De enige manier om uit te vinden wat voor u het snelst is, is door uw eigen query's te testen op uw eigen data.

Is er een fundamenteel architectuurverschil?

De lanceringspost van TIN schreef het prestatievoordeel toe aan de keuze van de document-identificator. Wij zijn daar sceptisch over. We denken echter dat er een dieper, fundamenteel architectuurverschil is dat het gat bij complexere query's verklaart: hoeveel van de query kan naar de index worden gepusht (push-down).

TIN is expliciet een tekst-alleen index. Elke index bestrijkt één tekstkolom, waardoor niet-tekstfilters worden overgelaten aan Postgres en diens andere indexen. Voor query's waarbij we filterden op een numerieke waarde of sorteerden op tijd, vertrouwt TIN op B-tree indexen over die niet-tekstkolommen. ParadeDB kan al deze kolommen samen in één index indexeren.

Dit onderscheid is cruciaal voor zowel filtering als sortering:

  1. Filtering: Bij query's met zowel tekst- als niet-tekstfilters moeten de TIN- en B-tree indexen onafhankelijk van elkaar al hun matches produceren voordat ze worden gecombineerd. De B-tree weet niet welke documenten aan de tekstquery voldoen, waardoor er miljoenen matches verzameld kunnen worden die de intersectie later weer weggooit.
  2. Sortering: Bij sorteren op tijd kan TIN de tekstmatching niet coördineren met de tijdsordening. Postgres moet de matches buiten de index sorteren, in plaats van dat de zoekfunctie de 10 nieuwste matches bijhoudt terwijl hij doorgaat.

Moderne engines zoals ParadeDB (en Elasticsearch) lossen dit op door tekst- en metastructuren samen op te slaan, gekoppeld aan dezelfde document-identificator. Dit maakt het mogelijk om tekstmatching, filtering en sortering tijdens de uitvoering te coördineren.

Het verschil wordt duidelijk in de indexdefinities:

ParadeDB (tekst en filters in één index):

CREATE INDEX hn_items_idx
ON public.hn_items
USING paradedb (
((text)::pdb.unicode_words(
'pnorms=true',
)),
score,
"time"
)
WITH (partition_by=ctid, target_segment_count=4);

TIN (tekst apart, B-trees voor andere velden):

CREATE INDEX hn_items_text_bm25_idx
ON public.hn_items
USING tin (text)
WITH (initial_segment_count='4');

CREATE INDEX hn_items_score
ON public.hn_items USING btree (score);

CREATE INDEX hn_items_time
ON public.hn_items USING btree ("time");

Slotgedachten

Deel I riep meer reacties op dan we hadden verwacht. We willen herhalen dat de open-source zoek- en databasegemeenschappen een lange traditie hebben van vriendelijke samenwerking en competitie. Projecten als Lucene en Tantivy wisselen constant ideeën uit en verbeteren elkaars prestaties; dit drijft de innovatie vooruit en maakt applicaties in de echte wereld sneller. Als committers aan Tantivy delen we die ethos.

We zagen dat TIN zijn BM25-prestaties verbeterde als reactie op Deel I en we feliciteren het team hiermee. We zijn blij om opnieuw vergelijkingen te maken zodra de nieuwe versie beschikbaar is.

Een woord over onze benchmarkbenadering

In de vorige berichten kwamen alle cijfers uit onze benchmarker-tool, die workloads draait met k6. Toen we echter COUNT gingen vergelijken, zagen we een probleem met de client-side latentie.

Bij zeer lage latenties (bijv. 1,6ms voor ParadeDB versus 3,6ms voor TIN) beïnvloedde de extra netwerktijd op het pad van TIN het resultaat materieel. We wisten dat TIN werd beïnvloed door netwerklatentie in meer mate dan ParadeDB. Daarom stopten we met het gebruik van de benchmarker voor deze specifieke vergelijking en stapten we over op een server-side PL/pgSQL benadering.

Deze methode registreert doorvoersnelheid en latentie zonder netwerkverkeer, waardoor netwerkoverhead wordt geëlimineerd. Hoewel we niet graag een andere tool gebruiken, was dit de enige manier om de systemen nauwkeurig te vergelijken zonder dat PlanetScale onterecht gestraft zou worden voor hogere lag en jitter. Interessant is dat, hoewel deze aanpak eerlijker is, er zeer weinig verschil was in de uiteindelijke ratio's.

***

Voetnoten:

  1. Voeg partition_by = ctid toe aan de index-opties.
  2. Deze post benchmarkt TIN versie 1.0.4. ParadeDB is gebenchmarkt vanaf main op commit a637cbee55a987807325e445b00c31ae64ef7241. Voor bestaande gebruikers vereisen de bitmap/ctid-optimalisaties een reindex.
  3. Er zijn nog steeds enkele verschillen. TIN gebruikte een PlanetScale M-640 Intel machine, terwijl ParadeDB draaide in een 8-CPU Docker container op een i7i.8xlarge instance. Beide configuraties gebruikten dezelfde NVMe-opslag en Intel-chipsets.