`Cardinality`（`基数`）的`估算`：`优化器`如何`估算`索引`列`的`唯一`值`数量`。

Cardinality 估算：优化器如何估算索引列的唯一值数量

大家好，今天我们来深入探讨数据库优化器中的一个核心概念：Cardinality Estimation（基数估算）。准确的基数估算对于数据库查询优化至关重要，它直接影响着优化器选择最佳执行计划的能力。本文将重点讨论优化器如何估算索引列的唯一值数量，也就是Distinct Value Count (DVC)，并结合代码示例进行说明。

1. 什么是 Cardinality 以及 DVC 的重要性

Cardinality 指的是一个查询结果集中返回的行数。在数据库优化中，我们通常关注中间结果集的 Cardinality，因为它会影响后续操作的选择。而 Distinct Value Count (DVC) 是 Cardinality 的一个特例，它指的是某一列中唯一值的数量。

DVC 在优化过程中扮演着重要角色，原因如下：

• 选择率（Selectivity）估算： 选择率是指满足某个谓词条件的行数占总行数的比例。DVC 可以用来估算选择率。例如，对于 column = value 这种等值谓词，如果知道 column 列的 DVC，就可以大致估算出满足该谓词的行数。
• 索引选择： 优化器会根据 DVC 来判断是否应该使用索引。如果一个列的 DVC 很高，意味着每个值对应的行数较少，使用索引的效率可能更高。反之，如果 DVC 很低，大部分行都具有相同的值，全表扫描可能更有效。
• 连接顺序（Join Order）优化： 在多表连接查询中，连接顺序对性能影响很大。优化器会根据连接键的 Cardinality 来决定最佳的连接顺序。通常，先连接 Cardinality 较小的表可以减少中间结果集的大小，从而提高效率。

举例说明：

假设我们有一个 orders 表，包含 order_id (主键), customer_id, 和 order_date 列。

order_id	customer_id	order_date
1	101	2023-01-01
2	102	2023-01-02
3	101	2023-01-03
4	103	2023-01-04
5	102	2023-01-05
…	…	…

如果我们要执行以下查询：

SELECT * FROM orders WHERE customer_id = 101;

优化器需要估算有多少行满足 customer_id = 101 这个条件。如果 customer_id 列的 DVC 很小（例如，只有 3 个不同的 customer_id），那么优化器可能会认为有很多行满足这个条件，从而选择全表扫描。如果 DVC 很大（例如，每个 customer_id 对应很少的订单），优化器可能会选择使用 customer_id 上的索引。

2. 优化器估算 DVC 的方法

优化器通常会使用以下方法来估算索引列的 DVC：

• 统计信息（Statistics）： 这是最常用的方法。数据库会定期收集表的统计信息，包括 DVC、最小值、最大值、NULL 值数量等。优化器会利用这些统计信息来估算 Cardinality。
• 直方图（Histograms）： 直方图是一种更高级的统计信息，它可以更精确地描述数据的分布情况。直方图将数据分成若干个桶（buckets），并记录每个桶内的数据频率。优化器可以利用直方图来更准确地估算 DVC 和选择率。
• 采样（Sampling）： 如果统计信息不准确或者没有可用的统计信息，优化器可以对表进行采样，然后根据样本数据来估算 DVC。
• 规则（Rules）和启发式方法（Heuristics）： 优化器会使用一些预定义的规则和启发式方法来估算 DVC。例如，对于主键列，优化器通常会假设 DVC 等于表的总行数。
• 基数传播（Cardinality Propagation）： 对于复杂的查询，优化器会根据已知的 Cardinality 信息来推导出其他列的 Cardinality。例如，如果知道 A 表和 B 表的 Cardinality，以及 A.x = B.y 这个连接条件的 Cardinality，就可以推导出连接结果的 Cardinality。

3. 统计信息

统计信息是优化器进行 Cardinality 估算的基础。数据库通常会提供命令来收集统计信息。例如，在 PostgreSQL 中，可以使用 ANALYZE 命令：

ANALYZE orders;

这条命令会收集 orders 表的统计信息，包括 DVC、最小值、最大值、NULL 值数量等。这些统计信息会被存储在系统目录中，优化器在查询优化时会读取这些信息。

我们可以通过查询系统目录来查看统计信息。例如，在 PostgreSQL 中，可以使用以下查询来查看 orders 表 customer_id 列的 DVC：

