Complexidade em dados e I/O

Onde a unidade de custo deixa de ser a operação e passa a ser o acesso — banco, disco e rede, com medição.

Toda a análise das outras páginas conta operações, e supõe que todas custam igual. Quando o dado sai da memória, essa suposição quebra: um acesso a disco vale cem mil operações, e uma ida à rede vale dez milhões.

A conta muda de unidade. O que se conta aqui não é instrução — é ida e volta.

O N+1: o O(n) que ninguém vê#

Buscar uma lista e depois, para cada item, buscar o relacionado. O código parece linear e é linear — em consultas, que é a unidade cara:

// N+1: uma consulta pela lista, e mais uma por cliente
soma := 0.0
cycle c in DB.select(db, "clientes"):
    linhas := DB.query(db, "SELECT total FROM pedidos WHERE cliente_id = ?", [c["id"]])
    cycle l in linhas:
        soma += l["total"]

// uma consulta so: o banco agrupa, e volta uma vez
soma := 0.0
cycle l in DB.query(db, "SELECT cliente_id, SUM(total) AS t FROM pedidos GROUP BY cliente_id", []):
    soma += l["t"]

N+1 (501 consultas): 6.5 ms
uma consulta:        1.0 ms
razao: 6.4x

6,4x com o banco na mesma memória do processo, onde uma consulta é barata. Com o banco em outra máquina, cada uma das 501 paga uma ida à rede, e a mesma diferença vira centenas de vezes.

É o problema de desempenho mais comum em sistema com banco, e ele não aparece em teste: com dez linhas de exemplo, as 11 consultas são instantâneas.

Índice: de O(n) para O(log n), medido#

Sem índice, o banco lê a tabela inteira a cada consulta. Com índice, ele desce uma árvore. O explain mostra a diferença antes de você medir:

adopt Arcane.Database as DB
adopt Arcane.Time as T

db := DB.memory()
DB.create_table(db, "pedidos", {"id": "INTEGER PRIMARY KEY", "cliente": "TEXT", "total": "REAL"})
DB.insert_many(db, "pedidos",
    [{"cliente": $"c{i % 500}", "total": i * 1.0} cycle i in range(0, 20000)])

inicio := T.monotonic()
cycle k from 1 to 200:
    DB.query(db, "SELECT * FROM pedidos WHERE cliente = ?", [$"c{k}"])
sem_indice := (T.monotonic() - inicio) * 1000

DB.create_index(db, "pedidos", ["cliente"])

inicio := T.monotonic()
cycle k from 1 to 200:
    DB.query(db, "SELECT * FROM pedidos WHERE cliente = ?", [$"c{k}"])
com_indice := (T.monotonic() - inicio) * 1000

out $"sem indice: {round(sem_indice, 1)} ms"
out $"com indice: {round(com_indice, 1)} ms"
out $"razao: {round(sem_indice / com_indice, 1)}x"
out DB.explain(db, "SELECT * FROM pedidos WHERE cliente = ?", ["c1"])

sem indice: 73.6 ms
com indice: 4.4 ms
razao: 16.6x
{passos: [SEARCH pedidos USING INDEX idx_pedidos_cliente (cliente=?)], varre_tabela: no, aviso: }

Antes do índice, o mesmo explain responde varre_tabela: yes e o aviso le a tabela inteira: SCAN pedidos. Esse campo é o que vale procurar num CI: uma consulta que varre a tabela inteira é aceitável com mil linhas e derruba o sistema com um milhão.

O que um índice custa#

Ele não é grátis, e por isso não se indexa tudo:

Indexe o que aparece em WHERE, JOIN e ORDER BY de consulta frequente. Uma tabela de escrita pesada com seis índices paga seis árvores a cada linha inserida.

Paginar por deslocamento é quadrático#

LIMIT 20 OFFSET 100000 parece constante e não é: o banco produz e descarta as cem mil primeiras linhas para chegar na página. Percorrer todas as páginas assim é O(n^2).

// O(offset) por pagina — a ultima pagina e a mais cara
DB.query(db, "SELECT * FROM pedidos ORDER BY id LIMIT 20 OFFSET 100000", [])

// O(log n) por pagina: continua de onde parou
DB.query(db, "SELECT * FROM pedidos WHERE id > ? ORDER BY id LIMIT 20", [ultimo_id])

A segunda forma — paginação por cursor — exige um campo ordenado e único, e em troca cada página custa o mesmo. DB.paginate faz a primeira; para listas grandes e rolagem infinita, escreva a segunda.

Ler arquivo: o custo é o bloco#

Disco não entrega byte, entrega bloco. Ler um arquivo de n bytes em blocos de B custa O(n/B) acessos — e é por isso que ler de mil em mil linhas ganha de ler de uma em uma, com a mesma classe assintótica.

// carrega o arquivo inteiro na memoria: O(n) de espaco
linhas := IO.read_lines("grande.csv")

// um item por vez: O(1) de espaco, e o mesmo O(n) de tempo
stream action registros(caminho):
    cycle linha in IO.read_lines(caminho):
        emit split(linha, ",")

A segunda forma processa arquivo maior que a memória quando a fonte é preguiçosa. Ver complexidade de espaço e generators.

A lista de conferência#

• Conte as idas ao banco, não as linhas de código. Um laço com uma consulta dentro é um N+1 até prova em contrário.
• Rode `DB.explain` nas consultas quentes e procure varre_tabela: yes.
• `DB.watch_slow` e `DB.slow_log` registram o que passou do prazo, em produção.
• Agregue no banco (SUM, GROUP BY, DB.aggregate): trazer mil linhas para somar em memória paga transporte por nada.
• Use transação para escrita em lote. Sem ela, cada insert confirma sozinho, e o custo é por linha.
• Pagine por cursor quando a lista for grande.

Por onde seguir#