La Complexité de fonctions intégrées SQL telles que somme, compte, avg

Question

Quelle est la complexité temporelle d'une fonction telle que le nombre, somme, moyenne ou tout autre construit dans -functions « mathématiques » dans MySQL, SQL Server, Oracle et d'autres?

On pourrait penser que l'appel somme (mycolumn) serait linéaire.

Mais le nombre (1) n'est pas. Comment venir et quels sont les temps réel complexité?

Dans un monde parfait, je veux sum, avg et compte être O (1). Mais nous ne vivons pas dans un de ces, ne nous?

Answer 1

Dans SQL la complexité de la fonction mathématique des agrégats est totalement irelevant. La seule chose qui compte vraiment est la complexité des données: quel chemin d'accès est choisi (scan de table, balayage de plage d'index, recherche d'index, etc.) et combien de pages sont lues. Il peut y avoir de légères différences dans les entrailles de chaque agrégat, mais ils travaillent tous à peu près de la même façon (garder l'état en cours d'exécution et de calculer en cours d'exécution d'agrégation pour chaque valeur d'entrée) et il est tout à fait NON global qui ressemble à entrée deux fois, de sorte que tous O (n) en tant que mise en oeuvre interne, où « n » est le nombre de Recordes alimentés à l'agrégat (non necesarily le nombre d'enregistrement de la table!).

Certains agrégats ont des raccourcis internes, par exemple. COUNT (*) peut retourner le nombre de métadonnées sur certains systèmes, si possible.

Answer 2

  

Quelle est la complexité temporelle d'une fonction telle que le nombre, somme, moyenne ou tout autre construit dans -functions « mathématiques » dans MySQL, SQL Server, Oracle et d'autres?

• MySQL avec MyISAM, COUNT(*) sans GROUP BY est O(1) (constante)

  Il est stocké dans les métadonnées de table.

• Dans tous les systèmes, et MAX MIN sur les expressions indexées sans GROUP BY sont O(log(n)) (logarithmique).

  Ils sont extraites avec un seul recherche d'index.

• Les fonctions d'agrégat sont O(n) (linéaire), lorsqu'il est utilisé sans GROUP BY ou GROUP BY utilise HASH

• Les fonctions d'agrégation sont O(n log(n)) lorsque GROUP BY utilise SORT.

Toutes les valeurs doivent être extraites, calculées et mémorisées dans des variables d'état (qui peuvent être stockées dans une table de hachage).

En outre, lors de l'utilisation SORT, ils doivent également être triés.

Answer 3

Note:. C'est la spéculation basée sur ma compréhension de la façon dont les planificateurs de requêtes SQL fonctionnent et ne peut pas être tout à fait exact

Je crois que toutes les fonctions d'agrégation, ou tout au moins les « mathématiques » ceux que vous nommez ci-dessus, doit être O (n). La requête sera exécutée à peu près comme suit:

1. extraire des lignes correspondant à la jointure des prédicats et des prédicats de filtre (par exemple "clause WHERE")
2. Créer rangée-groupes en fonction de la clause GROUP BY. Un seul groupe de ligne est créée pour les requêtes sans GROUP BY
3. Pour chaque groupe de lignes, appliquer la fonction d'agrégation aux rangées du groupe. Pour des choses comme des algorithmes SUM, AVG, MIN, MAX ainsi que des fonctions non numériques comme CONCAT il y a O simple (n), et je soupçonne que ceux-ci sont utilisés. Créer une ligne de la sortie prévue pour chaque rangée groupe créé à l'étape # 2
4. Si un prédicat HAVING est présente, filtrer les lignes de sortie en utilisant ce prédicat

Notez, cependant, que même si les fonctions d'agrégation sont O (n), l'opération pourrait ne pas être. Si vous créez une requête qui cartésienne se joint à une table pour lui-même, vous regarderez O (n * n) minimum juste pour créer le jeu de ligne initiale (étape 1). Tri pour créer rangée-groupes (étape 2) peut être O (nlogn), et peut nécessiter le stockage sur disque pour l'opération de tri (par opposition à un fonctionnement en mémoire uniquement), de sorte que votre requête peut encore effectuer mal si vous êtes manipulation de lignes.

Answer 4

Pour les grandes requêtes de style-entrepôt de données, les principales bases de données peuvent paralléliser la tâche, ont donc plusieurs processeurs travaillent. Il y aura donc des points de seuil où il est pas tout à fait linéaire que le coût de la coordination des fils parallèles métiers par rapport au bénéfice de l'utilisation des multiples processeurs.