CTE a narozeninový paradox

Will Leinweber z Postgres Open napsal zajímavý dotaz:

-- 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;

Líbí se mi tento příklad:překvapivý výsledek, který lze vysvětlit (a skutečně pomáhá vysvětlit) chování CTE.

Neočekávané pravdy se označují slovem „paradox“ a ve skutečnosti je to projev („případ“, v programátorském žargonu) toho, co je známé jako narozeninový paradox .

Nejjednodušší formulace je pravděpodobně tato:pokud náhodně vyberete 23 osob, pravděpodobnost, že dva z nich budou mít stejné narozeniny, je větší než 50 %.

Výsledek je neočekávaný, protože existuje 366 různých narozenin a číslo 23 se zdá velmi malé ve srovnání s 366.

Je to však správné, jak to lze ukázat přímým výpočtem. V PostgreSQL můžeme spustit další rekurzivní 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;

výsledkem je 23.

Rekurzivní CTE se zastaví, když rekurzivní krok nepřidá žádné nové řádky. V posledním dotazu acc představuje pravděpodobnost, že první i narozeniny jsou odlišné, takže rekurze se zastaví, když toto číslo nepřekročí 50 %.

V dotazu zmíněném na začátku, kterému budeme zkráceně říkat „náhodný dotaz“, rekurzivní CTE končí, když random() nepřidá nový řádek. To znamená, když náhodně vypočítaná hodnota již byla vypočtena v předchozí iteraci; je to proto, že rekurzivní CTE používá UNION místo UNION ALL .

Toto je skutečně narozeninový paradox, kdy 366 je nahrazeno maximálním možným počtem různých hodnot, které random() může vyrábět. Co přesně je to číslo?

random() funkce vrací hodnotu s dvojnásobnou přesností, jejíž přesná definice závisí na systému. Ne všechny hodnoty s dvojnásobnou přesností však lze vytvořit; základní funkce C může poskytnout 2^31 různých výsledků bez ohledu na bitovou velikost hodnoty s dvojnásobnou přesností. To je v praxi dostačující a zároveň je zajištěna kompatibilita se všemi různými architekturami a implementacemi knihoven.

V našem dotazu tedy můžeme nahradit 366 2^31 a místo 23 dostaneme jako odpověď 54563.

Blíží se to skutečnému výstupu náhodného dotazu? Spusťte to několikrát, shromážděte výsledek a vypočítejte průměr:

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)

Průměr skutečných výsledků je poměrně blízko očekávané hranici 54563; rozdíl je menší než 0,3 %, zcela ortodoxně , dalo by se říci!