CTE dan Paradoks Ulang Tahun

Sebuah kueri menarik telah di-twit oleh Will Leinweber dari 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;

Saya menyukai contoh ini:hasil yang mengejutkan, yang dapat dijelaskan dengan (dan memang membantu menjelaskan) perilaku CTE.

Kebenaran tak terduga dilambangkan dengan kata "paradoks", dan sebenarnya ini adalah manifestasi ("contoh", dalam jargon programmer) dari apa yang dikenal sebagai Paradoks Ulang Tahun .

Rumusannya yang paling sederhana mungkin begini:jika Anda memilih 23 orang secara acak, kemungkinan dua dari mereka memiliki tanggal lahir yang sama lebih besar dari 50%.

Hasilnya tidak terduga, karena ada 366 hari lahir yang berbeda, dan angka 23 sepertinya sangat kecil dibandingkan dengan 366.

Namun itu benar, karena dapat ditunjukkan dengan perhitungan langsung. Di PostgreSQL kita dapat menjalankan CTE rekursif lainnya:

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;

menghasilkan 23 sebagai hasilnya.

CTE rekursif berhenti ketika langkah rekursif tidak menambahkan baris baru. Dalam kueri terakhir, acc mewakili probabilitas bahwa i . pertama ulang tahun berbeda, jadi rekursi berhenti ketika angka itu tidak di atas 50%.

Dalam kueri yang disebutkan di awal, yang akan kita sebut sebagai "kueri acak", CTE rekursif berakhir ketika random() tidak menambahkan baris baru. Yaitu, ketika nilai yang dihitung secara acak telah dihitung dalam iterasi sebelumnya; itu karena CTE rekursif menggunakan UNION bukannya UNION ALL .

Ini memang paradoks Ulang Tahun, dengan 366 diganti dengan jumlah maksimum nilai yang berbeda yang random() dapat menghasilkan. Apa sebenarnya nomor itu?

random() fungsi mengembalikan nilai presisi ganda, yang definisi pastinya bergantung pada sistem. Namun, tidak semua nilai presisi ganda dapat dihasilkan; fungsi C yang mendasarinya dapat menghasilkan 2^31 hasil yang berbeda, terlepas dari ukuran bit dari nilai presisi ganda. Ini cukup baik dalam praktiknya, dan pada saat yang sama kompatibilitas dengan semua berbagai arsitektur dan implementasi perpustakaan dipastikan.

Jadi kita bisa mengganti 366 dengan 2^31 dalam kueri kita, dan bukannya 23 kita mendapatkan 54563 sebagai jawabannya.

Apakah itu mendekati keluaran aktual dari kueri acak? Mari kita jalankan beberapa kali, kumpulkan hasilnya, dan hitung rata-ratanya:

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)

Rata-rata hasil aktual cukup mendekati ambang batas yang diharapkan yaitu 54.563; perbedaannya kurang dari 0,3%, cukup secara ortodoks , kita mungkin mengatakan!