Interesujące zapytanie zostało wysłane przez Willa Leinwebera z 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;Podoba mi się ten przykład:zaskakujący wynik, który można wytłumaczyć (i rzeczywiście pomaga wyjaśnić) zachowanie CTE.
Nieoczekiwane prawdy są oznaczane słowem „paradoks” i w rzeczywistości jest to przejaw („przykład”, w żargonie programistów) tego, co jest znane jako paradoks urodzinowy. .
Jego najprostsze sformułowanie jest prawdopodobnie takie:jeśli losowo wybierzesz 23 osoby, prawdopodobieństwo, że dwie z nich mają te same urodziny, jest większe niż 50%.
Wynik jest nieoczekiwany, ponieważ jest 366 różnych urodzin, a liczba 23 wydaje się bardzo mała w porównaniu z 366.
Jest jednak słuszne, co można wykazać za pomocą obliczeń bezpośrednich. W PostgreSQL możemy uruchomić kolejne rekurencyjne CTE:
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;w wyniku czego powstaje 23.
Rekurencyjne CTE zatrzymuje się, gdy krok rekurencyjny nie dodaje żadnych nowych wierszy. W ostatnim zapytaniu acc reprezentuje prawdopodobieństwo, że pierwszy i urodziny są różne, więc rekursja zatrzymuje się, gdy liczba ta nie przekracza 50%.
We wspomnianym na początku zapytaniu, które w skrócie nazwiemy „losowym zapytaniem”, rekurencyjne CTE kończy się, gdy random() nie dodaje nowego wiersza. To znaczy, gdy losowo obliczona wartość została już obliczona w poprzedniej iteracji; to dlatego, że rekurencyjne CTE używa UNION zamiast UNION ALL .
To rzeczywiście paradoks urodzinowy, w którym 366 zastąpiono maksymalną możliwą liczbą odrębnych wartości, które random() Może produkować. Jaka dokładnie jest ta liczba?
random() funkcja zwraca wartość podwójnej precyzji, której dokładna definicja zależy od systemu. Jednak nie wszystkie wartości podwójnej precyzji mogą zostać wytworzone; podstawowa funkcja C może dawać 2^31 różnych wyników, niezależnie od wielkości bitowej wartości podwójnej precyzji. W praktyce jest to wystarczająco dobre, a jednocześnie zapewniona jest kompatybilność ze wszystkimi różnymi architekturami i implementacjami bibliotek.
Możemy więc zastąpić 366 przez 2^31 w naszym zapytaniu, a zamiast 23 otrzymamy 54563 jako odpowiedź.
Czy zbliża się do rzeczywistego wyniku losowego zapytania? Uruchommy to kilka razy, zbierzmy wynik i obliczmy średnią:
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)Średnia rzeczywistych wyników jest dość blisko oczekiwanego progu 54563; różnica jest mniejsza niż 0,3%, całkiem ortodoksalnie , możemy powiedzieć!
