CTE en de verjaardagsparadox

Will Leinweber van Postgres Open heeft een interessante vraag gesteld:

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

Ik hou van dit voorbeeld:een verrassend resultaat, dat kan worden verklaard door (en inderdaad helpt bij het verklaren van) CTE-gedrag.

Onverwachte waarheden worden aangeduid met het woord 'paradox', en in feite is dit een manifestatie (een 'exemplaar' in het jargon van programmeurs) van wat bekend staat als de Verjaardagsparadox .

De eenvoudigste formulering is waarschijnlijk deze:als u willekeurig 23 personen kiest, is de kans dat twee van hen dezelfde verjaardag delen groter dan 50%.

Het resultaat is onverwacht, want er zijn 366 verschillende verjaardagen, en het aantal 23 lijkt erg klein in vergelijking met 366.

Het is echter correct, zoals kan worden aangetoond met een directe berekening. In PostgreSQL kunnen we nog een recursieve CTE uitvoeren:

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;

met als resultaat 23.

Een recursieve CTE stopt wanneer de recursieve stap geen nieuwe rijen toevoegt. In de laatste zoekopdracht, acc geeft de kans weer dat de eerste i verjaardagen zijn verschillend, dus recursie stopt wanneer dat aantal niet hoger is dan 50%.

In de aan het begin genoemde zoekopdracht, die we kortweg de "willekeurige zoekopdracht" zullen noemen, eindigt de recursieve CTE wanneer random() voegt geen nieuwe rij toe. Dat wil zeggen, wanneer de willekeurig berekende waarde al is berekend in een eerdere iteratie; dat komt omdat de recursieve CTE UNION gebruikt in plaats van UNION ALL .

Dit is inderdaad de verjaardagsparadox, waarbij 366 is vervangen door het maximaal mogelijke aantal verschillende waarden dat random() kan produceren. Wat is dat nummer precies?

De random() functie retourneert een waarde met dubbele precisie, waarvan de exacte definitie afhangt van het systeem. Niet alle dubbele precisiewaarden kunnen echter worden geproduceerd; de onderliggende C-functie kan 2^31 verschillende resultaten opleveren, ongeacht de bitgrootte van een waarde met dubbele precisie. Dit is in de praktijk goed genoeg en tegelijkertijd is de compatibiliteit met alle verschillende architecturen en bibliotheekimplementaties verzekerd.

Dus we kunnen 366 vervangen door 2^31 in onze zoekopdracht, en in plaats van 23 krijgen we 54563 als antwoord.

Komt het in de buurt van de werkelijke output van de willekeurige query? Laten we het een paar keer uitvoeren, het resultaat verzamelen en het gemiddelde berekenen:

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)

Het gemiddelde van de werkelijke resultaten ligt vrij dicht bij de verwachte drempel van 54563; het verschil is minder dan 0,3%, nogal orthodox , zouden we kunnen zeggen!