CTEと誕生日のパラドックス

興味深いクエリがPostgresOpenのWillLeinweberによってツイッターされました：

-- 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人をランダムに選択した場合、2人が同じ誕生日を共有する確率は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％未満で、かなり正統的に 、私たちは言うかもしれません！