Une requête intéressante a été twittée par Will Leinweber de 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;J'aime cet exemple :un résultat surprenant, qui peut s'expliquer par (et aide en fait à expliquer) le comportement CTE.
Les vérités inattendues sont désignées par le mot "paradoxe", et en fait il s'agit d'une manifestation (une "instance", dans le jargon des programmeurs) de ce que l'on appelle le paradoxe de l'anniversaire .
Sa formulation la plus simple est probablement la suivante :si vous choisissez au hasard 23 personnes, la probabilité que deux d'entre elles partagent le même anniversaire est supérieure à 50 %.
Le résultat est inattendu, car il y a 366 anniversaires différents, et le nombre 23 semble très petit par rapport à 366.
Cependant elle est correcte, comme on peut le montrer avec un calcul direct. Dans PostgreSQL, nous pouvons exécuter un autre CTE récursif :
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;produisant 23 comme résultat.
Un CTE récursif s'arrête lorsque l'étape récursive n'ajoute aucune nouvelle ligne. Dans la dernière requête, acc représente la probabilité que le premier i les anniversaires sont distincts, donc la récursivité s'arrête lorsque ce nombre n'est pas supérieur à 50 %.
Dans la requête mentionnée au début, que nous appellerons la "requête aléatoire" en abrégé, le CTE récursif se termine lorsque random() n'ajoute pas de nouvelle ligne. Autrement dit, lorsque la valeur calculée de manière aléatoire a déjà été calculée lors d'une itération précédente ; c'est parce que le CTE récursif utilise UNION au lieu de UNION ALL .
C'est bien le paradoxe de l'Anniversaire, avec 366 remplacé par le nombre maximum possible de valeurs distinctes que random() peut produire. Quel est exactement ce nombre ?
Le random() renvoie une valeur en double précision, dont la définition exacte dépend du système. Cependant, toutes les valeurs de double précision ne peuvent pas être produites; la fonction C sous-jacente peut produire 2^31 résultats différents, quelle que soit la taille en bits d'une valeur en double précision. C'est assez bon dans la pratique, et en même temps la compatibilité avec toutes les différentes architectures et implémentations de bibliothèques est assurée.
Nous pouvons donc remplacer 366 par 2^31 dans notre requête, et au lieu de 23, nous obtenons 54563 comme réponse.
Est-ce que cela se rapproche de la sortie réelle de la requête aléatoire ? Exécutons-le plusieurs fois, recueillons le résultat et calculons la moyenne :
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 moyenne des résultats réels est assez proche du seuil attendu de 54563; la différence est inférieure à 0,3 %, tout à fait orthodoxement , pourrait-on dire !
