PlanetScale heeft Text Search uitgebracht en we hebben hier veel over te zeggen (Deel I)

We willen het team van PlanetScale complimenteren. Het is geweldig om te zien dat er een ander Postgres-platform investeert in search (het blijkt dat mensen hun relationele data willen doorzoeken), en het is duidelijk dat er veel doordachte engineering in TIN is gestoken. We zijn ook blij te zien dat PlanetScale de benchmarktool van ParadeDB heeft overgenomen, die we precies voor dit soort tests hebben gebouwd.

Laten we één ding heel duidelijk maken: TIN is snel (ten minste 8x sneller dan ParadeDB 0.25 in elke benchmark van PlanetScale). Zo snel, dat de enige logische reactie was om stil te zijn en onze "performance optimization"-pet op te zetten. Twee weken later presenteren we hier de BM25-gerangete resultaten van vóór en na de optimalisatie, gebruikmakend van dezelfde StackExchange-benchmarkdataset, harness en machinestypes (hoewel TIN niet open-source is en daarom op PlanetScale draait):

StackExchange Top K search 150M documenten · 8 gelijktijdige cliënten · run van 5 minuten

QueriesParadeDBTIN
Throughput81.9 QPS33 QPS

Hogere waarden zijn beter. Warm-cache, read-only runs. TIN gebruikt dense_ratio=2 met search elision uitgeschakeld. Latentie gebruikt nearest-rank percentielen.

Wat interessant is, is niet zozeer dat we het gat snel hebben gedicht, maar hoe we dat hebben gedaan. De post van TIN claimt dat hun prestaties voortkomen uit een fundamenteel architectonisch verschil, waarbij de interne ctid-velden van Postgres als document-identificatoren worden gebruikt. Wij hebben dit gat echter gedicht via een aantal optimalisaties die weinig te maken hadden met hoe documenten worden geïdentificeerd. Daarnaast hebben we enkele benchmarkinstellingen aangepast die geen volledig eerlijke vergelijking boden — hierover later meer.

Laten we de fixes en configuratiewijzigingen één voor één analyseren.

Een overzicht van tekstzoeken en hoe TIN beweert sneller te zijn

De kern van elke tekstzoekindex is een postingslijst: een per-term lijst van document-identificatoren waarin die term voorkomt. Als een index documenten 1 tot 10 heeft en het woord "database" verschijnt in documenten 2 en 4, dan is de postingslijst voor "database" simpelweg [2, 4]. Postingslijsten maken het mogelijk om zeer efficiënt documenten te identificeren die aan specifieke termen voldoen.

Tantivy, de zoekbibliotheek achter ParadeDB, gebruikt sequentiële u32 document-ID's voor zijn postings. Deze identificatoren zijn intern aan Tantivy en worden toegewezen op basis van de volgorde van invoer. In dit artikel verwijst DocId naar deze u32 document-identificator.

Postgres identificeert zijn rijen via ctid-waarden. Een ctid is een tuple die wijst naar de fysieke locatie van een rij in de blokgebaseerde opslag van Postgres. Bijvoorbeeld: (190, 17) identificeert de rij die zich momenteel in slot 17 van blok 190 bevindt.

Omdat ParadeDB een Postgres-index is die wordt aangedreven door Tantivy, moet er een mapping bestaan tussen DocId en ctid-waarden. De kern van het argument van TIN is dat het direct gebruiken van ctid-waarden als document-identificatoren deze mapping elimineert en efficiënte bitmap-operaties en zichtbaarheidscontroles mogelijk maakt. PlanetScale schrijft een groot deel van het prestatievoordeel van TIN toe aan de voordelen van deze keuze.

Gaat het echt alleen om een andere document-identificator?

De aankondiging benchmarkt twee brede querytypen: Top K matches op basis van BM25-score en COUNT-queries over overeenkomende documenten.

Voor counts maakte het ctid-argument zinvol. Wanneer miljoenen matches zichtbaarheidscontroles vereisen, tellen de vertalingen van DocId naar ctid op. Het organiseren van postings rondom Postgres-pagina's creëert kansen om minder data te lezen en dat werk te batchten.

Voor BM25 Top K-queries waren we sceptisch. ParadeDB stelt ctid-lookups uit tot de uiteindelijke Top K-documenten zijn verzameld. Voor een top 10-query betekent dit 10 lookups. Deze lookups zijn niet gratis, maar ze zijn minuscuul in het profiel en verklaren geen verschil van meerdere grootteordes. In plaats daarvan vermoedden we dat we het gat konden dichten met diverse optimalisaties elders in onze code.

