SQL `LIKE` 复杂度

Question

有谁知道最流行的数据库的 SQL LIKE 运算符的复杂度是多少？

Answer 1

让我们分别考虑三个核心案例。此讨论是特定于 MySQL 的，但也可能适用于其他 DBMS，因为索引通常以类似的方式实现。

LIKE 'foo%' 如果在索引列上运行会很快。 MySQL 索引是 B 树的变体，因此在执行此查询时它可以简单地下降foo 对应的节点，或具有该前缀的第一个节点，并向前遍历树。所有这些都非常有效。

LIKE '%foo' 无法通过索引加速并将导致全表扫描。 如果您有其他可以使用索引执行的条件，它只会扫描初始过滤后剩余的行。

虽然有一个技巧:如果您需要进行后缀匹配 - 例如搜索扩展名为 .foo 的文件名 - 您可以通过添加来实现相同的性能与原始内容相同但字符顺序相反的列。

ALTER TABLE my_table ADD COLUMN col_reverse VARCHAR (256) NOT NULL;
ALTER TABLE my_table ADD INDEX idx_col_reverse (col_reverse);
UPDATE my_table SET col_reverse = REVERSE(col);

搜索 col 以 .foo 结尾的行会变成:

SELECT * FROM my_table WHERE col_reverse LIKE 'oof.%'

最后，还有 LIKE '%foo%'，对此没有捷径。如果没有其他限制条件将行数减少到可行数字，它会导致严重的性能损失。您可能需要考虑使用全文搜索解决方案或其他一些专门的解决方案。