Emulando índices Hash manualmente

From PostgreSQL wiki
Jump to navigationJump to search

By Emanuel Calvo Franco

Introducción y armado del ambiente

Este artículo no plantea un nuevo método sino más bien, un 'know how' de como funcionan los índices de tipo hash y como 'emular' su funcionamiento de manera sencilla.

Por lo tanto nos valdremos de una lista de nombres en un archivo de texto que luego importaremos a través de la herramienta 'copy'.

Las siguientes pruebas se realizaron sobre un Postgres Versión 8.4 Beta 1. 

CREATE TABLE hashy (name text, namehash int);
CREATE RULE hashy_rule AS ON insert TO hashy DO update hashy set namehash = hashbpchar(hashy.name) where namehash is NULL; 
-- o utilizar hashtext...
CREATE OR REPLACE RULE hashy_rule AS ON insert TO hashy DO update hashy set namehash = hashtext(hashy.name) where namehash is NULL; 
COPY hashy(name) from '/usr/local/pgsql84/listado.txt';
insert into hashy(name) (select name || '_1' from hashy);
insert into hashy(name) (select name || '_2' from hashy);
...
insert into hashy(name) (select name || '_5' from hashy);
insert into hashy(name) (select '0' || name from hashy);

La idea principal es generar un campo el cual contenga el hash del nombre. Debido a que es más rápida la búsqueda sobre campos enteros que en los de tipo texto, en teoría la busqueda sería más rápida utilizando este campo 'hasheado'.

Ejemplo: 

postgres=# explain analyze verbose select * from hashy where namehash = hashbpchar('picolo');
                                            QUERY PLAN                                             
---------------------------------------------------------------------------------------------------
 Seq Scan on hashy  (cost=0.00..123.78 rows=27 width=36) (actual time=1.522..1.523 rows=1 loops=1)
   Output: name, namehash
   Filter: (namehash = 564982275)
 Total runtime: 1.554 ms
(4 rows)

postgres=# explain analyze verbose select * from hashy where namehash = hashtext('picolo');
                                            QUERY PLAN                                             
---------------------------------------------------------------------------------------------------
 Seq Scan on hashy  (cost=0.00..123.78 rows=27 width=36) (actual time=1.549..1.551 rows=1 loops=1)
   Output: name, namehash
   Filter: (namehash = 564982275)
 Total runtime: 1.578 ms
(4 rows)

postgres=# explain analyze verbose select * from hashy where name = 'picolo';
                                            QUERY PLAN                                             
---------------------------------------------------------------------------------------------------
 Seq Scan on hashy  (cost=0.00..123.78 rows=27 width=36) (actual time=1.571..1.573 rows=1 loops=1)
   Output: name, namehash
   Filter: (name = 'picolo'::text)
 Total runtime: 1.605 ms
(4 rows)

Podemos observar que existe una pequeña diferencia entre hashtext y hashbpchar en cuanto a rendimiento. En cuanto a la busqueda secuencial sobre el campo 'name' arrojó resultados muy similares a los del campo hash. En teoría, en grandes cantidades de datos esto puede variar aún más.

Más allá de la simple emulación

Ahora jugaremos con índices reales para probar su funcionamiento. Primero creamos un índice sobre la columna namehash: 

postgres=# create index hashy_namehash on hashy USING hash (namehash);
CREATE INDEX
postgres=# explain analyze verbose select * from hashy where namehash = hashtext('picolo');
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..51.77 rows=26 width=36) (actual time=0.024..0.025 rows=1 loops=1)
   Output: name, namehash
   Recheck Cond: (namehash = 564982275)
   ->  Bitmap Index Scan on hashy_namehash  (cost=0.00..4.45 rows=26 width=0) (actual time=0.013..0.013 rows=1 loops=1)
         Index Cond: (namehash = 564982275)
 Total runtime: 0.062 ms
(6 rows)

A mejorado enormemente, es lógico. Sin embargo, en teoría un indice sobre el campo de 'name' debería ser más lento. 


postgres=# create index hashy_ix on hashy using btree (name);
CREATE INDEX
postgres=# explain analyze verbose select * from hashy where name = 'picolo';
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..51.77 rows=26 width=36) (actual time=0.101..0.102 rows=1 loops=1)
   Output: name, namehash
   Recheck Cond: (name = 'picolo'::text)
   ->  Bitmap Index Scan on hashy_ix  (cost=0.00..4.45 rows=26 width=0) (actual time=0.093..0.093 rows=1 loops=1)
         Index Cond: (name = 'picolo'::text)
 Total runtime: 0.143 ms
(6 rows)

Aqui creamos un índice de tipo btree sobre la columna que contiene el nombre. Seremos justos y crearemos un índice de tipo hash sobre esa columna: 

