SQL查詢時間複雜度 - 加入VS子查詢

我的問題是關於使用窘境和join方法sub-query給出相同的結果時，SQL查詢時間複雜度 - 加入VS子查詢

哪一個更好，更快？ （純粹在時間複雜度方面）

是否join採取O(M+N)時間複雜度？ sub-query以O(M*N)？

我想錯了這種想法嗎？如果是，請糾正我。

這裏，（M，N）是兩個表格中合併獲得結果的行數。

我在尋找基於SQL標準的答案，不僅僅是MySQL。

P.S - 我已經通過this問題及其所有答案。它並不關心時間複雜性部分。

來源

2017-08-30 pro_cheats

MySQL（以及其他RDMS）中的查詢規劃模塊非常複雜，以至於這個問題唯一可以想到的答案是「這取決於」。規劃師可以將一些查詢從子查詢表單轉換爲連接表單。其他人不能。索引和表基數都進入查詢規劃人員的決策。 –

關於O（M + N）和O（M * N）部分的提示？ @ O.Jones –

通常情況下，連接執行得更好..但正如O.Jones所建議的那樣..「depends」 – scaisEdge

是否加入O（M + N）時間複雜度？並做子查詢O（M * N）？我這樣想是錯的嗎？

是的，相對而言，您錯誤地認爲這樣。 SQL是聲明式。您可以使用它來陳述您想要的結果，並且服務器根據可用的索引和數據結構找出實現該結果的最佳方式 - 以滿足您的查詢。

數千年 - 真的！ - 開發人員的努力已經開始研究各種算法，優化和黑客手段，以降低服務器用於滿足查詢的過程的複雜性。

隨着數千年的經驗累積，相關子查詢和連接查詢之間的性能差異變得不那麼重要。

由於某種原因，您的想法是錯誤的：您在程序上認爲，不是聲明。當您斷言某個特定類型的查詢可以在例如O(m*n)時間內得到滿足時，您正在對用於滿足它的過程進行假設。幾代開發人員一直致力於讓您的假設錯誤。

當然，可以創建具有病態性能特徵的表格，索引和查詢。它總是發生。但有人修復索引並解決問題。

來源

2017-08-30 18:06:01

我能期待的最佳答案！感謝@O瓊斯說明具體原因。現在讓概念清楚了。 –

據我瞭解，表現應該是一樣的。在表格上應用正確的索引和集羣更重要。

來源

2017-08-30 17:51:51

O（M + N）和O（M * N）部分的任何提示？（時間複雜度w.r.t行數）。我讀過一篇文章，哈希技術可以被編譯器用於連接，而在子查詢中則不是這種情況。 –

我相信這是你對數據庫表和JOIN的想法不正確。這是不正確的想法（O（M + N）和O（M * N））並坦率地說，我真的不知道你在這裏試圖得到什麼。

無論何時加入表格，您都會鏈接關係並返回所需的行。

Select * from dbo.Table A 
JOIN dbo.table O on O.ID = A.ID 
JOIN (Select * from dbo.Table B) B on b.ID = A.ID 
-- here you need to make sure there's a relationship between your two tables.

上面的選擇將返回的所有值從所有3個表。表A和O和B與匹配的ID。沒有row1 + row2或row1 * row2或諸如時間複雜性之類的東西。要麼你有匹配的關係，要麼你沒有。

我建議你閱讀數據庫的基本教程和目的。每個行和列都像Excel一樣「可視化」。如果他們有匹配的標準，您可以鏈接其他文件。

來源

2017-08-30 18:03:55 Isaiah3015

SQL查詢時間複雜度 - 加入VS子查詢

回答

相關問題