Dlaczego kierunek indeksu ma znaczenie w MongoDB?

114

Aby zacytować dokumenty :

Podczas tworzenia indeksu liczba skojarzona z kluczem określa kierunek indeksu, więc zawsze powinna wynosić 1 (rosnąco) lub -1 (malejąco). Kierunek nie ma znaczenia dla indeksów z pojedynczym kluczem lub dla pobierania dostępu swobodnego, ale jest ważny, jeśli wykonujesz zapytania sortowania lub zakresowe na indeksach złożonych.

Jednak nie widzę powodu, dla którego kierunek indeksu miałby mieć znaczenie w przypadku indeksów złożonych. Czy ktoś może podać dalsze wyjaśnienie (lub przykład)?

johndodo
źródło

Odpowiedzi:

113

MongoDB w jakiś sposób łączy klucz złożony i używa go jako klucza w BTree.

Podczas wyszukiwania pojedynczych elementów - kolejność węzłów w drzewie nie ma znaczenia.

Jeśli zwracasz zakres węzłów - elementy znajdujące się blisko siebie będą znajdować się w tych samych gałęziach drzewa. Im bliżej węzłów znajdują się w zasięgu, tym szybciej można je odzyskać.

Z jednym indeksem pola - kolejność nie ma znaczenia. Jeśli są blisko siebie w porządku rosnącym, będą również blisko siebie w porządku malejącym.

Kiedy masz klucz złożony - kolejność zaczyna mieć znaczenie.

Na przykład, jeśli klucz to A rosnąco B rosnąco, indeks może wyglądać mniej więcej tak:

Rząd AB
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Zapytanie o A rosnąco B malejąco będzie wymagało przeskoczenia po indeksie w niewłaściwej kolejności, aby zwrócić wiersze, i będzie wolniejsze. Na przykład zwróci Row1, 3, 2, 6, 5, 4, 7

Zapytanie zasięgowe w tej samej kolejności co indeks po prostu zwróci wiersze sekwencyjnie we właściwej kolejności.

Znalezienie rekordu w BTree zajmuje O (Log (n)) czasu. Znalezienie szeregu rekordów w kolejności to tylko OLog (n) + k, gdzie k to liczba rekordów do zwrócenia.

Jeśli rekordy są niesprawne, koszt może sięgać nawet OLog (n) * k

Jared Kells
źródło
1
Wynikowy wiersz prawdopodobnie powinien być 1, 3, 2, 6, 5, 4, 7?
johndodo
Nadal nie widzę powodu, dla którego byłby wolniejszy. Tylko algorytm powinien być inny (dla każdej grupy wartości w A powinien przeskoczyć na koniec grupy i przetworzyć ją w odwrotnej kolejności), ale ponieważ indeksy MongoDB są w pamięci, nie powinno to mieć zauważalnego wpływu na szybkość. Poza tym RDBMS nic nie wie o kierunku z indeksami, a sytuacja jest dość podobna?
johndodo
8
Powodem, dla którego jest to hit wydajnościowy, jest to, że nie jest to tylko kolejna lista w pamięci, jak w uproszczonym przykładzie. W rzeczywistości jest to obciążone drzewo. Wyskoczenie z kolejności będzie wymagało ponownego przejścia przez drzewo. RDMS ma definitywnie porządek na indeksy.
Jared Kells
1
Pobieranie węzłów z BTree w kolejności jest tak proste, jak poruszanie się wzdłuż każdego liścia, aż skończy się, a następnie przejście w górę i w dół do następnej gałęzi. To O (n) Nie w porządku, jest znacznie bardziej obciążające procesor.
Jared Kells
Dzięki za dalsze wyjaśnienia. Sprawdziłem dokumenty pod kątem indeksów MySQL - naprawdę można określić kierunek indeksu, ale ustawienie jest ignorowane.
johndodo
46

Prosta odpowiedź , że szukasz jest to, że kierunek ma znaczenie tylko podczas sortowania na dwóch lub więcej pól .

Jeśli sortujesz według {a : 1, b : -1}:

Indeks {a : 1, b : 1}będzie wolniejszy niż indeks{a : 1, b : -1}

Zaid Masud
źródło
1
@MarkPieszak ponieważ cały rodzaj musiałyby być zrobione w pamięci dzięki czemu indeks bezużyteczny
Sammaye
@Sammaye Myślę, że to dobry pomysł, chociaż nie jestem pewien, czy to cały rodzaj. Musiałbym spojrzeć na realizację wiedzieć jak to naprawdę działa, ale myślę, że wyniki mogłyby być odciągany do tyłu klasyfikowane według sam, a następnie dodatkowe b sort musiałyby być zrobione w pamięci.
Zaid Masud
1
hmm, dziwne, jak ostatnio sprawdzałem kod, wypadł częściowo z powodu sortowania, ale eee, może to się zmieniło
Sammaye
A co, jeśli sortuję {a: -1, b: -1}, czy mam {a: -1, b: -1}indeks, czy {a: 1, b: 1}wystarczy.
Hussain
@Hussain w twoim przykładzie {a: 1, b: 1}indeks powinien wystarczyć, ponieważ całkowite odwrócenie indeksu jest w porządku. np. Index on {a: 1}może być użyty do sortowania{a: -1}
Zaid Masud
12

