Una domanda interessante è stata twittata da Will Leinweber di 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;
Mi piace questo esempio:un risultato sorprendente, che può essere spiegato da (e in effetti aiuta a spiegare) il comportamento CTE.
Le verità inaspettate sono indicate con la parola "paradosso", e in effetti questa è una manifestazione (un'"istanza", nel gergo dei programmatori) di quello che è noto come il paradosso del compleanno .
La sua formulazione più semplice è probabilmente questa:se scegli casualmente 23 persone, la probabilità che due di loro condividano lo stesso compleanno è maggiore del 50%.
Il risultato è inaspettato, perché ci sono 366 compleanni diversi e il numero 23 sembra molto piccolo rispetto a 366.
Comunque è corretto, come si può dimostrare con un calcolo diretto. In PostgreSQL possiamo eseguire un altro CTE ricorsivo:
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;
producendo 23 come risultato.
Un CTE ricorsivo si interrompe quando il passaggio ricorsivo non aggiunge nuove righe. Nell'ultima query, acc
rappresenta la probabilità che il primo i
i compleanni sono distinti, quindi la ricorsione si interrompe quando il numero non supera il 50%.
Nella query menzionata all'inizio, che chiameremo in breve "query casuale", il CTE ricorsivo termina quando random()
non aggiunge una nuova riga. Cioè, quando il valore calcolato in modo casuale è già stato calcolato in un'iterazione precedente; questo perché il CTE ricorsivo utilizza UNION
invece di UNION ALL
.
Questo è davvero il paradosso del compleanno, con 366 sostituito dal numero massimo possibile di valori distinti che random()
può produrre. Qual è esattamente quel numero?
Il random()
La funzione restituisce un valore a doppia precisione, la cui esatta definizione dipende dal sistema. Tuttavia, non tutti i valori di doppia precisione possono essere prodotti; la funzione C sottostante può produrre 2^31 risultati diversi, indipendentemente dalla dimensione in bit di un valore a doppia precisione. Questo è abbastanza buono in pratica e allo stesso tempo è assicurata la compatibilità con tutte le varie architetture e implementazioni di librerie.
Quindi possiamo sostituire 366 con 2^31 nella nostra query e invece di 23 otteniamo 54563 come risposta.
Si avvicina all'output effettivo della query casuale? Eseguiamolo alcune volte, raccogliamo il risultato e calcoliamo la media:
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)
La media dei risultati effettivi è abbastanza vicina alla soglia prevista di 54563; la differenza è inferiore allo 0,3%, abbastanza ortodossalmente , potremmo dire!