postgres=# drop index hashy_ix;
DROP INDEX
postgres=# create index hashy_ix on hashy using hash (name);
CREATE INDEX
postgres=# explain analyze verbose select * from hashy where name = 'picolo';
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..51.77 rows=26 width=36) (actual time=0.022..0.023 rows=1 loops=1)
   Output: name, namehash
   Recheck Cond: (name = 'picolo'::text)
   ->  Bitmap Index Scan on hashy_ix  (cost=0.00..4.45 rows=26 width=0) (actual time=0.011..0.011 rows=1 loops=1)
         Index Cond: (name = 'picolo'::text)
 Total runtime: 0.059 ms
(6 rows)

Vemos que en este caso particular, un índice hash es mejor que un btree (que es el tipo de índice por defecto). Esto tiene una explicación aceptable y es que todas las ocurrencias de la columna 'name' no generan colisiones en la columna 'namehash'. Si tuviesemos un algoritmo de tipo CRC de 32 bits, quizás tuviesemos algunas colisiones (o al menos 1, quizás ninguna). En grandes cantidades de datos, las colisiones generan procesamientos adicionales (doble hash). Para entender un poco más del tema de las colisiones vea el apartado de 'Colisiones'. 

postgres=# explain analyze verbose select * from hashy where name = 'emanuel_1_2_3_4';
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..51.77 rows=26 width=36) (actual time=0.027..0.029 rows=1 loops=1)
   Output: name, namehash
   Recheck Cond: (name = 'emanuel_1_2_3_4'::text)
   ->  Bitmap Index Scan on hashy_ix  (cost=0.00..4.45 rows=26 width=0) (actual time=0.013..0.013 rows=1 loops=1)
         Index Cond: (name = 'emanuel_1_2_3_4'::text)
 Total runtime: 0.067 ms
(6 rows)

postgres=# explain analyze verbose select * from hashy where namehash = hashtext('emanuel_1_2_3_4');
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..51.77 rows=26 width=36) (actual time=0.024..0.025 rows=1 loops=1)
   Output: name, namehash
   Recheck Cond: (namehash = (-1849844477))
   ->  Bitmap Index Scan on hashy_namehash  (cost=0.00..4.45 rows=26 width=0) (actual time=0.014..0.014 rows=1 loops=1)
         Index Cond: (namehash = (-1849844477))
 Total runtime: 0.062 ms
(6 rows)

Lógicamente como era de esperar, los resultados varian debido a la 'ubicación' física del registro. En este caso 'picolo' estaba al final de la tabla, en cambio 'emanuel_1_2_3_4' estaba por al mitad.

Colisiones

Una colisión sucede cuando dos o más cadenas son pasadas por un algoritmo de hash y arrojan idéntico resultado. Es como si ambas cadenas tuviesen la 'misma dirección'.

Para hacer explícito el problema de las colisiones expondré una prueba: 

CREATE TABLE i(i text, hash int);
insert into i (select random()::text from generate_series(1,1000000));
update i set hash = hashtext(i);
select * from i a,i b where a.hash = b.hash and a.i <> b.i;

Esa consulta nos arroja varias colisiones... en este caso particular unas 133 (sobre 1000001 representan el 0,01 % ). 1 cada ~ 7518,80. 

postgres=# select * from i a right join i b USING (hash) where a.i <> b.i limit 20;
    hash     |         i         |         i         
-------------+-------------------+-------------------
   688880719 | 0.861061272677034 | 0.776890672277659
  1837677207 | 0.436147989239544 | 0.160792944487184
   688880719 | 0.776890672277659 | 0.861061272677034 <----- Se repite debido a que estamos
  1837677207 | 0.160792944487184 | 0.436147989239544        juntando la misma tabla !! (OJO)
   -98745840 | 0.431216648779809 | 0.905636982992291
(...)

postgres=# select count(*) from (select distinct(hash) from i a left join i b USING (hash) where a.i <> b.i) k;
 count 
-------
   133
(1 row)

postgres=# select count(hash) from i group by hash having count(hash) > 2;
 count 
-------
(0 rows) <----- Esto nos indica que no hay colisiones de a 3 ocurrencias.

En ese caso, tenemos que solventar la colisión debido a que si realizamos la consulta nos traerá dos registros: 

postgres=# select * from i where hash = hashtext('0.545927470549941');
         i         |   hash    
-------------------+-----------
 0.545927470549941 | 994753854
 0.571486297063529 | 994753854
(2 rows)

Para ello tenemos que discriminar cual de los dos utilizaremos. 

postgres=# select * from i where hash = hashtext('0.545927470549941') and i = '0.545927470549941';
         i         |   hash    
-------------------+-----------
 0.545927470549941 | 994753854
(1 row)


Poniendo un poco más a prueba

Hasta ahora solo hicimos esto sobre una tabla de dos columnas, pero lo ideal sería probar esto en una tabla un poco más grande en 'ancho'. 

postgres=# alter table hashy add c3 text;
ALTER TABLE
postgres=# alter table hashy add c4 text;
ALTER TABLE
postgres=# alter table hashy add c5 text;
ALTER TABLE
postgres=# update hashy set c3 = 'columna' || name where namehash > 100000;
UPDATE 2575
postgres=# update hashy set c4 = 'col ' || name where namehash < 100000;
UPDATE 2674

