de Martin LE TARNEC.

Hash join


El algoritmo de la unión “hash join” intenta solucionar el punto débil de la unión “nested loops”: muchos recorridos del B-tree a través de la sentencia interna. En su lugar, se cargan los registros candidatos desde un lado de la unión hacia una tabla hash, que puede ser comparada rápidamente por cada registro contra el otro lado de la unión. Optimizar una unión “hash join” requiere un enfoque de la indexación completamente diferente que la unión “nested loops”. Más allá de eso, es posible mejorar el rendimiento de las uniones “hash join” seleccionando pocas columnas, un reto para la mayoría de las herramientas ORM.

La estrategia de indexación para una unión “hash join” es muy diferente porque no se necesitan indexar las columnas de la unión. Solamente los índices sobre los predicados where independientes mejoran el rendimiento de la unión “hash join”.

Sugerencia

Indexar los predicados where independientes para mejorar el ren­dimiento de la unión “hash join”.

Considera el siguiente ejemplo. Selecciona todas las ventas de los últimos seis meses con los detalles correspondientes de los empleados:

SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

El filtro SALE_DATE es un filtro where independiente. Eso significa que se refiere solamente a una tabla y no pertenece a los predicados de la unión.

DB2
Explain Plan
------------------------------------------------------------
ID | Operation          |                       Rows |  Cost
 1 | RETURN             |                            | 60750
 2 |  HSJOIN            |             50795 of 10000 | 60750
 3 |   TBSCAN SALES     | 50795 of 1011118 (  5.02%) | 60053
 4 |   TBSCAN EMPLOYEES |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

El filtro where se ha cambiado para obtener el resultado deseado: WHERE s.sale_date > current_date - 6 MONTH.

Oracle
--------------------------------------------------------------
| Id | Operation          | Name      | Rows  | Bytes | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT   |           | 49244 |    59M| 12049|
|* 1 |  HASH JOIN         |           | 49244 |    59M| 12049|
|  2 |   TABLE ACCESS FULL| EMPLOYEES | 10000 |     9M|   478|
|* 3 |   TABLE ACCESS FULL| SALES     | 49244 |    10M| 10521|
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID")
   3 - filter("S"."SALE_DATE">TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

La primera etapa de la ejecución es el escaneo de la tabla entera para cargar todos los empleados dentro de la tabla hash (plan id 2). La tabla hash usa los predicados de la unión como llave. En la siguiente etapa, la base de datos hace otro escaneo completo de la tabla SALES y descarta todas las ventas que no cumplen con la condición sobre SALE_DATE (plan id 3). Para los registros restantes de SALES, la base de datos tiene acceso a la tabla “hash” para cargar los detalles correspondientes a los empleados.

El único propósito de la tabla hash es actuar como una estructura temporal en memoria con el fin de evitar tener acceso muchas veces a la tabla EMPLOYEE. La tabla hash se carga inicialmente en una sola iteración así que no existe la necesidad de un índice para traer eficientemente los registros individuales. La información de los predicados confirma que ni un solo filtro es aplicado sobre la tabla EMPLOYEES (plan id 2). La sentencia no tiene ningún predicado independiente sobre esta tabla.

Importante

Indexar los predicados no mejora el rendimiento de la unión “hash join”.

Eso no significa que sea imposible indexar una unión “hash join”. Los predicados independientes pueden ser indexados. Existen condiciones que se aplican durante una de los dos operaciones de accesos. En el ejemplo anterior, corresponde al filtro sobre SALE_DATE.

CREATE INDEX sales_date ON sales (sale_date)

El siguiente plan de ejecución usa ese índice. Sin embargo, utiliza un escaneo de la tabla entera para la tabla EMPLOYEES porque la sentencia no tiene predicados where independientes sobre EMPLOYEES.

DB2
Explain Plan
----------------------------------------------------------------
ID | Operation              |                       Rows |  Cost
 1 | RETURN                 |                            | 16655
 2 |  HSJOIN                |             50795 of 10000 | 16655
 3 |   FETCH SALES          |   50795 of 50795 (100.00%) | 15958
 4 |    RIDSCN              |   50795 of 50795 (100.00%) |  1655
 5 |     SORT (UNQIUE)      |   50795 of 50795 (100.00%) |  1655
 6 |      IXSCAN SALES_DATE | 50795 of 1011118 (  5.02%) |  1631
 7 |   TBSCAN EMPLOYEES     |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)
 6 - START ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

