Comparacion de Métodos y Tipos de joins en Oracle

Para armar el plan de ejecución el optimizador debe realizar las siguientes acciones básicas:

1. Determinar el orden de evaluación de las tablas.
2. Determinar el método de join.
3. Determinar los tipos de accesos (access path, ej: full scan, rowid, index range, etc).
4. Determinar el orden de filtrado.

Los 3 primeros forman la estructura de árbol que da soporte al plan de ejecución. El 4to define el caudal de datos que "fluye" por el árbol. En esta oportunidad solo voy a concentrarme en el punto 2, dejando los otros para futuras notas.

Los joins se realizan siempre entre dos set de datos, si la sentencias tuviera mas de dos tablas se determinan la dos primeras tablas a joinear y el resultado se joinea con la siguiente tabla, ese resultado se joinea con la siguiente tabla y asi siguiendo.

Los métodos de join mas comunes son:

• NESTED LOOP JOIN
• SORT MERGE JOIN
• HASH JOIN
• CARTESIAN JOIN

Descripción de NESTED LOOP JOIN

Los dos set de datos procesados por nested loop (NL) se llaman outer loop e inner loop. El outer loop es ejecutado una sola vez y el inner loop una vez por cada registro retornado por el outer loop. Las principales caracteristicas de NL son:

• Son la mejor opción cuando se requiere obtener la primera fila lo antes posible, de esta forma no es necesario tener que procesar todos los datos para comenzar a retornar resultados. Esto es muy performante, por ejemplo, para aplicaciones front-end que usan paginación.
• Permiten aprovechar los filtros y condiciones de joins usando los indices disponibles.
• Se pueden usar con cualquier tipo de joins.

Descripción de HASH JOIN

Los dos set de datos procesados por hash join (HJ) son build input y probe input. Con el build input se construye en memoria (o en tablespace temporal si no hubiera suficiente memoria fisica disponible) una tabla de hash. Una vez que se construyó la build input se comienza a procesar usando para cada registro de la probe input la tabla de hash de modo de comparar si se satisface o no la condición de join. Las principales caracteristicas de HJ son:

• La tabla de hash usualmente es contruida usando el set de datos mas pequeño.
• No todos los tipos de joins pueden usarse, por ejemplo los theta joins y cross joins no son soportados.
• Para que se comiencen a retornar las filas la tabla de hash debe estar creada y procesada.
• HJ no puede aplicar condiciones de joins usando indices.

Descripción de SORT MERGE JOIN

Los dos set de datos procesado por el merge join (MJ) son leidos y ordenados de acuerdo a las columnas referenciadas en la condición de join. Una vez que los dos set estan ordenados son mezclados (merge). El ordenamiento se realiza en memoria siempre y cuando la memoria fisica sea suficiente, sino alcanza la memoria (pga) se deberá usar espacio temporal como soporte lo cual, como es esperable, ralentizará las operaciones. Las principales caracteristicas de MJ son:

• Ambos data set deben ser ordenados antes del merge
• La primera fila del result set recien es retornada cuando comienza el merge.
• Todos los tipos de joins son soportados.

Tipos de Joins

Existen dos sintaxis posibles para usar con joins:

SQL-ANSI-86
SQL-ANSI-92

La primera es la que uso en general, y es la mas común, la segunda es mas nueva y es standard para otros motores de base de datos, es mas común para la nuevas generaciones de desarrolladores y dbas o para los que vengan de usar sql server . Es, además mas clara porque separa los filtros de los joins, lo cual es mas sencillo para leer e interpretar. Ahora voy a hacer un breve repaso de los tipos de joins con ejemplos en la dos notaciones:


Cross Join

Tambien llamado producto cartesiano. En general se usa cuando no se especifican los joins para algunas tablas. Tambien lo he visto en ciertos planes particulares donde es la mejor opción , aunque es muy raro

select emp.ename,dept.dname
from emp, dept

select emp.ename,dept.dname
from emp CROSS JOIN dept

Theta Join

