Sådan estimerer planner’en antal rækker

Planlæggeren ser ikke på dine data under planlægningen. Den læser forudberegnede oversigter fra systemkataloget pg_statistic, som udfyldes af ANALYZE (køres automatisk af autovacuum). Den læsevenlige visning af kataloget er pg_stats.

For hver kolonne viser pg_stats byggestenene til estimeringen:

• null_frac — andelen af NULL-værdier.
• n_distinct — antallet af forskellige værdier.
• most_common_vals / most_common_freqs — MCV-listen.
• histogram_bounds — intervaller for de resterende værdier, som ikke er MCV'er.

Selektivitet er den andel af rækkerne, som et prædikat forventes at udvælge, mellem 0 og 1. Det estimerede antal rækker er ganske enkelt:

• estimated_rows = selectivity × total_rows

hvor total_rows kommer fra pg_class.reltuples (som også opdateres af ANALYZE). Estimering handler altså om to spørgsmål: hvor mange rækker har tabellen, og hvilken andel overlever hvert prædikat? Alt andet er detaljer om, hvordan denne andel beregnes.

For column = 'value' undersøger planlæggeren først listen over most_common_vals (MCV). Hvis værdien findes på listen, bruger den den nøjagtige hyppighed fra most_common_freqs — ingen beregning, kun et opslag.

Eksempel: Hvis most_common_vals = {shipped, pending, cancelled} og most_common_freqs = {0.62, 0.25, 0.08}, har status = 'shipped' en selektivitet på 0.62. I en tabel med 1.000.000 rækker giver det et estimat på 620.000 rækker.

MCV'er gør det muligt at estimere skæve fordelinger præcist — planlæggeren ved nøjagtigt, hvor populære de hyppige værdier er.

Hvis værdien ikke findes på MCV-listen, antager planlæggeren, at alle værdier uden for MCV-listen er lige sandsynlige. Den beregner den resterende sandsynlighedsmasse og fordeler den ligeligt:

• residual = 1 − sum(most_common_freqs) − null_frac
• n_distinct_residual = n_distinct − count(MCVs)
• selectivity = residual / n_distinct_residual

Derfor kan estimater for sjældne værdier være dårlige, når den lange hale i sig selv er skæv: Antagelsen om en ensartet fordeling i resten holder ikke. MCV'er dækker toppen; resten er en flad tilnærmelse af halen.

For uligheder som amount > 500 eller created_at BETWEEN … bruger planlæggeren histogram_bounds. Disse grænser opdeler værdierne uden for MCV-listen i intervaller, som hver indeholder omtrent det samme antal rækker (samme dybde, ikke samme bredde).

For at estimere amount < X finder planlæggeren, hvor X ligger blandt grænserne, og interpolerer lineært i det interval, der indeholder værdien. Med N intervaller repræsenterer hvert interval cirka 1/N af rækkerne uden for MCV-listen, så planlæggeren tæller hele intervaller under X plus en brøkdel af grænseintervallet.

Med flere AND-betingelser på forskellige kolonner ganger PostgreSQL deres selektiviteter, fordi den antager, at kolonnerne er statistisk uafhængige:

• sel(A AND B) = sel(A) × sel(B)

Hvis status = 'shipped' er 0.62, og country = 'DE' er 0.10, estimerer planlæggeren, at 0.062 af tabellen opfylder betingelserne. Men hvis afsendte ordrer for det meste er tyske, kan den reelle andel være 0.30 — en undervurdering på 5 gange. Korrelerede kolonner er dér, hvor statistikker for enkelte kolonner fejler, og planerne bryder sammen.

Når kolonner er korrelerede, kan du oprette udvidet statistik med CREATE STATISTICS. Typen dependencies lærer planlæggeren om funktionelle afhængigheder, mens mcv gemmer kombinationer af de mest almindelige værdier på tværs af flere kolonner, så AND-prædikater estimeres samlet i stedet for at blive ganget.

Efter at objektet er oprettet, skal du køre ANALYZE på tabellen for at udfylde det. Derefter læser planlæggeren den samlede fordeling og holder op med at antage uafhængighed for disse kolonner.

Antallet af rækker i et join bygger på estimaterne for de enkelte tabeller. For et equi-join estimerer PostgreSQL omtrent antallet af resultatrækker sådan:

• rows ≈ (outer_rows × inner_rows) / max(n_distinct_outer, n_distinct_inner)

med n_distinct for joinkolonnen fra hver side. Derfor får et dårligt estimat for en enkelt tabel en kaskadeeffekt: Hvis planlæggeren tror, at en filtreret side har 5 rækker, selv om den faktisk har 50.000, viderefører alle joins over den fejlen og kan vælge et nested loop, der kører 50.000 gange, i stedet for et hash-join.

Estimater er kun så gode som den statistik, de bygger på. Praktiske greb:

• Kør ANALYZE efter masseindlæsninger, og lad autovacuum holde statistikken opdateret.
• Hæv opløsningen for skæve kolonner med ALTER TABLE … ALTER COLUMN … SET STATISTICS n (en større MCV-liste og et større histogram).
• Tilføj CREATE STATISTICS for grupper af korrelerede kolonner.
• Sammenlign estimerede og faktiske rækker i EXPLAIN ANALYZE for at finde den node, hvor gættet først bliver forkert.

Du fejlsøger nedefra og op i planen: Den første node med en stor forskel mellem estimeret og faktisk antal rækker er normalt den egentlige årsag.

Du kan nu følge et rækkeestimat fra start til slut:

• ANALYZE udfylder pg_statistic / pg_stats og angiver reltuples.
• Lighed bruger MCV-listen, når værdien er almindelig, og ellers den ensartede rest fordelt over n_distinct.
• Intervaller interpolerer i histogram_bounds med samme dybde.
• Flere AND'er ganger selektiviteterne under antagelse af uafhængighed — den vigtigste kilde til estimeringsfejl.
• Udvidet statistik (dependencies, mcv) korrigerer for korrelerede kolonner.
• Joins kombinerer estimaterne fra hver side via joinkolonnens n_distinct, så fejl i en enkelt tabel forplanter sig opad.

Selektivitet × antal rækker giver de kardinaliteter, der styrer valg af scanning, join og rækkefølge. Når du mestrer dette, holder EXPLAIN-output op med at være mystisk — det bliver en historie, du kan læse.