Quanto um índice precisa para restringir os resultados de uma pesquisa para ser útil?

A diversidade dos dados de uma coluna é conhecida como seletividade. A seletividade é útil para saber ao determinar se um índice será útil, mas não é a única coisa que determina o benefício de velocidade. Outros fatores incluem a velocidade do armazenamento do índice em comparação com a tabela, quanto da tabela/índice já está armazenado em cache, quão grande é o índice em comparação com a tabela e várias outras coisas.

Saber o tipo de dados da coluna não nos ajuda necessariamente a determinar o quão seletivo será um índice na coluna. Mesmo uma coluna restrita a dois valores pode usar esses valores para apenas algumas linhas e ter o restante NULL. Por outro lado, uma coluna que pode ter muitos valores distintos pode ter o mesmo valor em todas as linhas. Mesmo com sua idcoluna onde todas as linhas teriam valores exclusivos, se você estiver procurando por linhas com id>= 10, o índice provavelmente não seria útil, embora seja altamente seletivo.

Você não pode usar apenas a seletividade para determinar se um índice será útil ou não, porque mesmo que retorne 100% das linhas, se o índice incluir todos os dados necessários para a consulta, será mais rápido do que usar a tabela. Por outro lado, para uma tabela pequena, pode ser mais rápido consultar tudo, mesmo que a linha procurada represente apenas 1% do total.

Determinar quais índices devem ser criados tem menos a ver com a estrutura da tabela do que com as consultas importantes e quais dados eles precisam recuperar.

Em geral, sim, você está correto. Um índice b-tree é mais útil quando permite identificar uma fração relativamente pequena das linhas na tabela que precisam ser retornadas.

Quanto ao que é esse corte, depende. Quase todo banco de dados relacional corporativo moderno terá um otimizador baseado em custo que tenta elaborar o melhor plano de consulta, dado um monte de estatísticas sobre a distribuição de dados, a despesa relativa de diferentes operações, etc. Bancos de dados diferentes e versões diferentes de o mesmo banco de dados dependerá de uma ampla variedade de configurações, estatísticas e outras informações para descobrir onde está esse corte. Meu palpite seria que, quando você está recuperando mais de 10-15% das linhas, provavelmente está no intervalo em que uma varredura de tabela será mais eficiente. Mas é fácil chegar a casos em que é melhor fazer uma varredura de tabela se o índice fornecer apenas 5% dos dados ou se você

Depende do tipo de índice! Presumo que você esteja pensando em um índice de árvore binária "comum". Eles são normalmente usados ​​por "planejadores" quando se espera que 10% das linhas da tabela sejam recuperadas. Por que uma porcentagem tão baixa? Não se esqueça de que o DBMS precisa recuperar blocos de índice, não linhas, e muitos dos dados recuperados não serão verificados para a linha que está sendo procurada (ou seja, sobrecarga). Além disso, um índice em si usa espaço, certamente não está nem perto de uma operação "livre" ou mesmo de tempo constante (e, portanto, espaço).

Veja http://docs.oracle.com/cd/B28359_01/server.111/b28274/optimops.htm#autoId25 para uma boa visão geral das considerações do "planejador" (pelo menos, aquelas pensadas de forma razoavelmente atual versão do Oracle).

A velocidade de certas operações baseadas em disco afeta a decisão da Oracle de usar uma varredura de índice ou uma varredura de tabela completa também.

E em minha resposta até agora, presumi que estamos falando sobre uma pesquisa de índice comum para um valor. Existem muitas outras varreduras de índice usadas no Oracle, por exemplo (consulte o link que forneci).

Também há índices de bitmap: eles armazenam um bitmap (ou seja, 0 e 1, 1 para cada linha) para cada valor exclusivo. Eles são ideais para booleanos e outras colunas de baixa cardinalidade (mas também podem ser úteis em outros casos, como mostraram alguns artigos).

A desvantagem dos índices de bitmap é que eles são muito caros para atualizar e, portanto, mais úteis para bancos de dados somente leitura (como sistemas de suporte à decisão, data warehouses e similares).

Boas respostas, ambas. A maioria dos mecanismos de banco de dados otimizará as consultas para minimizar a E/S de disco, portanto, se um índice não restringir as opções a uma porcentagem bastante pequena da tabela, o otimizador de consulta usará uma verificação completa da tabela. Essa porcentagem varia entre os mecanismos de banco de dados, mas geralmente é da ordem de 2 a 10%.

As colunas binárias geralmente não são um bom índice usado sozinho, mas podem ser usados ​​em conjunto com outra coluna.

Uma coluna "id" (para aqueles que podem não estar familiarizados com Ruby/Rails, considere isso uma coluna inteira de chave primária única e auto-incrementada) na maioria das vezes DEVE ser indexada devido à natureza de seu uso. Se for declarado como chave primária, você não precisa declarar um índice... ele obtém um de qualquer maneira.

As colunas varchar podem ou não ser um bom índice, dependendo do conteúdo. Muitos mecanismos de banco de dados permitirão que você indexe apenas as primeiras colunas de um varchar. Bom exemplo: os primeiros 8 do sobrenome mais os primeiros 4 do primeiro nome.

Existem exceções para a maioria das regras; leia sobre o banco de dados específico que você está usando.

Recentemente, participei de um evento de imersão SQL Skills (IE1) de Paul Randall e Kimberly Tripp, Kimberly sendo a autoridade em indexação e internos do SQL Server.

Não posso te dizer teoricamente quando seria ideal usar um índice, tenho certeza que um modelo matemático poderia ser criado para te dizer isso. Em termos práticos dentro do SQL Server, em suas demonstrações foi utilizado um índice se pudesse evitar a varredura de 90% da tabela. Os resultados variaram embora. Às vezes, ele usaria uma varredura de tabela em uma porcentagem muito menor. Tinha a ver com carnalidade em suas estatísticas também.

Posso obter as informações e analisá-las se achar que serão úteis para você.