Tambien llamados inner join, y retorna solo las filas que satisfacen una condición de join

select emp.enam, salgrade.grade
from emp, salgrade
where emp.sal between salgrade.local and salgrade.hisal

select emp.ename, salgrade.grade
from emp INNER JOIN salgrade on emp.sal between salgrade.losal and salgrade.hisal

Equi Join

Tambien llamado natural join, es un caso especial de theta join donde solo se usan operadores
de igualdad para las condiciones de join

select emp.ename, dept.dname
from emp, dept
where emp.deptno = dept.deptno

select emp.ename, dept.dname
from emp NATURAL JOIN dept on emp.deptno = dept.deptno

Self Join

Son un caso especial de theta join donde la tabla joineada es la misma.

select emp.ename,mgr.ename
from emp, emp mgr
where emp.mgr = mgr.empno


select emp.ename, mgr.ename
from emp JOIN emp mgr on emp.mgr = mgr.empno

Outer Join

Los outer join extienden el result set de los theta joins. Con este tipo de join todas las filas de una de la tablas involucradas son retornadas aunque no matcheen con las columnas de join de la otra tabla, retornando NULL en las columnas de los registros de la tabla que no matchea. Oracle usa una sintaxis propia pero lo recomendable es usar la sintaxis ansi-92 ya que es portable a otros motores de base de datos.

Por ejemplo, para ver la cantidad de empleados por departamento, considerando tambien los departamentos que no tienen ningun empleado:

select dept.dname,count(emp.ename)
from  emp,  dept
where dept.deptno = emp.DEPTNO (+)
group by dept.dname

select dept.dname,count(emp.ename)
from dept LEFT OUTER JOIN emp on (dept.deptno = emp.DEPTNO)
group by dept.dname

Con la nueva sintaxis tambien se puede usar RIGHT OUTER JOIN y FULL OUTER JOIN.

A partir de Oracle 10g es posible usar un nuevo tipo de join ( o subtipo) llamado partitioned outer join. Este tipo de join a priori pareceria estar relacionado con tablas particionadas pero no, en este caso, el concepto de particionado es que los datos se dividen en subset durante la ejecución

select dept.dname, count(emp.empno)
from dept LEFT JOIN emp PARTITION BY (emp.job)  ON emp.deptno = dept.deptno
group by dept.dname

Semi Join

Este tipo de join entre dos tablas retorna solo las filas de una de las tablas cuyas columas de join existen en la otra tabla.

Por ejemplo para ver que empleados tienen bonus:

select *
from  scott.emp emp
where exists (select null from scott.bonus bon
            where emp.EMPNO = bon.ename)
         
select *
from  scott.emp emp
where empno in (select empno from scott.bonus bon)

Anti Join

Este tipo de join entre dos tablas retorna solo las filas de una de las tablas cuyas columnas de join NO existen en la otra tabla

Por ejemplo para consultar los empleados que no tienen bonus:

select *
from  scott.emp emp
where not exists (select null from scott.bonus bon
            where emp.EMPNO = bon.ename)
         
select *
from  scott.emp emp
where empno not in (select empno from scott.bonus bon)

Una vez repasados los tipos de joins retomemos los métodos de joins y veamos con algunos ejemplos como se arman los planes según cada método:

Como siempre voy a crear el entorno para poder probar y si alguien quiere testearlo en su propio ambiente puede hacerlo:

-- Creo tabla T1
create table t1
as
select rownum c1,
     trunc(dbms_random.value(1,100)) c2,
     dbms_random.string('a',100) c3
from dual
connect by rownum <= 1000000  -- Creo tabla T2 create table t2 as select rownum c1,        trunc(dbms_random.value(1,100000)) c2,        dbms_random.string('a',100) c3 from dual connect by rownum <= 2000000  -- Creo un indice para la tabla T2 create index t2_idx on t2(c2)  -- Recolecto estadisticas para los segmentos creados: begin     dbms_stats.gather_table_stats(ownname => user,tabname => 'T1',cascade => true);
  dbms_stats.gather_table_stats(ownname => user,tabname => 'T2',cascade => true);
