SQL Server查询能否达O(1)复杂度？分区表查询延迟分析

问题背景 #

假设有两张存储每日时间序列数据的SQL Server表，两者均包含复合主键（SQL Server中主键同时为聚集索引），且主键包含DATE类型的BUSINESS_DATE字段，表均按月分区：

• Table_Short仅存储2年数据
• Table_Long存储50年数据

终端用户每次最多查询最近1年的数据，执行的SELECT语句如下：

SELECT <some columns>
FROM <Table>
WHERE BUSINESS_DATE >= t1 
AND BUSINESS_DATE <= t2

（t1、t2为指定日期）

核心疑问 #

基于用户仅查询最近1年数据、表已按BUSINESS_DATE分区并排序的前提，是否查询延迟与表大小无关？即查询Table_Long与Table_Short耗时相同？

另外，已知SQL Server以B+树存储聚集索引，最坏搜索复杂度为O(log n)，但仅查询最近1年数据时，时间复杂度能否变为O(1)？

回答 #

1. 查询延迟是否与表大小无关？ #

可以认为查询耗时几乎一致，仅存在可忽略的微小差异。

原因在于两张表都是按月分区，SQL Server会通过分区函数直接定位到查询覆盖的最近12个分区，不会扫描其他无关分区。不管表总共有24个分区（2年）还是600个分区（50年），实际参与查询的都是12个分区，这部分的数据量、存储结构完全一致，核心的读取、过滤操作耗时基本无差别。

唯一可能的差异来自分区元数据的读取，但这部分开销极小，对整体查询延迟的影响可以忽略。

2. 时间复杂度能否达到O(1)？ #

无法达到严格定义的O(1)，但实际执行效率接近O(1)的表现。

SQL Server的分区定位是通过范围匹配快速找到目标分区，这一步开销极低；但进入目标分区后，仍需通过聚集索引的B+树定位BUSINESS_DATE的起始和结束行，这一步的复杂度是O(log k)（k为单个分区内的数据量）。不过单个分区仅对应1个月的每日数据（最多31条），log k的数值极小，实际执行起来几乎和O(1)无差别，但从算法复杂度的定义上，仍属于对数级，不是严格的O(1)。

内容的提问来源于stack exchange，提问作者Alex S.