数据库等值查询与统计信息

本文涉及的产品
云原生数据库 PolarDB MySQL 版,通用型 2核4GB 50GB
云原生数据库 PolarDB PostgreSQL 版,标准版 2核4GB 50GB
简介: 统计信息是为优化器的 cost 估算提供数据支撑,其中很重要的一点需求便是等值查询(EQUALS, IN 等) 场景下的基数估算。

概念

统计信息是为优化器的 cost 估算提供数据支撑,其中很重要的一点需求便是等值查询(EQUALS, IN 等) 场景下的基数估算。考虑以下 Case

CREATE TABLE `mc_tac_template` (
  `ID` BIGINT ,
  `NAME` varchar(50) NOT NULL,
  `GENDER` varchar(10) NOT NULL,
  PRIMARY KEY (`ID`),
  KEY `KEY_NAME` USING BTREE (`NAME`),
  KEY `KEY_GENDER` USING BTREE (`GENDER`)
) 

SELECT * FROM User WHERE Name='wy' AND Gender='female'

我们的客户同时为性别和姓名设置了索引,这时优化器就要基于各个条件过滤行数多寡来估算选择不同索引的代价开销。就这个 case 而言,如果选到了 gender 的索引,查询过程很可能就不太妙了。

如果统计信息可以提供精确基数,例如 Name='wy' 可以过滤出5行, Gender='female' 只能过滤出一半的数据, 优化器就会知道,此时选择 KEY_NAME 是代价更小的选择。

为了支撑这里的估算过程,统计信息需要决定使用什么样的算法,这也决定了如何收集,如何估算。

算法

数据库中的基数估算类似于 Data Sketching,等值场景下的基数估算一般有两种选择,基于 sample 或基于全量数据。

SAMPLE

当数据量增长时, sample 是一种非常有效提升估算效率的手段。但 sample 必须至少面对以下问题
● 采样的随机化
● 采样数据与整体数据间的差异估算
○ 多少 sample 量才能确保误差率
● 当新数据出现时,如何采样

采样随机化是个很现实的问题,例如存储中的采样有两种做法, 一种按页采样,一种是每页都采一部分数据。第一种方案虽然非常高效,但随机性太差很容易导致估算的效果非常差,第二种方案虽然估算效果高一些,但在 IO 上相当于全量扫描了一遍。

3.png

在 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 这篇论文中,作者比较了基于 Sample 的 GEE/AE 与面向全量数据的 HyperLogLog sketch 算法,HyperLogLog 的精确度完胜。当然这仅仅是在计算 NDV 的场景。

当我们需要某个单一确定数据在集群中的特征时, sample 都很难回答该类问题。举个例子,数据的存在问题,即某数据是否在集群中存在,如果该数据不在 sample 集中存在,那既有可能整体中也不存在,也有可能只是没有被 sample 到。

再例如通过采样估算 ndv 时,如果采样数据(假设 100000 行) 中 ndv 接近 100000,那么整体数据(假设 10000000行)的 ndv 有可能是 100000,或者也有可能是 10000000。

NDV: number of the different value

Sample 的数据集更适合用于解答范围条件下数据的特征问题。例如通过 sample 的数据来构建直方图,用于处理范围条件的查询问题,或者通过 sample 集估算多表等值 Join 的基数问题等。这些问题不在本文的讨论范围内,暂不展开。

非 Sample

● frequency:等值场景的基数估算就是获取某值在集合中的数量,也就是一个获取 frequency 的问题

CountMin Sketch

CountMin Sketch 通常用于解决 frequency 问题。它有点像 Bloom filter,同样需要一个数组以及一个 Hash 函数的集合,当遍历数据时,每个数据会被各个 Hash 函数 Map 到数组中的某个位置,并使该位置的计数器加1。在估算环节,取该数据对应所有计数器所得的最小值。可以预见它一定会确保估算值大于等于真实值,然后再通过一些手段确保误差率。具体的原理这里不再赘述。

CountMin Sketch 具体原理见 An Improved Data Stream Summary:The Count-Min Sketch and its Applications

4.png

CountMin Sketch 最大的问题是当 Sketch 大小不合适时,很容易因 Hash collision 出现过度膨胀的估算。不管是增大 rows (即 Hash 函数)数量或 columns (即 Counter)的数量,都可以减少错误率。CountMin Sketch 在处理大量重复数据时很有优势,但在处理非倾斜数据时,很容易产生过于膨胀的结果。

当然,最开始 CountMin 也是用于处理热点数据获取这种场景。但在数据分布比较均匀的场景并不十分友好。

HyperLogLog+TopN

