30

大多数编程语言中方法的复杂性可以用静态源代码分析器以圈复杂度来衡量。是否有类似的度量标准来衡量 SQL 查询的复杂性？

测量查询返回所需的时间很简单，但如果我只想能够量化查询的复杂程度怎么办？

[编辑/注释] 虽然获取执行计划很有用，但在这种情况下，这不一定是我想要确定的。我不是在寻找服务器执行查询的难度，我在寻找一个指标来确定开发人员编写查询的难度以及包含缺陷的可能性有多大。

[编辑/注释 2] 诚然，有时测量复杂性没有用，但也有有时有用。有关该主题的进一步讨论，请参阅此问题。

4

12 回答 12

14

软件复杂度的常用度量包括圈复杂度（衡量控制流复杂程度的度量）和Halstead 复杂度（衡量算术复杂程度的度量）。

SQL 查询中的“控制流”最好与查询中的“and”和“or”运算符相关。

“计算复杂度”最好与 SUM 或隐式 JOINS 等运算符相关。

一旦决定了如何对 SQL 查询的每个语法单元进行分类，即它是“控制流”还是“计算”，就可以直接计算 Cyclomatic 或 Halstead 度量。

我认为SQL 优化器对查询所做的事情完全无关紧要。复杂性度量的目的是描述一个人理解查询的难度，而不是评估它的效率。

同样，DDL 所说的内容或是否涉及视图不应包含在此类复杂性度量中。这些指标背后的假设是，当您简单地调用它时，使用的抽象内部的机器复杂性并不有趣，因为推测该抽象做了一些编码人员很好理解的事情。这就是为什么 Halstead 和 Cyclomatic 度量在计数中不包括被调用的子例程的原因，我认为您可以很好地说明视图和 DDL 信息是那些“调用”的抽象。

最后，这些复杂性数字是多么完全正确或多么完全错误并不重要，只要它们反映了关于复杂性的一些真相，并且您可以将它们相互比较。这样，您可以选择哪些 SQL 片段是最复杂的，从而将它们全部排序，并将您的测试注意力集中在最复杂的片段上。

于 2010-07-31T04:27:17.023 回答
11

我不确定查询计划的检索是否会回答这个问题：查询计划隐藏了在数据返回（或在过滤器中使用）之前对数据执行的计算的一部分复杂性；查询计划需要一个有意义的数据库是相关的。事实上，复杂性和执行时间有些相反。类似“好、快、便宜 - 选择任意两个”之类的东西。

最终是关于犯错的可能性，或者不理解我写的代码？

就像是：

  • 表次数（1
  • 每个连接表达式 +1（每个外连接 +1？）
  • WHERE在or之后每个谓词 +1HAVING
  • +1 每个GROUP BY表达式
  • +1 每UNION或INTERSECT
  • 每个函数调用 +1
  • +1 每个CASE表达式
  • )
于 2010-07-28T14:36:53.913 回答
4

请随意尝试我的脚本，该脚本概述了存储过程的大小、对象依赖项的数量和参数的数量 -

计算 TSQL 存储过程复杂度

于 2012-12-23T09:20:36.340 回答
1

SQL 查询是声明性的而不是过程性的：它们没有指定如何实现其目标。SQL 引擎将创建一个攻击程序计划，这可能是寻找复杂性的好地方。尝试检查 EXPLAIN（或 EXPLAIN PLAN）语句的输出，这将是引擎用于执行查询的步骤的粗略描述。

于 2010-07-28T14:05:39.500 回答
1

好吧，我不知道有什么工具可以做到这一点，但在我看来，使查询更复杂的因素将通过以下方式衡量：连接数 where 条件数 ​​函数数 子查询数转换为不同数据类型的数量 case 语句的数量 循环或游标的数量 事务中的步骤数

然而，虽然更复杂的查询可能看起来是最有可能缺陷的查询，但我发现简单的查询很可能包含缺陷，因为它们更有可能是由不懂的人编写的数据模型，因此它们可能看起来正常工作，但实际上返回了错误的数据。所以我不确定这样的指标会告诉你很多。

于 2010-07-28T15:32:06.103 回答
1