El filtro where se ha cambiado para obtener el resultado deseado WHERE s.sale_date > current_date - 6 MONTH.

Oracle
--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |   59M| 3252|
|* 1 |  HASH JOIN                   |           |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID"  )
   4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

Indexar una unión “hash join” es, al contrario de la unión “Nested Loops”, un proceso simétrico. Eso significa que el orden de la unión no afecta a la indexación. El índice SALES_DATE también se puede utilizar para cargar la tabla “hash” si el orden de la unión está invertido.

Nota

Indexar una unión “hash join” es independiente del orden de la unión.

Un enfoque bastante diferente para optimizar el rendimiento de una unión “hash join” es minimizar el tamaño de la tabla hash. Este método funciona porque una unión “hash join” óptima es posible solamente si la tabla hash entera cabe en memoria. El optimizador utilizará automáticamente el lado más pequeño de la unión para la tabla hash. El plan de ejecución de Oracle muestra los requisitos de memoria estimados en la columna “Bytes”. En el plan de ejecución anterior, la tabla EMPLOYEES necesita nueve megabytes y es el más pequeño de los dos.

También es posible reducir el tamaño de la tabla hash cambiando la sentencia SQL, por ejemplo, agregando unas condiciones adicionales donde la base de datos carga pocos registros candidatos dentro de la tabla hash. Continuando con el ejemplo anterior, podría significar agregar un filtro sobre el atributo DEPARTMENT para que solamente fueran considerados los equipos de ventas. Eso mejora el rendimiento de la unión “hash join” aun si no existe un índice sobre el atributo DEPARTMENT porque la base de datos no necesita almacenar en la tabla “hash” a aquellos empleados que no pueden tener ventas. Al hacer eso, hay que asegurarse de que no existan registros SALES para los empleados que no trabajan en los servicios (DEPARTMENT) respectivos. Usa las restricciones para proteger frente a errores en estas suposiciones.

Cuando se minimiza el tamaño de la tabla hash, el factor relevante no es el número de registros, sino la memoria usada. En realidad, también es posible reducir el tamaño de la tabla hash seleccionando pocas columnas; de hecho, se puede hacer seleccionando solamente los atributos que realmente se necesitan:

SELECT s.sale_date, s.eur_value
     , e.last_name, e.first_name
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

Este método introduce pocas veces errores porque borrar la columna incorrecta producirá rápidamente un mensaje de error. Sin embargo, es posible reducir considerablemente el tamaño de la tabla hash; en este caso particular bajar, de 9 megabytes a 234 kilobytes; una reducción del 97%.

--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           | 2067K| 2202|
|* 1 |  HASH JOIN                   |           | 2067K| 2202|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |  234K|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |  913K| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |  133|
--------------------------------------------------------------

Sugerencia

Seleccionar pocas columnas mejora el rendimiento de la unión “hash join”.

Aunque a primera vista, parece sencillo quitar unas columnas desde una sentencia SQL, es realmente un desafío cuando se usa una herramienta ORM. El soporte de los llamados objetos parciales es muy escaso. Los siguientes ejemplos muestran algunas posibilidades.

Java

JPA define el FetchType.LAZY dentro de las anotaciones @Basic. Puede aplicarse a nivel de propiedad:

@Column(name="junk")
@Basic(fetch=FetchType.LAZY)
private String junk;

Los proveedores JPA son libres de ignorarlos:

La estrategia LAZY es un “hint” para los proveedores de persistencia donde el dato debería ser traído cuando tenga el primer acceso. Se permite usar una implementación “eagerly fetch” para los registros donde la estrategia LAZY fue especificada.

