Dipende da cosa intendi per "ricerca" e dalla selettività degli indici (ad esempio per mysql se è inferiore al 20% spesso scansiona tutte le righe).
Se hai, poniamo, 1.000.000 di persone diciamo 500.000 maschi e 500.000 femmine, e vuoi contare quante sono le femmine, allora l'interrogazione sarà comunque lenta, perchè non hai un indice che ti possa aiutare.
Se del milione vuoi cercare chi si chiama luigi allora sarà veloce, perchè potrai fare un ='luigi'.