सीटीई और जन्मदिन विरोधाभास

विल लेइनवेबर ने पोस्टग्रेज ओपन से एक दिलचस्प सवाल ट्वीट किया है:

-- 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;

मुझे यह उदाहरण पसंद है:एक आश्चर्यजनक परिणाम, जिसे सीटीई व्यवहार (और वास्तव में समझाने में मदद करता है) द्वारा समझाया जा सकता है।

अप्रत्याशित सत्य को "विरोधाभास" शब्द से दर्शाया जाता है, और वास्तव में यह एक अभिव्यक्ति (एक "उदाहरण", प्रोग्रामर के शब्दजाल में) है जिसे जन्मदिन विरोधाभास के रूप में जाना जाता है। ।

इसका सबसे सरल सूत्र शायद यह है:यदि आप यादृच्छिक रूप से 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() फ़ंक्शन एक दोहरा सटीक मान देता है, जिसकी सटीक परिभाषा सिस्टम पर निर्भर करती है। हालांकि, सभी दोहरे सटीक मूल्यों का उत्पादन नहीं किया जा सकता है; अंतर्निहित सी फ़ंक्शन दोहरे सटीक मान के बिट आकार की परवाह किए बिना, 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% से कम है, काफी रूढ़िवादी रूप से , हम कह सकते हैं!