EJB 3.0 JPA, párrafo 9.1.18

Hibernate 3.6 implementa la propiedad “lazy” devolviendo los datos a través de una instrumentación compilada de “time bytecode”. . La instrumentación agrega código extra para las clases compiladas que no devuelven las propiedades LAZY hasta que haya un acceso. El enfoque es completamente transparente para la aplicación pero abre una puerta hacia una nueva dimensión de problemas N+1: un select por cada registro y cada propiedad. Es particularmente peligroso porque JPA no ofrece un control de ejecución para recuperar los datos “eagerly” si se necesitan.

El lenguaje nativo de Hibernate HQL resuelve el problema con la cláusula FETCH ALL PROPERTIES (ver FewerColumnsInstrumentedHibernate.java):

select s from Sales s FETCH ALL PROPERTIES
 inner join fetch s.employee e FETCH ALL PROPERTIES
 where s.saleDate >:dt

La cláusula FETCH ALL PROPERTIES obliga Hibernate a devolver rápidamente los datos aun cuando se utiliza el código de la herramienta y la propiedad LAZY.

Otra manera de cargar solamente las columnas seleccionadas es usar los objetos de transporte de datos (en inglés, data transport objects) (DTO) al lugar de las entidades. Este método trabaja de la misma manera que HQL y JPQL, que inicializan un objeto dentro de la sentencia ( Ejemplo FewerColumnsJPA.java:

select new SalesHeadDTO(s.saleDate , s.eurValue
                       ,e.firstName, e.lastName)
  from Sales s
  join s.employee e
 where s.saleDate > :dt

La sentencia selecciona solamente los datos solicitados y devuelve un objeto SalesHeadDTO, un simple objeto Java(POJO), no una entidad.

Resolver problemas de rendimiento en el mundo real implica generalmente intervenir en mucho código existente. Migrar ese código hacia unas clases nuevas es seguramente imposible. Pero la instrumentación “byte-code” causa problemas N+1 que son probablemente peores que los problemas originales de rendimiento. El ejemplo FewerColumnsJPA.java usa una interfaz común para su entidad y el DTO para resolver este problema. La interfaz define solamente los métodos obtenidos así que el cliente en sólo-lectura puede fácilmente cambiarse para aceptar el DTO como una entrada. En general es suficiente porque normalmente las grandes uniones “hash join” se activan mostrando procedimientos que no actualizan cualquier cosa.

Si se construye un nuevo reporte, se debe considerar devolver los datos a través de DTO o un Map sencillo, como se ha explicado en el ejemplo FewerColumnsHibernate.java .

Perl

El framework DBIx::Class no actúa como un administrador de entidades así que la herencia no causa problemas de alias. El cookbook soporta esta estrategia. La definición del siguiente esquema define la clase Sales en dos niveles:

package UseTheIndexLuke::Schema::Result::SalesHead;
use base qw/DBIx::Class::Core/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/sale_id employee_id subsidiary_id
                            sale_date eur_value/);
__PACKAGE__->set_primary_key(qw/sale_id/);
__PACKAGE__->belongs_to('employee', 'Employees', 
           {'foreign.employee_id'   => 'self.employee_id'
           ,'foreign.subsidiary_id' => 'self.subsidiary_id'});

package UseTheIndexLuke::Schema::Result::Sales;
use base qw/UseTheIndexLuke::Schema::Result::SalesHead/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/junk/);

La clase Sales proviene de la clase SalesHead y agrega algunos atributos que faltan. Observa que es necesaria la tabla de configuración dentro de la clase derivada.

Se pueden obtener todos los detalles de los empleados a través de una carga previa o seleccionando solamente las columnas del siguiente modo:

my @sales =
   $schema->resultset('SalesHead')
          ->search($cond
                  ,{      join => 'employee'
                   ,'+columns' => ['employee.first_name'
                                  ,'employee.last_name']
                   }
                  );

