Nested loops

El “nested loops join” es el algoritmo fundamental de unión. Funciona como dos sentencias anidadas: la sentencia exterior o guía para traer el resultado desde una tabla y una segunda sentencia (interna) por cada registro desde la sentencia guía para traer los datos correspondientes a la otra tabla.

Realmente se puede utilizar un “nested selects” para implementar el algoritmo del “nested loop” por ti mismo. Sin embargo, este es un enfoque problemático porque las latencias de red se suman a las de disco, lo que generalmente da lugar a un tiempo de respuesta todavía peor. Los “Nested selects” son aún muy comunes porque es fácil implementarlos sin ser consciente de ello. Las herramientas de mapeo objeto-relacional (en inglés, ORM) son particularmente “útiles” en este aspecto...para ampliar el problema llamado N+1 selects, que se ha ganado la mala reputación en este ámbito.

Los siguientes ejemplos muestran esos “nested select” accidentales producidos por las herramientas ORM. En los ejemplos se buscan todos los empleados cuyo apellido empiece por 'WIN' obteniendo todas las ventas (SALES) de esos empleados.

Java

El ejemplo JPA usa la interfaz CriteriaBuilder.

CriteriaBuilder queryBuilder = em.getCriteriaBuilder();
CriteriaQuery<Employees>
   query = queryBuilder.createQuery(Employees.class);
Root<Employees> r = query.from(Employees.class); 
query.where(
  queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%"
  )
);

List<Employees> emp = em.createQuery(query).getResultList();

for (Employees e: emp) {
  // process Employee
  for (Sales s: e.getSales()) {
    // process sale for Employee
  }
}

Hibernate JPA 3.6.0 genera sentencias select N+1:

select employees0_.subsidiary_id as subsidiary1_0_
       -- MORE COLUMNS
  from employees employees0_ 
 where upper(employees0_.last_name) like ?

  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=? 
     and sales0_.employee_id=?

  select sales0_.subsidiary_id as subsidiary4_0_1_
         -- MORE COLUMNS
    from sales sales0_
   where sales0_.subsidiary_id=? 
     and sales0_.employee_id=?

Perl

El siguiente ejemplo muestra el framework Perl DBIx::Class:

my @employees = 
   $schema->resultset('Employees')
          ->search({'UPPER(last_name)' => {-like=>'WIN%'}});

foreach my $employee (@employees) {
   # process Employee
   foreach my $sale ($employee->sales) {
      # process Sale for Employee
   }
}

DBIx::Class 0.08192 genera sentencias select N+1:

SELECT me.employee_id, me.subsidiary_id
     , me.last_name, me.first_name, me.date_of_birth 
  FROM employees me 
 WHERE ( UPPER(last_name) LIKE ? )

   SELECT me.sale_id, me.employee_id, me.subsidiary_id
        , me.sale_date, me.eur_value
     FROM sales me
    WHERE ( ( me.employee_id = ? 
      AND me.subsidiary_id = ? ) )

   SELECT me.sale_id, me.employee_id, me.subsidiary_id
        , me.sale_date, me.eur_value
     FROM sales me
    WHERE ( ( me.employee_id = ? 
      AND me.subsidiary_id = ? ) )

PHP

El ejemplo de Doctrine usa la interfaz generadora de sentencias:

$qb = $em->createQueryBuilder();
$qb->select('e')
   ->from('Employees', 'e')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();
foreach ($r as $row) {
   // process Employee
   foreach ($row->getSales() as $sale) {
      // process Sale for Employee
   }
}

Doctrine 2.0.5 genera sentencias select N+1:

SELECT e0_.employee_id AS employee_id0 -- MORE COLUMNS
  FROM employees e0_
 WHERE UPPER(e0_.last_name) LIKE ?

   SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS
     FROM sales t0 
    WHERE t0.subsidiary_id = ? 
      AND t0.employee_id = ?

   SELECT t0.sale_id AS SALE_ID1 -- MORE COLUMNS
     FROM sales t0 
    WHERE t0.subsidiary_id = ? 
      AND t0.employee_id = ?

Los ORM no generan uniones de SQL , pero en su lugar, seleccionan la tabla SALES con “select anidados” (o en inglés, “nested selects”). Este efecto es conocido como el problema de “selects N+1” o simplemente el “problema N+1”. porque ejecuta N+1 "selects" en total si la sentencia guía devuelve N registros.

