Eine interessante Abfrage wurde von Will Leinweber von Postgres Open getwittert:
-- 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;Ich mag dieses Beispiel:ein überraschendes Ergebnis, das durch CTE-Verhalten erklärt werden kann (und tatsächlich hilft, es zu erklären).
Unerwartete Wahrheiten werden mit dem Wort „Paradoxon“ bezeichnet, und tatsächlich ist dies eine Manifestation (eine „Instanz“, im Programmiererjargon) dessen, was als Geburtstagsparadoxon bekannt ist .
Die einfachste Formulierung lautet wahrscheinlich so:Wenn Sie zufällig 23 Personen auswählen, ist die Wahrscheinlichkeit, dass zwei von ihnen denselben Geburtstag haben, größer als 50 %.
Das Ergebnis ist unerwartet, da es 366 verschiedene Geburtstage gibt und die Zahl 23 im Vergleich zu 366 sehr klein erscheint.
Es ist jedoch richtig, wie man mit einer direkten Rechnung zeigen kann. In PostgreSQL können wir einen weiteren rekursiven CTE ausführen:
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;23 als Ergebnis erzeugen.
Ein rekursiver CTE stoppt, wenn der rekursive Schritt keine neuen Zeilen hinzufügt. In der letzten Abfrage acc stellt die Wahrscheinlichkeit dar, dass das erste i Geburtstage sind unterschiedlich, daher stoppt die Rekursion, wenn diese Zahl nicht über 50 % liegt.
Bei der eingangs erwähnten Abfrage, die wir kurz „Random Query“ nennen, terminiert der rekursive CTE bei random() fügt keine neue Zeile hinzu. Das heißt, wenn der zufällig berechnete Wert bereits in einer vorherigen Iteration berechnet wurde; das liegt daran, dass der rekursive CTE UNION verwendet statt UNION ALL .
Dies ist in der Tat das Geburtstagsparadoxon, bei dem 366 durch die maximal mögliche Anzahl unterschiedlicher Werte ersetzt wird, die random() produzieren kann. Was genau ist diese Nummer?
Der random() Die Funktion gibt einen Wert mit doppelter Genauigkeit zurück, dessen genaue Definition vom System abhängt. Es können jedoch nicht alle Werte mit doppelter Genauigkeit erzeugt werden; Die zugrunde liegende C-Funktion kann unabhängig von der Bitgröße eines Werts mit doppelter Genauigkeit 2^31 unterschiedliche Ergebnisse liefern. Dies reicht in der Praxis aus, und gleichzeitig ist die Kompatibilität mit allen verschiedenen Architekturen und Bibliotheksimplementierungen gewährleistet.
So können wir in unserer Abfrage 366 durch 2^31 ersetzen und erhalten statt 23 54563 als Antwort.
Kommt es der tatsächlichen Ausgabe der Zufallsabfrage nahe? Lass es uns ein paar Mal laufen lassen, das Ergebnis sammeln und den Durchschnitt berechnen:
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)Der Durchschnitt der tatsächlichen Ergebnisse liegt ziemlich nahe am erwarteten Schwellenwert von 54563; der Unterschied beträgt orthodox weniger als 0,3 % , könnten wir sagen!
