Tenho um banco de dados com mais de 250 tabelas, existem tabelas com mais de milhões de registros e quando preciso procurar ou alterar algum desses registros, leva bastante tempo, o que acaba deixando a experiência bem ruim para o usuário.

A tabela Clientes tem mais de 50 milhões de registros. Essa tabela fica em produção 24 horas por dia, numa média de 200 *queries*/min em certas horas do dia. Sempre que preciso procurar um cliente, existe uma forma mais rápida, que é procurando pela chave primária da tabela, mas nem sempre tenho a possibilidade de saber o ID de um cliente de cor. Nesses casos, utilizo uma busca parcial pelo nome (usando o operador [`LIKE`][1]), ou seja, procurando por `Dar`, ele me retorna:

    Darth Vader
    Darcisio Araujo
    Darlene Silva
    [...]

Claro, além de só o nome, existem mais filtros que possam ser aplicados na mesma *query*.  Das duas formas apresentadas, procurar pelo Nome acaba demorando bastante em certos casos. 

**EDIT**: em minhas *queries*, costumo filtrar colunas do tipo `varchar(n)` e `bit`. Faço também intervalos entre datas com colunas do tipo `date` usando operador `BETWEEN`.

-----

 - O que fazer para otimizar a velocidade das consultas?
 - O que costuma deixar as consultas lentas? (além de ter milhões de registros na tabela, acredito que existam más práticas que deixam-as ainda menos performáticas)

  [1]: http://www.w3schools.com/sql/sql_like.asp