Het artikel beschrijft een specifiek performance-probleem met de SELECT DISTINCT-clausule in Postgres. Hoewel men intuïtief zou verwachten dat de query snel is bij een correcte indexering, voert Postgres in werkelijkheid een volledige indexscan uit van alle rijen die aan de predicates voldoen, ongeacht het aantal unieke waarden.
Dit wordt problematisch bij 'smalle maar diepe' workloads: situaties met weinig unieke waarden (partities), maar zeer veel rijen per waarde. Omdat Postgres geen 'loose index scan' ondersteunt (een feature die bijvoorbeeld MySQL wel heeft), schaalt de latentie lineair mee met het totale aantal rijen in plaats van met het aantal unieke resultaten.
Om dit te omzeilen, stelt de auteur het gebruik van een recursieve Common Table Expression (CTE) voor. Deze methode dwingt Postgres om iteratief de min() waarde op te vragen, waardoor per unieke waarde slechts één rij wordt opgehaald. Hierdoor wordt de complexiteit teruggebracht naar $O(\text{aantal unieke waarden})$, wat resulteert in constante latentie, ongeacht de grootte van de partities.
Postgres SELECT DISTINCT schaalt niet
Er is de laatste tijd geen tekort aan populaire blogposts over hoe Postgres schaalt of waarom je het voor alles zou moeten gebruiken. In dit artikel doen we iets anders: we beschrijven een probleem dat we hadden met een Postgres-functie die intuïtief zou moeten schalen, maar dat in de praktijk niet gebeurt.
SELECT DISTINCT is een ogenschijnlijk onschuldige clausule die alle unieke waarden van een kolom zoekt. De prestatiekenmerken zijn echter niet wat je zou verwachten: ongeacht hoe je je tabel indexeert en ongeacht hoe weinig unieke waarden er opgehaald moeten worden, zal SELECT DISTINCT altijd elke rij scannen die voldoet aan de predicates.
We merkten dit onlangs op bij het diagnosticeren van de prestaties van een workload voor wachtrijen (queues) die op Postgres is gebaseerd. Hier bleek SELECT DISTINCT de duurste query te zijn, hoewel deze de eenvoudigste en goedkoopste leek. In dit artikel leggen we uit wat er is gebeurd, welke ontwerpbeslissingen in Postgres SELECT DISTINCT traag maken en hoe je dit kunt omzeilen.
Het vinden van unieke partities met SELECT DISTINCT
We observeerden de vertraging in een workload met gepartitioneerde wachtrijen op Postgres. Elke wachtrij is verdeeld in partities (bijvoorbeeld één per gebruiker), zodat flowcontrol onafhankelijk per partitie kan worden toegepast (bijvoorbeeld om elke gebruiker maximaal één taak tegelijk te laten uitvoeren).
De eerste stap bij het ophalen van workflows uit een gepartitioneerde wachtrij is het vinden van alle "actieve" partities; dit zijn partities met een workflow met de status ENQUEUED. Oorspronkelijk gebruikten we SELECT DISTINCT om dit te doen.
Wat SELECT DISTINCT doet, is het vinden van alle unieke waarden van een kolom gegeven een bepaalde voorwaarde. Deze query zoekt dus alle unieke, niet-NULL partitiesleutels tussen de ENQUEUED workflows op een specifieke wachtrij. We verwachtten dat deze query snel zou zijn, omdat deze correct is geïndexeerd met een index op de wachtrijnaam, de status van de workflow en de partitiesleutel.
Intuïtief ziet de index er als volgt uit: workflows zijn geordend in een boomstructuur, eerst op wachtrijnaam, dan op status en vervolgens op partitiesleutel. Dit stelt Postgres in staat om workflows efficiënt te lokaliseren met behulp van deze drie velden.
Vanwege deze structuur verwachtten we dat de prestaties van deze query $O(\text{aantal actieve partities})$ zouden zijn. Immers, om aan deze query te voldoen, hoeft Postgres slechts één rij uit elke unieke partitie te zoeken en vervolgens de gevonden partitiesleutels terug te geven.
In het begin leek dit naar behoren te werken. De meeste van onze wachtrij-workloads waren "breed maar ondiep", met veel partities maar weinig wachtende workflows per partitie. Voor deze gevallen presteerde de query zoals verwacht. We stuitten echter al snel op problemen met "smalle maar diepe" workloads, waarbij er weinig partities waren, maar deze elk veel wachtende workflows bevatten. We verwachtten dat de query in minder dan een milliseconde klaar zou zijn omdat er zo weinig partities waren, maar in plaats daarvan duurde het seconden. We realiseerden ons snel dat de query niet schaalde met het aantal actieve partities, maar met het totale aantal wachtende workflows, wat het onaanvaardbaar traag maakte.
We hebben deze observatie gevalideerd met een benchmark waarbij we het aantal partities vastzetten op 10, maar het aantal rijen per partitie schaalden van 100 naar 1 miljoen. Hieruit bleek dat de latentie van de query lineair meeschaalt met het aantal rijen per partitie.
Om te begrijpen waarom dit gebeurde en hoe we dit konden oplossen, moeten we kijken naar hoe Postgres deze query plant en uitvoert.
Het queryplan van SELECT DISTINCT
Wanneer we het queryplan bekeken dat Postgres gebruikte voor de SELECT DISTINCT-query (uitgaande van 1 miljoen wachtende workflows verdeeld over 3 partities), zagen we het volgende:
In essentie voert Postgres een volledige indexscan uit: de index wordt volledig doorlopen om elke individuele wachtende workflow op een specifieke wachtrij op te halen (in dit geval 1 miljoen rijen in totaal) om vervolgens te controleren of deze een unieke partitiesleutel bevat. Dit verklaart de prestaties: de reden dat de looptijd schaalt met het totale aantal wachtende workflows is dat Postgres daadwerkelijk elke workflow scant.
Dit is uiterst inefficiënt: in dit voorbeeld scande Postgres 1 miljoen rijen om slechts drie partitiesleutels te vinden die direct uit de index hadden kunnen worden opgehaald.
De Postgres query-planner kiest voor dit plan omdat er geen alternatief is. Elke operator die in Postgres is geïmplementeerd voor het scannen van een index, voert een volledige indexscan uit en haalt alle geïndexeerde waarden op die aan de predicates voldoen. Andere relationele databases doen dit beter: MySQL biedt bijvoorbeeld een "loose index scan"-operator die alleen elke unieke waarde ophaalt die aan de predicates voldoet.
Interessant is dat Postgres 18 iets vergelijkbaars heeft toegevoegd: een skip scan-optimalisatie die rijen "overslaat" bij het doorzoeken van een multicolumn-index op een kolom die niet de meest linkse kolom is. In ons geval scant dit echter nog steeds alle rijen die aan de predicates voldoen, waardoor het niet kan worden gebruikt om SELECT DISTINCT te versnellen. Afzonderlijk was er in 2018 een aanzienlijke poging om een loose index scan toe te voegen, maar deze werd na vier jaar inspanning en wisselingen in het beheerteam stopgezet.
De vertraging verminderen
Omdat de prestaties van SELECT DISTINCT schalen met de grootte van de tabel en niet met het aantal unieke waarden, is het op grote schaal niet bruikbaar. Om efficiënt het aantal unieke waarden in een tabel te tellen, hebben we een workaround nodig: een complexere query die Postgres effectief dwingt om een efficiënt queryplan te genereren.
Deze query is opmerkelijk moeilijk leesbaar omdat deze gebruikmaakt van een recursieve common table expression (CTE). In essentie is dit een manier om imperatieve code te schrijven in anders declaratieve SQL. De query werkt als een loop waarvan de eerste iteratie de "kleinste" partitiesleutel vindt en de daaropvolgende iteraties telkens de "volgende" unieke partitiesleutel vinden.
Elke iteratie van de loop voert een SELECT min() uit op een gesorteerde index, waardoor er slechts één waarde wordt opgehaald in plaats van de hele index te scannen. Omdat elke iteratie een vaste hoeveelheid werk verricht en het totale aantal iteraties gelijk is aan het aantal unieke partities, biedt deze query de benodigde prestaties van $O(\text{aantal partities})$.
Om deze prestaties te valideren, hebben we de nieuwe query gebenchmarkt door het aantal partities op 10 vast te zetten en het aantal rijen per partitie te variëren van 1.000 naar 1 miljoen. Hieruit bleek dat de mediane latentie niet verandert, ongeacht hoe groot de partities worden.
Postgres SELECT DISTINCT schaalt niet
Er is de laatste tijd geen tekort aan populaire blogposts over hoe Postgres schaalt of waarom je het voor alles zou moeten gebruiken. In dit artikel doen we iets anders: we beschrijven een probleem dat we hadden met een Postgres-functie die intuïtief zou moeten schalen, maar dat in de praktijk niet gebeurt.
SELECT DISTINCT is een ogenschijnlijk onschuldige clausule die alle unieke waarden van een kolom zoekt. De prestatiekenmerken zijn echter niet wat je zou verwachten: ongeacht hoe je je tabel indexeert en ongeacht hoe weinig unieke waarden er opgehaald moeten worden, zal SELECT DISTINCT altijd elke rij scannen die voldoet aan de predicates.
We merkten dit onlangs op bij het diagnosticeren van de prestaties van een workload voor wachtrijen (queues) die op Postgres is gebaseerd. Hier bleek SELECT DISTINCT de duurste query te zijn, hoewel deze de eenvoudigste en goedkoopste leek. In dit artikel leggen we uit wat er is gebeurd, welke ontwerpbeslissingen in Postgres SELECT DISTINCT traag maken en hoe je dit kunt omzeilen.
Het vinden van unieke partities met SELECT DISTINCT
We observeerden de vertraging in een workload met gepartitioneerde wachtrijen op Postgres. Elke wachtrij is verdeeld in partities (bijvoorbeeld één per gebruiker), zodat flowcontrol onafhankelijk per partitie kan worden toegepast (bijvoorbeeld om elke gebruiker maximaal één taak tegelijk te laten uitvoeren).
De eerste stap bij het ophalen van workflows uit een gepartitioneerde wachtrij is het vinden van alle "actieve" partities; dit zijn partities met een workflow met de status ENQUEUED. Oorspronkelijk gebruikten we SELECT DISTINCT om dit te doen.
Wat SELECT DISTINCT doet, is het vinden van alle unieke waarden van een kolom gegeven een bepaalde voorwaarde. Deze query zoekt dus alle unieke, niet-NULL partitiesleutels tussen de ENQUEUED workflows op een specifieke wachtrij. We verwachtten dat deze query snel zou zijn, omdat deze correct is geïndexeerd met een index op de wachtrijnaam, de status van de workflow en de partitiesleutel.
Intuïtief ziet de index er als volgt uit: workflows zijn geordend in een boomstructuur, eerst op wachtrijnaam, dan op status en vervolgens op partitiesleutel. Dit stelt Postgres in staat om workflows efficiënt te lokaliseren met behulp van deze drie velden.
Vanwege deze structuur verwachtten we dat de prestaties van deze query $O(\text{aantal actieve partities})$ zouden zijn. Immers, om aan deze query te voldoen, hoeft Postgres slechts één rij uit elke unieke partitie te zoeken en vervolgens de gevonden partitiesleutels terug te geven.
In het begin leek dit naar behoren te werken. De meeste van onze wachtrij-workloads waren "breed maar ondiep", met veel partities maar weinig wachtende workflows per partitie. Voor deze gevallen presteerde de query zoals verwacht. We stuitten echter al snel op problemen met "smalle maar diepe" workloads, waarbij er weinig partities waren, maar deze elk veel wachtende workflows bevatten. We verwachtten dat de query in minder dan een milliseconde klaar zou zijn omdat er zo weinig partities waren, maar in plaats daarvan duurde het seconden. We realiseerden ons snel dat de query niet schaalde met het aantal actieve partities, maar met het totale aantal wachtende workflows, wat het onaanvaardbaar traag maakte.
We hebben deze observatie gevalideerd met een benchmark waarbij we het aantal partities vastzetten op 10, maar het aantal rijen per partitie schaalden van 100 naar 1 miljoen. Hieruit bleek dat de latentie van de query lineair meeschaalt met het aantal rijen per partitie.
Om te begrijpen waarom dit gebeurde en hoe we dit konden oplossen, moeten we kijken naar hoe Postgres deze query plant en uitvoert.
Het queryplan van SELECT DISTINCT
Wanneer we het queryplan bekeken dat Postgres gebruikte voor de SELECT DISTINCT-query (uitgaande van 1 miljoen wachtende workflows verdeeld over 3 partities), zagen we het volgende:
In essentie voert Postgres een volledige indexscan uit: de index wordt volledig doorlopen om elke individuele wachtende workflow op een specifieke wachtrij op te halen (in dit geval 1 miljoen rijen in totaal) om vervolgens te controleren of deze een unieke partitiesleutel bevat. Dit verklaart de prestaties: de reden dat de looptijd schaalt met het totale aantal wachtende workflows is dat Postgres daadwerkelijk elke workflow scant.
Dit is uiterst inefficiënt: in dit voorbeeld scande Postgres 1 miljoen rijen om slechts drie partitiesleutels te vinden die direct uit de index hadden kunnen worden opgehaald.
De Postgres query-planner kiest voor dit plan omdat er geen alternatief is. Elke operator die in Postgres is geïmplementeerd voor het scannen van een index, voert een volledige indexscan uit en haalt alle geïndexeerde waarden op die aan de predicates voldoen. Andere relationele databases doen dit beter: MySQL biedt bijvoorbeeld een "loose index scan"-operator die alleen elke unieke waarde ophaalt die aan de predicates voldoet.
Interessant is dat Postgres 18 iets vergelijkbaars heeft toegevoegd: een skip scan-optimalisatie die rijen "overslaat" bij het doorzoeken van een multicolumn-index op een kolom die niet de meest linkse kolom is. In ons geval scant dit echter nog steeds alle rijen die aan de predicates voldoen, waardoor het niet kan worden gebruikt om SELECT DISTINCT te versnellen. Afzonderlijk was er in 2018 een aanzienlijke poging om een loose index scan toe te voegen, maar deze werd na vier jaar inspanning en wisselingen in het beheerteam stopgezet.
De vertraging verminderen
Omdat de prestaties van SELECT DISTINCT schalen met de grootte van de tabel en niet met het aantal unieke waarden, is het op grote schaal niet bruikbaar. Om efficiënt het aantal unieke waarden in een tabel te tellen, hebben we een workaround nodig: een complexere query die Postgres effectief dwingt om een efficiënt queryplan te genereren.
Deze query is opmerkelijk moeilijk leesbaar omdat deze gebruikmaakt van een recursieve common table expression (CTE). In essentie is dit een manier om imperatieve code te schrijven in anders declaratieve SQL. De query werkt als een loop waarvan de eerste iteratie de "kleinste" partitiesleutel vindt en de daaropvolgende iteraties telkens de "volgende" unieke partitiesleutel vinden.
Elke iteratie van de loop voert een SELECT min() uit op een gesorteerde index, waardoor er slechts één waarde wordt opgehaald in plaats van de hele index te scannen. Omdat elke iteratie een vaste hoeveelheid werk verricht en het totale aantal iteraties gelijk is aan het aantal unieke partities, biedt deze query de benodigde prestaties van $O(\text{aantal partities})$.
Om deze prestaties te valideren, hebben we de nieuwe query gebenchmarkt door het aantal partities op 10 vast te zetten en het aantal rijen per partitie te variëren van 1.000 naar 1 miljoen. Hieruit bleek dat de mediane latentie niet verandert, ongeacht hoe groot de partities worden.
Groetjes,