MySQL中WHERE EXISTS查询的时间复杂度及优化方案咨询

一、当前查询的时间复杂度判断 #

从给出的执行计划来看，当前查询的时间复杂度不是O(NM)，而是接近O(N)：

• 执行计划中先对表A做全表扫描（type: ALL），这一步时间复杂度为O(N)；
• 对表A中每一行符合A.key != 1234的数据，通过主键索引查询表B（type: eq_ref，主键查找的时间复杂度为O(1)）；
• 整体复杂度为O(N) + O(K)（K为表A中符合过滤条件的行数，最坏情况K=N），属于O(M+N)的范畴（实际比O(M+N)更优，因为未遍历表B的全部M行）。

若执行计划选择以表B为驱动表（全扫表B，再通过主键查A），复杂度则为O(M)，同样属于O(M+N)范畴。

二、优化方案（进一步稳定执行效率） #

当前查询已避免了O(NM)级别的复杂度，但可以通过以下方式让执行效率更稳定：

1. 添加复合索引：给表A创建(account, key)的复合索引，查询时可直接通过索引过滤A.key != 1234的条件，无需回表查询原数据：

   CREATE INDEX idx_account_key ON A(account, key);
   

2. 改写为JOIN查询：通过JOIN方式实现相同逻辑，利用索引优化关联过程：

   SELECT COUNT(DISTINCT B.account) 
   FROM B 
   JOIN A ON B.account = A.account 
   WHERE A.key != 1234;
   

   该查询在有合适索引的情况下，时间复杂度稳定在O(M + N)，可通过主键索引快速完成两表的关联匹配。

内容的提问来源于stack exchange，提问作者Metal Slime