¿Cuál es el Big-O para la selección de SQL, para una tabla con filas n y para el que deseo devolver el resultado m?¿Qué es Big-O para SQL select?
Y ¿Cuál es el Big-O para una operación Update, o delete, o Create?
Estoy hablando de mysql y sqlite en general.
Como no se controla el algoritmo seleccionado, no hay forma de saberlo directamente. Sin embargo, sin índices, un SELECT debería ser O (n) (un escaneo de tabla tiene que inspeccionar cada registro, lo que significa que se escalará con el tamaño de la tabla).
Con un índice, SELECCIONAR es probablemente O (log (n)) (aunque dependería del algoritmo utilizado para la indexación y las propiedades de los datos si eso se cumple para cualquier tabla real). Para determinar los resultados de cualquier tabla o consulta, debe recurrir a la creación de perfiles de datos del mundo real para estar seguro.
INSERTAR sin índices debe ser muy rápido (cerca de O (1)) mientras que ACTUALIZAR necesita encontrar los registros primero y por lo tanto será más lento (ligeramente) que el SELECCIONAR que lo lleva allí.
INSERT con índices probablemente volverá a estar en el parque de O (log (n^2)) cuando el árbol de índice deba reequilibrarse, más cerca de O (log (n)) en caso contrario. La misma ralentización ocurrirá con una ACTUALIZACIÓN si afecta a las filas indexadas, además de los costos SELECCIONAR.
Todas las apuestas están apagadas una vez que hable de JOIN en la mezcla: tendrá que crear un perfil y utilizar las herramientas de estimación de consultas de sus bases de datos para leerlas. También tenga en cuenta que si esta consulta es crítica para el rendimiento, deberá re perfilarse de vez en cuando ya que los algoritmos utilizados por su optimizador de consultas cambiarán a medida que cambie la carga de datos.
Otra cosa a tener en cuenta ... big-O no le informa sobre los costos fijos de cada transacción. Para tablas más pequeñas, estos son probablemente más altos que los costos de trabajo reales. Como ejemplo: la configuración, el desmontaje y los costos de comunicación de una consulta de red cruzada para una sola fila seguramente serán más que la búsqueda de un registro indexado en una tabla pequeña.
Debido a esto encontré que ser capaz de agrupar un grupo de consultas relacionadas en un lote puede tener un impacto mucho mayor en el rendimiento que cualquier optimización que hice a la base de datos propiamente dicha.
En línea con el comentario del orden de un seleccionar con una combinación, tenga en cuenta que una selección con una unión doble a una tabla puede ser n^2. Por ejemplo; select * from table where id> (seleccione avg (id) de la tabla) probablemente crezca cuadrado por registro, sin usar índices. –
Creo que la respuesta real solo puede determinarse caso por caso (motor de base de datos, diseño de tabla, índices, etc.).
Sin embargo, si usted es un usuario de MS SQL Server, puede familiarizarse con el plan de ejecución estimada en Query Analyzer (2000) o Management Studio (2005+). Eso le da mucha información que puede usar para el análisis.
Todo depende de cómo (bien) escriba su SQL y qué tan bien está diseñada su base de datos para la operación que está realizando. Intenta usar la función explicar plan para ver cómo el db ejecutará las cosas. Los. Puede calcular el gran O
duplicado: http://stackoverflow.com/questions/727719/database-query-time-complexity –