部分索引排除子句性能：索引查询中检查排除子句的时间复杂度

你示例里创建的是PostgreSQL的部分索引（Partial Index），插入数据时数据库需要检查该行是否符合索引的过滤条件（也就是title NOT IN ('a','b','c','d','e')），这一步的时间复杂度可以从以下角度理解：

• 对于NOT IN后跟固定常量列表的过滤条件，数据库会把这些常量预编译为一个固定集合。每次检查时，仅需将插入的字段值与集合内的元素做比较：
  • 当常量数量较少（比如你示例中的5个），数据库会直接执行逐个比较，时间复杂度为O(k)（k为常量数量）。但由于k是固定不变的常量（不会随表数据量增长而变化），实际可视为**O(1)**的常数时间操作。
  • 当常量数量极大时，数据库会自动优化为哈希查找，此时单次检查的时间复杂度依然是O(1)。
• 这个检查的耗时和表中已有的数据总量无关，仅取决于NOT IN中的元素数量，以及字段值的比较成本（比如字符串的长度）。

以你给出的插入操作为例：插入'f'时，数据库会将'f'依次与'a'、'b'、'c'、'd'、'e'做比较，确认不在排除列表中，整个过程是非常高效的常数时间操作。

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