Índices

Conceito

Um índice é uma estrutura ordenada auxiliar: as chaves em ordem, cada uma apontando para a linha. É uma 2. Árvore de Busca Binária em disco — mais precisamente uma B-tree, que é a mesma ideia com nós largos para minimizar leituras de bloco.

Por que O(log n): cada nível do B-tree descarta a maior parte do espaço de busca. Com fan-out de algumas centenas por nó, três ou quatro níveis cobrem milhões de linhas — quatro leituras de bloco em vez de varrer tudo.

Por que ele não ajuda em LIKE '%x': o índice está ordenado pelo início da chave. Você pode navegar por prefixo; não existe ordenação por sufixo. Com o curinga à esquerda, a única opção é varrer. (Para busca por sufixo: índice sobre reverse(coluna), ou trigram/GIN no Postgres.)

O custo, que a discussão sobre índice costuma omitir:

• escrita — todo INSERT/UPDATE/DELETE atualiza cada índice afetado. Cinco índices, cinco árvores para manter.
• espaço — o índice guarda a chave e o ponteiro. Índices podem somar mais que a tabela.
• manutenção — fragmentação, estatísticas desatualizadas, VACUUM/ANALYZE.

Índice composto e a regra do prefixo mais à esquerda. Um índice em (a, b) está ordenado por a, e por b dentro de cada a. Logo:

É a mesma razão pela qual você acha "Silva, João" numa lista telefônica ordenada por sobrenome, e não acha todos os "João".

Índice coberto (covering): se o índice contém todas as colunas da consulta, o banco responde sem tocar na tabela. É o index-only scan, e costuma ser a otimização de maior retorno.

Ler o EXPLAIN é a habilidade que fecha a semana. O que procurar: varredura completa onde você esperava busca por índice, e estimativa de linhas muito diferente do real (sinal de estatística velha).

Na prática

Verificado com 200 mil linhas. Sem índice:

sqlite> EXPLAIN QUERY PLAN SELECT * FROM evento WHERE usuario_id = 42;
`--SCAN evento

Com índice:

sqlite> CREATE INDEX idx_usuario ON evento(usuario_id);
sqlite> EXPLAIN QUERY PLAN SELECT * FROM evento WHERE usuario_id = 42;
`--SEARCH evento USING INDEX idx_usuario (usuario_id=?)

SCAN → SEARCH. E o ganho medido, 200 execuções de cada:

sem índice (usuario_id+0): 10.14 ms
com índice (usuario_id):    0.014 ms
razão: 720x

Prefixo mais à esquerda, verificado com índice em (usuario_id, tipo):

-- filtro com o prefixo: usa
WHERE usuario_id=42 AND tipo='login'
  `--SEARCH evento USING INDEX idx_comp (usuario_id=? AND tipo=?)

-- filtro só pela SEGUNDA coluna: não usa
WHERE tipo='login'
  `--SCAN evento

LIKE com prefixo — e uma descoberta que vale a nota. Eu esperava que LIKE 'log%' usasse o índice, e não usou:

WHERE tipo LIKE 'log%'
  `--SCAN evento          <- surpresa

Investigando: o otimizador reescreve LIKE 'prefixo%' como um intervalo, e para isso a collation do índice precisa casar com a semântica do LIKE. O LIKE do SQLite é case-insensitive para ASCII por padrão, então um índice BINARY não serve. Com a collation certa:

-- índice COLLATE NOCASE:
  `--SEARCH evento USING INDEX idx_tipo_nc (tipo>? AND tipo<?)
