数据库查询优化中的基于直方图的统计信息与选择性估算

字数 2830 2025-11-30 22:12:54

数据库查询优化中的基于直方图的统计信息与选择性估算

一、知识点描述
在数据库查询优化中，选择性估算（Selectivity Estimation）是一个核心环节。它用于预测一个查询条件（谓词）能够过滤掉多少数据。优化器依靠选择性估算来评估不同执行计划的代价，并选择最优计划。基于直方图（Histogram）的统计信息是实现高精度选择性估算最常用和最重要的技术之一。本知识点将详细讲解直方图的原理、构建方法，以及如何利用它进行选择性估算。

二、循序渐进讲解

第一步：为什么需要直方图？——数据分布不均的问题

理想情况：如果表中某一列的数据是均匀分布的（例如，age列的值从1到100，每个年龄出现次数大致相同），那么优化器可以使用简单的假设来进行选择性估算。例如，对于条件 age = 25，选择性可以简单估算为 1 / 100 = 0.01（即1%）。
现实情况：实际数据往往是非均匀分布的。例如，在users表的city列中，“北京”和“上海”的用户可能占总数的一半，而其他城市用户数很少。如果仍然使用均匀分布的假设，估算 city = ‘北京’ 的选择性为 1 / 城市总数，会导致巨大的估算错误，从而可能选择错误的执行计划（如本应使用索引扫描却错误地选择了全表扫描）。
直方图的作用：直方图就是一种用来描述数据分布情况的工具。它将一列数据的值域划分为若干个连续的“桶”（Bucket），并记录每个桶中包含了多少数据。通过直方图，优化器可以更准确地了解数据在不同值区间的集中情况，从而做出更准确的选择性估算。

第二步：直方图是如何构建的？

数据库系统会定期（或根据设置）自动收集统计信息，包括直方图。构建过程通常如下：

数据采样：对于大表，不会扫描全部数据，而是先进行采样，得到一个有代表性的数据子集。
排序：对采样得到的列数据进行排序。
分桶：这是核心步骤。目标是创建N个桶（N是可配置的，例如100或200）。常见的分桶策略有两种：
- 等高直方图：每个桶内包含大致相同数量的数据行（即频率相等）。这种直方图能很好地反映数据的频率分布。
  - 过程：假设有S条采样数据，要分成N个桶。那么每个桶应包含大约 S / N 条数据。系统从排序后的数据中依次划分，使得每个桶的数据量尽可能相等。最后，记录每个桶的边界值（最小值、最大值）和累计频率。
- 等宽直方图：将整个值域范围平均分成N个宽度相等的区间，每个区间就是一个桶。然后统计每个桶内数据的数量。这种直方图在数据分布极度不均时效果不佳，因为某些桶可能数据很多，而某些桶可能为空。
- 现代数据库（如Oracle, SQL Server, PostgreSQL）通常采用等高直方图或其变种，因为它对选择性估算更有效。

第三步：如何利用直方图进行选择性估算？

假设我们有一个关于产品价格的直方图（等高型），包含5个桶，数据如下表所示：

桶号	最小值	最大值	累计频率	不同值数量
1	0.0	50.0	20%	10
2	50.0	100.0	40%	15
3	100.0	200.0	60%	8
4	200.0	500.0	80%	20
5	500.0	1000.0	100%	5

注：累计频率指价格小于等于该桶最大值的行数占比。不同值数量是该桶内唯一取值的个数。

现在，我们来估算不同查询条件的选择性：