Habilitar el registro SQL

Habilita el registro SQL durante la fase de desarrollo y analiza las sentencias SQL generadas.

DBIx::Class

exportar DBIC_TRACE=1 en tu shell.

Doctrine

Solamente sobre el código fuente; no olvidar deshabilitarlo en producción. Considera construir su propio registro configurable.

$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger;
$config->setSQLLogger($logger);

Hibernate (native)

<property name="show_sql">true</property> en App.config o hibernate.cfg.xml

JPA

En persistence.xml pero depende del proveedor de JPA ” por ejemplo, para eclipselink, Hibernate y OpenJPA:

<property name="eclipselink.logging.level" value="FINE"/>
<property name="hibernate.show_sql" value="TRUE"/>
<property name="openjpa.Log" value="SQL=TRACE"/>

La mayoría de los ORM ofrecen una manera pragmática para habilitar el registro SQL. Eso conlleva el riesgo de implementar este parámetro por error en producción.

Aunque el enfoque de los “selects anidados” es un anti-patrón, explica todavía bien la unión nested loops. La base de datos ejecuta la unión exactamente como las herramientas ORM vistas previamente. Indexar sobre la unión “nested loops” es por lo tanto como indexar para las sentencias select. Eso es un índice sobre expresiones sobre la tabla EMPLOYEES y un índice concatenado para la unión de los predicados sobre la tabla SALES:

CREATE INDEX emp_up_name ON employees (UPPER(last_name))

CREATE INDEX sales_emp ON sales (subsidiary_id, employee_id)

Una unión SQL es aún más eficiente que unos “selects anidados”, aunque realiza las mismas búsquedas “lookups” del índice, porque evita muchas comunicaciones de red. Es todavía más rápido si la cantidad total de datos transferida es muy grande debido a la duplicación de los atributos de los empleados por cada venta. Eso se debe a las dos dimensiones del rendimiento: tiempo de repuesta y capacidad; en redes informáticas, se denomina latencia y ancho de banda. El ancho de banda tiene un impacto menor sobre el tiempo de respuesta pero las latencias tienen un gran impacto. Eso significa que el número de idas y vueltas hacia la base de datos es más importante para el tiempo de respuesta que la cantidad de datos transferidos.

Sugerencia

Ejecutar uniones dentro de la base de datos.

La mayoría de las herramientas ofrecen algunas maneras para crear uniones SQL. El llamado modo eager fetching es probablemente el más importante. Normalmente se configura a nivel de parámetros dentro de la entidad de mapeo; por ejemplo, para el parámetro de los empleados employees dentro de la clase Sales. La herramienta ORM juntará siempre la tabla EMPLOYEES teniendo acceso a la tabla SALES. Configurar “eager fetching” en la entidad de mapeo tiene sentido solamente si siempre se necesita el detalle del empleado junto con el dato de las ventas.

“Eager fetching” tiene un efecto negativo si no se necesitan los registros secundarios cada vez que se tiene acceso al objeto padre. Para una aplicación de guía telefónica, por ejemplo, no tiene sentido cargar los registros de ventas SALES mostrando los detalles de los empleados. Se podrían necesitar los datos relativos a las ventas en otros casos, pero no siempre. Una configuración estática no es la solución.

Para un rendimiento óptimo, se debe conseguir el control total sobre las uniones. Los siguientes ejemplos muestran cómo obtener la mejor flexibilidad controlando el comportamiento de las uniones en el momento de la ejecución.

Java

La interfaz JPA CriteriaBuilder provee el método Root<>.fetch() para controlar las uniones. Permite especificar cuándo y cómo la unión consulta los objetos dentro de la sentencia principal. En este ejemplo, usamos un “left join” para traer todos los empleados aun si algunos de ellos no tienen ventas.

Aviso

JPA y Hibernate devuelven los empleados por cada venta.

Eso significa que un empleado con 30 ventas aparecerá 30 veces. Aunque es muy desconcertante, es el comportamiento especificado de la (persistencia EJB 3.0, párrafo 4.4.5.3 “Fetch Joins”). Se puede de-duplicar manualmente la relación padre, por ejemplo, usando LinkedHashSet o usar la función distinct() como se puede ver en el ejemplo.