Deze post richt zich op onze Top K BM25-optimalisaties. We hebben ook COUNT geoptimaliseerd, wat we in Deel II zullen behandelen.

Optimalisatie 1: Verminderen van random access tijdens BM25-scoring

We begonnen met een eenvoudige query: geef de tien meest relevante documenten die een enkele term bevatten, gerangschikt op BM25-score.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, title, by
FROM hn_items
WHERE title === 'database'
ORDER BY pdb.score(id) DESC
LIMIT 10;

TIN raakte veel minder Postgres-pagina's aan dan ParadeDB bij deze query, dus we vermoedden dat dit de belangrijkste reden was voor de snelheid. ParadeDB heeft een nieuwe functie die pagina-toegang toeschrijft aan de datastructuren die in die pagina's zijn opgeslagen. Dit wees ons direct op het probleem:

DatastructuurAandeel pagina-toegangen
Fieldnorms1.513 (83%)
Overig (postings, metadata, etc.)311 (17%)

"Fieldnorms" coderen de lengte van een geïndexeerd veld van een document, wat BM25 gebruikt om scores te normaliseren. Een fieldnorm in Tantivy is klein: een documentlengte gekwantiseerd in een enkele-byte fieldnorm_id-waarde. Hoe kon iets dat zo klein is verantwoordelijk zijn voor zoveel reads?

Het probleem was lokaliteit. Tantivy slaat fieldnorms apart van postings op, in een array geïndexeerd op DocId. Het lezen van de postings van een term is sequentieel, maar het ophalen van de bijbehorende fieldnorms kan over die array springen. In Postgres betekende dit dat we voor deze query ongeveer 1.500 verschillende fieldnorm-pagina's moesten aanraken.

Onze oplossing was om een fieldnorm-array naast elke postingslijst op te slaan, in dezelfde volgorde als de DocId-waarden van de postings. De scoring kon vervolgens fieldnorms sequentieel lezen naast de postings, waardoor de verspreide lookups werden geëlimineerd. Na deze wijziging daalden de fieldnorm-toegang van 1.500 pagina's naar slechts 30.

Voorheen: Gedeelde fieldnorm-array

  • Postings: "database": [DocId waarden] → Fieldnorms: [fieldnorm IDs voor alle documenten]
  • Postings: "rust": [DocId waarden]

Nu: Fieldnorm-array per term

  • Postings: "database": [DocId waarden] → Fieldnorms: "database": [fieldnorm IDs]
  • Postings: "rust": [DocId waarden] → Fieldnorms: "rust": [fieldnorm IDs]

De trade-off is opslagruimte, aangezien de fieldnorm van een document nu wordt herhaald voor elke unieke term die het bevat. Gelukkig betekent dit niet per se dat de opslag wordt vermenigvuldigd met het aantal termen. In echte corpora hebben de meeste termen korte postingslijsten. Deze wijziging vergrootte de 28.7M HN-index met ongeveer 9%.

Optimalisatie 2: Kiezen van het juiste Blockmax Pruning-algoritme

Het uitbreken van fieldnorms zorgde voor een enorme versnelling bij queries met een klein aantal termen, maar we waren nog steeds niet tevreden met de prestaties bij disjunction queries (OR-queries) met veel termen.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, title, by
FROM hn_items
WHERE text ||| 'rust arc clone memory safety borrow checker ownership lifetime rules'
ORDER BY pdb.score(id) DESC
LIMIT 10;

We ontdekten via profiling dat de meeste tijd werd besteed aan de Blockmax WAND loop.

Ter context: Blockmax is het standaardalgoritme dat zoekmachines gebruiken om efficiënt delen van postings over te slaan bij disjunction-queries. Er zijn twee families van Blockmax: WAND en MAXSCORE.

  • Blockmax werkt door postings in blokken te verdelen en per blok de maximale mogelijke score op te slaan die een term uit dit blok kan bijdragen aan de uiteindelijke BM25-score.
  • Een blok wordt overgeslagen als de max-score de huidige Top K-drempel niet kan verslaan.
  • WAND slaat meer over, maar verbruikt meer CPU-cycli om dat te beslissen.
  • MAXSCORE slaat minder over, maar heeft minder overhead. Wanneer queries meer termen bevatten, kan de overhead van WAND groter worden dan het werk dat het bespaart.