在 PolarDB-X 中,我们权衡之后使用 HyperLogLog+TopN 的方式处理 frequency 问题。具体的做法是这样的。
HyperLogLog 用于估算出准确的 NDV 值,TopN 用于处理数据倾斜。具体的算法大致如下:
if (topN.get(i) != 0) {

return (long)(topN.get(i) / sampleRate);

}
return (rowcount / cardinality);
HyperLogLog 需要扫描全量数据, TopN 可以通过 Sample 数据构建。

这种数据结构在处理数据的分布整体较为平均,仅有少数倾斜严重的数据场景中非常优秀。通过 rowcount / cardinality 稳定大多数非倾斜数据,通过 TopN 解决倾斜数据,但 TopN 的 Sample 可能会导致倾斜数据出现较大偏差。

从优化器的需求考虑,能够通过估算值明显的区别出倾斜与非倾斜数据,这已经可以满足 Plan 的选择需求。

测试

我们基于模拟的随机数据,对比了 CountMin Sketch 与 HyperLogLog+TopN ,在几个特定场景下的表现。
主要观察的数据有以下两项:

● 最大误差:估算值与真实值最大差异值
● 误差平方差:代表误差范围的稳定程度

数据场景有以下三种:

bound = 100000
// 均衡:
for (int i = 0; i < size; i++) {
    rs[i] = r.nextInt(bound);
}

// 一半数据倾斜到 1000 个 slot 中
if (r.nextBoolean()) {
    rs[i] = r.nextInt(1000);
} else {
    rs[i] = r.nextInt(bound);
}

// 一半数据倾斜至 100 个 slot 中
if (r.nextBoolean()) {
    rs[i] = r.nextInt(100);
} else {
    rs[i] = r.nextInt(bound);
}

算法初始化参数如下:

● CountMin Sketch 初始化参数 epsOfTotalCount = 0.0001,confidence=0.99,形成了 7*20000 的 long 数组,sketch大约占1M空间
● TopN 固定 sample 10W 个数据,保留约不超过5000个最大值。 HyperLogLog 精确度在1.04/sqrt(2^16) = 0.004, 空间大约在50K以下

测试的大致结果如下:

5.jpg

6.jpg

在最大误差中,CountMin 主要来自于均衡数据的膨胀。Hll + TopN 在 10W 的场景最大误差来自于单一值被估算成了 rowcount/cardinality, 但这个误差非常小。在100W 和 1000W 的场景,Hll + TopN 的最大误差远大于 CountMin,但从整体上判断,HLL+TopN的误差平方差相比而方更加稳定,这些误差主要来自于 TopN 中未记录的 Skew 数据(未 Sample 到或 TopN 容量不足)。

整体上比较来看,CountMin Sketch 随数据量增长,针对倾斜数据的估算会更准确,但非倾斜数据的估算会出现较严重偏差,这体现在误差平方差在大数据场景一直保持较高。Hll+TopN 非倾斜数据的估算中非常稳定且准确,倾斜数据的估算会随数据量增长或 sample 的非随机性增加而有较严重膨胀。

从等值条件基数估算的场景考虑,如果要确保倾斜数据的精确度,应该要选择 CountMin Sketch,如果要保证非倾斜数据的精确度,倾斜数据只要能识别出就好,采用 Hll+TopN 是更加实用的选择。

注意以上测试结果仅针对模拟的数据场景。

采集

虽然 CountMin 和 HyperLogLog 回答的问题不同(一个是 frequency, 一个是 ndv ),但本质上都是基于 Sketch 来描述整体数据。基于 Sketch 的算法除了内存占用小以外,还有个非常大的好处是多个 Sketch 可以合并,并用于描述多分片数据。

大部分统计信息模块需要收集的数据是不需要考虑多分片带来的影响的,比如说最大最小值,rowcount,null 值数量,列长度等等。但 ndv 不同,多个分片的 ndv 值无法简单相加得出。但 HyperLogLog 的 Sketch 数据可以通过多分片合并的方式估算出整体的 ndv 值。CountMin 的 Sketch 也可以通过合并处理。

CountMin 和 HyperLogLog 如果想要较高的精确度,必须要扫描全量的数据,但这会至少给 IO 带来巨大的影响。 Sketch 类型的算法可以针对各个分片数据建立不同的 Sketch,然后仅扫描有数据变更分片并更新其 Sketch,这样避免了扫描全量数据的同时,仍然可以在全局得到精确的估算值。
7.jpg

在 Oracle 11g 中,对不活跃的数据分片分成一组统一进行 sketch,这可以极大减少 sketch 占用的内存空间

结语

The approximate approach is often faster and more efficient

--BY GRAHAM CORMODE

到目前为止,数据特征领域已然展开了很长时间的研究,非常多的工具被开发出来。本文主要简单介绍了其中一部分基于 Sketch 的技术在数据库等值查询场景中的区别与影响。

