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子查询

回答

相关问题