自动检查两个SQL查询在语义上是否相等

Question

我得到了两个查询：

'UPDATE foo SET bar = baz WHERE a = b AND c = d'

和

'UPDATE foo SET bar = baz WHERE c = d AND a = b'

两者在语义上是相等的（它们做得相同），但简单的比较会表明它们不同，因为第一个使用a = b AND c = d，而第二个使用c = d AND a = b。

如何检查两个查询在语义上是否相等

这显然是一个简单的例子，可以通过在WHERE节点对语法树进行简单的字母排序来解决。我感兴趣的是一种通用方法，它也可以解决更复杂的查询——甚至是子查询。

另一个限制是我不能访问数据库，只能使用查询的字符串。因此，运行查询是毫无疑问的，因为它不会反映查询的平等性

上面粗体文本的示例：

FooTable:

A |  B |  C
1 | xx | xx
2 | yy | zz

FooTable'：（FooTable'是另一个数据库上的FooTable）

A |  B |  C
1 | xx | xx
2 | ee | zz
3 | ss | xx

运行查询不会产生有效结果的示例：

1）对同一数据库的查询：

UPDATE FooTable SET B = 'rr' WHERE C = 'xx'

和

UPDATE FooTable SET B = 'rr' WHERE C = 'xx' OR B = 'ss'

这两个查询的结果完全相同，但并不相等。

2）包含不同数据库（相同架构但不同数据）时的查询：

SELECT A,B,C FROM FooTable where C = 'xx'

和

SELECT A,B,C FROM FooTable' where C = 'xx'

这两个查询在语义上基本相等，但不会产生相同的结果。

Answer 1

这个任务确实不平凡。

本质上，您必须构建自己的查询解析器和优化器。这是优化器的任务——转换执行计划中的查询运算符，使查询的最终结果对于底层表中的任何可能数据都保持不变（考虑所有约束）。智能优化器能够为看起来非常不同的查询生成相同的计划（例如IN和EXISTS），它们简化和统一了WHERE子句中的逻辑条件，可以沿着执行树推送谓词，还可以做许多其他事情。

从头开始编写这样的优化器会很困难，但您可以查看现有的开源数据库（Postgres？），看看是否可以从中借鉴一些东西。

另一种更实用的方法可以是利用一个现有数据库，而不是运行查询，让优化器返回生成的执行计划。然后，您可以比较执行计划，而不是比较原始SQL文本。如果计划是相同的，那么原始查询是100%等效的。如果计划不同，优化器仍然可能不够聪明，无法推断出查询是等效的，但您必须接受假阴性的可能性。

我会看看几个不同的数据库，看看你可以使用内置功能从它们的优化器中获得什么样的信息。在任何情况下，生成的执行计划都应该比原始SQL文本更有结构，并且应该更容易自动比较它们。