MySQL - Complessità di:SELECT COUNT(*) FROM MyTable;

Dipende dal motore di archiviazione.

• Per MyISAM il conteggio totale delle righe viene memorizzato per ogni tabella, quindi SELECT COUNT(*) FROM yourtable è un'operazione O(1). Ha solo bisogno di leggere questo valore.
• Per InnoDB il conteggio totale delle righe non viene memorizzato, quindi è necessaria una scansione completa. Questa è un'operazione O(n).

Dal manuale :