CTE и парадоксът за рождения ден

Уил Лейнвебер от 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;

Харесвам този пример:изненадващ резултат, който може да се обясни с (и наистина помага да се обясни) CTE поведение.

Неочакваните истини се обозначават с думата „парадокс“ и всъщност това е проявление („екземпляр“, на жаргона на програмистите) на това, което е известно като Парадокс на рождения ден .

Най-простата му формулировка вероятно е следната:ако изберете на случаен принцип 23 човека, вероятността двама от тях да споделят една и съща рождена дата е по-голяма от 50%.

Резултатът е неочакван, защото има 366 различни рождени дни, а числото 23 изглежда много малко в сравнение с 366.

Въпреки това е правилно, тъй като може да се покаже с директно изчисление. В PostgreSQL можем да изпълним друг рекурсивен 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;

като резултатът се получава 23.

Рекурсивният CTE спира, когато рекурсивната стъпка не добавя нови редове. В последната заявка acc представлява вероятността първият i рождените дни са различни, така че рекурсията спира, когато това число не е над 50%.

В заявката, спомената в началото, която ще наречем накратко „случайна заявка“, рекурсивният CTE завършва, когато random() не добавя нов ред. Тоест, когато произволно изчислената стойност вече е била изчислена в предишна итерация; това е, защото рекурсивният CTE използва UNION вместо UNION ALL .

Това наистина е парадоксът за рождения ден, като 366 се заменят с максималния възможен брой различни стойности, които random() може да произвежда. Какво точно е това число?

random() функцията връща стойност с двойна точност, чиято точна дефиниция зависи от системата. Не всички стойности с двойна точност обаче могат да бъдат произведени; основната функция C може да даде 2^31 различни резултата, независимо от размера на битовете на стойността с двойна точност. Това е достатъчно добре на практика и в същото време е осигурена съвместимост с всички различни архитектури и библиотечни реализации.

Така че можем да заменим 366 с 2^31 в нашата заявка и вместо 23 получаваме 54563 като отговор.

Доближава ли се до действителния резултат от произволната заявка? Нека го стартираме няколко пъти, да съберем резултата и да изчислим средната стойност:

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)

Средната стойност на действителните резултати е доста близка до очаквания праг от 54563; разликата е под 0,3%, съвсем ортодоксално , можем да кажем!