Oi,
Preocupe-se também com o tipo de pesquisa que você está fazendo. É parcial ou exata? Se for parcial e você estiver procurando em qualquer parte do texto (%bla%), o desempenho deve cair muito. Talvez, se for aplicável, você pode também fazer apenas buscas exatas, ou, pelo menos, pelo começo do nome, ou ainda, deixar que o usuário decida o que quer pesquisar e pague o preço (em desempenho) da busca desejada.
Outra coisa, eu já vi gente montando os objetos inteiramente ao realizar uma busca. Acreditem, isso acontece! Ou seja, o Cliente tem um Contrato que tem um Serviço Contratado e blá, blá, blá. Aí, na busca por clientes, o contrato de cada cliente era buscado e o serviço de cada contrato também e mais trezentos quilos de blá, blá, blá. Caras, que horror. Isso tudo sem nada de lazy reference, ou qualquer outro cuidado. Não tem índice, nem mágica que resolva. É claro que isso foi um caso absurdo e extremo, mas é sempre bom dar uma verificada no código pra ver se não há nada sendo executado desnecessáriamente (principalmente quando falamos em 2M pessoas). Um ifzinho bobo que seja, ou até mesmo uma concatenação de Strings com + poderia ser executado 2M x e liberar uma boa quantidade de décimos de segundos se retirado.
Um abraço.