在没有任何工具可以做到这一点的情况下，一种务实的方法是确保被分析的查询格式一致，然后计算代码行数。

或者，在保存到文件时使用以字节为单位的查询大小（注意所有查询都使用相同的字符编码保存）。

在我认为没有其他任何东西的情况下，这并不出色，但可以作为复杂性的合理代表。

于 2012-08-09T13:16:37.567 回答
0

这是一个计算与查询可读性相关的复杂度分数的简单算法的想法：

  1. 对查询应用一个简单的词法分析器（例如用于文本编辑器中的语法着色或此处为 SO 的词法分析器）以将查询拆分为标记并为每个标记赋予一个类：
    • SQL 关键字
    • SQL 函数名称
    • 带有字符转义的字符串文字
    • 没有字符转义的字符串文字
    • 日期或日期+时间的字符串文字
    • 数字文字
    • 逗号
    • 插入语
    • SQL 注释 (--, /* ... */)
    • 引用的用户词
    • 非引用用户词：其他一切
  2. 对每个标记使用不同的权重（以及 SQL 关键字的不同权重）给每个标记打分。
  3. 添加每个令牌的分数。
  4. 完毕。

这应该可以很好地工作，例如计算子查询就像计算SELECT和FROM关键字的数量。

通过将此算法与不同的权重表一起使用，您甚至可以测量不同维度的复杂性。例如，在查询之间进行细微的比较。或者使用特定于 SQL 引擎的关键字或函数的查询得分更高（例如：GROUP_CONCAT在 MySQL 上）。

还可以调整算法以考虑 SQL 关键字的大小写：如果它们不是一致的大写，则增加复杂性。或考虑缩进（回车，关键字在一行中的位置）

注意：我受到@redcalx 回答的启发，该回答建议应用标准格式化程序并计算代码行数。但是，我的解决方案更简单，因为它没有构建完整的 AST（抽象语法树）。

于 2020-03-12T08:33:49.690 回答
0

在编程语言中，我们有几种计算时间复杂度或空间复杂度的方法。

类似地，我们可以与 sql 进行比较，也可以像在程序中一样，您使用类似于编程语言的循环的行数，但与通常在 sql 中的编程语言中的输入不同，它与输入一起将完全取决于表中的数据/查看等操作加上查询本身的开销复杂性。

就像一个简单的逐行查询

   Select * from table ; 
  // This will totally depend on no of 
       records say n hence O(n)

   Select max(input) from table;
   // here max would be an extra 
   overhead added to each 
   Therefore t*O(n) where t is max 
   Evaluation time
于 2020-03-12T08:40:24.867 回答
-1

好吧，如果您使用的是 SQL Server，我会说您应该查看执行计划中的查询成本（特别是子树成本）。

这是一个链接，其中介绍了您应该在执行计划中查看的一些内容。

于 2010-07-28T14:05:57.250 回答
-1

根据您的 RDBMS，可能有查询计划工具可以帮助您分析 RDBMS 在获取查询时将采取的步骤。

SQL Server Management Studio Express 有一个内置的查询执行计划。Pervasive PSQL 有它的查询计划查找器。DB2 有类似的工具（忘记叫什么了）。

于 2010-07-28T14:10:41.793 回答
-1

一个好问题。问题是对于像这样的 SQL 查询：

SELECT * FROM foo;

复杂性可能取决于“foo”是什么以及数据库实现。对于像这样的功能：

int f( int n ) {
   if ( n == 42 ) {
      return 0;
   }
   else {
      return n;
   }
}

没有这种依赖。

但是，我认为应该可以为 SELECT 提供一些有用的指标，即使它们不是很精确，我很想看看这会得到什么答案。

于 2010-07-28T14:12:29.580 回答
-3

如果您自己编写查询代码，那么考虑复杂性就足够了。如果表有 N 行，那么，

  1. 一个简单的 SELECT 将是 O(N)
  2. ORDER BY 是 O(NlogN)
  3. 一个连接是 O(N*M)
  4. 一个 DROP TABLE 是 O(1)
  5. SELECT DISTINCT 是 O(N^2)
  6. 查询1 NOT IN/IN 查询2将是 O( O 1 (N) * O 2 (N) )
于 2019-08-22T10:22:49.500 回答