PostgreSQL
 sql >> Database >  >> RDS >> PostgreSQL

CTE e il paradosso del compleanno

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!