Esto es solo para que por lo menos una de las dos columnas contenga datos.

Inclusive con los indices encontramos diferencias: 

postgres=# explain analyze verbose select * from hashy where namehash = hashtext('emanuel_1_2_3_4');
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..60.45 rows=26 width=132) (actual time=0.021..0.022 rows=1 loops=1)
   Output: name, namehash, c3, c4, c5
   Recheck Cond: (namehash = (-1849844477))
   ->  Bitmap Index Scan on hashy_hashname  (cost=0.00..4.45 rows=26 width=0) (actual time=0.011..0.011 rows=1 loops=1)
         Index Cond: (namehash = (-1849844477))
 Total runtime: 0.061 ms
(6 rows)

postgres=# explain analyze verbose select * from hashy where name = 'emanuel_1_2_3_4';
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on hashy  (cost=4.45..60.46 rows=26 width=132) (actual time=0.027..0.029 rows=1 loops=1)
   Output: name, namehash, c3, c4, c5
   Recheck Cond: (name = 'emanuel_1_2_3_4'::text)
   ->  Bitmap Index Scan on hashy_ix  (cost=0.00..4.45 rows=26 width=0) (actual time=0.013..0.013 rows=1 loops=1)
         Index Cond: (name = 'emanuel_1_2_3_4'::text)
 Total runtime: 0.069 ms
(6 rows)

Sin índices: 

postgres=# explain analyze verbose select * from hashy where name = 'emanuel_1_2_3_4';
                                             QUERY PLAN                                             
----------------------------------------------------------------------------------------------------
 Seq Scan on hashy  (cost=0.00..178.54 rows=38 width=132) (actual time=2.587..2.892 rows=1 loops=1)
   Output: name, namehash, c3, c4, c5
   Filter: (name = 'emanuel_1_2_3_4'::text)
 Total runtime: 2.927 ms
(4 rows)

postgres=# explain analyze verbose select * from hashy where namehash = hashtext('emanuel_1_2_3_4');
                                             QUERY PLAN                                             
----------------------------------------------------------------------------------------------------
 Seq Scan on hashy  (cost=0.00..178.54 rows=38 width=132) (actual time=1.504..1.747 rows=1 loops=1)
   Output: name, namehash, c3, c4, c5
   Filter: (namehash = (-1849844477))
 Total runtime: 1.779 ms
(4 rows)

Y aquí vemos una diferencia un poco más sustancial. Quedan comprobado entonces los beneficios de este algoritmo.

En esta prueba lo que hicimos fue agregar más carga de datos para corroborar el funcionamiento con un poco más de stress (aunque evidentemente Postgres no sufre mucho).

Un poco más sobre los algoritmos de CRC32

Creamos un archivo llamado crc.c y guardamos el siguiente código en el archivo: 

/*
 * CYCLIC REDUNDANCY CHECK
 */

#include "postgres.h"
#include "fmgr.h"

#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

PG_FUNCTION_INFO_V1(pg_crc_simple);


Datum 
pg_crc_simple(PG_FUNCTION_ARGS){

        char *message = PG_GETARG_TEXT_P(0);
        //size_t argumentlen = VARSIZE(message)-VARHDRSZ;

        int i, j;
        unsigned int byte, crc, mask;
        static unsigned int table[256];
        /* Seteamos la tabla de ser necesario. */
        if (table[1] == 0) {
                for (byte = 0; byte <= 255; byte++) {
                        crc = byte;
                        for (j = 7; j >= 0; j--) { // 8veces
                                mask = -(crc & 1);
                                crc = (crc >> 1) ^ (0xEDB88320 & mask);
                        }
                        table[byte] = crc;
                }
        }

        /* tenemos la tabla y calculamos*/
        i = 0;
        crc = 0xFFFFFFFF;
        while (message[i] != 0) {
                byte = message[i]; // Get next byte.
                crc = (crc >> 8) ^ table[(crc ^ byte) & 0xFF];
                i = i + 1;
        }
        
        PG_RETURN_INT32(~crc);
}


Luego lo compilamos como un shared object: 

gcc -I $DIRECTORIO_POSTGRES/include/server/ --shared crc.c

Luego, tenemos que incluir esa función en el motor: 

CREATE OR REPLACE FUNCTION pg_crc_simple(text) RETURNS integer
     AS '/usr/local/pgsql84/a.out', 'pg_crc_simple'
     LANGUAGE C STRICT;

Esto nos permitirá crear nuestro propio algoritmo de hash.

Nótese que compile el código en la carpeta /usr/local/pgsql84 y por defecto el 'gcc' nombra al archivo de salida como a.out.

Probemos como funciona! 

postgres=# select pg_crc_simple(random()::text);
 pg_crc_simple_2 
-----------------
      1107002784
(1 row)
Retrieved from "https://wiki.postgresql.org/index.php?title=Emulando_índices_Hash_manualmente&oldid=17481"