计算一个查询将以x的形式返回多少行

Question

我有下表：

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时，它会更有用。我只是想了解它是如何渐进地执行的。

有什么想法吗？谢谢

Answer 1

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

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

Answer 2

读到你对性能和big-O表示法的评论，我突然明白了你在追求什么——或者至少我想我明白了。

n是表中元素的数量，第一次选择的性能为O（n）：

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

第二次选择时，您是对的。它给出（n*（n1））/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联接不会返回这些行。在big-O表示法中，无论是否使用WHERE子句，它仍然是O（n²）。所以LEFT JOIN与否，都是一样的。因此，您的第三个选择将跟随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为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)

我希望这能回答你的问题。如果没有，我很抱歉。。。但即使在那时，我仍然很喜欢分析您的查询：）

Answer 3

您是想识别两个相同名称的条目，还是想了解查询如何运行的技术解释？

我为dups设置了一个SQLfiddle，并放入了一些带有一个重复值的行。它通过查询当前行的值来查找valu列中的重复值，并使用count（）函数来确定是否有多个值。

如果你愿意，你可以运行连接查询，但我不会跳过两个连接。：）