Uniones LINQ - Rendimiento

Question

Tengo curiosidad sobre cómo exactamente LINQ (no LINQ to SQL) se está produciendo se une detrás de las escenas en relación con la forma en que Sql Server realiza combinaciones.

Sql Servidor antes de ejecutar una consulta, genera un plan de ejecución. El plan de ejecución es básicamente un árbol de expresiones en lo que cree que es la mejor manera de ejecutar la consulta. Cada nodo proporciona información sobre si hacer un Ordenar, Escanear, Seleccionar, Unir, etc.

En un nodo 'Unir' en nuestro plan de ejecución, podemos ver tres posibles algoritmos; Hash Join, Merge Join y Nested Loops Join. Sql Server elegirá qué algoritmo para cada operación de unión se basa en el número esperado de filas en tablas internas y externas, qué tipo de unión estamos haciendo (algunos algoritmos no admiten todos los tipos de uniones), si necesitamos datos ordenados, y probablemente muchos otros factores.

Ingreso Algoritmos:

Nested Loop Ingreso: Mejor para entradas pequeñas, se puede optimizar con tabla interna ordenada.

Merge Unir: Ideal para entradas medianas o grandes, entradas clasificadas, o una salida que se debe pedir.

Hash Únase a: Ideal para entradas medianas a grandes, se puede paralelizar para escalar linealmente.

LINQ consulta:

DataTable firstTable, secondTable; 

... 

var rows = from firstRow in firstTable.AsEnumerable() 
       join secondRow in secondTable.AsEnumerable() 
        on firstRow.Field<object> (randomObject.Property) 
        equals secondRow.Field<object> (randomObject.Property) 
      select new {firstRow, secondRow}; 

de consultas SQL:

SELECT * 
FROM firstTable fT 
    INNER JOIN secondTable sT ON fT.Property = sT.Property 

SQL Server podría utilizar un bucle anidado Ingreso si sabe que hay un pequeño número de filas de cada tabla, una combinación de mezcla si sabe que una de las tablas tiene un índice y Hash se une si sabe que hay muchas filas en ninguna de las tablas y ninguno tiene un índice.

¿Linq elige su algoritmo para las uniones? o siempre usa uno?

Answer 1

Linq to SQL no envía sugerencias de unión al servidor. Por lo tanto, el rendimiento de una combinación que utiliza Linq a SQL será idéntico al rendimiento de la misma combinación enviada "directamente" al servidor (es decir, utilizando ADO puro o SQL Server Management Studio) sin ninguna sugerencia especificada.

Linq to SQL también no permite que utilice consejos de unión (hasta donde yo sé). Por lo tanto, si desea forzar un tipo específico de unión, deberá hacerlo utilizando un procedimiento almacenado o el método Execute[Command|Query]. Pero a menos que especifique un tipo de unión escribiendo INNER [HASH|LOOP|MERGE] JOIN, entonces SQL Server siempre elige el tipo de combinación que cree que será más eficiente, no importa de dónde provenga la consulta.

Otros proveedores de consultas de Linq, como Entity Framework y NHibernate Linq, harán exactamente lo mismo que Linq to SQL. Ninguno de estos tiene conocimiento directo de cómo ha indexado su base de datos, por lo que ninguno de ellos envía sugerencias para unirse.

Linq to Objects es un poco diferente: (casi?) Siempre realizará una "combinación de hash" en el lenguaje SQL Server. Esto se debe a que carece de los índices necesarios para realizar una unión combinada, y las uniones hash son generalmente más eficientes que los bucles anidados, a menos que la cantidad de elementos sea muy pequeña.Pero determinar el número de elementos en un IEnumerable<T> puede requerir una iteración completa en primer lugar, por lo que en la mayoría de los casos es más rápido simplemente suponer lo peor y usar un algoritmo hash.

Answer 2

LINQ no elige algoritmos de ningún tipo, ya que LINQ, en sentido estricto, es simplemente una forma de expresar una consulta en sintaxis similar a SQL que se puede asignar a llamadas de función ya sea en IEnumerable<T> o IQueryable<T>. LINQ es completamente una característica de idioma y no proporciona funcionalidad, solo otra forma de expresar llamadas a funciones existentes.

En el caso de IQueryable<T>, depende totalmente del proveedor (como LINQ a SQL) elegir el mejor método para producir los resultados.

En el caso de LINQ to Objects (usando IEnumerable<T>), la enumeración simple es lo que se usa (más o menos equivalente a los bucles anidados) en todos los casos. No hay una inspección profunda (o incluso conocimiento) de los tipos de datos subyacentes para optimizar la consulta.

Answer 3

Los métodos en System.Linq.Enumerable se realizan en el orden en que se emiten. No hay optimizador de consultas en juego.

Muchos métodos son muy vagos, lo que le permite no enumerar por completo la fuente poniendo .First o .Any o .Take al final de la consulta. Esa es la optimización más fácil de obtener.

Para System.Linq.Enumerable.Join específicamente, the docs declara que se trata de una combinación hash.

El comparador de igualdad predeterminado, Predeterminado, se usa para comparar y comparar claves.

Así ejemplos:

//hash join (n+m) Enumerable.Join 
from a in theAs 
join b in theBs on a.prop equals b.prop 

//nestedloop join (n*m) Enumerable.SelectMany 
from a in theAs 
from b in theBs 
where a.prop == b.prop