Quel est le Big-O pour SQL sélectionner, pour une table avec n lignes et pour lequel je veux retourner le résultat m?Qu'est-ce que le Big-O pour SQL sélectionner?
Et quel est le Big-O pour une opération Update ou delete ou Create? Je parle de mysql et de sqlite en général. Je parle de mysql et de sqlite en général.
Comme vous ne contrôlez pas l'algorithme sélectionné, il n'y a aucun moyen de le savoir directement. Cependant, sans index, un SELECT doit être O (n) (un balayage de table doit inspecter chaque enregistrement, ce qui signifie qu'il sera mis à l'échelle avec la taille de la table). Avec un index, un SELECT est probablement O (log (n)) (bien que cela dépende de l'algorithme utilisé pour l'indexation et des propriétés des données elles-mêmes si cela est vrai pour toute table réelle). Pour déterminer vos résultats pour n'importe quelle table ou requête, vous devez utiliser le profilage de données réelles pour être sûr. INSERT sans index doit être très rapide (proche de O (1)) alors que UPDATE doit d'abord trouver les enregistrements et sera donc plus lent (légèrement) que le SELECT qui vous y amène.
INSERT avec des index sera probablement à nouveau dans l'approximation de O (log (n^2)) lorsque l'arbre d'index doit être rééquilibré, plus proche de O (log (n)) sinon. Le même ralentissement se produira avec un UPDATE s'il affecte les lignes indexées, en plus des coûts SELECT.
Tous les paris sont désactivés lorsque vous parlez de JOIN dans le mix: vous devrez profiler et utiliser les outils d'estimation de requêtes de vos bases de données pour les lire. Notez également que si cette requête est critique pour les performances, vous devriez de temps en temps re profil car les algorithmes utilisés par votre optimiseur de requête changeront au fur et à mesure que la charge de données change. Autre chose à garder à l'esprit ... big-O ne vous parle pas des coûts fixes pour chaque transaction. Pour les petits tableaux, ils sont probablement plus élevés que les coûts de travail réels. A titre d'exemple: les coûts d'installation, de démontage et de communication d'une requête de réseau croisé pour une seule ligne seront certainement supérieurs à la recherche d'un enregistrement indexé dans une petite table. Pour cette raison, j'ai trouvé qu'être capable de regrouper un groupe de requêtes liées dans un lot peut avoir beaucoup plus d'impact sur les performances que toute optimisation que j'ai faite à la base de données proprement dite.
En ligne avec le commentaire de l'ordre d'un select avec une jointure, gardez à l'esprit qu'un select avec une double jointure à une table peut être n^2. Par exemple; select * from table où id> (select avg (id) from table) augmente probablement par carré, sans utiliser d'index. –
Je pense que la vraie réponse ne peut être déterminée qu'au cas par cas (moteur de base de données, conception de table, indices, etc.). Toutefois, si vous êtes un utilisateur MS SQL Server, vous pouvez vous familiariser avec le plan d'exécution estimé dans Query Analyzer (2000) ou Management Studio (2005+). Cela vous donne beaucoup d'informations que vous pouvez utiliser pour l'analyse.
Tout dépend de comment (bien) vous écrivez votre SQL et comment votre base de données est conçue pour l'opération que vous effectuez. Essayez d'utiliser la fonction expliquez plan pour voir comment les choses seront exécutées par le db. Le. Vous pouvez calculer le big-O
en double: http://stackoverflow.com/questions/727719/database-query-time-complexity –