Tantivy gebruikt WAND. Lucene gebruikte ook WAND tot 2023, waarna ze MAXSCORE introduceerden voor bepaalde queries. Tegenwoordig kiest Lucene dynamisch tussen WAND en MAXSCORE afhankelijk van de vorm van de query.

Wij hebben een MAXSCORE-pad geïmplementeerd met een eenvoudige heuristiek: MAXSCORE voor disjunctions met minstens drie termen en voldoende dichte postings, en WAND voor de rest. Voor de bovenstaande query met 10 termen brachten we de p50-latentie met ~6x en de p95 met ~8x omlaag. We zijn nu 2x sneller dan TIN op onze 28.7M HN-dataset:

Hacker News top-k search 28.7M documenten · 8 gelijktijdige cliënten · run van 5 minuten

ResultatenParadeDBTIN
Throughput344.6 QPS145.7 QPS

Hogere waarden zijn beter. Warm-cache, read-only runs. TIN gebruikt dense_ratio=0.1 met search elision ingeschakeld.

Wijzigingen in de Benchmarkconfiguratie

De benchmarks van PlanetScale waren redelijk opgesteld, met uitzondering van twee anomalieën die onbedoeld in het voordeel van TIN werkten: een syntaxfout bij ParadeDB en de manier waarop TIN omgaat met veelvoorkomende termen.

ParadeDB Syntax

We merkten dat de TIN-benchmarks de query-string parser van ParadeDB gebruikten via de @@@ operator, maar dat deze queries niet waren gekwalificeerd met een veldnaam (bijv. <query> in plaats van <veld>:<query>). Wanneer queries niet gekwalificeerd zijn, zoekt ParadeDB standaard in alle geïndexeerde tekstvelden. In de StackExchange-dataset waren zowel de id als de body kolommen geïndexeerd, wat betekent dat ParadeDB in het nadeel was omdat het in twee kolommen zocht, terwijl TIN slechts in één zocht.

Om dit te voorkomen, hebben we alle ParadeDB-queries omgezet naar onze native ||| (disjunction), &&& (conjunction) en ### (phrase) operators.

Omgaan met veelvoorkomende termen (Common Terms)

Bij de HN-benchmark versloegen we TIN gemakkelijk, maar op de StackExchange-dataset van PlanetScale liepen we nog steeds 30% achter op throughput door langere tail-latencies.

De oorzaak bleek een scoring-shortcut voor veelvoorkomende termen te zijn, die TIN dense-term elision noemt. Veelvoorkomende termen zoals "the" en "is" hebben enorme postingslijsten die duur zijn om te lezen, terwijl BM25 ze zo laag weegt dat ze de uiteindelijke rangschikking nauwelijks beïnvloeden. TIN slaat de scoring over voor elke term die in meer dan 10% van het corpus voorkomt (configureerbaar via dense_ratio).

Er is echter een trade-off: correctheid. Met elision berekent TIN een benadering van BM25. Dit kan ertoe leiden dat resultaten in een andere volgorde verschijnen dan bij een echte BM25-berekening.

Wanneer we naar de Stack Overflow-benchmark keken, waren we verrast te vinden dat er volledige queries bestonden uit deze veelvoorkomende woorden (bijv. "is it", "to a"), omdat ze waren gegenereerd door willekeurige woordreeksen uit het corpus te samplen. Op deze (niet-realistische) queries sloeg TIN bijna al het werk over, terwijl ParadeDB exacte scores berekende.

Voor TIN (met elision ingeschakeld) vonden we dat:

  • 47.8% van de queries minstens één resultaat in de Top 10 teruggaf dat niet in de "ware" Top 10 zat.
  • 6.4% van de queries resultaten gaf waarbij geen enkele van de Top 10 in de "ware" Top 10 zat.
  • Bij disjunctions was dit het ergst: 88.2% van de queries had minstens één foutief resultaat in de Top 10.

Om deze reden gebruiken we in onze hoofdvergelijking exact BM25 voor beide engines, met TIN geconfigureerd op dense_ratio=2 (uitgeschakeld). We tonen echter ook de resultaten met de standaard elision-instellingen, zodat lezers hun eigen conclusies kunnen trekken.

TIN dense_ratio vergelijking 150M documenten · mixed Top K · 8 gelijktijdige cliënten · run van 5 minuten