CriteriaBuilder qb = em.getCriteriaBuilder();
CriteriaQuery<Employees> q = qb.createQuery(Employees.class);
Root<Employees> r = q.from(Employees.class); 
q.where(queryBuilder.like(
    queryBuilder.upper(r.get(Employees_.lastName)),
    "WIN%")
);

r.fetch("sales", JoinType.LEFT);
// needed to avoid duplication of Employee records
q.distinct(true);

List<Employees> emp = em.createQuery(q).getResultList();

Hibernate 3.6.0 genera la siguiente sentencia SQL:

select distinct 
       employees0_.subsidiary_id as subsidiary1_0_0_
     , employees0_.employee_id as employee2_0_0_
       -- MORE COLUMNS
     , sales1_.sale_id as sale1_0__
  from employees employees0_
  left outer join sales sales1_ 
          on employees0_.subsidiary_id=sales1_.subsidiary_id
         and employees0_.employee_id=sales1_.employee_id 
 where upper(employees0_.last_name) like ?

La sentencia tiene un “left join” esperado pero también una palabra clave innecesaria distinct. Desafortunadamente, JPA no provee una llamada API separada para filtrar las entradas padres duplicadas sin de-duplicar los registros secundarios. La palabra clave distinct dentro de la sentencia SQL es preocupante porque la mayoría de las bases de datos filtran realmente los registros duplicados. Solamente algunas bases de datos reconocen que la llave primaria garantiza la unicidad en este caso.

La API nativa de Hibernate resuelve el problema del lado del cliente usando un transformador de resultado:

Criteria c = session.createCriteria(Employees.class);
c.add(Restrictions.ilike("lastName", 'Win%'));

c.setFetchMode("sales", FetchMode.JOIN);
c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

List<Employees> result = c.list();

Que genera la siguiente sentencia:

select this_.subsidiary_id as subsidiary1_0_1_
     , this_.employee_id as employee2_0_1_
       -- MORE this_ columns on employees
     , sales2_.sale_id as sale1_3_
       -- MORE sales2_ columns on sales
  from employees this_ 
  left outer join sales sales2_ 
          on this_.subsidiary_id=sales2_.subsidiary_id 
         and this_.employee_id=sales2_.employee_id 
 where lower(this_.last_name) like ?

Este método produce un SQL directo sin filtros inesperados.Observa que Hibernate usalower() para las sentencias que diferencian minúsculas y mayúsculas, un detalle importante para los índices sobre expresiones.

Perl

El siguiente ejemplo usa el framework Perl DBIx::Class:

my @employees = 
   $schema->resultset('Employees')
          ->search({ 'UPPER(last_name)' => {-like => 'WIN%'}
                   , {prefetch => ['sales']}
                   });

DBIx::Class 0.08192 genera la siguiente sentencia SQL:

SELECT me.employee_id, me.subsidiary_id, me.last_name
       -- MORE COLUMNS
  FROM employees me 
  LEFT JOIN sales sales 
         ON (sales.employee_id   = me.employee_id 
        AND  sales.subsidiary_id = me.subsidiary_id) 
 WHERE ( UPPER(last_name) LIKE ? )
 ORDER BY sales.employee_id, sales.subsidiary_id

Observa que el comando order by no lo ha solicitado la aplicación. La base de datos tiene que ordenar el resultado. Esto podría introducir una penalización adicional de rendimiento.

PHP

El siguiente ejemplo usa el framework PHP Doctrine :

$qb = $em->createQueryBuilder();
$qb->select('e,s')
   ->from('Employees', 'e')
   ->leftJoin('e.sales', 's')
   ->where("upper(e.last_name) like :last_name")
   ->setParameter('last_name', 'WIN%');
$r = $qb->getQuery()->getResult();

Doctrine 2.0.5 genera la siguiente sentencia SQL:

SELECT e0_.employee_id AS employee_id0
       -- MORE COLUMNS
  FROM employees e0_ 
  LEFT JOIN sales s1_ 
         ON e0_.subsidiary_id = s1_.subsidiary_id 
        AND e0_.employee_id = s1_.employee_id 
 WHERE UPPER(e0_.last_name) LIKE ?

El plan de ejecución muestra una operación NESTED LOOPS OUTER:

