Rendimiento MySQL

Yo creo que el tema está en el punto 2... comprueba la configuración de mysql... memoria consumida, si cacheas en temporales o accedes directamente... y por último intenta optimizar las consultas que igual rascas tiempo ahí.
Por descartar activa el Slow Query Log en la config de mysql para ver si hay consultas lentas que te frenan el rendimiento:

#Donde va el log
log-slow-queries=/var/log/mysql-slow-queries.log

#Tiempo de consulta en Segundos
long_query_time = 5

o si no desde consola tira un "show processlist" y ves el rendimiento de las consultas cuando se estén ejecutando.

También depende del motor que uses puedes mejorar el rendimiento en función de las consultas que realices...

#3 Si sólo ha cambiado eso y no el número de registros... y si así fuera tienes controlado el auto_increment para que mantenga esa regla, no debería haber problema. Al final la estructura es igual y el índice de la tabla sigue siendo el mismo campo.

Mi especialidad no son las bases de datos, pero que no te quepa la menor duda de que el punto 3 ha influido. No sé exactamente cuánto habrá influido, si mucho o poco (es posible que poco), pero estoy totalmente seguro de que con ese cambio el rendimiento va a ser peor.

Bueno, el punto 3 en sí no, sino el usar BIGINT en vez de INT. Al ser un tipo de dato más grande, los índices van a aumentar su tamaño, lo que va a hacer que usarlos sea más lento.

El hecho de haber cambiado los valores de las claves primarias a la vez que cambiar su tamaño también puede haber tenido un impacto negativo. Lo mismo ahora esta tabla está peor distribuida físicamente en el disco. No sé, es una suposición, como ya te digo, no soy ningún experto, pero quizá podrías intentar usar alguna de las órdenes de MySQL para optimizar la tabla (OPTIMIZE, creo que era).

De todas formas, ¿seguro que necesitas usar un BIGINT en vez de un INT? Date cuenta de que con un UNSIGNED INT puedes llegar a almacenar hasta 4.300 millones de valores distintos. Bueno, en tu caso, ya que añades un 10 al principio de cada número, 100 millones (los dos primeros dígitos siempre van a ser 1 y 0, por lo que el mayor ID en tu caso es 1.099.999.999).

¡Un saludo!

#9 el valor máximo de INT (unsigned) es 4294967295. ¿Realmente necesitas almacenar más de cuatro mil millones de registros?

#11 es que antes de pensar en el espacio que necesitarás en un futuro debéis arreglar la chapuza que habéis hecho. No hay por donde cogerlo xD

#15 con mis comienzos limitados de bbdd, imagino que si no creas un índice no mejará nada. En principio sólo sirve para mantener la integridad relacional, tendrías que crear un índice.

No creo que tenga que ver el BIGINT vs INT, yo tengo tablas con 7kk de registros en mysql con bigint de identificador, consultas mas o menos normalillas con 1 group by, average, etc.. y va como un tiro.

Cómo tienes estos parametros ?

innodb_buffer_pool_size
join_buffer_size
sort_buffer_size
read_rnd_buffer_size

Haz un:
explain select ....... ;

de tu consulta.

#16 Yo diria que se crean solos para las FK