可以看到,这些技术提供了不同场景下解决特定问题的能力,但并非银弹,谨慎权衡的选择工具,才能带来更佳的优化效果。

参考

● Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g∗
● An Improved Data Stream Summary:The Count-Min Sketch and its Applications
● Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates
● HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
● Towards Estimation Error Guarantees for Distinct Values
● Data Sketching
● New Sampling-Based Summary Statistics for Improving Approximate Query Answers
● A Comparison of Five Probabilistic View-Size Estimation Techniques in OLAP
http://content.research.neustar.biz/blog/hll.html

欢迎关注PolarDB-X知乎机构号,阅读更多技术好文。

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
相关文章
|
25天前
|
SQL 数据库
LangChain-09 Query SQL DB With RUN GPT 查询数据库 并 执行SQL 返回结果
LangChain-09 Query SQL DB With RUN GPT 查询数据库 并 执行SQL 返回结果
30 2
|
1天前
|
SQL 安全 Java
MyBatis-Plus条件构造器:构建安全、高效的数据库查询
MyBatis-Plus 提供了一套强大的条件构造器(Wrapper),用于构建复杂的数据库查询条件。Wrapper 类允许开发者以链式调用的方式构造查询条件,无需编写繁琐的 SQL 语句,从而提高开发效率并减少 SQL 注入的风险。
7 1
MyBatis-Plus条件构造器:构建安全、高效的数据库查询
|
19小时前
|
存储 关系型数据库 MySQL
查询服务器CPU、内存、磁盘、网络IO、队列、数据库占用空间等等信息
查询服务器CPU、内存、磁盘、网络IO、队列、数据库占用空间等等信息
11 1
|
1天前
|
SQL 关系型数据库 数据库
PostgreSQL性能飙升的秘密:这几个调优技巧让你的数据库查询速度翻倍!
【10月更文挑战第25天】本文介绍了几种有效提升 PostgreSQL 数据库查询效率的方法,包括索引优化、查询优化、配置优化和硬件优化。通过合理设计索引、编写高效 SQL 查询、调整配置参数和选择合适硬件,可以显著提高数据库性能。
6 1
|
20天前
|
SQL Java 数据库连接
如何使用`DriverManager.getConnection()`连接数据库,并利用`PreparedStatement`执行参数化查询,有效防止SQL注入。
【10月更文挑战第6天】在代码与逻辑交织的世界中,我从一名数据库新手出发,通过不断探索与实践,最终成为熟练掌握JDBC的开发者。这段旅程充满挑战与惊喜,从建立数据库连接到执行SQL语句,再到理解事务管理和批处理等高级功能,每一步都让我对JDBC有了更深的认识。示例代码展示了如何使用`DriverManager.getConnection()`连接数据库,并利用`PreparedStatement`执行参数化查询,有效防止SQL注入。
61 5
|
22天前
|
SQL 存储 安全
SQL查询数据库:基础概念与操作指南
在数字化时代,数据库已成为信息管理的重要工具之一。作为管理和操作数据库的核心语言,SQL(结构化查询语言)已成为数据管理和查询的关键技能。本文将全面介绍SQL查询数据库的基本概念、语句和操作指南,以帮助初学者快速上手,同时为进阶用户提供有价值的参考。一、数据库与SQL简介数据库是一种存储、管理和检索
30 3
|
24天前
|
SQL 存储 缓存
SQL数据库查询详解
数据库是现代信息社会的基石,它们存储和管理着大量的数据。而SQL(StructuredQueryLanguage)作为一种强大的数据库查询语言,广泛应用于各种数据库系统中。本文将详细介绍SQL数据库查询的基本概念、语法、常用操作以及优化策略。一、SQL数据库查询概述SQL是一种用于管理关系数据库的标
115 3
|
24天前
|
应用服务中间件 PHP Apache
PbootCMS提示错误信息“未检测到您服务器环境的sqlite3数据库扩展...”
PbootCMS提示错误信息“未检测到您服务器环境的sqlite3数据库扩展...”
|
25天前
|
存储 SQL 关系型数据库
MySQL查询数据库锁表的SQL语句
MySQL查询数据库锁表的SQL语句
68 1
|
27天前
|
安全 算法 Java
数据库信息/密码加盐加密 —— Java代码手写+集成两种方式,手把手教学!保证能用!
本文提供了在数据库中对密码等敏感信息进行加盐加密的详细教程,包括手写MD5加密算法和使用Spring Security的BCryptPasswordEncoder进行加密,并强调了使用BCryptPasswordEncoder时需要注意的Spring Security配置问题。
82 0
数据库信息/密码加盐加密 —— Java代码手写+集成两种方式,手把手教学!保证能用!