Dlaczego indeksy

Zrozum dwa kluczowe punkty.

  1. Chociaż indeks jest lepszy niż brak indeksu, poprawny indeks jest znacznie lepszy niż jeden z nich.
  2. MongoDB użyje tylko jednego indeksu na zapytanie, tworząc indeksy złożone z odpowiednim porządkiem pól, które prawdopodobnie chcesz użyć.

Indeksy nie są darmowe. Zabierają pamięć i nakładają spadek wydajności podczas wstawiania, aktualizacji i usuwania. Zwykle wpływ na wydajność jest pomijalny (zwłaszcza w porównaniu ze wzrostem wydajności odczytu), ale to nie znaczy, że nie możemy sprytnie tworzyć naszych indeksów.

Jak Indexes

Określenie, która grupa pól powinna być razem indeksowana, polega na zrozumieniu wykonywanych zapytań. Kolejność pól używanych do tworzenia indeksu ma kluczowe znaczenie. Dobra wiadomość jest taka, że ​​jeśli pomylisz się w zamówieniu, indeks nie będzie w ogóle używany, więc łatwo będzie go znaleźć za pomocą wyjaśnienia.

Dlaczego sortowanie

Twoje zapytania mogą wymagać sortowania. Ale sortowanie może być kosztowną operacją, dlatego ważne jest, aby traktować pola, według których sortujesz, tak jak pole, którego dotyczy zapytanie. Więc będzie szybciej, jeśli ma index. Jest jednak jedna ważna różnica, sortowane pole musi być ostatnim polem w indeksie. Jedynym wyjątkiem od tej reguły jest to, że jeśli pole jest również częścią zapytania, reguła musi być ostatnią nie ma zastosowania.

Jak sortować

Możesz określić sortowanie dla wszystkich kluczy indeksu lub podzbioru; jednak klucze sortowania muszą być wymienione w tej samej kolejności, w jakiej pojawiają się w indeksie. Na przykład wzorzec klucza indeksu {a: 1, b: 1} może obsługiwać sortowanie na {a: 1, b: 1}, ale nie na {b: 1, a: 1}.

Sortowanie musi określać ten sam kierunek sortowania (tj. Rosnąco / malejąco) dla wszystkich swoich kluczy co wzorzec klucza indeksu lub określać odwrotny kierunek sortowania dla wszystkich swoich kluczy jako wzorzec klucza indeksu. Na przykład wzorzec klucza indeksu {a: 1, b: 1} może obsługiwać sortowanie na {a: 1, b: 1} i {a: -1, b: -1}, ale nie na {a: -1 , b: 1}.

Załóżmy, że istnieją te indeksy:

{ a: 1 }
{ a: 1, b: 1 }
{ a: 1, b: 1, c: 1 }

Example                                                    Index Used
db.data.find().sort( { a: 1 } )                            { a: 1 }
db.data.find().sort( { a: -1 } )                           { a: 1 }
db.data.find().sort( { a: 1, b: 1 } )                      { a: 1, b: 1 }
db.data.find().sort( { a: -1, b: -1 } )                    { a: 1, b: 1 }
db.data.find().sort( { a: 1, b: 1, c: 1 } )                { a: 1, b: 1, c: 1 }
db.data.find( { a: { $gt: 4 } } ).sort( { a: 1, b: 1 } )   { a: 1, b: 1 }
Somnath Muluk
źródło
Rozumiem, że to przykład, ale jeśli istnieje indeks { a: 1, b: 1, c: 1 }, czy naprawdę potrzebujesz indeksów { a: 1}i { a: 1, b: 1}czy indeks { a: 1, b: 1, c: 1 }obejmuje wszystkie sprawy? Jeśli zapytania zawsze używają tego samego sortowania: 1 nie sortuje w zapytaniu z -1
Lukas Liesis
1
Jeśli istnieje wiele zapytań, które działają tylko na właściwości „a”, szybsze jest wyszukiwanie z indeksem z właściwością „a” dla silnika bazy danych niż wyszukiwanie według indeksu z 3 właściwościami „a”, „b”, „c”. Ponieważ rozmiar indeksu wzrośnie, a liczba również wzrośnie. dawny. Jeśli w książce jest 20 rozdziałów. Więc szybciej jest przejść do rozdziału 3, a potem do konkretnej strony. @LukasLiesis
Somnath Muluk