Выбирая несколько строк по идентификатору, существует более быстрый способ, чем WHERE IN

Ответ 1

ОК, поэтому я быстро это сделал, указав тип таблицы, а затем передав этот тип непосредственно в запрос и присоединившись к нему.

в SQL

CREATE TYPE [dbo].[IntTable] AS TABLE(
    [value] [int] NULL
)

в коде

DataTable dataTable = new DataTable("mythang");
dataTable.Columns.Add("value", typeof(Int32));

toSelect.ToList().ForEach(selectItem => dataTable.Rows.Add(selectItem));

using (SqlCommand command = new SqlCommand(
    @"SELECT * 
    FROM [dbo].[Entities] e 
    INNER JOIN @ids on e.id = value", con))
{
    var parameter = command.Parameters.AddWithValue("@ids", dataTable);
    parameter.SqlDbType = System.Data.SqlDbType.Structured;
    parameter.TypeName = "IntTable";

    using (SqlDataReader reader = command.ExecuteReader())
    {
        while (reader.Read())
        {
            results.Add(reader.GetInt32(0));
        }
    }
}

это дает следующие результаты:

Querying for 1 random keys (passed in table value) took 2ms
Querying for 1000 random keys (passed in table value) took 3ms
Querying for 2000 random keys (passed in table value) took 4ms
Querying for 3000 random keys (passed in table value) took 6ms
Querying for 4000 random keys (passed in table value) took 8ms
Querying for 5000 random keys (passed in table value) took 9ms
Querying for 6000 random keys (passed in table value) took 11ms
Querying for 7000 random keys (passed in table value) took 13ms
Querying for 8000 random keys (passed in table value) took 17ms
Querying for 9000 random keys (passed in table value) took 16ms
Querying for 10000 random keys (passed in table value) took 18ms

Ответ 2

Я думаю, если бы вы присоединились к своей таблице с таблицей памяти, индексированной с помощью первичного ключа, например:

declare @tbl table (ids int primary key)

вы можете заполнить эту таблицу идентификатором, который вам нужен, и заготовьте оптимизированное внутреннее соединение.

Проблемой может быть время, необходимое для ее заполнения. Я предполагаю, что у вас может быть связанный сервер для этого или, возможно, использовать служебную программу BCP для заполнения временной таблицы, а затем удалить ее.

Ответ 3

Во-первых, я думаю, что довольно сложно утверждать, что ваши данные наводят на размышления о O(n log(n)). (Замечательно, что вы выполнили тест производительности, кстати.) Вот время за значение:

1000    0.046
2000    0.047
3000    0.083
4000    0.079
5000    0.078
6000    0.078
7000    0.079
8000    0.081
9000    0.083
10000   0.085

Несмотря на небольшое увеличение с течением времени, скачок с 2000-3000 годов намного, гораздо более заметен. Если это воспроизводимо, то для меня возникает вопрос, почему такой разрыв.

Для меня это больше предложений O(n) и O(n log(n)). НО, эмпирические оценки теоретических значений трудно аппроксимировать. Таким образом, точное ограничение не так важно.

Я ожидаю, что производительность будет O(n) (где n - это фактическое значение, а не длина бит, как и в некоторых оценках). Я понимаю, что in ведет себя как гигантский набор or s. Большинство записей не проходят тест, поэтому они должны делать все сравнения. Следовательно, O(n).

Следующий вопрос: если у вас есть индекс в поле id. В этом случае вы можете получить набор идентификаторов соответствия в O(n log(n)) time ( log (n) for traversing the index and n` для выполнения этого для каждого значения). Эти швы хуже, но мы не учитываем коэффициент размера оригинальной таблицы. Это должно быть большой победой.

Как говорит Андре, вы можете загрузить таблицу и присоединиться к временной таблице. Я бы отказался от индекса, потому что вам, вероятно, лучше использовать индекс в большой таблице. Это должно сделать вам O(n log(n)) - без (существенной) зависимости от размера исходной таблицы. Или вы можете оставить индекс и иметь O(n * m), где m - размер исходной таблицы. Я думаю, что любой индекс, построенный на временной таблице, вернет вас к производительности O(n log(n)) (если данные не предварительно настроены).

Размещение всего в запросе имеет аналогичную, неустановленную проблему - разбор запроса. Это занимает больше времени, поскольку строка становится длиннее.

Короче говоря, я рекомендую вам выполнить измерения производительности, но не для того, чтобы прийти к выводам об алгоритмической сложности. Я не думаю, что ваши данные подтверждают ваше заключение. Кроме того, обработка запросов немного сложнее, чем вы предлагаете, и вы оставили размер большой таблицы, которая может иметь доминирующий аффект. И мне очень любопытно, что происходит между 2000 и 3000 рядами.