代码之家 › 专栏 › 技术社区 › neubert

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

join math sql mysql

neubert · 技术社区 · 13 年前

我有下表:

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

有什么想法吗?谢谢

3 回复 | 直到 13 年前

Tonci 13 年前

这里有一种不太数学的方法来找到你要找的多项式。您可以使用 fiddle 你设法找到前几个数字的结果。之后,您可以使用 WolframAlpha .

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

Hazzit 13 年前

读到你对性能和大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不会返回这些行。在big-O表示法中,这仍然是O( n ),包含或不包含WHERE子句。所以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 right side.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Â²)

数据库是否真的这样执行,或者它是否会构建完整的笛卡尔乘积,然后消除绝大多数行,这取决于数据库的查询优化器的实现,并且必须根据特定的数据库实现来回答。最坏的情况是,数据库将执行如下操作:

从样本中选择计数(1),样本,样本,样品=>O(n ^4)

我希望这能回答你的问题。如果没有,我很抱歉。。。但即使在那时,我仍然很喜欢剖析你的疑问:)

Just Aguy 13 年前

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

我设置了一个 SQLfiddle 对于dup,并抛出了一些具有一个重复值的行。它通过查询当前行的值来查找valu列中的重复值,并使用count()函数来确定是否有多个值。

如果你愿意,你可以运行连接查询,但我不会跳过两个连接。:)