sql - SQL select 的 Big-O 是什么？

Question

SQL 选择的 Big-O 是什么，对于一个有 n 行的表，我想为其返回 m 结果？

更新、删除或创建操作的大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)) 。除了 SELECT 成本之外，如果 UPDATE 影响索引行，也会发生同样的减速。

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

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

正因为如此，我发现能够将一组相关查询捆绑在一个批处理中对性能的影响比我对数据库本身所做的任何优化都要大得多。