Pourquoi la direction de l'index est-elle importante dans MongoDB?

114

Pour citer les documents :

Lors de la création d'un index, le nombre associé à une clé spécifie la direction de l'index, il doit donc toujours être 1 (croissant) ou -1 (décroissant). La direction n'a pas d'importance pour les index à clé unique ou pour la récupération à accès aléatoire, mais elle est importante si vous effectuez des tris ou des requêtes de plage sur des index composés.

Cependant, je ne vois aucune raison pour laquelle la direction de l'indice devrait avoir une importance sur les indices composés. Quelqu'un peut-il fournir une explication supplémentaire (ou un exemple)?

johndodo
la source

Réponses:

113

MongoDB concatène la clé composée d'une certaine manière et l'utilise comme clé dans un BTree.

Lors de la recherche d'éléments uniques - L'ordre des nœuds dans l'arborescence n'est pas pertinent.

Si vous renvoyez une plage de nœuds - Les éléments proches les uns des autres seront dans les mêmes branches de l'arbre. Plus les nœuds sont proches dans la plage, plus vite ils peuvent être récupérés.

Avec un seul index de champ - L'ordre n'a pas d'importance. S'ils sont rapprochés dans l'ordre croissant, ils le seront également dans l'ordre décroissant.

Lorsque vous avez une clé composée - L'ordre commence à avoir de l'importance.

Par exemple, si la clé est A croissant B croissant, l'index peut ressembler à ceci:

Rangée AB
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Une requête pour A croissant B décroissant devra sauter autour de l'index dans le désordre pour renvoyer les lignes et sera plus lente. Par exemple, il retournera Row1, 3, 2, 6, 5, 4, 7

Une requête à distance dans le même ordre que l'index renverra simplement les lignes séquentiellement dans le bon ordre.

La recherche d'un enregistrement dans un BTree prend O (Log (n)) temps. Trouver une plage d'enregistrements dans l'ordre n'est que OLog (n) + k où k est le nombre d'enregistrements à renvoyer.

Si les enregistrements sont dans le désordre, le coût peut être aussi élevé que OLog (n) * k