En este caso, no es posible cargar solamente las columnas seleccionadas desde la tabla raíz SalesHead.

DBIx::Class 0.08192 genera la siguiente sentencia SQL. Devuelve todas las columnas desde la tabla SALES y selecciona los atributos desde EMPLOYEES:

SELECT me.sale_id,
       me.employee_id,
       me.subsidiary_id,
       me.sale_date,
       me.eur_value,
       employee.first_name,
       employee.last_name
  FROM sales me
  JOIN employees employee
        ON( employee.employee_id   = me.employee_id
       AND  employee.subsidiary_id = me.subsidiary_id)
 WHERE(sale_date > ?)
PHP

La versión 2 del framework Doctrine soporta la selección de los atributos en el momento de la ejecución. La documentación explica que la carga parcial de los objetos podría tener un comportamiento extraño y requiere la palabra clave partial para ser consciente del riesgo. Además, se debe seleccionar la columna sobre la llave primaria de manera explícita:

$qb = $em->createQueryBuilder();
$qb->select('partial s.{sale_id, sale_date, eur_value},'
          . 'partial e.{employee_id, subsidiary_id, '
                     . 'first_name , last_name}')
   ->from('Sales', 's')
   ->join('s.employee', 'e')
   ->where("s.sale_date > :dt")
   ->setParameter('dt', $dt, Type::DATETIME);

La sentencia SQL generada contiene las columnas solicitadas y una vez más las columnas SUBSIDIARY_ID y EMPLOYEE_ID desde la tabla SALES.

SELECT s0_.sale_id       AS sale_id0,
       s0_.sale_date     AS sale_date1,
       s0_.eur_value     AS eur_value2,
       e1_.employee_id   AS employee_id3,
       e1_.subsidiary_id AS subsidiary_id4,
       e1_.first_name    AS first_name5,
       e1_.last_name     AS last_name6,
       s0_.subsidiary_id AS subsidiary_id7,
       s0_.employee_id   AS employee_id8
  FROM sales s0_
 INNER JOIN employees e1_
         ON s0_.subsidiary_id = e1_.subsidiary_id
        AND s0_.employee_id   = e1_.employee_id
 WHERE s0_.sale_date > ?

Los objetos devueltos son compatibles con todos los objetos cargados, pero las columnas ausentes permanecen no inicializadas. Tener acceso a ellas no genera ninguna excepción.

Si te gusta mi manera de explicar, te encantará mi libro.

Aviso

MySQL no soporta las uniones “hash joins” al 100% (esta caracterís­tica ya ha sido solicitada)

Hechos

  • Las uniones ”hash joins” no necesitan índices sobre los predicados de la unión. En su lugar, usan una tabla “hash”.

  • Una unión “hash join” usa un índice solamente si el índice soporta los predicados independientes.

  • Reducir el tamaño de la tabla hash mejora el rendimiento; ya sea en horizontal (menos registros) o en vertical (menos columnas).

  • Las uniones “hash joins” no pueden hacer uniones que tengan un rango de condiciones dentro de los predicados de la unión. (theta joins).

Acerca del autor

Foto de Markus Winand

Markus Winand enseña SQL eficiente, en casa y online. Mejora el tiempo de desarrollo utilizando SQL moderno y optimiza el tiempo de ejecución con indexación inteligente. Su libro Rendimiento SQL explicado se ha convertido en lectura obligada sobre el tema.

Adquiere tu libro en Amazon

Portada de “Rendimiento SQL explicado”: Ardilla corriendo en la hierba

La esencia del tuning de SQL en 200 páginas

Compra en Amazon
(solo en papel)

Libro y PDF también disponible en la tienda de Markus.

Contratar a Markus

La manera más rápida y fácil de beneficiarse de su extenso conocimiento y experiencia.
Aprende más »

“Use The Index, Luke” de Markus Winand se halla bajo licencia Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Aspectos legales | Contacto | SIN GARANTÍA | Marcas | Privacy | CC-BY-NC-ND 3.0 licencia