等值查询：price = 75
- 步骤1：定位桶。75这个值落在第二个桶（50.0 - 100.0）内。
- 步骤2：估算桶内频率。假设数据在单个桶内是均匀分布的。第二个桶的频率是 40% - 20% = 20%。桶内有15个不同的价格。
- 步骤3：计算选择性。每个不同值在桶内出现的频率假设相等，因此 price = 75 的选择性为 (桶频率) / (桶内不同值数量) = 20% / 15 ≈ 1.33%。
- 结论：优化器估算约有1.33%的产品价格是75。
范围查询：price BETWEEN 80 AND 300
- 步骤1：定位涉及的桶。此范围跨越了桶2、桶3和桶4。
- 步骤2：分桶计算。
  - 桶2（50.0-100.0）：只取80到100这部分。假设桶内均匀，该部分占桶的比例为 (100 - 80) / (100 - 50) = 20/50 = 0.4。因此，桶2的贡献为 20% * 0.4 = 8%。
  - 桶3（100.0-200.0）：整个桶都在80-300范围内，因此贡献全部频率 60% - 40% = 20%。
  - 桶4（200.0-500.0）：只取200到300这部分。该部分占桶的比例为 (300 - 200) / (500 - 200) = 100/300 ≈ 0.333。因此，桶4的贡献为 20% * 0.333 ≈ 6.67%。
- 步骤3：求和。总选择性为 8% + 20% + 6.67% = 34.67%。
- 结论：优化器估算约有34.67%的产品价格在80到300之间。

第四步：直方图的局限性与进阶考虑

桶数量的限制：直方图的精度受桶数量限制。如果一列有上万个不同值，但只有100个桶，那么一个桶内可能包含很多不同值，估算“等值查询”的准确性会下降。
相关性缺失：直方图是单列的统计信息。它无法捕捉多列之间的关联关系。例如，对于条件 city=‘北京’ AND district=‘海淀区’，如果直接使用两列选择性的乘积，会忽略“海淀区”绝大部分都属于“北京”这个强相关性，导致估算过小。解决这个问题需要更复杂的统计信息，如多列统计（扩展统计）。
数据更新：当表中的数据被频繁增删改后，直方图会变得过时。需要定期更新统计信息以保证估算准确性。

总结
基于直方图的统计信息是数据库查询优化器的“眼睛”，它通过将数据分布量化为桶信息，使优化器能够超越简单的均匀分布假设，对查询条件的选择性进行更智能、更准确的估算。理解其原理有助于DBA和开发人员解读执行计划、判断优化器决策的合理性，并在必要时通过收集更详细的统计信息或使用查询提示来引导优化器。

