Uma consulta interessante foi twittada por Will Leinweber do 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;Eu gosto deste exemplo:um resultado surpreendente, que pode ser explicado pelo (e de fato ajuda a explicar) o comportamento da CTE.
Verdades inesperadas são indicadas com a palavra "paradoxo" e, na verdade, esta é uma manifestação (uma "instância", no jargão dos programadores) do que é conhecido como Paradoxo do aniversário .
Sua formulação mais simples é provavelmente esta:se você escolher aleatoriamente 23 pessoas, a probabilidade de que duas delas façam aniversário no mesmo dia é maior que 50%.
O resultado é inesperado, porque há 366 aniversários diferentes e o número 23 parece muito pequeno em comparação com 366.
No entanto, está correto, como pode ser mostrado com um cálculo direto. No PostgreSQL, podemos executar outro CTE recursivo:
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;produzindo 23 como resultado.
Um CTE recursivo é interrompido quando a etapa recursiva não adiciona novas linhas. Na última consulta,
acc representa a probabilidade de que o primeiro i aniversários são distintos, então a recursão para quando esse número não estiver acima de 50%. Na consulta mencionada no início, que chamaremos de “consulta aleatória” para abreviar, o CTE recursivo termina quando
random() não adiciona uma nova linha. Ou seja, quando o valor calculado aleatoriamente já foi calculado em uma iteração anterior; isso ocorre porque o CTE recursivo está usando UNION em vez de UNION ALL . Este é realmente o paradoxo do aniversário, com 366 substituído pelo número máximo possível de valores distintos que
random() pode produzir. O que exatamente é esse número? O
random() A função retorna um valor de precisão dupla, cuja definição exata depende do sistema. No entanto, nem todos os valores de precisão dupla podem ser produzidos; a função C subjacente pode produzir 2^31 resultados diferentes, independentemente do tamanho do bit de um valor de precisão dupla. Isso é bom o suficiente na prática e, ao mesmo tempo, a compatibilidade com todas as várias arquiteturas e implementações de biblioteca é garantida. Assim, podemos substituir 366 por 2^31 em nossa consulta e, em vez de 23, obtemos 54563 como resposta.
Ele se aproxima da saída real da consulta aleatória? Vamos executá-lo algumas vezes, coletar o resultado e calcular a média:
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)A média dos resultados reais está bastante próxima do limite esperado de 54563; a diferença é inferior a 0,3%, bastante ortodoxalmente , poderíamos dizer!
