Quali indici utilizzi? Come è strutturata la query di selezione?

io non sto ottimizzando per un solo server, io voglio fare un programma che posso usare ed installare dove voglio, senza limiti e senza sapere a quanta gente serve
Le note fatte in merito ad indici, ottimizzazione di query (etc) rimangono comunque valide. Anzi, per certi versi, l'ottimizzazione dovrebbe essere spinta ancor di più se non vuoi avere un sistema che si siede a causa di un carico eccessivo del server (tipico su sistemi shared e vps).

ammesso che esista programmazione multicore in php o mysql (sarei proprio curioso di istruirmi, non conosco questa realtà, se esiste, sono sempre contento di conoscere qualcosa di nuovo) se la seconda query dipende dalla prima dubito che io possa mandarle in elaborazione in parallelo...
La "programmazione multicore" non esiste ne in PHP, ne in MySQL. Esiste il multi-threading ed il multi-process implementato dal server web e da MySQL. La tua nota "se la seconda query dipende dalla prima" è valida solo se il sistema è mono utente. Non appena si hanno più utenti concorrenti, un'applicazione che può essere eseguita in maniera "non-atomica", senza dover impiegare tutte le risorse della CPU (core) in modo sequenziale potrà essere gestita in modo più ottimale dal processore e dal software.

da quello che avete scritto chi produce antivirus, editor di testo, partizionatori, fogli di calcolo o che altro lo dovrebbe fare solo per un determinato pc
Da quello che hai scritto non sembra tu comprenda fino in fondo la differenza tra un editor di testo ed un database che deve gestire 200.000.000 di record. Ne della differenza che consiste tra "ottimizzare un indice ed una query" e compilare un'applicazione per una CPU target specifica.

Certo, tutto si può ottimizzare al meglio, ma se seguo il vostro discorso prima di scrivere il programma devo fare delle audizioni a tutti i futuri utenti del mio sito
Sai che cosa significa "ottimizzare una query" o "creare degli indici"?

Per fare questo NON è necessario fare alcuna audizione. E' sufficiente studiare la query che vuoi eseguire, individuare i campi utilizzati, creare i relativi indici, eventualmente utilizzare EXPLAIN, ristrutturare la tabella in modo da sfruttare al massimo gli indici creati, eventualmente creare delle tabelle d'appoggio per migliorare le ricerca su chiavi specifiche (es. quelle piu' utilizzate). Tutto questo non richiede di conoscere ne cosa faranno gli utenti, ne su quale piattaforma andrai a fare il deploy dell'applicazione.

Prima di iniziare a parlare di "velocità", studiati le basi di creazione di database, indici ed ottimizzazioni comprese.