Por que a direção do índice é importante no MongoDB?

114

Para citar os documentos :

Ao criar um índice, o número associado a uma chave especifica a direção do índice, portanto, deve ser sempre 1 (crescente) ou -1 (decrescente). A direção não importa para índices de chave única ou para recuperação de acesso aleatório, mas é importante se você estiver fazendo classificações ou consultas de intervalo em índices compostos.

No entanto, não vejo razão para que a direção do índice seja importante nos índices compostos. Alguém pode fornecer uma explicação adicional (ou um exemplo)?

johndodo
fonte

Respostas:

112

O MongoDB concatena a chave composta de alguma forma e a usa como a chave em um BTree.

Ao encontrar itens únicos - A ordem dos nós na árvore é irrelevante.

Se você estiver retornando um intervalo de nós - Os elementos próximos um do outro estarão nos mesmos galhos da árvore. Quanto mais próximos os nós estão no intervalo, mais rapidamente eles podem ser recuperados.

Com um único índice de campo - A ordem não importa. Se eles estiverem próximos em ordem crescente, também estarão próximos em ordem decrescente.

Quando você tem uma chave composta - A ordem começa a importar.

Por exemplo, se a chave for A ascendente B ascendente, o índice pode ter a seguinte aparência:

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

Uma consulta para A ascendente B descendente precisará pular o índice fora de ordem para retornar as linhas e será mais lenta. Por exemplo, ele retornará Row1, 3, 2, 6, 5, 4, 7

Uma consulta variada na mesma ordem do índice simplesmente retornará as linhas sequencialmente na ordem correta.

Encontrar um registro em um BTree leva tempo O (Log (n)). Encontrar um intervalo de registros em ordem é apenas OLog (n) + k, onde k é o número de registros a serem retornados.

Se os registros estiverem fora de ordem, o custo pode ser tão alto quanto OLog (n) * k

Jared Kells
fonte
1
A linha resultante provavelmente deve ser 1, 3, 2, 6, 5, 4, 7?
johndodo
Ainda não vejo razão para ser mais lento. Apenas o algoritmo deve ser diferente (para cada grupo de valores em A, ele deve pular para o final do grupo e processá-lo na ordem inversa), mas como os índices do MongoDB estão na memória, isso não deve ter nenhum efeito perceptível na velocidade. Além disso, RDBMS não sabe nada sobre direção com índices e a situação lá é afaik bastante semelhante?
johndodo
8
O motivo pelo qual é um impacto no desempenho é porque não é apenas uma lista sequencial na memória como o exemplo simplificado. Na verdade, é uma árvore com peso. Saltar fora de ordem envolverá atravessar a árvore novamente. RDMS definitivamente tem pedido de índices.
Jared Kells
1
Buscar nós de um BTree em ordem é tão simples quanto mover ao longo de cada folha até que você acabe e então subir um nível e descer no próximo galho. Está O (n) fora de serviço e consome muito mais CPU.
Jared Kells
Obrigado por mais esclarecimentos. Eu verifiquei a documentação dos índices do MySQL - realmente é possível especificar a direção do índice, mas a configuração é ignorada.
johndodo
45

A resposta simples que você está procurando é que a direção só importa quando você está classificando em dois ou mais campos .

Se você está classificando em {a : 1, b : -1}:

O índice {a : 1, b : 1}será mais lento que o índice{a : 1, b : -1}

Zaid Masud
fonte
1
@MarkPieszak porque a classificação inteira teria que ser feita na memória, tornando o índice inútil
Sammaye
@Sammaye Acho que é a ideia certa, embora não tenha certeza de que seja o tipo inteiro . Eu teria que olhar a implementação para saber como ela realmente funciona, mas eu acho que os resultados poderiam ser classificados por a sozinho e, em seguida, a classificação b adicional precisaria ser feita na memória.
Zaid Masud
1
Hmm, estranho da última vez que verifiquei o código, ele descartou classificações parciais devido à forma como a classificação era, mas, talvez tenha mudado
Sammaye
E se eu estiver classificando {a: -1, b: -1}, devo ter {a: -1, b: -1}índice ou será {a: 1, b: 1}o suficiente.
Hussain
@Hussain em seu exemplo, o {a: 1, b: 1}índice deve ser suficiente, já que inverter um índice completamente é bom. por exemplo, o índice {a: 1}pode ser usado para uma classificação{a: -1}
Zaid Masud
12

Por que índices

Compreenda dois pontos principais.

  1. Embora um índice seja melhor do que nenhum índice, o índice correto é muito melhor do que qualquer um deles.
  2. O MongoDB usará apenas um índice por consulta, criando índices compostos com a ordenação de campo adequada o que você provavelmente deseja usar.

Os índices não são gratuitos. Eles ocupam memória e impõem uma penalidade de desempenho ao fazer inserções, atualizações e exclusões. Normalmente, o impacto no desempenho é insignificante (especialmente em comparação com os ganhos no desempenho de leitura), mas isso não significa que não podemos ser inteligentes ao criar nossos índices.

Como índices

Identificar qual grupo de campos deve ser indexado em conjunto é compreender as consultas que você está executando. A ordem dos campos usados ​​para criar seu índice é crítica. A boa notícia é que, se você errar na ordem, o índice não será usado, então será fácil localizá-lo com uma explicação.

Por que classificar

Suas consultas podem precisar de classificação. Mas a classificação pode ser uma operação cara, por isso é importante tratar os campos que você está classificando como um campo que você está consultando. Então será mais rápido se tiver índice. Porém, há uma diferença importante: o campo que você está classificando deve ser o último campo em seu índice. A única exceção a esta regra é se o campo também fizer parte da sua consulta, então a regra deve ser o último não se aplica.

Como classificar

Você pode especificar uma classificação em todas as chaves do índice ou em um subconjunto; no entanto, as chaves de classificação devem ser listadas na mesma ordem em que aparecem no índice. Por exemplo, um padrão de chave de índice {a: 1, b: 1} pode suportar uma classificação em {a: 1, b: 1}, mas não em {b: 1, a: 1}.

A classificação deve especificar a mesma direção de classificação (ou seja, crescente / decrescente) para todas as suas chaves como o padrão de chave de índice ou especificar a direção de classificação reversa para todas as suas chaves como o padrão de chave de índice. Por exemplo, um padrão de chave de índice {a: 1, b: 1} pode suportar uma classificação em {a: 1, b: 1} e {a: -1, b: -1}, mas não em {a: -1 , b: 1}.

Suponha que existam estes índices:

{ 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
fonte
Eu entendo que é um exemplo, mas se houver índice { a: 1, b: 1, c: 1 }, você realmente precisa de índices { a: 1}e / { a: 1, b: 1}ou índice { a: 1, b: 1, c: 1 }cobre todos os casos? Se as consultas sempre usarem a mesma classificação: 1 nenhuma classificação na consulta com -1
Lukas Liesis
1
Se houver muitas consultas que estão trabalhando apenas na propriedade 'a', é mais rápido pesquisar com índice com propriedade 'a' para mecanismo de banco de dados, do que pesquisar por índice com 3 propriedades 'a', 'b', 'c'. Porque o tamanho do índice aumentará e a contagem também aumentará. ex. Se houver 20 capítulos no livro. Portanto, é mais rápido ir para o capítulo 3 e depois para a página específica. @LukasLiesis
Somnath Muluk