Jared Kells
la source
1
La ligne résultante devrait probablement être 1, 3, 2, 6, 5, 4, 7?
johndodo
Je ne vois toujours aucune raison pour qu'il soit plus lent. Seul l'algorithme doit être différent (pour chaque groupe de valeurs dans A, il doit sauter à la fin du groupe et le traiter dans l'ordre inverse), mais comme les index MongoDB sont en mémoire, cela ne devrait avoir aucun effet notable sur la vitesse. De plus, le SGBDR ne sait rien de la direction avec les index et la situation est-elle assez similaire?
johndodo
8
La raison pour laquelle il s'agit d'un impact sur les performances est qu'il ne s'agit pas simplement d'une liste séquentielle en mémoire, comme l'exemple simplifié. C'est en fait un arbre pondéré. Sauter dans le désordre impliquera de parcourir à nouveau l'arbre. Les RDMS ont définitivement l'ordre des index.
Jared Kells
1
Récupérer les nœuds d'un BTree dans l'ordre est aussi simple que de se déplacer le long de chaque feuille jusqu'à ce que vous soyez épuisé, puis de monter d'un niveau et de descendre la branche suivante. C'est O (n) Hors service, c'est beaucoup plus gourmand en CPU.
Jared Kells
Merci pour plus de précisions. J'ai vérifié les documents pour les index MySQL - il est vraiment possible de spécifier la direction de l'index, mais le paramètre est ignoré.
johndodo
46

La réponse simple que vous recherchez est que la direction n'a d'importance que lorsque vous triez sur deux champs ou plus .

Si vous triez sur {a : 1, b : -1}:

L'index {a : 1, b : 1}sera plus lent que l' index{a : 1, b : -1}

Zaid Masud
la source
1
@MarkPieszak parce que tout le tri devrait être fait en mémoire, ce qui rend l'index inutile
Sammaye
@Sammaye Je pense que c'est la bonne idée, même si je ne suis pas sûr que ce soit le genre entier . Je devrais regarder l'implémentation pour savoir comment cela fonctionne vraiment, mais je pense que les résultats pourraient être tirés en arrière triés par a seul, puis le tri supplémentaire b devrait être fait en mémoire.
Zaid Masud
1
hmm, bizarre la dernière fois que j'ai vérifié le code, il a abandonné les tris partiels en raison de la façon dont le tri était, mais meh, peut-être que ça a changé
Sammaye
Que faire si je trie {a: -1, b: -1}, dois-je avoir un {a: -1, b: -1}index ou cela {a: 1, b: 1}suffira.
Hussain
@Hussain dans votre exemple, l' {a: 1, b: 1}index devrait être suffisant car inverser complètement un index est très bien. par exemple, l'index sur {a: 1}peut être utilisé pour un tri sur{a: -1}
Zaid Masud
12

Pourquoi les index

Comprenez deux points clés.

  1. Alors qu'un index vaut mieux que pas d'index, l'index correct est bien meilleur que l'un ou l'autre.
  2. MongoDB n'utilisera qu'un seul index par requête, créant des index composés avec un ordre de champ approprié pour ce que vous souhaitez probablement utiliser.

Les index ne sont pas gratuits. Ils prennent de la mémoire et imposent une pénalité de performance lors des insertions, des mises à jour et des suppressions. Normalement, l'impact sur les performances est négligeable (en particulier par rapport aux gains de performances de lecture), mais cela ne signifie pas que nous ne pouvons pas être intelligents dans la création de nos index.

Comment les index

Identifier le groupe de champs à indexer ensemble consiste à comprendre les requêtes que vous exécutez. L'ordre des champs utilisés pour créer votre index est critique. La bonne nouvelle est que, si vous vous trompez dans l'ordre, l'index ne sera pas du tout utilisé, il sera donc facile à repérer avec l'explication.

Pourquoi trier

Vos requêtes peuvent nécessiter un tri. Mais le tri peut être une opération coûteuse, il est donc important de traiter les champs sur lesquels vous triez comme un champ que vous interrogez. Ce sera donc plus rapide s'il a un index. Il y a cependant une différence importante, le champ que vous triez doit être le dernier champ de votre index. La seule exception à cette règle est que si le champ fait également partie de votre requête, la règle doit être le dernier ne s'applique pas.

Comment le tri

Vous pouvez spécifier un tri sur toutes les clés de l'index ou sur un sous-ensemble; cependant, les clés de tri doivent être répertoriées dans le même ordre qu'elles apparaissent dans l'index. Par exemple, un modèle de clé d'index {a: 1, b: 1} peut prendre en charge un tri sur {a: 1, b: 1} mais pas sur {b: 1, a: 1}.

Le tri doit spécifier le même sens de tri (c'est-à-dire croissant / décroissant) pour toutes ses clés comme modèle de clé d'index ou spécifier le sens de tri inversé pour toutes ses clés comme modèle de clé d'index. Par exemple, un modèle de clé d'index {a: 1, b: 1} peut prendre en charge un tri sur {a: 1, b: 1} et {a: -1, b: -1} mais pas sur {a: -1 , b: 1}.

Supposons qu'il existe ces index:

{ 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
la source
Je comprends que c'est un exemple, mais s'il y a un index { a: 1, b: 1, c: 1 }avez-vous vraiment besoin d'index { a: 1}et / { a: 1, b: 1}ou un index { a: 1, b: 1, c: 1 }couvre tous les cas? Si les requêtes utilisent toujours le même tri: 1 pas de tri dans la requête avec -1
Lukas Liesis
1
S'il y a beaucoup de requêtes qui ne travaillent que sur la propriété 'a', il est plus rapide de rechercher avec l'index avec la propriété 'a' pour le moteur de base de données, que la recherche par index avec 3 propriétés 'a', 'b', 'c'. Parce que la taille de l'index augmentera et que le nombre augmentera également. ex. S'il y a 20 chapitres dans le livre. Il est donc plus rapide d'aller au chapitre 3 puis à une page spécifique. @LukasLiesis
Somnath Muluk