Los primary normalmente estan indexados, los indices se ponen en campos de mucho uso, por ejemplo si tiene una tabla donde hace querys que regularmente hace un where como este:
Código SQL
[-]
... where fecha between :f1 an :f2
Entonces yo pondría un indice al campo fecha, este indice se puede crear o poner en cualquier momento, osea si la tabla ya tiene un millón de registros no la va afectar. He visto querys que se demoran hasta 20 minutos y al ponerle un indice bien ubicado pasa a demorarse pocos segundos. una tabla puede tener muchos Indices, pueden ser compuestos... pueden ser únicos o no... en los joins es muy recomendable que los campos que relaciones dichos joins estén indexados.