LINQ Joins - Производительность

Question

Мне любопытно, как именно LINQ (не LINQ to SQL) выполняет соединения за кулисами в связи с тем, как Sql Server выполняет соединения.

Sql Server перед выполнением запроса генерирует план выполнения. План выполнения - это, по сути, дерево выражений, которое, по его мнению, является наилучшим способом выполнения запроса. Каждый узел предоставляет информацию о том, нужно ли выполнять сортировку, сканирование, выбор, объединение и т. Д.

На узле 'Join' в нашем плане выполнения мы видим три возможных алгоритма; Hash Join, Merge Join и Nested Loops Join. Sql Server будет выбирать, какой алгоритм использовать для каждой операции объединения, основываясь на ожидаемом количестве строк во внутренних и внешних таблицах, типе объединения, которое мы делаем (некоторые алгоритмы не поддерживают все типы объединений), нужно ли нам упорядочивать данные, и вероятно много других факторов.

Алгоритмы соединения:

Соединение с вложенным циклом: оптимально для небольших входов, может быть оптимизировано с помощью упорядоченной внутренней таблицы

Объединение слиянием: лучше всего подходит для средних и больших входов, отсортированных входов или выходов, которые необходимо упорядочить.

Hash Join: лучше всего подходит для средних и больших входов, может быть распараллелен для линейного масштабирования.

LINQ Query:

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-запрос:

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

Sql Server может использовать Nested Loop Join, если ему известно, что в каждой таблице имеется небольшое количество строк, объединению слиянием, если ему известно, что у одной из таблиц есть индекс, и Hash join, если он знает, что в каждой строке много строк. таблица и ни один не имеет индекса.

Linq выбирает алгоритм объединения? или он всегда использует один?

Answer 1

Linq to SQL не отправляет подсказки о присоединении на сервер. Таким образом, производительность объединения с использованием Linq to SQL будет идентичной производительности того же объединения, отправленного "напрямую" на сервер (т. Е. С использованием чистого ADO или SQL Server Management Studio) без каких-либо указаний.

Linq to SQL также не позволяет использовать подсказки о соединении (насколько я знаю). Поэтому, если вы хотите принудительно установить определенный тип соединения, вам придется сделать это с помощью хранимой процедуры или Execute[Command|Query] метод. Но если вы не укажете тип соединения, написав INNER [HASH|LOOP|MERGE] JOINзатем SQL Server всегда выбирает тип объединения, который он считает наиболее эффективным - не имеет значения, откуда поступил запрос.

Другие поставщики запросов Linq, такие как Entity Framework и NHibernate Linq, будут делать то же самое, что и Linq to SQL. Ни один из них не имеет прямого знания о том, как вы проиндексировали свою базу данных, и поэтому ни один из них не посылает подсказки о присоединении.

Linq to Objects немного отличается - он будет (почти?) Всегда выполнять "хэш-соединение" на языке SQL Server. Это связано с тем, что в нем отсутствуют индексы, необходимые для объединения слиянием, а хеш-соединения обычно более эффективны, чем вложенные циклы, если только количество элементов не очень мало. Но определение количества элементов в IEnumerable<T> во-первых, может потребоваться полная итерация, поэтому в большинстве случаев быстрее просто предположить худшее и использовать алгоритм хеширования.

Answer 2

Методы на System.Linq.Enumerable выполняются в порядке их выдачи. В игре нет оптимизатора запросов.

Многие методы очень ленивы, что позволяет не полностью перечислять источник, помещая .First или же .Any или же .Take в конце запроса. Это самая простая оптимизация.

В частности, для System.Linq.Enumerable.Join документы указывают, что это хеш-соединение.

Сравнитель равенства по умолчанию, Default, используется для хеширования и сравнения ключей.

Итак примеры:

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

Answer 3

Сама LINQ не выбирает какие-либо алгоритмы, поскольку, строго говоря, LINQ - это просто способ выражения запроса в SQL-подобном синтаксисе, который может отображаться на вызовы функций любого из них. IEnumerable<T> или же IQueryable<T>, LINQ - это полностью языковая функция, которая не обеспечивает функциональность, а является еще одним способом выражения существующих вызовов функций.

В случае IQueryable<T>от поставщика (такого как LINQ to SQL) зависит выбор наилучшего метода получения результатов.

В случае LINQ to Objects (используя IEnumerable<T>), во всех случаях используется простое перечисление (примерно эквивалентное вложенным циклам). Нет глубокой проверки (или даже знания) базовых типов данных для оптимизации запроса.