Warning: Declaration of Suffusion_MM_Walker::start_el(&$output, $item, $depth, $args) should be compatible with Walker_Nav_Menu::start_el(&$output, $item, $depth = 0, $args = Array, $id = 0) in /DISK2/WWW/plsql.cz/www/wp-content/themes/suffusion/library/suffusion-walkers.php on line 0
Sep 082011
 

Při čtení oblíbené stránky asktom.oracle.com jsem narazil na velice zajímavý příspěvek přímo od autora této stránky, který se týkal sql funkce ORA_HASH. Tato funkce, jak napovidá její název, vrací hash z dané hodnoty, což se hodí, pokud je nutné získat unikátní hodnotu (zde číslo) z nějakého textu/výrazu/data atd. Co ale příspěvek naznačoval je možný vznik kolizí.
Obyčejně kolize zanedbáváme, protože hashovací funkce typicky poskytuje dostateční počet hodnot, aby nás ochránila pravděpodobnost, ORA_HASH však poskytuje jako výstup pouze číselnou hodnotu a to od 1 do 4294967295. Číslo vypadá na první pohled vcelku ohromě ale ohromně ale zdání klame.
Ve svém příspěvku se Tom Kyte zmiňuje o klasickém narozeninovém paradoxu (“Kolik lidí musí být ve skupině, aby byla 50% šance, že jsou tam dva lidé se stejným datem narozenin?” – tzn. kolize), který řiká že 50% šance na jednu kolizi bude v množině která má počet prvků odmocina(počet všech hodnot), zde je to konkrétně:

select sqrt(4294967295) from dual;
65536

Což je pekelně málo, aby ORA_HASH dal použít například jako primární klíč i pro malé tabulky, takže jsem se jeho krátkou poznámku o kolizích funkce ORA_HASH rozhodl rozvinout v podobě následujicího testu:

1) Vytvořím si sekvenci

CREATE SEQUENCE SEQ_ORA_HASH MINVALUE 1 MAXVALUE 999999999999999 INCREMENT BY 1 START WITH 1;

2) Vytvořím si tabulku pro data
(pro tento účel bez indexu i primárního klíče)

CREATE TABLE T_ORA_HASH_TEST (
ID NUMBER,
ORA NUMBER
);

3) Tabulku naplním PL/SQL anonymním blokem
(alternativně stačí pouze insert, pokud si člověk nepřipravuje půdu na nějaké další výpisy)

BEGIN
FOR I IN 1..65536 LOOP
INSERT INTO T_ORA_HASH_TAST VALUES(SEQ_ORA_HASH.NEXTVAL,ORA_HASH(SEQ_ORA_HASH.CURRVAL));
END LOOP;
COMMIT;
END;

4) A pokusím se najít kolizi:

select count(*),ora from T_ORA_HASH_TAST group by ora having count(*)>1

A BINGO, jsou tam hned 3 kolize:

NUMBER ORA_HASH(NUMBER)
19521 2531233754
24089 3650971228
35139 3650971228
40669 2531233754
44236 3042541444
43025 3042541444

 

A tedy ORA_HASH mi například pro čísla 44236 a 43025 vrátí stejný hash:

select ora_hash(44236),ora_hash(43025) from dual;

Nepatřím k lidem, kteří by v životě měli štěstí, takže jsem se automaticky začal připravovat, že budu loopovat dlouho přes několik mil. záznamů, než se mi podaří něco najít, nicméně statistika je statistika a kolize tu jsou a je jich hodně, takže si nakonec lze předchozí můj pokus odpustit a klidně si vyselektovat nějakou kolizi přímo z dualu:

select r,count(*) from (
select rownum rt,ora_hash(rownum) r from dual connect by level<=65536) group by r having count(*)>1;

Suma sumárum na ORA_HASH bacha, na kolize narazíte scela určitě a generovat podle toho primární klíč lze jen pokud jste schopni akceptovat, že se se vám například při MERGE zmergují úplně jiné řádky ;)

 Posted by at 19:17

 Leave a Reply

(required)

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>