Warum ist die Richtung des Index in MongoDB wichtig?

114

So zitieren Sie die Dokumente :

Beim Erstellen eines Index gibt die einem Schlüssel zugeordnete Nummer die Richtung des Index an, daher sollte sie immer 1 (aufsteigend) oder -1 (absteigend) sein. Die Richtung spielt keine Rolle für Einzelschlüsselindizes oder für das Abrufen von Direktzugriffen, ist jedoch wichtig, wenn Sie Sortier- oder Bereichsabfragen für zusammengesetzte Indizes durchführen.

Ich sehe jedoch keinen Grund, warum die Richtung des Index bei zusammengesetzten Indizes von Bedeutung sein sollte. Kann jemand bitte eine weitere Erklärung (oder ein Beispiel) geben?

Johndodo
quelle

Antworten:

111

MongoDB verkettet den zusammengesetzten Schlüssel auf irgendeine Weise und verwendet ihn als Schlüssel in einem BTree.

Beim Suchen einzelner Elemente - Die Reihenfolge der Knoten im Baum spielt keine Rolle.

Wenn Sie eine Reihe von Knoten zurückgeben - Die Elemente, die nahe beieinander liegen, befinden sich in denselben Zweigen des Baums. Je näher die Knoten im Bereich sind, desto schneller können sie abgerufen werden.

Mit einem einzelnen Feldindex - Die Reihenfolge spielt keine Rolle. Wenn sie in aufsteigender Reihenfolge nahe beieinander liegen, sind sie auch in absteigender Reihenfolge nahe beieinander.

Wenn Sie einen zusammengesetzten Schlüssel haben - Die Reihenfolge spielt eine Rolle.

Wenn der Schlüssel beispielsweise A aufsteigend B aufsteigend ist, sieht der Index möglicherweise folgendermaßen aus:

Reihe AB
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Eine Abfrage für A aufsteigend B absteigend muss in der falschen Reihenfolge um den Index springen, um die Zeilen zurückzugeben, und ist langsamer. Zum Beispiel wird Row zurückgegeben1, 3, 2, 6, 5, 4, 7

Eine Bereichsabfrage in derselben Reihenfolge wie der Index gibt die Zeilen einfach nacheinander in der richtigen Reihenfolge zurück.

Das Finden eines Datensatzes in einem BTree benötigt O (Log (n)) Zeit. Das Finden eines Bereichs von Datensätzen in der Reihenfolge ist nur OLog (n) + k, wobei k die Anzahl der zurückzugebenden Datensätze ist.

Wenn die Datensätze nicht in Ordnung sind, können die Kosten bis zu OLog (n) * k betragen

Jared Kells
quelle
1
Die resultierende Zeile sollte wahrscheinlich sein 1, 3, 2, 6, 5, 4, 7?
Johndodo
Ich sehe immer noch keinen Grund dafür, dass es langsamer ist. Nur der Algorithmus sollte unterschiedlich sein (für jede Gruppe von Werten in A sollte er zum Ende der Gruppe springen und ihn in umgekehrter Reihenfolge verarbeiten), aber da sich MongoDB-Indizes im Speicher befinden, sollte dies keinen merklichen Einfluss auf die Geschwindigkeit haben. Auch wissen RDBMS nichts über die Richtung mit Indizes und die Situation dort ist ziemlich ähnlich afaik?
Johndodo
8
Der Grund, warum es sich um einen Leistungseinbruch handelt, liegt darin, dass es sich nicht nur um eine sequentielle Liste im Speicher handelt, wie im vereinfachten Beispiel. Es ist eigentlich ein gewichteter Baum. Wenn Sie nicht in der richtigen Reihenfolge springen, müssen Sie den Baum erneut durchqueren. RDMS haben definitiv die Reihenfolge der Indizes.
Jared Kells
1
Das Abrufen von Knoten aus einem BTree in der angegebenen Reihenfolge ist so einfach wie das Bewegen entlang jedes Blattes, bis Sie ausgehen und dann eine Ebene höher und den nächsten Zweig hinunter gehen. Es ist O (n) Außer Betrieb ist es viel CPU-intensiver.
Jared Kells
Vielen Dank für die weitere Klarstellung. Ich habe die Dokumente auf MySQL-Indizes überprüft - es ist wirklich möglich, die Indexrichtung anzugeben, aber die Einstellung wird ignoriert.
Johndodo
45

Die einfache Antwort , nach der Sie suchen, ist, dass die Richtung nur wichtig ist, wenn Sie nach zwei oder mehr Feldern sortieren .

Wenn Sie sortieren nach {a : 1, b : -1}:

Der Index {a : 1, b : 1}ist langsamer als der Index{a : 1, b : -1}

