SQL funkce ORA_HASH a kolize

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:

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