Wybieranie wielu wierszy według identyfikatora, czy istnieje szybszy sposób niż WHERE IN

Question

Mam tabelę SQL i chciałbym wybrać wiele wierszy według identyfikatora. Na przykład chciałbym uzyskać wiersz z identyfikatorami 1, 5 i 9 z mojej tabeli.

robiłem to z czym w rachunku podobny do poniżej:

SELECT [Id] 
FROM [MyTable] 
WHERE [Id] IN (1,5,9) 

Jednak jest to dość powolne dla dużej liczby elementów w „IN” klauzuli

Poniżej znajdują się dane dotyczące wydajności od wybierania wierszy z użyciem miejsca z tabeli z 1 000 000 wierszy:

Querying for 1 random keys (where in) took 0ms 
Querying for 1000 random keys (where in) took 46ms 
Querying for 2000 random keys (where in) took 94ms 
Querying for 3000 random keys (where in) took 249ms 
Querying for 4000 random keys (where in) took 316ms 
Querying for 5000 random keys (where in) took 391ms 
Querying for 6000 random keys (where in) took 466ms 
Querying for 7000 random keys (where in) took 552ms 
Querying for 8000 random keys (where in) took 644ms 
Querying for 9000 random keys (where in) took 743ms 
Querying for 10000 random keys (where in) took 853ms 

Czy jest to szybszy sposób niż użycie GDZIE IN w tym celu.

Nie możemy dokonać sprzężenia, ponieważ jest między odłączonymi systemami.

Słyszałem, że in memory temp table joined to the data in MYSQL may be faster, ale z moich badań MSSQL nie ma opcji w pamięci tabeli, a nawet nie byłoby to podatne na dokładnie taki sam skan indeksu na wstawieniu do tabeli temp, ponieważ WHERE IN ma ?

EDIT:

Ten stół ma identyfikator jako PK tak ma indeks domyślny PK, cf

CREATE TABLE [dbo].[Entities](
    [Id] [int] IDENTITY(1,1) NOT NULL, 
CONSTRAINT [PK_dbo.Entities] PRIMARY KEY CLUSTERED 
(
    [Id] ASC 
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY] 
) ON [PRIMARY] 

Plan Wykonanie

Oto GIST dla aplikacja konsolowa, która generuje te wyniki wydajności: https://gist.github.com/lukemcgregor/5914774

EDIT 2 Utworzono funkcję, która tworzy tabelę tymczasową z oddzielonego przecinkiem ciągu znaków, a następnie łączy się z tą tabelą. Jest szybciej, ale myślę, że głównie z powodu problemu z parsowania kwerendy z którym w

Querying for 1 random keys took 1ms 
Querying for 1000 random keys took 34ms 
Querying for 2000 random keys took 69ms 
Querying for 3000 random keys took 111ms 
Querying for 4000 random keys took 143ms 
Querying for 5000 random keys took 182ms 
Querying for 6000 random keys took 224ms 
Querying for 7000 random keys took 271ms 
Querying for 8000 random keys took 315ms 
Querying for 9000 random keys took 361ms 
Querying for 10000 random keys took 411ms 

Answer 1

OK, więc udało mi się to bardzo szybko, definiując typ tabeli, a następnie przekazując ten typ bezpośrednio do zapytania i dołączając do niego.

w SQL

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

w kodzie

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

ten produkuje następujące wyniki

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 

Answer 2

Myślę, że jeśli dołączył swój stolik z tabeli pamięci indeksowane przez klucz podstawowy, takich jak:

declare @tbl table (ids int primary key) 

możesz wypełnić tę tabelę identyfikatorami, których potrzebujesz, i przygotować zoptymalizowane sprzężenie wewnętrzne.

Problem może być czasem, który zajmie wypełnienie go. Sądzę, że możesz albo mieć połączony serwer do tego, albo może użyć narzędzia BCP, aby wypełnić tabelę tymczasową, a następnie ją usunąć.

Answer 3

Po pierwsze, uważam, że twierdzenie, że dane sugerują wartość O(n log(n)), jest bardzo trudne. (To wspaniałe, że zrobiłaś test wydajności, przy okazji). Tu jest czas na wartość:

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 

Chociaż istnieje niewielki wzrost jako czas idzie w górę, skok od 2000-3000 jest dużo, znacznie bardziej widoczne. Jeśli jest to powtarzalne, pytanie brzmi: dlaczego taka nieciągłość.

Dla mnie jest to bardziej sugestia O(n) i O(n log(n)). ALE, empiryczne oszacowania wartości teoretycznych są trudne do oszacowania. Tak więc dokładny limit nie jest tak ważny.

Oczekuję, że wydajność będzie równa O(n) (gdzie n jest wartością rzeczywistą, a nie długością bitu, jak to jest w niektórych szacunkach). Rozumiem, że in zachowuje się jak gigantyczny zestaw or s. Większość zapisów kończy się niepowodzeniem, więc muszą wykonać wszystkie porównania. Stąd O(n).

Następne pytanie dotyczy indeksu w polu identyfikatora. W takim przypadku można uzyskać zestaw zgodnych identyfikatorów w O(n log(n)) time ( log (n) for traversing the index and n` za wykonanie dla każdej wartości). Te szwy są gorsze, ale pominęliśmy współczynnik wielkości oryginalnego stołu. To powinna być duża wygrana.

Zgodnie z sugestią Andre, można załadować tabelę i dołączyć do tabeli tymczasowej. Zostawiłbym indeks, ponieważ prawdopodobnie lepiej jest użyć indeksu na większym stole. Powinno ci to pomóc uzyskać O(n log(n)) - bez (znaczącej) zależności od rozmiaru oryginalnej tabeli. Lub możesz pominąć indeks i mieć O(n * m), gdzie m jest rozmiarem oryginalnej tabeli. Myślę, że każdy indeks zbudowany na tabeli tymczasowej przywraca wydajność (zakładając, że dane nie są wybierane).

Umieszczenie wszystkiego w zapytaniu ma podobny, nieaktualny problem - parsowanie zapytania. Trwa to dłużej, ponieważ ciąg staje się dłuższy.

Krótko mówiąc, pochwalam Cię za wykonanie pomiarów wydajności, ale nie za wyciąganie wniosków na temat złożoności algorytmicznej. Nie sądzę, aby twoje dane wspierały twój wniosek. Również obsługa zapytań jest nieco bardziej skomplikowana niż sugerujesz, a ty pomijasz rozmiar większego stołu - który może mieć dominujący wpływ. I jestem całkiem ciekawy, co się dzieje między 2000 a 3000 rzędów.