-- ou com PRAGMA case_sensitive_like=ON e índice BINARY:
  `--SEARCH evento USING INDEX idx_tipo (tipo>? AND tipo<?)

Repare no plano: tipo>? AND tipo<? — é literalmente o intervalo em que o LIKE foi reescrito. A regra geral vale (prefixo fixo é intervalo indexável; curinga à esquerda não), e a lição extra é que collation faz parte de se o índice serve. Em Postgres o equivalente é text_pattern_ops para bancos com locale não-C.

LIKE '%gin' continua SCAN em qualquer configuração — como esperado.

Em Go

Ver o plano do Go é uma linha, e vale ter num teste:

rows, _ := db.QueryContext(ctx, "EXPLAIN (ANALYZE, BUFFERS) SELECT ...")  // Postgres

Onde o Go apaga o índice sem você notar — os dois casos mais comuns:

1. filtro construído com função na coluna, pelo mesmo motivo de sempre. Se você normaliza em Go (strings.ToLower) e no SQL (lower(email)), só o segundo mata o índice. Normalize na escrita e compare direto na leitura.
2. sql.NullString levando a OR col IS NULL em query dinâmica — o OR frequentemente impede o uso do índice. Duas queries são melhores que um OR que não indexa.

Pool de conexões é a configuração de banco que mais impacta latência em Go, e o default é ruim para produção:

db.SetMaxOpenConns(25)                  // default: ILIMITADO — pode derrubar o banco
db.SetMaxIdleConns(25)                  // default: 2 — reabre conexão a toda hora
db.SetConnMaxLifetime(5 * time.Minute)  // recicla: essencial atrás de load balancer
db.SetConnMaxIdleTime(1 * time.Minute)

MaxOpenConns ilimitado por padrão significa que um pico de tráfego abre conexões até o banco recusar. E MaxIdleConns de 2 faz a aplicação reabrir conexão constantemente, o que com TLS custa handshake (3. TLS).

Sempre QueryContext com prazo, nunca Query: sem contexto, uma query lenta segura a conexão indefinidamente e o pool esgota.

Respostas às perguntas-guia

1. Por que um índice B-tree torna busca O(log n) — e por que ele não ajuda em LIKE '%x'?

Porque cada nível descarta a maior parte do espaço. Não ajuda com curinga à esquerda porque a ordenação é pelo início da chave — não existe ordem por sufixo.

2. Que custo o índice cobra em escrita e espaço?

Cada escrita atualiza cada índice afetado; cada índice ocupa espaço próprio. Índice não usado é custo puro.

Em Go: o sintoma é carga em lote lenta. O padrão é dropar índices, carregar, recriar.

3. O que é índice composto e por que a ordem das colunas importa?

Índice em várias colunas, ordenado lexicograficamente. A ordem importa porque só o prefixo mais à esquerda é utilizável. Verificado: (usuario_id, tipo) serve para usuario_id, e não serve para tipo sozinho.

4. Como ler um EXPLAIN e ver que o índice foi ignorado — e por quê?

Procure SCAN / Seq Scan onde esperava SEARCH / Index Scan. As causas, em ordem de frequência:

1. função ou expressão na coluna — verificado: 720× mais lento
2. filtro só pela segunda coluna de um índice composto
3. curinga à esquerda no LIKE, ou collation incompatível (a descoberta acima)
4. o banco julgou que a varredura é mais barata (seletividade baixa — e ele costuma estar certo)
5. estatísticas desatualizadas: rode ANALYZE

Trade-offs

Do conceito:

• Índice compra leitura O(log n) e cobra escrita, espaço e manutenção.
• Índice composto cobre mais consultas com uma estrutura e só pelo prefixo.
• Índice coberto elimina o acesso à tabela e engorda o índice.
• Muitos índices tornam a escrita lenta sem tornar a leitura rápida — só os usados valem.

Em Go:

• Normalizar na escrita compra índice utilizável na leitura e cobra disciplina no cadastro.
• Pool bem configurado compra latência estável; o default cobra em produção.
• EXPLAIN num teste de integração compra detecção de regressão de plano.

Comandos e consultas essenciais

-- ver o plano (o comando é diferente por banco)
EXPLAIN QUERY PLAN SELECT ...;              -- SQLite
EXPLAIN (ANALYZE, BUFFERS) SELECT ...;      -- Postgres: com tempo REAL
EXPLAIN ANALYZE SELECT ...;                 -- MySQL 8+

-- composto: a ordem é a decisão
CREATE INDEX idx ON evento(usuario_id, tipo);       -- serve p/ usuario_id, e p/ os dois
CREATE INDEX idx ON evento(tipo, usuario_id);       -- serve p/ tipo, e p/ os dois

-- índice de expressão: quando a função é inevitável
CREATE INDEX idx_email_lower ON cliente (lower(email));

-- parcial: menor e mais rápido (Postgres)
CREATE INDEX idx_pendentes ON pedido(criado_em) WHERE status = 'pendente';

-- coberto: responde sem tocar na tabela (Postgres)
CREATE INDEX idx_cob ON pedido(cliente_id) INCLUDE (total, status);

-- estatísticas
ANALYZE evento;

-- índices NUNCA usados (Postgres): candidatos a remoção
SELECT relname, indexrelname, idx_scan FROM pg_stat_user_indexes
WHERE idx_scan = 0 ORDER BY relname;

Relacionado

• 2. Árvore de Busca Binária — semana 3, a mesma ideia em memória
• 1. Busca Binária — semana 4, o descarte pela metade
• 7. Problema N+1 — índice bom não salva de N+1
• 2. Agregações — GROUP BY sobre coluna indexada evita ordenação

---

Parte de Semana 09 - Banco de Dados e SQL · 00 - MOC Fundamentos de Programação