Início / dba / Perguntas / 38717
Accepted
Juan Carlos Coto
Asked: 2013-03-28 12:26:31 +0800 CST

Qual é a complexidade algorítmica de um PosgtreSQL maior ou menor que a consulta de índice (em comparação com a igualdade)?

  • 772

Supondo que haja um índice idx_intem uma int_colcoluna, qual é a complexidade algorítmica de uma consulta como essa?

SELECT id FROM table
    WHERE table.int_col > 1;

Estou especificamente interessado em saber se a consulta é significativamente mais ineficiente do que se fizer uma cláusula de igualdade (que, se bem entendi, é O(log N)). Tenho certeza de que ambos podem usar uma árvore B, então espero que eles sejam quase os mesmos em termos de complexidade / eficiência.

Muito obrigado!

postgresql index

1 respostas

  1. Best Answer

    Não conheço o mecanismo PostgreSQL, porém no mundo real, fazer

    WHERE X > y

    fará com que o mecanismo procure o ponto no índice da árvore B em que X = y, em seguida, verifique o restante dos dados para retornar as linhas relevantes. Com dados suficientes, levará um tempo significativo para retornar.

    Claramente, WHERE X = yretornará mais rapidamente, pois só precisa retornar uma única linha, necessitando apenas da operação de busca inicial.

    Isso, é claro, assumindo que Xestá indexado.

    • 1

relate perguntas