2

我有下表：

CREATE TABLE sample (
  id INT
);

假设我有 x 行。

我这样做SELECT COUNT(1) FROM sample并得到 x 回来。

现在说我这样做：

SELECT COUNT(1)
FROM sample AS s1
JOIN sample AS s2
  ON s2.id < s1.id;

这让我 (x*(x-1))/2 行回来了。

现在说我这样做：

SELECT COUNT(1)
FROM sample AS s1
JOIN sample AS s2
  ON s2.id < s1.id
LEFT JOIN sample AS s3
  ON s3.id < s2.id;

这让我明白了x*(x-1)*(x-2)/6+(x-1)。如果我做了一个 JOIN 而不是一个 LEFT JOIN 我会得到回x*(x-1)*(x-2)/6行。

SELECT COUNT(1)
FROM sample AS s1
JOIN sample AS s2
  ON s2.id < s1.id
LEFT JOIN sample AS s3
  ON s3.id < s2.id
LEFT JOIN sample AS s4
  ON s4.id > s2.id
    AND s4.id < s1.id;

我不知道我会回来多少行。

顺便说一句，最终查询的目的是为您提供第二个 id。例如。

SELECT s1.id
FROM sample AS s1
JOIN sample AS s2
  ON s2.id < s1.id
LEFT JOIN sample AS s3
  ON s3.id < s2.id
LEFT JOIN sample AS s4
  ON s4.id > s2.id
    AND s4.id < s1.id
WHERE s3.id IS NULL
  AND s4.id IS NULL;

当 id 有与之关联的用户并且您尝试为特定用户或所有用户查找第二个 id 时，它会更有用。我只是想了解它是如何渐近执行的。

有任何想法吗？谢谢！

4

3 回答 3

1

阅读您对性能和大 O 表示法的评论，我突然明白了您所追求的 - 或者至少我认为我这样做了。

n是表中元素的数量，第一次选择的性能是 O( n )：

SELECT COUNT(1) FROM sample  -> O(n)

在您的第二次选择中，您是对的。它返回 ( n *( n -1))/2 行。由于等式的平方部分在n较大时占主导地位，因此您可以同时删除减法 (-1) 和除法 (/2)。性能为 O( n² )。回到您的 SQL 查询，这意味着您可以简单地在 JOIN 子句中删除条件。可以简化为：

SELECT COUNT(1) FROM sample, sample   => O(n²)

第三个选择中的 LEFT JOIN 将具有相同的效果。一个简单的左连接 ON (s1.id<s2.id) 将返回额外的 n*(-1) 行，而 INNER JOIN 不会。在大 O 表示法中，无论有无 WHERE 子句，它仍然是 O(n²) 。所以左加入与否，同样的事情。因此，您的第三个选择将遵循 O( n³ ) 大n。

SELECT COUNT(1) FROM sample, sample, sample => O(n³)

使用先前的理解，很容易看出您的第四个 SELECT 归结为

SELECT COUNT(1) FROM sample, sample, sample, sample => O(n^4)

很容易看出 O() 是如何跟随样本表的记录数和自连接数的。

唯一需要回答的问题是“WHERE rightside.id IS NULL”如何影响系统。根据定义，“SELECT FROM a, LEFT JOIN b where b.key IS NULL”只能返回与表 a 相同或更少的行数。因此，选择可以简化为：

SELECT COUNT(1) FROM sample, sample, const, const => O(n²)

一个数据库是否真的像那样执行，或者它是否会构建完整的笛卡尔积然后消除绝大多数行取决于数据库查询优化器的实现，并且必须针对特定的数据库实现来回答。最坏的情况下，数据库将像这样执行：

SELECT COUNT(1) FROM sample, sample, sample, sample => O(n^4)

我希望这回答了你的问题。如果不是，我很抱歉......但即便如此，我仍然很高兴剖析你的查询:)

于 2013-02-25T21:48:33.613 回答
1

这是找到您正在寻找的多项式的一种不太数学的方法。您可以使用您制作的小提琴来查找前几个数字的结果。之后，您可以使用WolframAlpha。

结果：x^4/24 - x^3/4 + 35*x^2/24 - 13*x/4 + 3。

于 2013-02-26T14:44:00.523 回答
0

您是在寻找两个相同名称的条目，还是在寻找有关查询运行方式的技术解释？

我为 dups 设置了一个SQLfiddle，并用一个重复值放入了一些行。它通过向自身查询当前行的值来查找 value 列中的重复值，使用 count() 函数确定是否存在多个。

如果您愿意，您可以运行您拥有的连接查询，但我不会超过两个连接。:)

于 2013-02-23T03:51:17.973 回答