end;

Ahora voy a mostrar cada método de join, obviamente lo voy a forzar con hints para hacerlo mas sencillo:

Forzamos para que se use NESTED LOOP JOIN:

select  /*+ leading(t1) use_nl(t2) index(t2)  */ count(1)
from t1, t2
where t1.c2 = t2.c2
and t1.c3 > 'zzz'

Plan hash value: 3705558160

------------------------------------------------------------------------------
| Id  | Operation           | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |        |     1 |   109 |  3602   (1)| 00:01:19 |
|   1 |  SORT AGGREGATE     |        |     1 |   109 |            |          |
|   2 |   NESTED LOOPS      |        |    21 |  2289 |  3602   (1)| 00:01:19 |
|*  3 |    TABLE ACCESS FULL| T1     |     1 |   104 |  3600   (1)| 00:01:19 |
|*  4 |    INDEX RANGE SCAN | T2_IDX |    21 |   105 |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

 3 - filter("T1"."C3">'zzz')
 4 - access("T1"."C2"="T2"."C2")

Forzamos para que se use MERGE JOIN:

select /*+ ordered use_merge(t2) */ count(1)
from t1, t2
where t1.c2 = t2.c2
and t1.c3 > 'zzz'

Plan hash value: 1164406001

------------------------------------------------------------------------------------------
| Id  | Operation               | Name   | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |        |     1 |   109 |       | 10796   (2)| 00:03:55 |
|   1 |  SORT AGGREGATE         |        |     1 |   109 |       |            |          |
|   2 |   MERGE JOIN            |        |    21 |  2289 |       | 10796   (2)| 00:03:55 |
|   3 |    SORT JOIN            |        |     1 |   104 |       |  3601   (1)| 00:01:19 |
|*  4 |     TABLE ACCESS FULL   | T1     |     1 |   104 |       |  3600   (1)| 00:01:19 |
|*  5 |    SORT JOIN            |        |  1997K|  9754K|    45M|  7195   (2)| 00:02:37 |
|   6 |     INDEX FAST FULL SCAN| T2_IDX |  1997K|  9754K|       |  1007   (2)| 00:00:22 |
------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

 4 - filter("T1"."C3">'zzz')
 5 - access("T1"."C2"="T2"."C2")
     filter("T1"."C2"="T2"."C2")

Forzamos para que se use HASH JOIN:

select /*+ leading(t1) use_hash(t2) */ t1.*
from t1, t2
where t1.c2 = t2.c2
and t1.c3 > 'zzz'


Plan hash value: 442409572

---------------------------------------------------------------------------------
| Id  | Operation              | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |        |     1 |   109 |  4620   (2)| 00:01:41 |
|   1 |  SORT AGGREGATE        |        |     1 |   109 |            |          |
|*  2 |   HASH JOIN            |        |    21 |  2289 |  4620   (2)| 00:01:41 |
|*  3 |    TABLE ACCESS FULL   | T1     |     1 |   104 |  3600   (1)| 00:01:19 |
|   4 |    INDEX FAST FULL SCAN| T2_IDX |  1997K|  9754K|  1007   (2)| 00:00:22 |
---------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

 2 - access("T1"."C2"="T2"."C2")
 3 - filter("T1"."C3">'zzz')

Comparando los 3 planes para cada método se ve que solo con NL usa index range en lugar de usar un full scan por el indice. Los tiempos de NL son los mejores según la estimación del plan. Ejecutando cada uno de los 3 queries se puede ver que dicha estimación coincide con la realidad y que NL es el mas rapido. Esto se da porque tanto con HJ como con MJ no se puede usar el indice para buscar las coincidencias sobre la tabla T2 basado en los valores retornados por la tabla T1. Con NL se aprovecha dicha información para acceder mas puntualmente, via el indice. Cuanto menor sea la selectividad (o mas fuerte) el método NL tendrá mayor ventaja sobre los otros dos.