Procedimientos almacenados

[CésarBalaguer]

Si hablas de millones de registros los SP son muy recomendables, sin embargo de nada servirían si tu query no esta bien estructurado, te recomiendo en primer lugar asegurarte de la existencia de indices en las tablas a las que vas a hacer los query, en segundo lugar, asegurarte que los JOIN que hagas entre tablas sea de la forma adecuada; para un motor de base de datos no es lo mismo hacer un join entre A y B que entre B y A, las estadísticas y los índices trabajan diferente en ambos casos.
Para su ejecución lo que Myakire te indica es correcto, es tan simple como llamarlo y listo.