SELECT n_distinct
FROM pg_stats
WHERE tablename = 'orders'
  AND attname = 'customer_id';

n_distinct 列存储了 DVC 的信息。如果 n_distinct 的值为正数，表示准确的 DVC。如果 n_distinct 的值为负数，表示估算的 DVC，其绝对值是 DVC 的估计值乘以 -1。例如，如果 n_distinct 的值为 -0.5，表示估算的 DVC 是表的总行数的一半。

示例代码 (Python 连接 PostgreSQL)：

import psycopg2

def get_dvc(table_name, column_name, conn_params):
  """
  获取指定表和列的 DVC。

  Args:
    table_name: 表名。
    column_name: 列名。
    conn_params: 数据库连接参数。

  Returns:
    DVC 的值，如果查询失败则返回 None。
  """
  try:
    conn = psycopg2.connect(**conn_params)
    cur = conn.cursor()

    query = """
    SELECT n_distinct
    FROM pg_stats
    WHERE tablename = %s
      AND attname = %s;
    """
    cur.execute(query, (table_name, column_name))
    result = cur.fetchone()

    cur.close()
    conn.close()

    if result:
      return result[0]
    else:
      return None

  except psycopg2.Error as e:
    print(f"Error: {e}")
    return None

# 数据库连接参数
conn_params = {
  'dbname': 'your_database_name',
  'user': 'your_username',
  'password': 'your_password',
  'host': 'localhost',
  'port': 5432
}

# 获取 orders 表 customer_id 列的 DVC
dvc = get_dvc('orders', 'customer_id', conn_params)

if dvc is not None:
  print(f"The DVC of orders.customer_id is: {dvc}")
else:
  print("Could not retrieve DVC.")

统计信息的更新：

统计信息不是静态的，随着数据的变化，统计信息会变得过时。因此，需要定期更新统计信息。数据库通常会自动更新统计信息，也可以手动更新。更新统计信息的频率取决于数据的变化频率。如果数据变化频繁，应该更频繁地更新统计信息。

4. 直方图

直方图是一种更高级的统计信息，它可以更精确地描述数据的分布情况。直方图将数据分成若干个桶（buckets），并记录每个桶内的数据频率。

PostgreSQL 支持多种类型的直方图，包括：

• Frequency Histogram： 记录每个桶内的数据频率。
• Equi-Width Histogram： 每个桶的宽度相等。
• Most Common Values (MCV)： 记录最常见的几个值及其频率。

可以使用 CREATE STATISTICS 命令来创建直方图。例如，以下命令创建一个 customer_id 列的频率直方图：

CREATE STATISTICS orders_customer_id_stats (mcv, histogram)
ON customer_id FROM orders;

ANALYZE orders;

创建直方图后，需要执行 ANALYZE 命令来收集统计信息。

可以通过查询系统目录来查看直方图的信息。例如，在 PostgreSQL 中，可以使用以下查询来查看 orders_customer_id_stats 统计信息对象的信息：

SELECT stavalues1, stavalues2, stanumbers1, stanumbers2
FROM pg_statistic
WHERE starelid = 'orders'::regclass
  AND stattarget > 0
  AND stxname = 'orders_customer_id_stats';

• stavalues1 和 stavalues2 存储了 MCV 的值。
• stanumbers1 和 stanumbers2 存储了 MCV 的频率和直方图的桶的边界值。

直方图的优势：

直方图可以更准确地描述数据的分布情况，从而提高 Cardinality 估算的准确性。例如，如果一个列的数据分布不均匀，使用简单的 DVC 可能无法准确估算选择率。而使用直方图可以更准确地估算选择率。

直方图的缺点：

直方图需要额外的存储空间，并且创建和维护直方图需要消耗一定的资源。因此，应该只对那些对查询性能影响较大的列创建直方图。

5. 采样

如果统计信息不准确或者没有可用的统计信息，优化器可以对表进行采样，然后根据样本数据来估算 DVC。

采样的方法有很多种，常见的有：

• 随机采样： 随机选择一部分行作为样本。
• 系统采样： 每隔一定数量的行选择一行作为样本。

采样估算 DVC 的方法很简单：首先，对表进行采样，然后计算样本数据中不同值的数量，最后，根据样本数据中不同值的数量来估算整个表的 DVC。

