SQL puzzler : náhody neexistují (Oracle)

Minulý týden jsem sem vložil první SQL puzzler týkající se generování náhodných čísel resp. výběru náhodných řádků v PostgreSQL, s tím že se jedná o první a na nějakou dobu asi poslední puzzler. Co čert nechtěl, dnes jsem na podobnou vychytávku narazil v Oracle - takže s chutí do toho!

Zadání úkolu je velmi podobné jako v PostgreSQL variantě - je dána tabulka o jediném sloupci, obsahující souvislou posloupnost 1 až N (v našem případě 10) celých čísel. Čili vytvoření a naplnění tabulky může vypadat například takto:

-- vytvořím tabulku
CREATE TABLE my_table (id INTEGER);

-- naplním ji 10 řádky
BEGIN
    FOR i IN 1..10 LOOP
        INSERT INTO my_table (id) VALUES (i);
    END LOOP;
END;

Uvažme následující - relativně jednoduchý dotaz:

-- spustím triviální dotaz pro náhodný výběr řádku(ů)
SELECT (CASE WHEN (id = random_value) THEN 'ROVNOST'
             ELSE 'NEROVNOST' END) AS vysledek FROM (

     -- inline pohled
     SELECT id, ROUND(DBMS_RANDOM.value(1,10)) AS random_value
     FROM my_table

) foo WHERE id = random_value;

Otázka: Co je výsledkem tohoto dotazu? (uvažujte Oracle 10g)

Opět vám dám několik možností k výběru:

  1. Náhodný počet řádků, všechny obsahují řetězec "ROVNOST".
  2. Náhodný počet řádků, všechny obsahují řetězec "NEROVNOST".
  3. Náhodný počet řádků, ale co obsahují těžko říct.

I tentokrát je odpověď skryta - zobrazí se až po kliknutí na nadpis "Odpověď".

Odpověď

Jak všichni dobře víme z reklam, možnost (c) je správně. Počet řádků je náhodný (náhodná veličina s binomickým rozdělením), ale problém nastává u vnějšího dotazu - konkrétně při vyhodnocení porovnání "id = random_value" které je prováděno v rámci CASE.

Formulace dotazu je totiž opět trochu zavádějící (jinak by to snad ani nebyl puzzler) protože "selský rozum" říká že když se z inline pohledu vyberou jenom takové řádky kde "id = random_value", potom se tato podmínka nutně v CASE musí vyhodnotit jako pravdivá.

Pravda je taková že Oracle (10g) se takto nechová - náhodnou hodnotu vygenerovanou v inline pohledu při vyhodnocování CASE podmínky nepoužije, ale výraz "ROUND(DBMS_RANDOM.value(1,10))" vyhodnotí znovu, v důsledku čehož dostane novou náhodnou hodnotu která se pravděpodobně nebude rovnat té původní. Čili CASE bude náhodně vypisovat "ROVNOST" a "NEROVNOST".

Zatím jsem neměl možnost to odzkoušet na Oracle 11g, ale dle informací které mám se to puzzler vyhodnotí jinak - totiž dle selského rozumu. Tj. počet řádek sice bude náhodný, nicméně výraz se nebude vyhodnocovat znovu - všechny řádky tedy budou obsahovat hodnotu "ROVNOST".

Jak to "opravit" na 10g? Lze použít "materialize" hint, kterým se inline pohled "zhmotní" a v dalším kroku už se výraz nebude vyhodnocovat - tj. vlastně ekvivalentní řešení jako používá 11g automaticky:

WITH t AS (SELECT /*+ materialize */ my_table.*,
                  ROUND(DBMS_RANDOM.value(1, 10)) as random_value
           FROM my_table)
SELECT (CASE WHEN (id = random_value) THEN 'ROVNOST'
             ELSE 'NEROVNOST' END) AS vysledek FROM t
WHERE id = random_value

A nyní trochu zábavy s pravděpodobnostmi ...

Matematické hrátky

Jak už bylo řečeno v předchozím puzzleru, počet vrácených řádků se řídí binomickým rozdělením, tj. pravděpodobnost že z celkem n řádků (v našem případě 10) bude vráceno právě k řádků je

Pn,k = n! / ((n-k)! * k!) * pk * (1-p)n-k

kde p je pravděpodobnost vrácení jednoho řádku nezávisle na ostatních (v našem případě p = 10-1).

Ale jaké hodnoty budou v těchto řádcích? Jak už bylo řečeno, budou náhodné - Oracle znovu vyhodnotí výraz a vygeneruje tedy nové náhodné hodnoty. Zafixujme nyní počet vrácených řádků k a počet řádků s hodnotou "ROVNOST" označme jako l - logicky platí nerovnost k >= l. Pravděpodobnost že v daném řádku bude "ROVNOST" je opět rovna 1/n = 10-1, ponechme tedy označení p.

Potom počet řádků s hodnotou "ROVNOST" je opět dán binomickým rozdělením - ve výše uvedeném vzorci stačí zaměnit n a k, resp. k a l, tj.

Pk,l = k! / ((k-l)! * l!) * pl * (1-p)k-l

Pravděpodobnost že pro tabulku o n řádcích bude vráceno právě k řádek, a v l z nich bude hodnota "ROVNOST" tedy je rovna součinu

Pn,k,l = Pn,k * Pk,l = n! / ((n-k)! * (k-l)! * l!) * pk+l * (1-p)n-l

Což například pro n = 10 dává následující tabulku (přičemž 0.00% označuje velmi malé byť nenulové pravděpodobnosti):

k / l 0 1 2 3 4 5 6 7 8 9 10
0 34,87%
                   
1 34.87% 3.87%                  
2 15.69% 3.49% 0.19%                
3 4.18% 1.39% 0.15% 0.01%              
4 0.73% 0.33% 0.05% 0.00% 0.00%            
5 0.09% 0.05% 0.01% 0.00% 0.00% 0.00%          
6 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%        
7 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%      
8 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%    
9 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%  
10 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%

 

Komentáře

K tomuto článku zatím žádné komentáře neexistují (nebo čekají na schválení).

Nový komentář

Všechny komentáře podléhají schválení - mezi odesláním komentáře a jeho zobrazením na této stránce tedy může být prodleva. Vyplníte-li e-mailovou adresu, budete o schválení či neschválení komentáře informováni.

V titulku ani v textu nejsou povoleny HTML tagy - budou automaticky odstraněny. Odstavec ukončíte prázdným řádkem.

(nepovinné)