Se eu entendi sua pergunta, você sabe que o MATCH AGAINST usa seu índice FULLTEXT e você está se perguntando como o MySQL aplica o resto da cláusula WHERE (ou seja, ele faz um tablecan ou uma pesquisa indexada).
Aqui está o que estou assumindo sobre sua tabela:ela tem uma PRIMARY KEY em alguma coluna id e o índice FULLTEXT.
Primeiro, o MySQL nunca use o índice FULLTEXT para a cláusula WHERE cidade/estado. Por quê? Porque os índices FULLTEXT só se aplicam com MATCH AGAINST. Veja aqui no parágrafo após o primeiro conjunto de marcadores (não os marcadores do Índice).
EDITAR: No seu caso, supondo que sua tabela não tenha apenas 10 linhas, o MySQL aplicará o índice FULLTEXT para seu MATCH AGAINST e, em seguida, fará um tablecan nesses resultados para aplicar a cidade/estado WHERE.
E daí se você adicionar um índice BTREE na cidade e no estado?
CREATE INDEX city__state ON table (city(10),state(2)) USING BTREE;
Bem, o MySQL só pode usar um index para esta consulta, pois é uma seleção simples. Será ou use o FULLTEXT ou o BTRE. Observe que quando digo um índice, quero dizer uma definição de índice, não uma coluna em um índice de várias partes. De qualquer forma, isso levanta a questão de qual faz ele usa?
Isso depende da análise da tabela. O MySQL tentará estimar (com base nas estatísticas da tabela da última OPTIMIZE TABLE) qual índice removerá a maioria dos registros. Se a cidade/estado WHERE reduzir para 10 registros enquanto o MATCH AGAINST apenas reduzir para 100, o MySQL usará o índice city__state primeiro para a cidade/estado WHERE e, em seguida, faça um tablecan para o MATCH AGAINST.
Por outro lado, se o MATCH_AGAINST reduzir para 10 registros enquanto a cidade/estado WHERE reduzir para apenas 1000, então o MySQL aplicará o índice FULLTEXT primeiro e as tabelas para cidade e estado.
A linha inferior é a cardinalidade do seu índice. Essencialmente, quão únicos são os valores que irão para o seu índice? Se todos os registros em sua tabela tiverem a cidade definida como Oakland, então não é uma chave muito exclusiva e, portanto, city ='Oakland' realmente não reduz tanto o número de registros para você. Nesse caso, dizemos que seu índice city__state tem uma baixa cardinalidade .
Conseqüentemente, se 90% das palavras em seu índice FULLTEXT são "João", isso também não ajuda muito pelas mesmas razões.
Se você puder arcar com o espaço e a sobrecarga de UPDATE/DELETE/INSERT, eu recomendaria adicionar o índice BTREE e deixar o MySQL decidir qual índice ele deseja usar. Na minha experiência, ele geralmente faz um trabalho muito bom em escolher o caminho certo.
Espero que isso responda sua pergunta.
EDITAR: Em uma nota lateral, certifique-se de escolher o tamanho certo para o seu índice BTREE (no meu exemplo eu escolhi os primeiros 10 caracteres na cidade). Isso obviamente causa um enorme impacto na cardinalidade. Se você escolheu cidade(1), então obviamente você terá uma cardinalidade menor do que se você escolheu cidade(10).
EDIT2: O plano de consulta do MySQL (estimativa) para o qual o índice elimina a maioria dos registros é o que você vê em EXPLAIN.