示例代码 (Python 连接 PostgreSQL)：

import psycopg2
import random

def estimate_dvc_by_sampling(table_name, column_name, conn_params, sample_size):
  """
  通过采样估算指定表和列的 DVC。

  Args:
    table_name: 表名。
    column_name: 列名。
    conn_params: 数据库连接参数。
    sample_size: 样本大小。

  Returns:
    估算的 DVC 值，如果查询失败则返回 None。
  """
  try:
    conn = psycopg2.connect(**conn_params)
    cur = conn.cursor()

    # 获取表的总行数
    cur.execute(f"SELECT COUNT(*) FROM {table_name}")
    total_rows = cur.fetchone()[0]

    # 随机选择样本行
    if sample_size > total_rows:
        sample_size = total_rows # 样本大小不能超过总行数
    random_rows = random.sample(range(1, total_rows + 1), sample_size)

    # 构建查询语句
    query = f"""
    SELECT DISTINCT {column_name}
    FROM {table_name}
    WHERE ROWID IN ({','.join(map(str, random_rows))})
    """

    # 执行查询
    cur.execute(query)
    distinct_values = cur.fetchall()

    # 估算 DVC
    estimated_dvc = len(distinct_values)

    cur.close()
    conn.close()

    return estimated_dvc

  except psycopg2.Error as e:
    print(f"Error: {e}")
    return None

# 数据库连接参数 (同上)
conn_params = {
  'dbname': 'your_database_name',
  'user': 'your_username',
  'password': 'your_password',
  'host': 'localhost',
  'port': 5432
}

# 估算 orders 表 customer_id 列的 DVC (样本大小为 1000)
estimated_dvc = estimate_dvc_by_sampling('orders', 'customer_id', conn_params, 1000)

if estimated_dvc is not None:
  print(f"The estimated DVC of orders.customer_id is: {estimated_dvc}")
else:
  print("Could not estimate DVC.")

ROWID 的说明：

上面的示例代码使用了 ROWID 来随机选择样本行。ROWID 是一个伪列，它表示表中每一行的物理地址。不同的数据库系统使用不同的方式来表示 ROWID。在 PostgreSQL 中，没有直接的 ROWID 列，需要使用其他方法来模拟 ROWID 的功能。上面的代码假设表有一个隐式的行号，可以通过 ROWID 来访问。 如果你的表没有类似的机制，可以考虑添加一个自增的整数列作为 ROWID 的替代品。

采样的优缺点：

采样方法的优点是简单易行，不需要额外的存储空间。缺点是估算的准确性取决于样本的大小。样本越大，估算的准确性越高，但同时也会消耗更多的资源。

6. 规则和启发式方法

优化器会使用一些预定义的规则和启发式方法来估算 DVC。例如：

• 主键列： 对于主键列，优化器通常会假设 DVC 等于表的总行数。
• 唯一索引列： 对于唯一索引列，优化器也会假设 DVC 等于表的总行数。
• 外键列： 对于外键列，优化器可以根据外键关系来估算 DVC。例如，如果 orders.customer_id 是 customers.customer_id 的外键，那么 orders.customer_id 的 DVC 不会超过 customers.customer_id 的 DVC。
• 常量： 如果谓词条件是 column = constant， 优化器可以根据常量值的类型来决定使用哪种估算方法。

这些规则和启发式方法虽然简单，但在很多情况下可以提供合理的 DVC 估计。

7. 基数传播

对于复杂的查询，优化器会根据已知的 Cardinality 信息来推导出其他列的 Cardinality。例如，考虑以下查询：

SELECT *
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE c.city = 'New York';

优化器首先需要估算 customers 表中 city = 'New York' 的行数。然后，根据 o.customer_id = c.customer_id 这个连接条件，优化器可以推导出 orders 表中 customer_id 相关的行数。

基数传播是一个复杂的过程，涉及到很多因素，包括连接类型、连接条件、数据分布等。优化器会使用各种算法和模型来进行基数传播。

8. 总结

准确的 Cardinality 估算对于数据库查询优化至关重要。优化器会使用多种方法来估算索引列的 DVC，包括统计信息、直方图、采样、规则和启发式方法，以及基数传播。了解优化器如何估算 DVC 可以帮助我们更好地理解查询优化过程，并编写更高效的 SQL 查询。