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)。LEFT JOIN の代わりに 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;

返される行数がわかりません。

ちなみに、最後のクエリの目的は、2 番目の 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 にユーザーが関連付けられていて、特定のユーザーまたはすべてのユーザーの 2 番目の ID を見つけようとしている場合に、より便利です。私はそれが漸近的にどのように機能するかを理解しようとしています。

何か案は？ありがとう！

4

3 に答える 3

1

パフォーマンスと Big-O 表記に関するあなたのコメントを読んで、あなたが求めているものを突然理解しました - または少なくとも私は理解していると思います。

nがテーブル内の要素の数である場合、最初の選択のパフォーマンスは O( n ) です。

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

2回目の選択で、あなたは正しいです。( n *( n -1))/2 行戻します。nが大きい場合は方程式の 2 乗部分が支配的であるため、減算 (-1) と除算 (/2) の両方を削除できます。性能はO( n² )です。SQL クエリに戻ると、これは、JOIN 句で条件を削除するだけでよいことを意味します。次のように簡略化できます。

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

3 番目の選択の LEFT JOIN には同じ効果があります。単純な左結合を ON (s1.id<s2.id) にすると、追加の n*(-1) 行が返されますが、INNER JOIN では返されません。big-O 表記では、WHERE 句の有無にかかわらず、 O( n ²) のままです。つまり、LEFT JOIN であろうとなかろうと、同じことです。そのため、3 番目の選択は O( n ³) に続き、大きなnになります。

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

以前の理解を使用すると、4 番目の 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

2 つの同じ名前のエントリを特定したいですか、それともクエリの実行方法に関する技術的な説明を探していますか?

複製用にSQLfiddleを設定し、1 つの重複値を持つ行をいくつか挿入しました。複数の値があるかどうかを判断する count() 関数を使用して、現在の行の値を自分自身に照会することにより、値列の重複する値を見つけます。

必要に応じて結合クエリを実行できますが、2 つの結合を超えることはありません。:)

于 2013-02-23T03:51:17.973 に答える