DB2

Explain Plan
---------------------------------------------------------------
ID | Operation               |                     Rows |  Cost
 1 | RETURN                  |                          | 10501
 2 |  NLJOIN (LEFT)          |               5745 of 57 | 10501
 3 |   FETCH EMPLOYEES       |       57 of 57 (100.00%) |    49
 4 |    RIDSCN               |       57 of 57 (100.00%) |     6
 5 |     SORT (UNIQUE)       |       57 of 57 (100.00%) |     6
 6 |      IXSCAN EMP_NAME    |    57 of 10000 (   .57%) |     6
 7 |   FETCH SALES           |     101 of 101 (100.00%) |   183
 8 |    IXSCAN SALES_SUB_EMP | 101 of 1011118 (   .01%) |    13

Predicate Information
 2 - JOIN (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID)
     JOIN (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID)
 3 - SARG (Q1.LAST_NAME LIKE ?)
 6 - START ($INTERNAL_FUNC$() <= Q1.LAST_NAME)
      STOP (Q1.LAST_NAME <= $INTERNAL_FUNC$())
      SARG (Q1.LAST_NAME LIKE ?)
 8 - START (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID)
     START (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID)
      STOP (Q2.SUBSIDIARY_ID = Q3.SUBSIDIARY_ID)
      STOP (Q2.EMPLOYEE_ID = Q3.EMPLOYEE_ID)

UPPER se ha eliminado desde el filtro where para obtener el resultado deseado.

Oracle

---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  822 |   38 |
| 1 | NESTED LOOPS OUTER          |             |  822 |   38 |
| 2 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*3 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |      |
| 4 |  TABLE ACCESS BY INDEX ROWID| SALES       |  821 |   34 |
|*5 |   INDEX RANGE SCAN          | SALES_EMP   |   31 |      |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  3 - access(UPPER("LAST_NAME") LIKE 'WIN%')
      filter(UPPER("LAST_NAME") LIKE 'WIN%')
  5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+)
        AND  "E0_"."EMPLOYEE_ID"  ="S1_"."EMPLOYEE_ID"(+))

La base de datos devuelve el resultado desde la tabla EMPLOYEES primero a través EMP_UP_NAME y después los registros correspondientes por cada empleado desde la tabla SALES.

Sugerencia

Profundizar en el funcionamiento del ORM en uso, y explicitar la ejecución de las uniones

Entre las diferentes herramientas ORM hay distintas maneras de controlar el comportamiento de las uniones. "Eager fetching" es solamente un ejemplo que no provee el mapeo para cada objeto relacional. Es una buena practica implementar un pequeño conjunto de ejemplos que exploren las capacidades de tu ORM. No es solamente un buen ejercicio; puede también servir como referencia durante la fase de desarrollo, y te mostrará los comportamientos inesperados, como la duplicación de los registros padres como un efecto secundario usando las uniones. Descarga los ejemplos para comenzar.

La unión “nested loops” proporciona un buen rendimiento si la sentencia guía devuelve un resultado pequeño. Por otra parte, el optimizador podría escoger un algoritmo de unión totalmente diferente, como un “hash join” (descrito en la próxima sección), pero eso solo sería posible si la aplicación usara una unión para avisar a la base de datos sobre qué datos se necesitan realmente.

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

Ver también

Ejemplos completos Java, Perl y PHP[ZIP]
Comandos CREATE y INSERT para los ejemplos
Artículo: " Latencia: Seguridad vs Rendimiento " acerca de las latencias de red y de las aplicaciones SQL.

Acerca del autor

Markus Winand es defensor del resurgimiento del SQL. Su misión es la de presentar a los desarrolladores la evolución de SQL en el siglo XXI. Es posible contratar a Markus según disponibilidad o como orador o consultor en winand.at.

Nested loops

Habilitar el registro SQL

Sugerencia

Aviso

Sugerencia

Ver también

Acerca del autor

Tabla de contenido

Latest blog Posts

Entrar en contacto con Markus

Nested loops

Habilitar el registro SQL

Sugerencia

Aviso

Sugerencia

Ver también

Acerca del autor

Adquiere tu libro

Contratar a Markus

Tabla de contenido

Latest blog Posts

Entrar en contacto con Markus