考虑一个id
带有PRIMARY KEY
索引的表:
CREATE TABLE test (id INT PRIMARY KEY)
现在考虑像这样的查询
SELECT COUNT(*) FROM test
SELECT * FROM test ORDER BY id LIMIT ?, 1
(使用 MySQL 语法LIMIT
:?
是偏移量)
看起来,尽管表上有索引(在 上id
),但这些查询(计算行数或在偏移处选择行)都需要线性时间,因为它们必须执行完整或部分表扫描;在排序顺序中的行的“等级”/位置上没有索引,这将有助于按等级计数或获取元素(与 Redis 的排序集相比,它允许有效地按等级进行操作)。
问题在于(通常是 B 树)索引仅限于id
并且根本没有“增强”以包含计数/排名。我研究过 SQLite、MySQL / MariaDB 和 PostgreSQL,这些 DBMS 似乎都不允许增加索引以包含计数/排名。
我的问题是:
- 是否可以扩充 SQLite、MySQL / MariaDB 或 PostgreSQL 使用的 B 树索引以包含计数?
- 如果没有,是否有另一种使用 SQL 作为查询语言的关系 DBMS 支持此类索引?
DBMS 不在表或索引中存储排名,因为排名是一个依赖于表中所有其他行的属性。
即使我们不考虑多版本并发性(其中单行可以有多个等级),添加或删除新行也需要按照所需的顺序更新新行/删除行之后的所有行的等级。
这将带来巨大的性能损失,而收益却微乎其微。
但是,您当然可以使用 TRIGGERS 自由添加排名系统。
这是假设你从不修改 id。
现在,您的查询将变为:
不幸的是,为了快速并且不需要表扫描,后者还需要 上的索引
rank
,但每次在表中插入或删除行时,此类索引也必须大量更新。最佳解决方案取决于具体情况以及您正在使用的数据库引擎。
对于 InnoDB:
当您执行 100、100 的 LIMIT OFFSET 查询时,数据库引擎将获取 200 条记录并丢弃前 100 条。如果您知道数据集的长度,则可以通过一些技巧来避免这种情况。其中之一是使用过滤器
SELECT Id FROM test WHERE Id > 100 LIMIT 100;
。计算行数有一些技巧,它们都取决于用例。如果您想要行数的近似值,您可以使用 a
EXPLAIN()
并获取rows
列。这将给出行数的良好近似值。您还可以引入一个表来缓存计数。不。
这对你来说是一个足够明确的答案吗?:-)
当您按值而不是位置(即使用
OFFSET
)搜索时,B 树索引可以提高性能。解决此问题的技巧通常是将行位置存储为值,然后对该列建立索引。或者按值查询不同的列。
另一种常见的解决方案是存储“汇总表”,以便快速访问预先计算的聚合值。但如果您的数据经常更新,那么保持更新是一件苦差事。
此外,如果您必须支持任意范围(如您的
ID BETWEEN x AND y
示例中所示),它们也没有多大帮助,因为尝试保留 O(n 2 ) 不同子范围的摘要可能比仅在需要时执行聚合查询的成本更高。有一组 RDBMS 实现称为面向列的 DBMS。这些针对分析查询进行优化。其中一些将数据存储在页面中,并在每个页面中内部保存汇总小计。因此,如果您想获取
COUNT(*)
某个范围内的 id,则只需访问涵盖该范围的每个页面,然后对每个页面中预先计算的小计求和,而不是访问每一行。我对面向列的数据库没有任何个人经验,但我知道有许多商业和开源产品。例如,ClickHouse 有时用作 MySQL 的补充。请参阅https://www.percona.com/blog/using-clickhouse-as-an-analytic-extension-for-mysql/
为了针对分析查询进行优化,一些面向列的数据库牺牲了对更典型的事务查询的优化。在选择面向列的数据库之前,应该在应用程序的工作负载下仔细测试它。
现有的 BTree 实现则不然。但也许这...
每当 BTree 块中发生更改(插入/删除)时,都会计算该块中的行数并将该计数放入父节点中。这需要最终更新该节点。
计划 A:只有倒数第二个节点才有该计数。要获得“排名”,您必须将 BTree 的该级别中的计数相加,然后深入到叶节点来完成计数。
B 计划:计数会渗透到树上。这会导致任何插入/删除的 Log(n) 非叶节点更新。为了减轻这种成本,这里有一条经验法则:一个典型的 BTree 节点(在 InnoDB 中)有 100 个子节点。也就是说,即使一万亿行 BTree 也只有 6 个级别 ( Log100(1e12) = 6 )。
(警告:此设计可能难以跟上 ACID/MVCC/等。)
查找“随机”行的近似方法: Random
OFFSET
因为分页是不好的,一个典型的可行的解决方法是: 分页;不仅包括“下一页”和“上一页”页面的建议。