與最長的輸入表相比，帶有連接的查詢可以創建更多的行或需要更多的操作嗎？

簡單地說，一個查詢，如：

SELECT * FROM a, b;

…將有一個按 O(a*b) 縮放的結果集，因此 O(N^2)。

但似乎一旦你用外鍵連接它們，就沒有辦法讓查詢創建比包含外鍵的表中更多的行，甚至不是中間步驟。

即使使用多級連接，這似乎也是正確的：您在輸出中創建的行永遠不會比在人口最多的輸入表中創建的行多，並且該表中的每行不需要執行多次操作。

好吧，除了輸出的任何最終排序，它可以按 O(nlog(n)) 左右縮放。

我是否遺漏了任何明顯的縮放問題？子查詢，也許？

聯盟

該UNION命令允許輸出大於輸入：

SELECT * FROM inputTable UNION ALL SELECT * FROM inputTable;

…可以連結 k 次，使其比最大的表長 k 倍，或者類似：

SELECT * FROM
   inputTable,
   (SELECT '1' n UNION ALL SELECT '2') N,
   (SELECT 'a' l UNION ALL SELECT 'b') L;

…這使得輸出inputTable只有 2 個 UNION 語句的長度是 4 倍。所以，好的，有了UNION，我們可以輸出 2^k 次，或者如果我們嵌套更深，可以隨心所欲地擴展。

但是 UNION 仍然只是將表大小乘以一個常數：它是 O(kN)，實際上仍然是 O(N)。那麼我還缺少什麼嗎*？*連接或子查詢的任何擴展方式都比 O(N) 更差？

帶有連接的查詢是否可以創建更多的行或需要比最大的更多的操作

$$ input $$涉及表？…即使所有連接都基於外鍵？

是的，它可以。例子：

Table A
 (a_id, aname)

Table B
 (b_id, bname, a_id)

Table C
 (c_id, cname, a_id)

其中a_id列是引用表 A 的 FK。

假設表 A 只有 1 行，表 B 有 5 行（都引用 A 中的單行），表 C 有 6 行（都引用 A 中的單行）。

然後以下查詢將產生 30 ( 1*5*6 = 30) 行，因為它實際上是一種交叉連接：

select a.*, b.*, c.*
from a
 join b on b.a_id = a.a_id
 join c on c.a_id = a.a_id ;

所以（最壞的情況）複雜性是O(N*M),是N和的M大小。B``C

通常，對於表 A、B、C、…、X 的連接，它可以是O(Nb*Nc*...*Nx)其中Nb, Nc, …是, , …Nx的大小。B``C``X

引用自：https://dba.stackexchange.com/questions/316368