数据库查询优化中的基于直方图的统计信息与选择性估算一、知识点描述在数据库查询优化中，选择性估算（Selectivity Estimation）是一个核心环节。它用于预测一个查询条件（谓词）能够过滤掉多少数据。优化器依靠选择性估算来评估不同执行计划的代价，并选择最优计划。基于直方图（Histogram）的统计信息是实现高精度选择性估算最常用和最重要的技术之一。本知识点将详细讲解直方图的原理、构建方法，以及如何利用它进行选择性估算。二、循序渐进讲解第一步：为什么需要直方图？——数据分布不均的问题理想情况：如果表中某一列的数据是均匀分布的（例如， age 列的值从1到100，每个年龄出现次数大致相同），那么优化器可以使用简单的假设来进行选择性估算。例如，对于条件 age = 25 ，选择性可以简单估算为 1 / 100 = 0.01 （即1%）。现实情况：实际数据往往是非均匀分布的。例如，在 users 表的 city 列中，“北京”和“上海”的用户可能占总数的一半，而其他城市用户数很少。如果仍然使用均匀分布的假设，估算 city = ‘北京’ 的选择性为 1 / 城市总数，会导致巨大的估算错误，从而可能选择错误的执行计划（如本应使用索引扫描却错误地选择了全表扫描）。直方图的作用：直方图就是一种用来描述数据分布情况的工具。它将一列数据的值域划分为若干个连续的“桶”（Bucket），并记录每个桶中包含了多少数据。通过直方图，优化器可以更准确地了解数据在不同值区间的集中情况，从而做出更准确的选择性估算。第二步：直方图是如何构建的？数据库系统会定期（或根据设置）自动收集统计信息，包括直方图。构建过程通常如下：数据采样：对于大表，不会扫描全部数据，而是先进行采样，得到一个有代表性的数据子集。排序：对采样得到的列数据进行排序。分桶：这是核心步骤。目标是创建 N 个桶（ N 是可配置的，例如100或200）。常见的分桶策略有两种：等高直方图：每个桶内包含大致相同数量的数据行（即频率相等）。这种直方图能很好地反映数据的频率分布。过程：假设有 S 条采样数据，要分成 N 个桶。那么每个桶应包含大约 S / N 条数据。系统从排序后的数据中依次划分，使得每个桶的数据量尽可能相等。最后，记录每个桶的边界值（最小值、最大值）和累计频率。等宽直方图：将整个值域范围平均分成 N 个宽度相等的区间，每个区间就是一个桶。然后统计每个桶内数据的数量。这种直方图在数据分布极度不均时效果不佳，因为某些桶可能数据很多，而某些桶可能为空。现代数据库（如Oracle, SQL Server, PostgreSQL）通常采用等高直方图或其变种，因为它对选择性估算更有效。第三步：如何利用直方图进行选择性估算？假设我们有一个关于产品价格的直方图（等高型），包含5个桶，数据如下表所示： | 桶号 | 最小值 | 最大值 | 累计频率 | 不同值数量 | | :--- | :------------- | :------------- | :------- | :------- | | 1 | 0.0 | 50.0 | 20% | 10 | | 2 | 50.0 | 100.0 | 40% | 15 | | 3 | 100.0 | 200.0 | 60% | 8 | | 4 | 200.0 | 500.0 | 80% | 20 | | 5 | 500.0 | 1000.0 | 100% | 5 | 注：累计频率指价格小于等于该桶最大值的行数占比。不同值数量是该桶内唯一取值的个数。现在，我们来估算不同查询条件的选择性：等值查询： price = 75 步骤1：定位桶。75这个值落在第二个桶（50.0 - 100.0）内。步骤2：估算桶内频率。假设数据在单个桶内是均匀分布的。第二个桶的频率是 40% - 20% = 20% 。桶内有15个不同的价格。步骤3：计算选择性。每个不同值在桶内出现的频率假设相等，因此 price = 75 的选择性为 (桶频率) / (桶内不同值数量) = 20% / 15 ≈ 1.33% 。结论：优化器估算约有1.33%的产品价格是75。范围查询： price BETWEEN 80 AND 300 步骤1：定位涉及的桶。此范围跨越了桶2、桶3和桶4。步骤2：分桶计算。桶2（50.0-100.0）：只取80到100这部分。假设桶内均匀，该部分占桶的比例为 (100 - 80) / (100 - 50) = 20/50 = 0.4 。因此，桶2的贡献为 20% * 0.4 = 8% 。桶3（100.0-200.0）：整个桶都在80-300范围内，因此贡献全部频率 60% - 40% = 20% 。桶4（200.0-500.0）：只取200到300这部分。该部分占桶的比例为 (300 - 200) / (500 - 200) = 100/300 ≈ 0.333 。因此，桶4的贡献为 20% * 0.333 ≈ 6.67% 。步骤3：求和。总选择性为 8% + 20% + 6.67% = 34.67% 。结论：优化器估算约有34.67%的产品价格在80到300之间。第四步：直方图的局限性与进阶考虑桶数量的限制：直方图的精度受桶数量限制。如果一列有上万个不同值，但只有100个桶，那么一个桶内可能包含很多不同值，估算“等值查询”的准确性会下降。相关性缺失：直方图是单列的统计信息。它无法捕捉多列之间的关联关系。例如，对于条件 city=‘北京’ AND district=‘海淀区’ ，如果直接使用两列选择性的乘积，会忽略“海淀区”绝大部分都属于“北京”这个强相关性，导致估算过小。解决这个问题需要更复杂的统计信息，如多列统计（扩展统计）。数据更新：当表中的数据被频繁增删改后，直方图会变得过时。需要定期更新统计信息以保证估算准确性。总结基于直方图的统计信息是数据库查询优化器的“眼睛”，它通过将数据分布量化为桶信息，使优化器能够超越简单的均匀分布假设，对查询条件的选择性进行更智能、更准确的估算。理解其原理有助于DBA和开发人员解读执行计划、判断优化器决策的合理性，并在必要时通过收集更详细的统计信息或使用查询提示来引导优化器。