Otimizar instrução SQL.

Pessoal, to com um pepinão e não sei como resolver, preciso da ajuda de vcs...

Tenho que montar um sistema onde eu tenha um cadastro de clientes, um cadastro de produtos e um cadastro de praças.

Depois permitir uma busca por nome do produto ou parte dele e filtro por cidade e estado onde este cliente atua.

O problema é que já tentei de varias formas e todos ficam lentos, vejam o problema

Opção que eu fiz

Tabela Cliente

-> Cliente | CNPJ | E-mail | Senha

Tabela Produtos (Esta tabela contem uns 500 produtos)

-> Produto | Descrição | Imagem

Tabela Praças (Esta tabela contem todas as cidades do pais, mais de 9 mil se nao me engano)

-> Estado | Praça

Então, penso que preciso de uma tabela para relacionar tudo isso, ou melhor, duas...

Tabela Cliente X Produtos

-> Cod Cliente | Cod Produto

e

Tabela Cliente X Praças

-> Cod Cliente | Cod Praça

Então, criei este sql maluco aqui, porem ele fica extremamente lento, pois cada cliente que atua no brasil todo, a tabela Cliente X Praças cresce 9 mil linhas, ou seja, ela tem milhoes de linhas ja, como resolver isso?

$sqlBusca = "SELECT * FROM tb_distribuidores INNER JOIN (SELECT cd_cliente FROM (SELECT cd_cliente,cd_produto FROM tb_distribuidores_produtos WHERE cd_cliente IN (SELECT cd_cliente FROM tb_distribuidores_pracas WHERE ((tb_distribuidores_pracas.cd_cidade = '$cidade' AND tb_distribuidores_pracas.cd_estado = '$estado') OR (tb_distribuidores_pracas.cd_cidade = '-1' AND tb_distribuidores_pracas.cd_estado = '$estado')) ORDER BY cd_cliente ASC) AND cd_tipo='$tipo') AS tabela INNER JOIN tb_produtos ON cd_produto = id WHERE ds_produto LIKE '%$pesquisa%' GROUP BY cd_cliente) AS tab1 ON tab1.cd_cliente = tb_distribuidores.id ORDER BY cliente ASC";

Alguem pode me ajudar a melhorar?