CTE och födelsedagsparadoxen

En intressant fråga har twittats av Will Leinweber från Postgres Open:

-- this returns a different result each time it is ran
with recursive s as (
  select random()
union
  select random() from s
) select count(*) from s;

Jag gillar det här exemplet:ett överraskande resultat som kan förklaras av (och faktiskt hjälper till att förklara) CTE-beteende.

Oväntade sanningar betecknas med ordet "paradox", och i själva verket är detta en manifestation (en "instans", i programmerares jargong) av vad som kallas födelsedagsparadoxen .

Den enklaste formuleringen är förmodligen denna:om du slumpmässigt väljer 23 personer är sannolikheten att två av dem har samma födelsedag större än 50 %.

Resultatet är oväntat, eftersom det finns 366 olika födelsedagar, och siffran 23 verkar väldigt liten jämfört med 366.

Det är dock korrekt, eftersom det kan visas med en direkt beräkning. I PostgreSQL kan vi köra ytterligare en rekursiv CTE:

WITH RECURSIVE r(i,acc) AS (
  SELECT 1, 1 :: double precision
UNION
  SELECT i + 1,
    acc * (((366 - i) :: double precision) / 366)
  FROM r WHERE acc > 0.5
) SELECT count(1) FROM r;

producerar 23 som resultat.

En rekursiv CTE stoppas när det rekursiva steget inte lägger till några nya rader. I den sista frågan, acc representerar sannolikheten att den första i födelsedagar är distinkta, så rekursionen upphör när den siffran inte är över 50 %.

I frågan som nämndes i början, som vi kort och gott kallar "random query", avslutas den rekursiva CTE när random() lägger inte till en ny rad. Det vill säga när det slumpmässigt beräknade värdet redan har beräknats i en tidigare iteration; det beror på att den rekursiva CTE använder UNION istället för UNION ALL .

Detta är verkligen födelsedagsparadoxen, med 366 ersatta av det högsta möjliga antalet distinkta värden som random() kan producera. Vad är det för nummer?

random() funktion returnerar ett dubbelt precisionsvärde, vars exakta definition beror på systemet. Inte alla dubbla precisionsvärden kan dock produceras; den underliggande C-funktionen kan ge 2^31 olika resultat, oavsett bitstorleken på ett dubbelt precisionsvärde. Detta är tillräckligt bra i praktiken, och samtidigt säkerställs kompatibilitet med alla olika arkitekturer och biblioteksimplementeringar.

Så vi kan ersätta 366 med 2^31 i vår fråga, och istället för 23 får vi 54563 som svar.

Kommer den i närheten av den faktiska utdata från den slumpmässiga frågan? Låt oss köra det några gånger, samla in resultatet och beräkna medelvärdet:

gianni=# create table t(n int);
CREATE TABLE

gianni=# with recursive s as (
  select random()
union
  select random() from s
) insert into t select count(1) from s;
INSERT 0 1

/* repeat the last query 49 times */

gianni=# select count(1), avg(n) from t;

 count | avg
-------+--------------------
    50 | 54712.060000000000
 (1 row)

Genomsnittet av de faktiska resultaten ligger ganska nära den förväntade tröskeln på 54563; skillnaden är mindre än 0,3 %, ganska ortodoxt , kan vi säga!