sql - SQL 选择的 Big-O 是什么？

Question

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

Update, or delete, orCreate操作的 Big-O 是什么？

我说的是一般的mysql和sqlite。

Answer 1

由于您不控制所选算法，因此无法直接知道。但是，如果没有索引，SE​​LECT 应该是 O(n)（表扫描必须检查每条记录，这意味着它将随着表的大小而缩放）。

使用索引，SE​​LECT 可能是 O(log(n)) （尽管它取决于用于索引的算法和数据本身的属性，如果这适用于任何真实表）。要确定任何表或查询的结果，您必须求助于分析真实世界的数据来确定。

没有索引的 INSERT 应该非常快（接近 O(1)），而 UPDATE 需要首先找到记录，因此会比让你到达那里的 SELECT 慢（稍微）。

当索引树需要重新平衡时，带有索引的 INSERT 可能再次处于 O(log(n^2)) 的范围内，否则更接近 O(log(n))。如果 UPDATE 影响索引行，除了 SELECT 成本之外，它也会出现同样的减速。

一旦您在混合中谈论 JOIN，所有的赌注都将被取消：您将不得不分析并使用您的数据库查询估计工具来阅读它。另请注意，如果此查询对性能至关重要，则应不时重新分析，因为查询优化器使用的算法会随着数据负载的变化而变化。

要记住的另一件事...... big-O 不会告诉您每笔交易的固定成本。对于较小的表，这些可能高于实际工作成本。举个例子：单行跨网络查询的设置、拆卸和通信成本肯定会超过在小表中查找索引记录的成本。

正因为如此，我发现能够在一个批次中捆绑一组相关查询对性能的影响比我对数据库进行的任何优化都大得多。

Answer 2

我认为真正的答案只能根据具体情况（数据库引擎、表设计、索引等）来确定。

但是，如果您是 MS SQL Server 用户，您可以熟悉查询分析器 (2000) 或 Management Studio (2005+) 中的估计执行计划。这为您提供了大量可用于分析的信息。

Answer 3

这一切都取决于您编写 SQL 的方式（以及）以及您的数据库是为您正在执行的操作而设计的。尝试使用解释计划功能来查看数据库将如何执行事情。这。你可以计算大O