LINQ Joins - Leistung

Question

Ich bin gespannt, wie genau LINQ (nicht LINQ to SQL) führt hinter den Kulissen in Bezug auf wie Sql Server Joins durchführt.

Sql Server generiert vor Ausführung einer Abfrage einen Ausführungsplan. Der Ausführungsplan ist im Grunde ein Ausdrucksbaum, von dem er glaubt, dass er die Abfrage am besten ausführt. Jeder Knoten bietet Informationen darüber, ob eine Sortierung, ein Scan, eine Auswahl, eine Join, ect durchgeführt werden soll.

Auf einem 'Join'-Knoten in unserem Ausführungsplan können wir drei mögliche Algorithmen sehen; Hash Join, Merge Join und Nested Loops Join. Sql Server wird entscheiden, welcher Algorithmus für jede Join-Operation basierend auf der erwarteten Anzahl von Zeilen in inneren und äußeren Tabellen, welche Art von Join wir tun (einige Algorithmen unterstützen nicht alle Arten von Joins), ob wir geordnete Daten benötigen und wahrscheinlich viele andere Faktoren.

Join-Algorithmen:

Nested Loop Join: Am besten für kleine Eingänge, ist mit dem inneren Tisch optimiert werden.

Zusammenführen Beitreten: Am besten für mittlere bis große Eingänge sortierte Eingänge oder einen Ausgang, der bestellt werden muss.

Hash-Verknüpfung: Am besten für mittlere bis große Eingänge, kann linear skaliert werden.

LINQ Abfrage:

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}; 

SQL Query:

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

SQL Server möglicherweise eine verschachtelte Schleife verwenden Sie Mitglied, wenn es weiß, eine kleine Anzahl von Zeilen aus jeder Tabelle gibt es eine Mergeverknüpfung wenn Es weiß, dass eine der Tabellen einen Index hat, und Hash tritt ein, wenn es weiß, dass auf jeder Tabelle viele Zeilen stehen und keiner einen Index hat.

Wählt Linq seinen Algorithmus für Joins? oder benutzt es immer eins?

Answer 1

Linq to SQL sendet keine Verknüpfungshinweise an den Server. Daher ist die Leistung eines Joins, der Linq mit SQL verwendet, identisch mit der Leistung desselben Joins, der "direkt" an den Server gesendet wird (d. H. Reines ADO oder SQL Server Management Studio verwendet), ohne dass irgendwelche Hinweise angegeben wurden.

Linq zu SQL auch nicht erlauben Sie Join Hinweise (soweit ich weiß) zu verwenden. Wenn Sie also einen bestimmten Join-Typ erzwingen wollen, müssen Sie eine gespeicherte Prozedur oder die Methode Execute[Command|Query] verwenden. Wenn Sie jedoch keinen Join-Typ angeben, indem Sie INNER [HASH|LOOP|MERGE] JOIN schreiben, wählt SQL Server immer den Join-Typ aus, von dem er denkt, dass er am effizientesten ist - es spielt keine Rolle, woher die Abfrage stammt.

Andere Linq-Abfrageanbieter - wie Entity Framework und NHibernate Linq - werden genau das Gleiche tun wie Linq to SQL. Keiner von diesen hat direkte Kenntnisse darüber, wie Sie Ihre Datenbank indiziert haben, und daher sendet keiner von ihnen Join-Hinweise.

Linq to Objects ist ein wenig anders - es wird (fast?) Immer einen "Hash-Join" im SQL Server-Sprachgebrauch durchführen. Das liegt daran, dass die für einen Merge-Join erforderlichen Indizes nicht vorhanden sind und Hash-Joins in der Regel effizienter sind als verschachtelte Schleifen, sofern die Anzahl der Elemente nicht sehr klein ist.Aber das Bestimmen der Anzahl der Elemente in einem kann an erster Stelle eine vollständige Iteration erfordern, so dass es in den meisten Fällen schneller ist, einfach das Schlimmste anzunehmen und einen Hash-Algorithmus zu verwenden.

Answer 2

LINQ selbst wählt keine Algorithmen aus, da LINQ streng genommen nur eine Möglichkeit darstellt, eine Abfrage in SQL-artiger Syntax auszudrücken, die Funktionsaufrufen unter IEnumerable<T> oder IQueryable<T> zugeordnet werden kann. LINQ ist vollständig eine Sprachfunktion und bietet keine Funktionalität, nur eine andere Möglichkeit, bestehende Funktionsaufrufe auszudrücken.

Im Fall von IQueryable<T> ist es völlig Sache des Anbieters (wie LINQ to SQL), die beste Methode zur Erstellung der Ergebnisse auszuwählen.

Bei LINQ to Objects (mit IEnumerable<T>) wird in allen Fällen eine einfache Enumeration verwendet (entspricht in etwa den verschachtelten Schleifen). Es gibt keine gründliche Inspektion (oder gar Kenntnis) der zugrunde liegenden Datentypen, um die Abfrage zu optimieren.

Answer 3

Die Methoden auf System.Linq.Enumerable werden in der Reihenfolge ausgeführt, in der sie ausgegeben werden. Es gibt keinen Abfrageoptimierer bei der Wiedergabe.

Viele Methoden sind sehr faul, wodurch Sie die Quelle nicht vollständig aufzählen können, indem Sie .First oder .Any oder .Take am Ende der Abfrage setzen. Das ist die einfachste zu erreichende Optimierung.

Für System.Linq.Enumerable.Join speziell, the docs Zustand, dass dies ein Hash-Join ist.

Der Standardgleichheitsvergleich, Standard, verwenden Schlüssel Hash und zu vergleichen.

So Beispiele:

//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