MySQL 中的位超集和子集

Question

以下查询在MySQL中是否有效：

SELECT * FROM table WHERE field & number = number; 
# to find values with superset of number's bits

SELECT * FROM table WHERE field | number = number; 
# to find values with subset of number's bits

如果没有为该字段创建索引，是否有办法使其运行更快？

如果没有，有什么方法可以使其运行更快？

- Meisner

---

这是一个很好的问题，但你需要接受一些答案 - 20%不会吸引人们尝试回答你。 - Fragsworth

Answer 1

更新：

有关性能详细信息，请参阅我的博客中的此条目：

• 位运算和索引

---

SELECT * FROM table WHERE field & number = number

SELECT * FROM table WHERE field | number = number

这个索引可以发挥两种作用：

1. 避免早期表扫描（因为要比较的值包含在索引本身中）
   • 限制检查的值范围。

上述查询条件都不是可搜索谓词（即SARG），因此该索引不会被用于范围扫描（当前条件下）。

然而，点 1 仍然成立，该索引仍然有用。

如果你的表中每行包含平均 100 个字节，并且有 1,000,000 条记录，则表扫描需要扫描 100 MB 的数据。

如果你有一个索引（具有 4 字节的键、6 字节的行指针和一些内部开销），则查询只需要扫描 10 MB 的数据加上表过滤成功后的额外数据。

• 如果你的条件不具有选择性（即很可能匹配条件），则表扫描更有效率。
• 如果你的条件具有选择性（即很可能不匹配条件），则索引扫描更有效率。

这两个查询都需要扫描整个索引。

但通过重写 AND 查询，你也可以从索引范围受益。

这个条件：

field & number = number

只有当 number 的最高位在 field 中也被设置时才能匹配字段。

你应该向查询提供额外的这个条件：

SELECT  *
FROM    table
WHERE   field & number = number
        AND field >= 0xFFFFFFFF & ~((2 << FLOOR(LOG(2, 0xFFFFFFFF & ~number))) - 1)

这将使用范围进行粗略过滤，使用条件进行精细过滤。

number的结尾未设置的位数越多，效果越好。

- Quassnoi

---

OR也可以进行优化：如果字段中设置的高位比数字的最高位还要高，则“field | number = number”永远不为真。因此：SELECT * FROM table WHERE field | number = number AND field < 2<<FLOOR(LOG(2,number)); 我还可以想象进一步优化，使用字段的多个最高位构建查询范围。极端情况是当字段的每个值都明确指定时（使用“field IN（value1，...）”）。无论如何，这是一个很好的答案。 - Meisner

Answer 2

我怀疑优化器不会想到那个...

也许你可以在这些查询上调用EXPLAIN并确认我的悲观猜测。(当然要记住，查询计划决策的很大一部分基于给定数据库实例的特定情况，即不同数量的数据和/或具有不同统计概要文件的数据可能会产生不同的计划)。

假设表中有大量行，并且“按位”条件仍然足够选择，则通过使用IN结构(或JOIN)重写查询来避免对每个单独行进行按位操作，可以实现可能的优化。

类似于这样的东西(概念性的，即未经测试)

CREATE TEMPORARY TABLE tblFieldValues
  (Field INT);

INSERT INTO tblFieldValues
   SELECT DISTINCT Field
   FROM table;

-- SELECT * FROM table WHERE field | number = number; 
-- now becomes
SELECT * 
FROM table t
WHERE field IN 
    (SELECT Field 
     FROM tblFieldValues 
     WHERE field | number = number); 

这种方法的全部优势需要通过不同的用例进行评估（所有这些用例都有一个相当数量的表行，否则直接使用“WHERE field | number = number”方法就足够高效），但我怀疑这可能会显著提高速度。如果不需要每次重新创建“tblFieldValues”，则可以实现进一步的收益。当然，有效地创建此表意味着在原始表中对字段进行索引。

- mjv

---

这是一个解决方案，在Field值减少的情况下变得越来越有趣。我会考虑将BIGINT字段拆分为一组TINYINT字段，仅出于此优化的目的。 - Meisner

Answer 3

我自己尝试过，位运算并不足以防止Mysql在“field”列上使用索引。然而，很可能正在进行索引的全扫描。

- Rob F