Zaid Masud
quelle
1
@ MarkPieszak, weil die gesamte Sortierung im Speicher durchgeführt werden müsste, um den Index unbrauchbar zu machen
Sammaye
@Sammaye Ich denke, das ist die richtige Idee, obwohl ich nicht sicher bin, ob es die ganze Art ist. Ich müsste mir die Implementierung ansehen, um zu wissen, wie sie wirklich funktioniert, aber ich würde denken, dass die Ergebnisse von a allein zurückgezogen werden könnten , und dann müsste die zusätzliche b- Sortierung im Speicher durchgeführt werden.
Zaid Masud
1
hmm, seltsam, als ich das letzte Mal den Code überprüft habe, hat er teilweise sortiert, weil die Sortierung so war, aber meh, vielleicht hat er sich geändert
Sammaye
Was ist, wenn ich sortiere {a: -1, b: -1}, sollte ich einen {a: -1, b: -1}Index haben oder {a: 1, b: 1}wird dies ausreichen ?
Hussain
@Hussain in Ihrem Beispiel sollte der {a: 1, b: 1}Index ausreichen, da das vollständige Invertieren eines Index in Ordnung ist. zB Index on {a: 1}kann für eine Sortierung verwendet werden{a: -1}
Zaid Masud
12

Warum Indizes?

Verstehe zwei wichtige Punkte.

  1. Während ein Index besser ist als kein Index, ist der richtige Index viel besser als beide.
  2. MongoDB verwendet nur einen Index pro Abfrage, wodurch zusammengesetzte Indizes mit der richtigen Feldreihenfolge erstellt werden, die Sie wahrscheinlich verwenden möchten.

Indizes sind nicht kostenlos. Sie belegen Speicherplatz und führen zu Leistungseinbußen beim Einfügen, Aktualisieren und Löschen. Normalerweise ist der Leistungseinbruch vernachlässigbar (insbesondere im Vergleich zu Verbesserungen der Leseleistung), aber das bedeutet nicht, dass wir beim Erstellen unserer Indizes nicht klug sein können.

Wie Indizes

Um festzustellen, welche Gruppe von Feldern zusammen indiziert werden soll, müssen Sie die von Ihnen ausgeführten Abfragen verstehen. Die Reihenfolge der Felder, die zum Erstellen Ihres Index verwendet werden, ist entscheidend. Die gute Nachricht ist, dass der Index bei falscher Reihenfolge überhaupt nicht verwendet wird, sodass es leicht zu erklären ist.

Warum sortieren?

Ihre Abfragen müssen möglicherweise sortiert werden. Das Sortieren kann jedoch eine teure Operation sein. Daher ist es wichtig, die Felder, nach denen Sie sortieren, wie ein Feld zu behandeln, das Sie abfragen. Es wird also schneller sein, wenn es einen Index hat. Es gibt jedoch einen wichtigen Unterschied: Das Feld, das Sie sortieren, muss das letzte Feld in Ihrem Index sein. Die einzige Ausnahme von dieser Regel besteht darin, dass die Must-be-last-Regel nicht gilt, wenn das Feld auch Teil Ihrer Abfrage ist.

Wie sortieren

Sie können eine Sortierung für alle Schlüssel des Index oder für eine Teilmenge angeben. Die Sortierschlüssel müssen jedoch in derselben Reihenfolge aufgelistet werden, in der sie im Index angezeigt werden. Beispielsweise kann ein Indexschlüsselmuster {a: 1, b: 1} eine Sortierung nach {a: 1, b: 1} unterstützen, jedoch nicht nach {b: 1, a: 1}.

Die Sortierung muss für alle Schlüssel dieselbe Sortierrichtung (dh aufsteigend / absteigend) wie das Indexschlüsselmuster oder für alle Schlüssel die umgekehrte Sortierrichtung als Indexschlüsselmuster angeben. Beispielsweise kann ein Indexschlüsselmuster {a: 1, b: 1} eine Sortierung nach {a: 1, b: 1} und {a: -1, b: -1} unterstützen, jedoch nicht nach {a: -1 , b: 1}.

Angenommen, es gibt diese Indizes:

{ 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
quelle
Ich verstehe, dass dies ein Beispiel ist, aber wenn es einen Index gibt, { a: 1, b: 1, c: 1 }brauchen Sie wirklich Indizes { a: 1}und / { a: 1, b: 1}oder Index { a: 1, b: 1, c: 1 }deckt alle Fälle ab? Wenn Abfragen immer dieselbe Sortierung verwenden: 1 Keine Sortierungen in Abfrage mit -1
Lukas Liesis
1
Wenn es viele Abfragen gibt, die nur für die Eigenschaft 'a' arbeiten, ist die Suche mit dem Index mit der Eigenschaft 'a' nach Datenbankmodulen schneller als die Suche nach dem Index mit den drei Eigenschaften 'a', 'b', 'c'. Weil die Indexgröße zunimmt und auch die Anzahl zunimmt. Ex. Wenn das Buch 20 Kapitel enthält. Es ist also schneller, zu Kapitel 3 und dann zu einer bestimmten Seite zu gelangen. @ LukasLiesis
Somnath Muluk