什么是SQL select的Big-O? [英] What is the Big-O for SQL select?

问题描述

对于具有n行的表并且要为其返回m结果的表，SQL选择的Big-O是什么?

What is the Big-O for SQL select, for a table with n rows and for which I want to return m result?

Update或delete或Create操作的最大操作是什么?

And What is the Big-O for an Update, or delete, or Create operation?

我一般来说是在谈论mysql和sqlite.

I am talking about mysql and sqlite in general.

推荐答案

由于您无法控制所选的算法，因此无法直接知道.但是，没有索引的SELECT应该为O(n)(表扫描必须检查每条记录，这意味着它会随着表的大小而缩放).

As you don't control the algorithm selected, there is no way to know directly. However, without indexes a SELECT should be O(n) (a table scan has to inspect every record which means it will scale with the size of the table).

使用索引时，SELECT可能为O(log(n))(如果它适用于任何实表，则它取决于用于索引的算法以及数据本身的属性).要确定任何表或查询的结果，您必须求助于对真实世界数据进行概要分析.

With an index a SELECT is probably O(log(n)) (although it would depend on the algorithm used for indexing and the properties of the data itself if that holds true for any real table). To determine your results for any table or query you have to resort to profiling real world data to be sure.

不带索引的INSERT应该非常快(接近O(1))，而UPDATE需要首先找到记录，因此比(使您到达)SELECT的速度(稍慢).

INSERT without indexes should be very quick (close to O(1)) while UPDATE needs to find the records first and so will be slower (slightly) than the SELECT that gets you there.

当索引树需要重新平衡时，带有索引的INSERT可能会再次处于O(log(n ^ 2))的范围之内，否则将更接近O(log(n)).如果它影响SELECT成本之上的索引行，则UPDATE也会发生相同的速度减慢.

INSERT with indexes will probably again be in the ballpark of O(log(n^2)) when the index tree needs to be rebalanced, closer to O(log(n)) otherwise. The same slowdown will occur with an UPDATE if it affects indexed rows, on top of the SELECT costs.

一旦您谈论混合中的JOIN，所有赌注都关闭了:您将必须分析并使用数据库查询估计工具来读取它.还要注意，如果此查询对性能至关重要，则应不时 re 配置文件，因为查询优化器使用的算法会随着数据负载的变化而变化.

All bets are off once you are talking about JOIN in the mix: you will have to profile and use your databases query estimation tools to get a read on it. Also note that if this query is performance critical you should reprofile from time to time as the algorithms used by your query optimizer will change as the data load changes.

要记住的另一件事... big-O不会告诉您每笔交易的固定成本.对于较小的桌子，这些费用可能会高于实际工作成本.举个例子:单行跨网络查询的设置，删除和通信成本肯定会比在一张小表中查找索引记录还要多.

Another thing to keep in mind... big-O doesn't tell you about fixed costs for each transaction. For smaller tables these are probably higher than the actual work costs. As an example: the setup, tear down and communication costs of a cross network query for a single row will surely be more than the lookup of an indexed record in a small table.

因此，我发现能够将一组相关查询捆绑在一起成批处理，对性能的影响要比我对数据库所做的任何优化都大得多.

Because of this I found that being able to bundle a group of related queries in one batch can have vastly more impact on performance than any optimization I did to the database proper.

这篇关于什么是SQL select的Big-O?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！