Paginar miles de registros

[tumbero_x]

Hola Amigos!!!
estoy intentando sin exito paginar miles de registros mysql con php ,perdon mi problema no es la paginacion si no, el tiempo en que tarda en devolverme los datos , en 2000 registros andaba bien pero ahora le agregue mas de 100.000 registros y se puso realmente muy pesada la consulta cuando pagino.
hay alguna manera de que me traiga los datos sin que tarde tanto (15 segundos) este es mi codigo

Código PHP:

$sql = mysql_query("select * from compras C LEFT OUTER JOIN proveedores P ON C.compra_cod_prov = P.proveedor_id
                                          LEFT OUTER JOIN monedas M ON C.compra_moneda = M.mone_id", Conectar::con());
    $res = mysql_num_rows($sql);
    $registros = 1;
    $pagina = isset($_GET['num']) ? $_GET['num'] : '';
    if ($pagina) {
        $inicio = (($pagina - 1) * $registros);
    } else {
        $inicio = 0;
    }
    $sql = mysql_query("select * from compras C  LEFT OUTER JOIN proveedores P ON C.compra_cod_prov = P.proveedor_id
                                           LEFT OUTER JOIN monedas M ON C.compra_moneda = M.mone_id
                                 LIMIT $inicio,$registros ", Conectar::con());
    $paginas = ceil($res / $registros);