ConfiguratiesThroughput
ParadeDB81.9 QPS
ParadeDB (stopwords ingeschakeld)161.9 QPS
TIN (dense_ratio=2)35.5 QPS
TIN (dense_ratio=0.1)114.4 QPS

Is er een superieure document-identificator?

Wat betreft de keuze tussen ctid (TIN) en u32 document-identificatoren (ParadeDB), zien wij dit als een trade-off.

Het uitgangspunt van TIN is dat ctid-waarden een universeel goede keuze zijn. Echter, niets comprimeert beter dan dichte, gesorteerde, unieke integers. De meeste zoeksystemen gebruiken daarom u32 DocId-waarden. Een 48-bit identificator (ctid) is niet inherent efficiënter.

Dichte u32 DocId-waarden hebben bovendien een groot voordeel: ze maken het eenvoudig om postings te koppelen aan columnar storage. Dit is cruciaal voor:

  • Top K per veld: "Geef producten die matchen, gesorteerd op prijs."
  • Range filters: "Geef producten tussen $50 en $100."
  • Faceting: "Geef de top 10 producten en groepeer per categorie."

Allemaal vereisen dit een columnair formaat. Met DocId is de verbinding direct: document 42 correspondeert met rij 42 in elke kolom. Een ctid geeft deze positie niet; het identificeert een fysieke locatie in Postgres. Om de prijs van dat document uit een kolom te halen, is er een mapping of lookup nodig.

TIN is geweldig in BM25-scoring en document-counting, maar dat is slechts het topje van de ijsberg van wat een zoekmachine (zoals Elasticsearch) doet. Voor de rest van de zoekfunctionaliteit heb je een columnaire representatie nodig.

Waarom Tantivy de juiste keuze blijft voor ons

TIN schrijft zijn voordeel toe aan het gebruik van ctid in plaats van DocId. Wij hebben het gat echter gedicht zonder onze identificatoren te wijzigen, door:

  1. Dichtere datastructuren met betere lokaliteit te schrijven.
  2. Een Blockmax-algoritme met een hogere throughput te gebruiken.
  3. Kleine optimalisaties in het lazy lezen van data.

De meeste van deze wijzigingen vonden plaats in Tantivy. Deze exercitie heeft ons vertrouwen in Tantivy versterkt. Het brengt meer dan een decennium aan ontwikkeling en battle-testing door some of the world's largest companies. Tantivy sluit misschien niet direct perfect aan op de bloklayout van Postgres, maar de extensibiliteit en functies compenseren dat ruimschoots.

Slotbeschouwingen

De open-source search-gemeenschap heeft een lange traditie van samenwerking. We hopen dat dit een nieuw voorbeeld daarvan wordt. We waarderen dat de auteurs van TIN hun engineering-beslissingen hebben gedeeld, zelfs als het project zelf niet open-source is. Al ons werk is open, en we zijn al begonnen met het upstreamen van de verbeteringen naar Tantivy.

We hebben een 0.26.0-rc.2 release candidate uitgebracht zodat deze resultaten reproduceerbaar zijn. Voor bestaande ParadeDB-gebruikers worden deze verbeteringen opgenomen in de volgende stabiele release, 0.26.0. Deze wijzigingen zijn backwards compatible, hoewel een reindex vereist is om alle optimalisaties te ervaren.

In het volgende deel bespreken we de optimalisaties die we hebben doorgevoerd voor onze COUNT-prestaties (spoiler: ook die vereisten geen wijziging van onze document-identificatoren). Tot dan, happy searching!

***

Voetnoten

  1. En vooral Eric ZomboDB, die voorheen bij ParadeDB werkte en het PlanetScale TIN-product heeft aangestuurd.
  2. Of zo dichtbij als mogelijk was. Omdat TIN niet open-source is, draaide het op de cloud van PlanetScale (8 CPU / 32 GB / NVMe). ParadeDB draaide op een vergelijkbare machine van dezelfde EC2-familie in een Docker-container.
  3. Het is mogelijk dat dit in MMAP ook niet optimaal is, aangezien MMAP op OS-niveau ook 4 KB pagina's gebruikt.
  4. Onze HN-dataset heeft hier geen last van omdat we alleen woorden uit een lijst met "interessante woorden" combineren.
  5. Deze metingen zijn verkregen door de resultaten van TIN met denseratio=0.1 te vergelijken met denseratio=2 (uitgeschakeld). We definiëren de "ware" Top 10 als de resultaten zonder dense-term elision.