Velocizzare Query MySql

ad esempio ho una tabella che contiene i seguenti campi:
Nome
Cognome
Importo speso

ora voglio sapere la media di quanto hanno speso tutte le persone che hanno un nome che inizia con Mar, quindi mario,marcello,marco ecc...

spero di essermi spiegato. quindi usano il like fa la scansione di tutta la tabella, e questo richiede molto tempo visto che sono molte righe, qualche suggerimento?

ovviamente ho fatto un esempio per l'iniziale mar, può essere anche in mezzo tipo tutti quelli che contiene uc, quindi luca e così via

Intendevo un esempio reale, non un'astrazione.
In altre parole, se non è un segreto di stato, puoi farci avere almeno un'idea di che cosa contenga questa tabella? Perché 60 milioni di record non sono una cosa comune.

scusami, so che stai cercando di aiutarmi, ma a me in realtà servirebbe sapere solo come posso cercare parzialmente del testo usando gli indici in modo tale da essere più veloce la ricerca.

... ma perchè non posti la struttura delle tabelle interessate ?