EthanWeee

网站标签

该站未曾设置keywords

网站描述

聚焦于个人的学习与成长历程，旨在系统记录在后端开发、数据库等领域的探索与实践。

上一篇：管控平台

下一篇：天津办公家具

网站快照

E t h a n W e e e E t h a n W e e e 首 页 分 类 归 档 搜 索 0 % 内 存 优 化 数 据 库 中 的 冷 数 据 管 理 发 表 于 2 0 2 5 0 4 0 6 更 新 于 2 0 2 5 0 6 2 0 分 类 于 高 级 数 据 存 储 摘 要 该 论 文 解 决 了 两 个 问 题 ： 如 何 将 记 录 迁 移 到 冷 存 储 以 及 从 冷 存 储 迁 出 。 如 何 以 事 务 一 致 的 方 式 读 取 和 更 新 冷 存 储 中 的 记 录 。 论 文 提 出 了 三 个 新 颖 的 想 法 ， 并 详 细 阐 述 了 每 个 想 法 的 实 现 方 法 ： 统 一 的 接 口 ， 向 高 层 隐 藏 记 录 的 物 理 位 置 ： 通 过 冷 存 储 、 访 问 过 滤 器 、 私 有 缓 存 和 更 新 备 忘 录 之 间 的 协 作 实 现 。 最 小 化 访 问 二 级 存 储 带 来 的 开 销 ： 每 个 事 务 拥 有 自 己 的 私 有 缓 存 。 热 存 储 与 冷 存 储 之 间 的 无 缝 迁 移 ： 系 统 在 事 务 中 使 用 插 入 和 删 除 操 作 执 行 迁 移 。 分 析 与 实 验 结 果 ： 论 文 在 Y C S B 基 准 测 试 和 多 步 骤 读 / 更 新 工 作 负 载 上 评 估 了 S i b e r i a 的 性 能 ， 得 出 以 下 结 论 。 在 现 实 的 客 户 端 延 迟 下 ， 吞 吐 量 损 失 仅 为 3 % 。 即 使 在 极 高 的 冷 数 据 访 问 率 下 ， 内 存 中 的 S i b e r i a 机 制 也 仅 带 来 较 低 的 性 能 损 失 。 当 实 时 迁 移 激 活 时 ， 系 统 性 能 保 持 稳 定 。 访 问 备 忘 录 的 开 销 较 大 ， 这 意 味 着 备 忘 录 清 理 对 于 提 高 性 能 很 重 要 。 在 冷 数 据 访 问 率 为 5 % 和 1 0 % 的 现 实 场 景 下 ， 只 读 事 务 的 性 能 损 失 分 别 为 7 % 和 1 4 % ， 这 是 可 接 受 的 。 对 于 纯 更 新 事 务 ， 5 % 的 冷 数 据 更 新 导 致 8 % 的 吞 吐 量 损 失 ， 1 0 % 的 冷 数 据 更 新 率 导 致 1 3 % 的 吞 吐 量 损 失 ， 同 样 可 接 受 。 在 Y C S B 工 作 负 载 下 ， 随 着 访 问 偏 斜 度 降 低 以 及 内 存 与 数 据 库 大 小 比 例 增 加 ， 性 能 会 下 降 ； 与 写 密 集 型 工 作 负 载 相 比 ， 读 密 集 型 工 作 负 载 在 更 高 的 偏 斜 率 下 表 现 出 更 低 的 事 务 中 止 率 。 论 文 优 势 论 文 提 供 了 全 面 的 文 献 综 述 。 在 H E K A T O N 存 储 与 索 引 部 分 ， 论 文 简 要 概 述 了 H E K A T O N 的 索 引 和 数 据 存 储 结 构 及 其 基 于 M V C C （ 多 版 本 并 发 控 制 ） 的 读 写 操 作 。 在 R E L A T E D W O R K 部 分 ， 论 文 分 析 了 现 有 数 据 库 系 统 如 何 处 理 冷 数 据 ， 解 释 了 H y p e r 使 用 虚 拟 页 管 理 冷 数 据 ， S t o i c a 等 人 提 出 将 热 冷 数 据 分 离 到 不 同 的 内 存 位 置 。 最 后 ， 论 文 描 述 了 反 缓 存 （ a n t i c a c h i n g ） 的 工 作 原 理 ， 并 指 出 了 其 两 个 缺 点 ： 节 省 空 间 有 限 和 重 复 执 行 。 论 文 详 细 描 述 了 将 S I B E R I A 集 成 到 H E K A T O N 后 的 工 作 原 理 。 它 展 示 了 数 据 迁 移 到 冷 存 储 期 间 使 用 的 两 种 事 务 的 工 作 流 程 。 插 入 和 更 新 操 作 确 保 数 据 被 放 入 热 存 储 ， 以 避 免 检 查 冷 存 储 的 开 销 。 删 除 和 读 取 操 作 利 用 更 新 备 忘 录 中 的 通 知 执 行 并 发 控 制 和 冲 突 检 测 。 冷 存 储 清 理 也 由 更 新 备 忘 录 驱 动 ， 这 使 得 可 以 及 时 从 冷 存 储 中 移 除 对 任 何 活 跃 事 务 都 不 可 见 的 记 录 。 此 外 ， 验 证 阶 段 也 利 用 更 新 备 忘 录 中 的 通 知 ， 并 计 算 T s B o u n d S e r 以 确 保 可 串 行 化 事 务 的 正 确 性 ， 从 而 增 强 了 幻 读 检 测 。 论 文 呈 现 了 相 对 全 面 的 实 验 。 实 验 基 于 Y C S B 基 准 测 试 和 多 步 骤 读 / 更 新 工 作 负 载 ， 这 可 以 测 试 S i b e r i a 在 不 同 工 作 负 载 下 的 性 能 。 此 外 ， 论 文 评 估 了 S i b e r i a 的 纯 内 存 开 销 、 运 行 实 时 迁 移 的 开 销 以 及 访 问 冷 记 录 路 径 上 更 新 备 忘 录 的 开 销 。 并 且 ， 在 Y C S B 工 作 负 载 下 ， 展 示 了 工 作 负 载 偏 斜 度 、 内 存 与 数 据 库 大 小 比 率 与 工 作 负 载 性 能 之 间 的 关 系 。 论 文 不 足 论 文 未 在 代 码 层 面 描 述 S i b e r i a 集 成 到 H E K A T O N 的 过 程 ， 仅 提 到 了 在 数 据 处 理 和 存 储 机 制 层 面 进 行 集 成 。 它 详 细 描 述 了 冷 数 据 迁 移 过 程 ， 并 解 释 了 插 入 、 删 除 、 读 取 和 更 新 操 作 中 的 更 新 备 忘 录 通 知 如 何 与 H E K A T O N 的 版 本 控 制 和 并 发 控 制 协 作 。 然 而 ， 论 文 未 涉 及 S i b e r i a 如 何 在 代 码 层 面 （ 如 识 别 核 心 函 数 、 代 码 段 及 相 应 修 改 ） 集 成 到 H E K A T O N 。 这 一 缺 失 使 得 读 者 难 以 轻 松 复 现 S i b e r i a 。 因 此 ， 论 文 至 少 应 提 供 代 码 修 改 的 概 要 说 明 。 在 S y n t h e t i c E n d t o E n d W o r k l o a d 部 分 ， 论 文 未 讨 论 中 等 至 高 冷 数 据 访 问 率 下 的 吞 吐 量 损 失 。 论 文 仅 展 示 了 在 5 % 和 1 0 % 冷 数 据 访 问 率 下 的 吞 吐 量 损 失 ， 并 声 称 这 些 是 现 实 的 冷 数 据 访 问 率 。 首 先 ， 在 R e a d O n l y T r a n s a c t i o n s 部 分 ， 论 文 未 能 说 明 是 哪 个 报 告 或 文 献 支 持 5 % 和 1 0 % 是 “ 真 实 的 冷 数 据 访 问 率 ” 。 其 次 ， 即 使 假 设 上 述 数 据 是 准 确 的 ， 论 文 也 未 描 述 当 冷 数 据 访 问 率 超 过 1 0 % 时 ， 吞 吐 量 损 失 如 何 变 化 。 这 一 缺 失 使 读 者 无 法 全 面 了 解 S i b e r i a 处 理 工 作 负 载 的 性 能 。 因 此 ， 论 文 应 解 释 “ 现 实 的 冷 数 据 访 问 率 ” 是 如 何 确 定 的 ， 并 描 述 在 中 等 至 高 冷 数 据 访 问 率 下 吞 吐 量 损 失 的 变 化 情 况 。 论 文 未 讨 论 S i b e r i a 的 性 能 限 制 或 其 性 能 可 能 下 降 的 条 件 ， 尽 管 实 验 部 分 展 示 了 令 人 印 象 深 刻 的 性 能 。 这 种 优 异 的 性 能 可 能 是 以 高 硬 件 利 用 率 （ 如 高 C P U 使 用 率 ） 为 代 价 获 得 的 。 或 者 ， 将 S i b e r i a 集 成 到 H E K A T O N 中 虽 然 增 强 了 热 冷 数 据 处 理 能 力 ， 但 可 能 损 害 了 H E K A T O N 原 有 的 某 些 特 性 。 因 此 ， 论 文 应 阐 明 S i b e r i a 性 能 可 能 下 降 的 情 形 。 参 考 文 献 : h t t p s : / / w w w . v l d b . o r g / p v l d b / v o l 7 / p 9 3 1 e l d a w y . p d f T i c T o c 发 表 于 2 0 2 5 0 3 1 8 更 新 于 2 0 2 5 0 6 2 0 分 类 于 高 级 数 据 存 储 摘 要 本 文 解 决 了 一 个 核 心 问 题 ： 如 何 设 计 一 种 高 效 的 并 发 控 制 算 法 ， 以 提 升 O L T P 数 据 库 管 理 系 统 在 多 核 环 境 下 的 可 扩 展 性 ？ 本 文 提 出 了 4 个 新 颖 的 想 法 ， 并 详 细 阐 述 了 每 个 想 法 的 实 现 方 案 ： T i c T o c 算 法 ： 在 乐 观 并 发 控 制 ( O C C ) 基 础 上 实 现 。 其 核 心 在 于 事 务 的 时 间 戳 将 延 迟 到 提 交 时 刻 ， 根 据 该 事 务 处 理 的 所 有 元 组 进 行 计 算 。 这 种 方 式 也 提 高 了 并 行 性 。 验 证 阶 段 的 无 等 待 锁 定 ( N o w a i t l o c k i n g i n v a l i d a t i o n p h a s e ) ： 如 果 事 务 无 法 为 其 写 集 ( w r i t e s e t ) 中 的 某 个 元 组 获 取 锁 ， 验 证 阶 段 将 立 即 中 止 。 T i c T o c 会 在 等 待 一 段 时 间 后 重 启 该 阶 段 。 抢 占 式 中 止 ( P r e e m p t i v e a b o r t s ) ： 基 于 一 个 近 似 的 提 交 时 间 戳 以 及 元 组 的 本 地 读 时 间 戳 ( r t s ) 和 写 时 间 戳 ( w t s ) ， 可 以 在 锁 定 写 集 中 的 元 组 之 前 就 判 断 是 否 应 中 止 该 事 务 。 时 间 戳 历 史 记 录 ( T i m e s t a m p h i s t o r y ) ： 当 读 取 的 元 组 的 本 地 读 时 间 戳 ( r t s ) 低 于 事 务 的 c o m m i t _ t s ， 且 其 写 时 间 戳 ( w t s ) 与 最 新 w t s 不 同 时 ， 会 进 一 步 检 查 该 元 组 的 历 史 缓 冲 区 ( h i s t o r y b u f f e r ) ， 以 决 定 是 否 启 动 验 证 阶 段 。 分 析 与 实 验 结 果 ： 本 文 比 较 了 五 种 算 法 ： T i c T o c , S i l o , H E K A T O N , D L _ D E T E C T 和 N O _ W A I T 。 T P C C 结 果 ： 在 4 仓 规 模 下 ， T i c T o c 实 现 了 最 高 的 吞 吐 量 ， 且 中 止 率 低 于 S i l o 。 随 着 仓 数 增 加 ， T i c T o c 的 吞 吐 量 最 终 在 约 8 0 仓 时 被 S i l o 超 越 ， 但 其 中 止 率 仍 低 于 S i l o 。 Y C S B 结 果 ： 处 理 只 读 事 务 时 ， T i c T o c 的 吞 吐 量 与 S i l o 接 近 ， 并 高 于 其 他 算 法 。 在 中 等 竞 争 条 件 下 处 理 读 写 事 务 时 ， T i c T o c 的 吞 吐 量 与 S i l o 相 当 ， 但 其 中 止 率 显 著 低 于 S i l o 、 H E K A T O N 和 N O _ W A I T 。 在 高 竞 争 条 件 下 ， T i c T o c 的 吞 吐 量 远 超 S i l o ， 尽 管 其 中 止 率 变 得 与 S i l o 更 为 接 近 。 优 化 测 试 ： 表 明 大 部 分 性 能 提 升 来 源 于 无 等 待 锁 定 和 抢 占 式 中 止 。 此 外 ， T i c T o c 的 时 间 戳 增 长 速 度 远 低 于 T S _ A L L O C 。 隔 离 级 别 影 响 ： 当 隔 离 级 别 降 低 时 ， T i c T o c 显 示 出 吞 吐 量 的 提 升 和 中 止 率 的 下 降 ， 但 这 些 变 化 的 程 度 与 其 他 算 法 相 比 并 不 显 著 。 论 文 优 势 背 景 与 问 题 阐 述 清 晰 ： 论 文 清 晰 地 描 述 了 背 景 知 识 和 待 解 决 的 问 题 。 它 详 细 阐 述 了 二 阶 段 锁 ( 2 P L ) 策 略 的 弱 点 ， 并 指 出 基 于 时 间 戳 排 序 ( T / O ) 的 策 略 （ 如 M V C C 和 O C C ） 已 逐 渐 成 为 主 流 。 接 着 指 出 传 统 T / O 算 法 中 集 中 式 时 间 戳 分 配 器 ( c e n t r a l i z e d t i m e s t a m p a l l o c a t o r ) 和 C P U 的 缓 存 一 致 性 协 议 ( c a c h e c o h e r e n c e p r o t o c o l ) 导 致 了 时 间 戳 分 配 瓶 颈 。 此 外 ， 文 中 提 到 的 所 有 硬 件 解 决 方 案 均 未 能 完 美 契 合 大 多 数 现 代 C P U 的 架 构 ， 即 使 实 现 其 性 能 也 欠 佳 。 论 文 还 简 要 描 述 了 O C C 的 执 行 阶 段 ， 并 介 绍 了 两 种 基 于 O C C 的 优 化 方 法 （ 即 D T A 和 S i l o ） ， 同 时 指 出 这 两 种 方 案 仍 存 在 可 扩 展 性 瓶 颈 。 为 解 决 这 些 问 题 ， 论 文 提 出 了 T i c T o c 算 法 。 核 心 流 程 描 述 详 实 ： 论 文 为 T i c T o c 算 法 的 核 心 流 程 提 供 了 代 码 、 图 表 和 示 例 ， 使 读 者 能 快 速 理 解 实 现 细 节 和 工 作 流 程 。 在 3 . 2 节 ， 论 文 展 示 了 读 取 阶 段 ( R e a d P h a s e ) 、 验 证 阶 段 ( V a l i d a t i o n P h a s e ) 和 写 入 阶 段 ( W r i t e P h a s e ) 的 伪 代 码 ， 清 晰 地 说 明 了 其 设 计 如 何 应 对 并 发 和 并 行 场 景 下 的 冲 突 ， 以 及 分 布 式 时 间 戳 分 配 。 在 3 . 6 节 ， 论 文 展 示 了 用 于 存 储 读 / 写 时 间 戳 的 结 构 ， 并 通 过 伪 代 码 有 效 地 呈 现 了 解 决 d e l t a 属 性 潜 在 溢 出 问 题 的 方 案 。 在 3 . 3 节 ， 论 文 提 供 了 一 个 交 错 执 行 事 务 的 示 例 ， 并 辅 以 条 形 图 ， 清 晰 地 展 示 了 T i c T o c 在 处 理 并 发 和 并 行 挑 战 时 的 高 灵 活 性 和 性 能 。 实 验 评 估 全 面 ： 论 文 在 D B x 1 0 0 0 上 对 T i c T o c 进 行 了 全 面 的 实 验 评 估 。 在 T P C C 和 Y C S B 场 景 下 评 估 了 T i c T o c 的 性 能 。 比 较 了 在 不 同 竞 争 级 别 和 不 同 仓 数 下 ， T i c T o c 与 S i l o 、 H E K A T O N 、 D L _ D E T E C T 、 N O _ W A I T 的 吞 吐 量 和 中 止 率 。 评 估 了 T i c T o c 各 项 优 化 的 效 果 ， 强 调 了 无 等 待 锁 定 和 抢 占 式 中 止 对 性 能 提 升 的 贡 献 。 比 较 了 T i c T o c 的 时 间 戳 增 长 速 率 与 线 性 时 间 戳 增 长 速 率 。 比 较 了 在 不 同 隔 离 级 别 下 ， T i c T o c 与 其 他 4 种 算 法 在 吞 吐 量 和 中 止 率 上 的 差 异 。 论 文 不 足 集 成 过 程 缺 失 ： 论 文 未 展 示 将 T i c T o c 集 成 到 D B x 1 0 0 0 的 过 程 。 作 为 一 个 并 发 控 制 算 法 ， T i c T o c 必 须 与 其 他 关 键 组 件 （ 如 事 务 、 索 引 、 日 志 ） 交 互 ， 这 涉 及 大 量 工 作 。 然 而 ， 论 文 未 涉 及 此 方 面 ， 使 读 者 难 以 复 现 该 算 法 。 因 此 ， 论 文 至 少 应 简 要 概 述 必 要 的 集 成 步 骤 ， 以 帮 助 读 者 实 现 此 功 能 。 普 适 性 验 证 不 足 ： 论 文 的 实 验 未 能 证 明 T i c T o c 在 多 种 数 据 库 上 的 通 用 性 。 评 估 仅 在 D B x 1 0 0 0 环 境 中 进 行 ， 因 此 仅 证 实 了 T i c T o c 在 D B x 1 0 0 0 内 的 高 性 能 。 但 许 多 商 用 数 据 库 （ 如 S Q L S e r v e r 、 M y S Q L 等 ） 在 不 同 工 作 负 载 下 表 现 出 不 同 的 特 性 ， 这 可 能 导 致 使 用 T i c T o c 时 性 能 表 现 各 异 。 然 而 ， 论 文 对 此 方 面 完 全 未 提 及 。 因 此 ， 论 文 还 应 包 含 T i c T o c 在 这 些 主 流 数 据 库 上 的 集 成 和 测 试 工 作 。 关 键 优 化 细 节 缺 失 ： 论 文 在 关 键 的 O P T I M I Z A T I O N S 章 节 中 ， 未 能 为 某 些 关 键 概 念 提 供 代 码 或 详 细 解 释 。 根 据 实 验 结 果 ， 无 等 待 锁 定 和 抢 占 式 中 止 带 来 了 显 著 的 性 能 提 升 。 然 而 ， 优 化 部 分 并 未 呈 现 任 何 相 关 代 码 。 例 如 ， 在 N o W a i t L o c k i n g i n V a l i d a t i o n P h a s e 小 节 ， 论 文 既 未 阐 明 给 定 上 下 文 中 抖 动 问 题 ( t h r a s h i n g p r o b l e m s ) 的 具 体 含 义 ， 也 未 展 示 无 等 待 锁 定 的 代 码 ， 或 指 出 其 相 对 于 原 始 T i c T o c 实 现 的 修 改 之 处 。 因 此 ， 论 文 应 包 含 优 化 代 码 以 及 对 相 关 概 念 的 解 释 。 参 考 文 献 : h t t p s : / / p e o p l e . c s a i l . m i t . e d u / s a n c h e z / p a p e r s / 2 0 1 6 . t i c t o c . s i g m o d . p d f 编 译 查 询 的 自 适 应 执 行 发 表 于 2 0 2 5 0 3 0 2 更 新 于 2 0 2 5 0 6 2 0 分 类 于 高 级 数 据 存 储 摘 要 该 论 文 解 决 了 三 个 问 题 ： 如 何 减 少 复 杂 但 快 速 查 询 的 编 译 时 间 ？ 如 何 减 少 极 大 查 询 的 编 译 时 间 ？ 如 何 减 少 首 次 传 入 查 询 的 编 译 时 间 ？ 论 文 提 出 了 两 个 新 颖 的 想 法 ， 并 详 细 阐 述 了 每 个 想 法 的 实 现 方 法 ： 自 适 应 执 行 ( A d a p t i v e e x e c u t i o n ) ： 对 于 特 定 的 查 询 流 水 线 （ p i p e l i n e ） ， 该 方 案 跟 踪 工 作 线 程 的 进 度 ， 基 于 流 水 线 中 所 有 线 程 的 整 体 状 态 预 测 三 种 执 行 模 式 下 剩 余 工 作 负 载 的 持 续 时 间 ， 最 终 选 择 持 续 时 间 最 短 的 模 式 应 用 于 所 有 线 程 。 快 速 字 节 码 解 释 ( F a s t b y t e c o d e i n t e r p r e t a t i o n ) ： 基 于 寄 存 器 机 器 ， 该 方 案 通 过 按 区 间 （ i n t e r v a l s ） 处 理 基 本 块 （ b a s i c b l o c k ） 并 利 用 并 查 集 （ d i s j o i n t s e t ） 和 路 径 压 缩 （ p a t h c o m p r e s s i o n ） 等 算 法 ， 实 现 了 线 性 时 间 的 活 性 计 算 （ l i v e n e s s c o m p u t a t i o n ） ， 从 而 进 一 步 优 化 了 寄 存 器 分 配 。 此 外 ， 字 节 码 解 释 器 的 行 为 与 生 成 的 机 器 码 等 效 ， 确 保 了 在 解 释 执 行 和 机 器 码 执 行 之 间 可 以 无 缝 切 换 。 分 析 与 实 验 结 果 ： 对 于 不 同 的 比 例 因 子 （ s c a l e f a c t o r s ） ， 自 适 应 执 行 能 够 切 换 到 具 有 最 优 性 能 的 模 式 ， 确 保 相 比 其 他 静 态 模 式 选 择 具 有 最 低 的 执 行 时 间 。 在 行 动 方 面 ， 自 适 应 执 行 能 够 立 即 在 所 有 可 用 工 作 线 程 上 开 始 处 理 流 水 线 分 片 （ p i p e l i n e m o r s e l s ） ， 并 对 工 作 负 载 繁 重 的 流 水 线 进 行 动 态 模 式 切 换 ， 使 其 完 成 查 询 的 速 度 比 竞 争 对 手 快 1 0 % 、 4 0 % 和 8 0 % 。 虽 然 解 释 执 行 的 代 码 比 编 译 后 的 代 码 慢 ， 但 它 比 P o s t g r e S Q L 快 ， 并 且 在 使 用 多 核 时 能 像 编 译 代 码 一 样 扩 展 。 此 外 ， 字 节 码 解 释 器 具 有 完 美 的 扩 展 性 ， 能 够 在 短 时 间 内 处 理 大 型 查 询 。 论 文 优 势 论 文 清 晰 详 尽 地 描 述 了 待 解 决 的 问 题 。 在 第 二 节 中 ， 通 过 流 程 图 展 示 了 S Q L 查 询 在 H y P e r 中 的 多 步 骤 处 理 过 程 ， 并 强 调 L L V M 编 译 任 务 占 据 了 总 执 行 时 间 的 大 部 分 。 通 过 比 较 在 比 例 因 子 1 的 T P C H Q u e r y 1 上 不 同 执 行 模 式 的 编 译 和 执 行 时 间 ， 论 文 引 入 了 解 释 器 和 编 译 器 之 间 的 权 衡 ， 论 证 了 可 以 对 同 一 查 询 的 不 同 部 分 应 用 不 同 的 执 行 模 式 。 此 外 ， 论 文 分 析 了 最 大 的 T P C H 和 T P C D S 查 询 ， 得 出 结 论 ： 编 译 时 间 随 查 询 规 模 呈 超 线 性 增 长 。 论 文 提 供 了 全 面 的 文 献 综 述 。 在 第 六 节 中 ， 引 用 了 其 他 关 于 编 译 时 间 的 研 究 论 文 中 的 实 验 结 果 ， 得 出 结 论 ： 编 译 到 L L V M 中 间 表 示 （ I R ） 比 编 译 到 C 语 言 更 快 。 基 于 实 践 经 验 ， 论 文 强 调 查 询 编 译 延 迟 在 生 产 环 境 中 成 为 一 个 主 要 问 题 ， 这 使 得 自 适 应 执 行 成 为 使 查 询 编 译 真 正 实 用 化 的 关 键 组 件 。 随 后 探 讨 了 将 自 适 应 执 行 集 成 到 M e m S Q L 、 L e g o B a s e 和 M i c r o s o f t H e k a t o n 等 数 据 库 系 统 中 的 可 行 性 。 此 外 ， 论 文 展 示 了 自 适 应 执 行 相 对 于 自 动 计 划 缓 存 （ a u t o m a t i c p l a n c a c h i n g ） 的 优 势 ， 即 能 够 在 每 次 执 行 时 重 新 优 化 查 询 。 最 后 ， 讨 论 了 自 适 应 执 行 与 编 程 语 言 中 执 行 引 擎 （ 如 J V M 、 V 8 和 C L R ） 的 异 同 。 论 文 取 得 了 显 著 的 改 进 ， 即 线 性 时 间 的 活 性 计 算 。 传 统 逐 个 基 本 块 计 算 活 性 的 解 决 方 案 通 常 需 要 $ O ( n ^ 2 ) $ 的 运 行 时 间 。 然 而 ， 论 文 提 出 了 一 种 线 性 时 间 算 法 。 该 算 法 以 逆 后 序 （ r e v e r s e p o s t o r d e r ） 标 记 所 有 基 本 块 并 将 其 组 织 成 支 配 树 （ d o m i n a t o r t r e e ） ， 这 使 得 解 释 器 能 够 在 $ O ( 1 ) $ 时 间 内 确 定 基 本 块 之 间 的 关 系 ， 并 为 识 别 循 环 铺 平 了 道 路 。 它 通 过 使 用 带 路 径 压 缩 的 并 查 集 （ d i s j o i n t s e t w i t h p a t h c o m p r e s s i o n ） 来 识 别 每 个 基 本 块 的 最 内 层 封 闭 循 环 （ i n n e r m o s t e n c l o s i n g l o o p ） ， 并 基 于 与 某 个 值 的 定 义 和 使 用 相 关 的 基 本 块 分 布 来 确 定 该 值 的 生 命 周 期 。 该 计 算 的 低 成 本 主 要 归 功 于 采 用 了 适 当 的 数 据 结 构 。 论 文 不 足 论 文 未 清 晰 解 释 基 本 概 念 。 在 第 二 节 中 ， 没 有 解 释 延 迟 和 吞 吐 量 在 H y P e r 上 下 文 中 的 具 体 含 义 ， 以 及 两 者 之 间 的 关 系 ， 因 此 读 者 可 能 无 法 认 识 到 权 衡 的 重 要 性 ， 也 可 能 不 理 解 后 续 实 验 结 果 中 性 能 提 升 是 如 何 实 现 的 。 例 如 ， 读 者 可 能 无 法 理 解 为 什 么 解 释 器 能 通 过 牺 牲 吞 吐 量 来 实 现 非 常 低 的 延 迟 。 因 此 ， 论 文 应 解 释 这 些 概 念 。 论 文 的 实 验 不 够 全 面 。 作 为 数 据 处 理 和 存 储 的 核 心 组 件 ， 自 适 应 执 行 框 架 仅 被 证 明 在 执 行 时 间 上 具 有 优 势 ， 而 缺 乏 展 示 其 物 理 设 备 利 用 率 、 稳 定 性 和 故 障 恢 复 性 能 的 实 验 。 这 些 指 标 对 于 评 估 框 架 的 整 体 性 能 同 样 至 关 重 要 。 例 如 ， 对 于 同 一 组 查 询 ， 如 果 执 行 时 间 短 但 C P U 和 内 存 使 用 率 极 高 ， 或 者 抛 出 异 常 的 概 率 高 且 需 要 大 量 时 间 进 行 故 障 恢 复 ， 那 么 该 框 架 仍 有 改 进 空 间 。 因 此 ， 论 文 应 包 含 这 些 指 标 的 实 验 结 果 。 论 文 未 详 细 解 释 如 何 翻 译 成 虚 拟 机 代 码 。 在 第 四 节 B 小 节 中 ， 论 文 提 到 被 归 约 （ s u b s u m e d ） 的 指 令 不 会 被 翻 译 ， 但 未 具 体 说 明 哪 些 类 型 的 指 令 会 被 归 约 ， 或 者 以 何 种 方 式 被 归 约 。 这 些 遗 漏 会 使 读 者 感 到 困 惑 ， 阻 碍 他 们 对 翻 译 伪 代 码 的 理 解 。 因 此 ， 论 文 应 解 释 归 约 指 令 背 后 的 原 理 。 参 考 文 献 : h t t p s : / / d b . i n . t u m . d e / ~ l e i s / p a p e r s / a d a p t i v e e x e c u t i o n . p d f O r c a 面 向 大 数 据 的 模 块 化 查 询 优 化 器 架 构 发 表 于 2 0 2 5 0 2 1 1 更 新 于 2 0 2 5 0 6 2 0 分 类 于 高 级 数 据 存 储 摘 要 本 文 解 决 了 两 个 问 题 ： 如 何 设 计 一 个 能 够 处 理 大 数 据 和 复 杂 分 析 查 询 ， 同 时 确 保 生 成 高 效 查 询 计 划 的 查 询 优 化 器 。 探 索 高 级 查 询 优 化 理 论 在 生 产 环 境 中 的 应 用 。 本 文 提 出 了 4 个 新 颖 的 想 法 ， 并 详 细 阐 述 了 每 个 想 法 的 实 现 方 法 ： 通 过 D X L 将 优 化 器 与 数 据 库 系 统 解 耦 ： 不 同 的 数 据 库 系 统 需 要 实 现 3 个 转 换 器 （ Q u e r y 2 D X L 、 M D P r o v i d e r 和 D X L 2 P l a n ） 来 支 持 O r c a 。 使 用 M e m o 和 组 哈 希 表 进 行 优 化 ： M e m o 中 的 每 个 组 存 储 给 定 操 作 的 所 有 逻 辑 等 价 表 达 式 （ 包 括 强 制 执 行 运 算 符 ） 。 组 哈 希 表 记 录 每 个 优 化 请 求 的 最 优 实 现 （ 即 最 佳 组 表 达 式 ） 。 在 查 询 优 化 期 间 ， 通 过 检 索 每 个 组 及 其 子 组 对 应 于 给 定 优 化 请 求 的 最 佳 组 表 达 式 （ b e s t G E x p r s ） ， 将 这 些 最 佳 G E x p r s 链 接 在 一 起 形 成 最 佳 执 行 计 划 。 利 用 作 业 依 赖 图 和 作 业 队 列 实 现 并 行 查 询 优 化 ： 如 果 一 个 组 当 前 正 在 处 理 一 个 优 化 作 业 ， 其 他 作 业 将 被 放 入 队 列 等 待 。 一 旦 作 业 完 成 ， 其 结 果 可 供 后 续 作 业 利 用 。 开 发 高 效 的 测 试 工 具 ： A M P E R e 用 于 捕 获 错 误 并 生 成 转 储 文 件 以 供 后 续 重 放 调 试 。 T A Q O 基 于 优 化 请 求 的 链 接 结 构 均 匀 采 样 计 划 ， 并 通 过 计 算 基 于 估 计 成 本 的 采 样 计 划 排 序 与 基 于 实 际 成 本 的 排 序 之 间 的 相 关 性 得 分 ， 来 评 估 优 化 器 的 准 确 性 。 分 析 与 实 验 结 果 ： 基 于 T P C D S 基 准 测 试 ， 使 用 有 限 的 查 询 集 测 试 了 G P D B 传 统 查 询 优 化 器 （ 1 1 1 个 查 询 ， M P P ） 和 O r c a ， 以 及 I m p a l a （ 3 1 个 查 询 ， H a d o o p ） 、 S t i n g e r （ 1 9 个 查 询 ， H a d o o p ） 、 P r e s t o （ 1 2 个 查 询 ， H a d o o p ） 和 H A W Q 。 结 果 表 明 ， 在 8 0 % 的 查 询 执 行 中 ， O r c a 的 性 能 匹 配 或 优 于 G P D B 优 化 器 。 对 于 1 4 个 查 询 ， O r c a 相 比 G P D B 优 化 器 实 现 了 至 少 1 0 0 0 倍 的 加 速 比 。 P r e s t o 在 所 有 测 试 条 件 下 均 未 能 处 理 任 何 T P C D S 查 询 ， 而 H A W Q 上 的 查 询 执 行 性 能 普 遍 优 于 I m p a l a 和 S t i n g e r 。 论 文 优 势 论 文 提 供 了 全 面 的 文 献 综 述 ， 并 涵 盖 了 理 解 O r c a 所 需 的 预 备 知 识 。 在 P R E L I M I N A R I E S 部 分 ， 论 文 简 要 分 析 了 G P D B ， 解 释 了 其 3 个 核 心 组 件 ： 主 节 点 （ m a s t e r ） 、 段 节 点 （ s e g m e n t s ） 和 互 联 层 （ i n t e r c o n n e c t l a y e r ） ； 阐 述 了 S Q L 和 查 询 优 化 器 如 何 集 成 到 H a d o o p 等 大 数 据 处 理 组 件 中 ； 并 分 析 了 由 O r c a 优 化 的 H A W Q 架 构 相 比 I m p a l a 和 P r e s t o 的 优 势 。 在 R E L A T E D W O R K 部 分 ， 论 文 介 绍 了 V o l c a n o 和 C a s c a d e s 框 架 ， 强 调 C a s c a d e s 比 V o l c a n o 提 供 了 更 大 的 灵 活 性 ； 随 后 讨 论 了 M P P 数 据 库 中 各 种 面 向 大 数 据 的 查 询 优 化 器 实 现 ， 如 P D W 和 S C O P E ； 最 后 回 顾 了 将 S Q L 与 H a d o o p 集 成 的 现 有 努 力 ， 例 如 将 查 询 转 换 为 M a p R e d u c e 作 业 （ H i v e ） 以 及 数 据 库 管 理 系 统 与 H a d o o p 技 术 的 共 置 （ H a d a p t ） 。 论 文 提 出 了 针 对 大 数 据 查 询 优 化 的 极 具 价 值 的 解 决 方 案 ： D X L 和 并 行 查 询 优 化 。 不 同 的 数 据 库 只 需 实 现 各 自 的 Q u e r y 2 D X L 和 D X L 2 P l a n 转 换 器 即 可 实 现 与 O r c a 的 兼 容 ， 这 赋 予 了 O r c a 适 配 任 何 现 有 数 据 库 系 统 的 潜 力 。 为 满 足 大 数 据 的 核 心 需 求 — — 并 发 处 理 ， O r c a 构 建 了 优 化 作 业 依 赖 图 来 确 定 作 业 间 的 依 赖 关 系 。 父 作 业 必 须 在 其 子 作 业 完 成 后 才 能 执 行 ， 而 独 立 的 作 业 可 以 并 行 运 行 。 为 处 理 资 源 争 用 ， O r c a 将 传 入 的 作 业 放 入 作 业 队 列 中 等 待 ， 直 到 正 在 运 行 的 作 业 完 成 。 这 些 等 待 的 作 业 随 后 可 以 利 用 已 完 成 作 业 生 成 的 结 果 。 论 文 在 Q U E R Y O P T I M I Z A T I O N 部 分 详 细 阐 述 了 O r c a 优 化 的 步 骤 。 在 探 索 （ E x p l o r a t i o n ） 阶 段 ， O r c a 创 建 逻 辑 等 价 表 达 式 并 使 用 M e m o 进 行 去 重 。 在 统 计 推 导 （ S t a t i s t i c s D e r i v a t i o n ） 阶 段 ， O r c a 估 算 M e m o 组 的 基 数 和 数 据 倾 斜 。 在 实 现 （ I m p l e m e n t a t i o n ） 阶 段 ， O r c a 生 成 逻 辑 表 达 式 的 物 理 实 现 。 在 优 化 （ O p t i m i z a t i o n ） 阶 段 ， 生 成 多 个 执 行 计 划 （ 必 要 时 包 含 强 制 执 行 运 算 符 ） ， 然 后 使 用 成 本 模 型 选 择 成 本 最 低 的 执 行 计 划 。 这 些 细 节 有 效 地 帮 助 读 者 对 O r c a 的 工 作 原 理 建 立 起 高 层 次 的 理 解 。 论 文 不 足 论 文 缺 乏 对 优 化 阶 段 如 何 计 算 执 行 计 划 成 本 的 描 述 。 具 体 而 言 ， 完 全 未 讨 论 成 本 模 型 ， 而 这 应 是 O r c a 的 核 心 功 能 。 这 一 点 在 处 理 大 数 据 和 无 共 享 架 构 （ s h a r e d n o t h i n g a r c h i t e c t u r e ） 时 尤 为 重 要 ， 此 处 的 成 本 模 型 可 能 不 同 于 S e l i n g e r 成 本 模 型 ， 需 要 纳 入 跨 多 个 工 作 节 点 的 协 调 和 通 信 成 本 ， 并 考 虑 网 络 带 宽 。 建 议 论 文 包 含 对 成 本 模 型 的 详 细 描 述 ， 并 讨 论 其 在 单 体 式 和 分 布 式 数 据 库 系 统 中 的 行 为 。 论 文 针 对 M P P 数 据 库 的 实 验 评 估 基 于 有 限 的 数 据 集 。 O r c a 仅 与 G P D B 传 统 查 询 优 化 器 使 用 1 1 9 个 查 询 进 行 了 比 较 。 无 论 是 查 询 数 量 还 是 被 比 较 的 M P P 数 据 库 优 化 器 的 数 量 都 不 足 以 令 人 信 服 地 证 明 O r c a 相 对 于 其 他 M P P 数 据 库 优 化 器 的 优 势 。 因 此 ， 实 验 应 进 行 更 广 泛 的 M P P 数 据 库 比 较 ， 例 如 与 A m a z o n R e d s h i f t 和 T e r a d a t a A s t e r 进 行 比 较 ， 以 提 供 更 全 面 的 评 估 。 论 文 的 实 验 未 反 映 O r c a 的 硬 件 利 用 率 ， 如 C P U 使 用 率 、 内 存 消 耗 等 。 O r c a 很 可 能 会 在 无 共 享 架 构 中 运 行 ， 它 将 跨 多 个 服 务 器 运 行 。 然 而 ， 在 生 产 环 境 中 ， 这 些 服 务 器 不 太 可 能 专 用 于 O r c a ， 包 括 O r c a 将 要 优 化 的 数 据 库 在 内 的 其 他 进 程 很 可 能 与 O r c a 运 行 在 同 一 台 服 务 器 上 。 如 果 O r c a 的 C P U 或 内 存 使 用 率 过 高 ， 可 能 会 对 这 些 数 据 库 的 查 询 执 行 以 及 其 他 应 用 程 序 的 性 能 产 生 负 面 影 响 。 这 种 影 响 可 能 在 多 台 服 务 器 上 累 积 ， 导 致 显 著 的 性 能 下 降 。 因 此 ， 论 文 还 应 包 含 对 O r c a 硬 件 资 源 消 耗 的 评 估 。 参 考 文 献 : h t t p s : / / d l . a c m . o r g / d o i / 1 0 . 1 1 4 5 / 2 5 8 8 5 5 5 . 2 5 9 5 6 3 7 查 询 优 化 发 表 于 2 0 2 5 0 1 3 0 更 新 于 2 0 2 5 0 6 2 5 分 类 于 高 级 数 据 存 储 查 询 优 化 是 构 建 高 性 能 数 据 库 管 理 系 统 时 最 困 难 的 部 分 之 一 ， 它 需 要 在 大 量 等 价 的 查 询 执 行 方 案 中 找 到 资 源 消 耗 最 小 的 那 个 方 案 。 其 核 心 目 标 是 以 某 种 成 本 函 数 衡 量 每 个 候 选 计 划 ， 并 选 择 估 算 成 本 最 低 的 计 划 。 查 询 优 化 的 首 要 目 标 就 是 在 可 行 的 计 划 中 选 出 “ 最 低 成 本 ” 的 一 个 ， 通 常 采 用 成 本 模 型 对 I / O 、 C P U 、 网 络 等 资 源 进 行 加 权 求 和 ， 得 出 一 个 标 量 成 本 值 ， 不 同 系 统 也 可 能 纳 入 缓 冲 区 命 中 率 、 并 行 度 等 额 外 因 素 。 成 本 评 估 在 关 系 型 数 据 库 的 * * 代 价 优 化 器 （ C o s t B a s e d O p t i m i z e r ） * * 中 ， 会 将 一 个 查 询 计 划 的 总 代 价 定 义 为 其 所 有 算 子 （ O p e r a t o r ） 估 算 代 价 的 累 加 ： C o s t o f P l a n = ∑ ( C o s t o f e a c h P l a n O p e r a t o r ) C o s t \ \ : o f \ \ : P l a n = \ \ s u m ( C o s t \ \ : o f \ \ : e a c h \ \ : P l a n \ \ : O p e r a t o r ) C o s t o f P l a n = ∑ ( C o s t o f e a c h P l a n O p e r a t o r ) 而 每 个 算 子 的 估 算 代 价 又 通 常 与 该 算 子 所 处 理 的 输 入 规 模 成 正 比 ： C o s t ( O p e r a t o r ) ∝ S i z e o f O p e r a t o r I n p u t C o s t ( O p e r a t o r ) \ \ p r o p t o S i z e \ \ : o f \ \ : O p e r a t o r \ \ : I n p u t C o s t ( O p e r a t o r ) ∝ S i z e o f O p e r a t o r I n p u t 以 上 两 条 公 式 构 成 了 代 价 估 算 的 基 础 ： 先 通 过 输 入 规 模 得 出 算 子 代 价 ， 然 后 累 加 得 到 整 个 执 行 计 划 的 成 本 。 接 下 来 ， 需 要 详 细 说 明 如 何 确 定 算 子 输 入 规 模 ， 以 及 如 何 基 于 选 取 性 （ S e l e c t i v i t y ） 估 算 非 基 表 算 子 的 输 出 规 模 。 对 于 基 表 扫 描 （ T a b l e S c a n ） 或 索 引 扫 描 （ I n d e x S c a n ） ， 输 入 规 模 通 常 等 于 表 或 索 引 在 磁 盘 上 的 物 理 存 储 量 （ 页 数 或 行 数 ） 。 [ ! N O T E ] 对 于 此 类 扫 描 操 作 ， 我 们 可 以 在 有 索 引 的 情 况 下 ， 可 将 过 滤 条 件 下 推 至 索 引 层 ， 只 读 取 满 足 谓 词 的 行 或 页 ， 以 减 少 输 入 规 模 和 I / O 操 作 ， 也 就 是 进 行 索 引 下 推 。 对 于 投 影 （ P r o j e c t ） 、 选 择 （ F i l t e r ） 等 算 子 ， 优 化 器 首 先 根 据 输 入 规 模 和 选 取 性 估 算 输 出 规 模 ； 连 接 （ J o i n ） 算 子 则 需 基 于 两 侧 子 计 划 的 输 出 规 模 与 连 接 选 取 性 共 同 计 算 其 输 出 规 模 ， 也 就 是 ： O u t p u t S i z e = S e l e c t i v i t y × ( ∣ L e f t ∣ × ∣ R i g h t ∣ ) O u t p u t \ \ : S i z e = S e l e c t i v i t y \ \ t i m e s ( | L e f t | \ \ t i m e s | R i g h t | ) O u t p u t S i z e = S e l e c t i v i t y × ( ∣ L e f t ∣ × ∣ R i g h t ∣ ) 选 取 性 （ S e l e c t i v i t y ） 是 算 子 发 出 数 据 量 与 接 收 数 据 量 之 比 ， 取 值 范 围 0 – 1 ， 表 示 谓 词 或 连 接 条 件 对 数 据 的 过 滤 强 度 。 O u t p u t S i z e = S e l e c t i v i t y × I n p u t S i z e O u t p u t \ \ : S i z e = S e l e c t i v i t y \ \ t i m e s I n p u t \ \ : S i z e O u t p u t S i z e = S e l e c t i v i t y × I n p u t S i z e 假 设 我 们 针 对 有 1 0 0 条 记 录 的 部 门 表 d e p t ， 1 0 0 0 0 条 记 录 的 职 员 表 e m p ， 3 0 0 0 0 条 记 录 的 儿 童 表 k i d s ， 执 行 如 下 S Q L 语 句 ： 1 2 3 4 5 S E L E C T * F R O M e m p , d e p t , k i d s W H E R E s a l > 1 0 0 0 0 A N D e m p . d n o = d e p t . d n o A N D e m p . e i d = k i d s . e i d ; 其 中 ， 每 1 0 0 条 记 录 是 一 个 页 面 ， 1 0 K B 是 一 个 页 面 的 大 小 ， 内 存 大 小 是 1 0 个 页 面 。 对 于 每 种 执 行 计 划 ， 我 们 可 以 进 行 如 下 步 骤 ： 第 一 步 ， 评 估 表 （ 关 系 ） 的 大 小 ： d e p t 只 有 1 0 0 条 记 录 ， 占 用 1 页 （ 1 0 K B / 页 ） ； e m p 有 1 0 0 0 0 条 记 录 ， 占 用 1 0 0 页 （ 1 0 K B / 页 ） ； k i d s 有 3 0 0 0 0 条 记 录 ， 占 用 3 0 0 页 （ 1 0 K B / 页 ） 。 第 二 步 ， 评 估 选 择 性 ： W H E R E s a l > 1 0 k 的 选 择 性 为 0 . 1 ； d e p t 和 e m p 的 J O I N 操 作 的 选 择 性 为 0 . 0 1 ， 产 生 结 果 集 A ； A 和 k i d s 的 J O I N 操 作 的 选 择 性 为 0 . 0 0 0 1 ， 产 生 结 果 B 。 第 三 步 ， 计 算 中 间 结 果 的 大 小 ， 如 下 执 行 计 划 树 所 示 ， 其 中 冒 号 右 边 的 数 据 为 此 次 操 作 得 到 的 结 果 集 的 大 小 ： 需 要 注 意 的 是 ， 整 棵 树 的 阅 读 顺 序 推 荐 从 叶 子 到 根 。 第 四 步 ， 评 估 各 个 执 行 计 划 的 成 本 并 选 出 最 低 的 。 以 上 只 是 一 个 简 单 的 流 程 ， 下 面 基 于 S e l i n g e r 等 人 提 出 的 S y s t e m R 成 本 优 化 器 框 架 给 出 每 个 步 骤 的 详 细 解 释 ， 该 框 架 迄 今 仍 被 主 流 关 系 型 数 据 库 （ 如 D B 2 、 P o s t g r e S Q L 、 M y S Q L 等 ） 沿 用 。 第 一 步 ， 评 估 关 系 的 大 小 ， 其 中 的 统 计 量 如 下 ： N C A R D ( T ) ： 关 系 T 的 基 数 ， 即 元 组 总 数 ； T C A R D ( T ) ： 关 系 T 所 占 用 的 数 据 页 数 ； I C A R D ( I ) ： 索 引 I 中 不 同 键 值 的 数 量 ； N I N D X ( I ) ： 索 引 I 在 磁 盘 上 占 用 的 页 数 。 [ ! N O T E ] 现 代 数 据 库 在 S y s t e m R 的 统 计 量 基 础 上 引 入 多 种 增 强 策 略 ： 直 方 图 （ H i s t o g r a m s ） 等 宽 直 方 图 （ E q u i w i d t h ） ： 将 值 域 划 分 为 固 定 宽 度 的 k 个 区 间 ， 区 间 内 数 据 不 均 匀 时 易 失 真 。 等 深 直 方 图 （ E q u i d e p t h ） ： 保 证 每 个 桶 内 的 元 组 数 近 似 相 同 ， 可 更 准 确 估 算 范 围 谓 词 。 最 常 见 值 列 表 （ F r e q u e n c y L i s t ） ： 维 护 出 现 频 率 最 高 的 m 个 键 值 及 其 频 率 分 布 ， 对 高 频 值 谓 词 （ 如 c o l I N ( … ) ） 提 供 精 确 估 算 。 聚 簇 因 子 （ C l u s t e r i n g F a c t o r ） ： 描 述 索 引 键 值 在 数 据 块 中 的 物 理 聚 集 度 ， 值 越 低 表 示 更 紧 密 的 簇 集 ， 有 助 于 优 化 随 机 v s 顺 序 I / O 的 成 本 估 算 。 分 区 增 量 统 计 ： 对 于 分 区 表 ， 会 为 每 个 分 区 单 独 收 集 统 计 信 息 ， 并 维 护 全 局 统 计 ， 通 过 分 区 修 剪 （ P a r t i t i o n P r u n i n g ） 显 著 降 低 查 询 开 销 。 分 层 采 样 ： 在 全 表 采 样 成 本 过 高 时 ， 数 据 库 可 基 于 分 区 或 分 层 样 本 抽 样 （ 如 1 % 分 区 样 本 ） ， 动 态 更 新 统 计 ， 同 时 避 免 全 表 扫 描 统 计 带 来 的 停 机 与 高 I / O 负 载 。 第 二 步 ， 评 估 选 择 性 ： 我 们 这 里 先 定 义 F 或 者 F ( p r e d ) = 谓 词 的 选 择 性 = 没 有 被 过 滤 掉 的 记 录 的 占 比 。 那 么 ， 对 于 等 值 谓 词 c o l = = v a l ： 若 有 索 引 ， 则 假 设 均 匀 分 布 ， 选 取 性 F = 1 / I C A R D F = 1 / I C A R D F = 1 / I C A R D ； 否 则 粗 略 取 1 / 1 0 。 对 于 范 围 谓 词 c o l > v a l 或 类 似 开 区 间 比 较 ： 若 有 索 引 ， 则 线 性 插 值 计 算 F = ( h i g h _ k e y − v a l ) / ( h i g h _ k e y − l o w _ k e y ) F = ( h i g h \ \ _ k e y \ \ : \ \ : v a l ) / ( h i g h \ \ _ k e y \ \ : \ \ : l o w \ \ _ k e y ) F = ( h i g h _ k e y − v a l ) / ( h i g h _ k e y − l o w _ k e y ) ； 否 则 取 1 / 3 。 对 于 列 间 相 等 谓 词 c o l 1 = c o l 2 ： 若 两 列 均 有 索 引 ， 取 两 索 引 基 数 （ I C A R D ） 较 大 值 的 倒 数 ： F = 1 m a x ( I C A R D ( c o l 1 ) , I C A R D ( c o l 2 ) ) F = \ \ f r a c ( c o l _ 1 ) , \ \ , \ \ t e x t ( c o l _ 2 ) \ \ b i g r ) } F = ​ m a x ( I C A R D ( c o l ​ 1 ​ ​ ) , I C A R D ( c o l ​ 2 ​ ​ ) ) ​ ​ 1 ​ ​ ； 若 只 有 单 列 有 索 引 ， 则 F = 1 / I C A R D F = 1 / I C A R D F = 1 / I C A R D ； 否 则 取 1 / 1 0 。 此 外 ， 在 查 询 中 常 有 多 重 谓 词 组 合 ， S e l i n g e r 优 化 器 使 用 以 下 规 则 在 逻 辑 优 化 和 成 本 估 算 阶 段 快 速 合 成 最 终 选 取 性 F ： 逻 辑 与 （ A N D ） ： F a n d = F ( p 1 ) × F ( p 2 ) F _ } = F ( p _ 1 ) \ \ , \ \ t i m e s \ \ , F ( p _ 2 ) F ​ a n d ​ ​ = F ( p ​ 1 ​ ​ ) × F ( p ​ 2 ​ ​ ) 逻 辑 或 （ O R ） ： F o r = 1 − F a n d = F ( p 1 ) + F ( p 2 ) − F ( p 1 ) F ( p 2 ) F _ } = 1 F _ } = F ( p _ 1 ) + F ( p _ 2 ) F ( p _ 1 ) \ \ , F ( p _ 2 ) F ​ o r ​ ​ = 1 − F ​ a n d ​ ​ = F ( p ​ 1 ​ ​ ) + F ( p ​ 2 ​ ​ ) − F ( p ​ 1 ​ ​ ) F ( p ​ 2 ​ ​ ) 逻 辑 非 （ N O T ） ： F n o t = 1 − F ( p ) F _ } = 1 F ( p ) F ​ n o t ​ ​ = 1 − F ( p ) 思 考 ： 为 什 么 等 值 谓 词 在 没 有 索 引 的 时 候 要 取 1 / 1 0 ？ 在 缺 乏 精 确 统 计 时 ， 优 化 器 宁 可 假 设 谓 词 对 数 据 的 过 滤 效 果 较 弱 （ 即 选 取 性 估 算 偏 大 ） ， 也 不 轻 易 假 设 它 过 滤 得 非 常 彻 底 。 如 果 低 估 谓 词 效 果 （ 认 为 它 能 过 滤 掉 更 多 行 ） ， 某 些 访 问 路 径 （ 如 索 引 扫 描 ） 看 起 来 成 本 极 低 ， 以 至 于 优 化 器 可 能 跳 过 对 其 他 方 案 的 评 估 ； 而 高 估 则 保 证 几 乎 所 有 可 行 方 案 都 被 保 留 用 于 比 较 ， 从 而 不 至 于 因 估 算 过 于 乐 观 而 错 过 实 测 可 能 更 优 的 计 划 。 假 设 有 两 种 访 问 e m p 表 的 方 案 ： 索 引 扫 描 + 连 接 ： 若 低 估 谓 词 效 果 （ 认 为 只 过 滤 1 % ） ， 算 出 极 低 的 中 间 行 数 ， 导 致 优 化 器 只 评 估 此 方 案 并 剪 掉 全 表 扫 描 方 案 。 高 估 策 略 （ 假 设 过 滤 1 0 % ） ： 使 得 索 引 扫 描 方 案 看 起 来 代 价 更 高 ， 全 表 扫 描 的 成 本 也 被 评 估 ， 优 化 器 才 会 真 正 比 较 两 者 。 最 终 在 实 际 运 行 中 ， 全 表 扫 描 + 哈 希 连 接 可 能 因 顺 序 I / O 更 快 而 胜 出 ， 但 若 一 开 始 就 剪 掉 它 ， 就 永 远 不 会 被 考 虑 。 第 三 步 ， 计 算 中 间 结 果 的 大 小 ， 该 步 骤 的 内 容 之 前 已 经 叙 述 过 。 第 四 步 ， 评 估 每 个 执 行 计 划 的 成 本 ： 在 基 于 成 本 的 优 化 器 中 ， 每 个 物 理 算 子 的 总 代 价 通 常 由 以 下 两 部 分 构 成 ： I / O 代 价 ： 以 读 取 页 面 的 次 数 为 单 位 ， 乘 以 相 应 的 I / O 权 重 （ 如 顺 序 读 取 s e q _ p a g e _ c o s t 或 随 机 读 取 r a n d o m _ p a g e _ c o s t ） 。 C P U 代 价 ： 以 处 理 记 录 或 执 行 谓 词 的 次 数 为 单 位 ， 乘 以 对 应 的 C P U 权 重 （ 如 c p u _ t u p l e _ c o s t 、 c p u _ o p e r a t o r _ c o s t ） 。 最 终 ， 优 化 器 对 算 子 代 价 取 页 读 次 数 与 记 录 处 理 次 数 的 线 性 组 合 来 估 算 ： C o s t = ( p a g e s   r e a d ) + W × ( r e c o r d s   e v a l u a t e d ) \ \ t e x t = ( \ \ t e x t ) + W \ \ t i m e s ( \ \ t e x t ) C o s t = ( p a g e s   r e a d ) + W × ( r e c o r d s   e v a l u a t e d ) ， 其 中 W 表 示 单 位 记 录 的 C P U 权 重 。 对 于 带 唯 一 索 引 的 等 值 谓 词 ， 访 问 路 径 通 常 为 ： B T r e e 索 引 查 找 ： 读 取 根 到 叶 的 路 径 上 若 干 索 引 页 （ 假 设 固 定 深 度 ） ， 通 常 记 为 “ 1 页 I / O ” 来 表 示 一 次 查 找 操 作 的 近 似 代 价 。 堆 表 行 定 位 （ H e a p F i l e l o o k u p ） ： 利 用 索 引 返 回 的 行 定 位 信 息 ， 再 读 取 对 应 数 据 页 ， 平 均 也 是 一 次 I / O 操 作 。 综 合 起 来 ， 此 算 子 的 总 代 价 可 表 示 为 ： 1   ( i n d e x   p a g e   r e a d ) + 1   ( d a t a   p a g e   r e a d ) + W   ( C P U ) 1 \ \ ( \ \ t e x t ) \ \ ; + \ \ ; 1 \ \ ( \ \ t e x t ) \ \ ; + \ \ ; W \ \ ( \ \ t e x t ) 1   ( i n d e x   p a g e   r e a d ) + 1   ( d a t a   p a g e   r e a d ) + W   ( C P U ) 。 该 模 型 假 设 索 引 组 织 为 聚 簇 或 近 似 聚 簇 结 构 ， 因 此 每 次 索 引 查 找 可 定 位 到 唯 一 一 条 记 录 。 对 于 聚 簇 索 引 的 范 围 扫 描 ， 算 子 需 扫 描 多 个 索 引 条 目 并 可 能 访 问 多 条 数 据 行 ， I / O 代 价 为 F × ( N I N D X + T C A R D ) F \ \ t i m e s ( \ \ t e x t + \ \ t e x t ) F × ( N I N D X + T C A R D ) ， C P U 代 价 为 W × ( t u p l e s   r e a d ) W \ \ t i m e s ( \ \ t e x t ) W × ( t u p l e s   r e a d ) ， 因 此 整 体 成 本 为 ： F × ( N I N D X + T C A R D ) + W × ( t u p l e s   r e a d ) F \ \ t i m e s ( \ \ t e x t + \ \ t e x t ) + W \ \ t i m e s ( \ \ t e x t ) F × ( N I N D X + T C A R D ) + W × ( t u p l e s   r e a d ) ， 其 中 N I N D X 为 索 引 页 数 ， T C A R D 为 表 的 总 页 数 ， F 为 谓 词 选 取 性 ； 每 个 匹 配 索 引 条 目 对 应 一 次 数 据 页 顺 序 I / O 。 对 于 非 聚 簇 索 引 的 范 围 扫 描 ， C P U 成 本 和 聚 簇 索 引 的 一 致 ， 但 是 I / O 成 本 为 F × ( N I N D X + N C A R D ) F \ \ t i m e s ( \ \ t e x t + \ \ t e x t ) F × ( N I N D X + N C A R D ) ， 因 此 整 体 成 本 为 ： F × ( N I N D X + N C A R D ) + W × ( t u p l e s   r e a d ) F \ \ t i m e s ( \ \ t e x t + \ \ t e x t ) + W \ \ t i m e s ( \ \ t e x t ) F × ( N I N D X + N C A R D ) + W × ( t u p l e s   r e a d ) ， 此 时 每 个 匹 配 条 目 都 可 能 落 在 不 同 的 数 据 页 上 ， 平 均 需 一 次 随 机 I / O ， 因 此 用 N C A R D （ 行 数 ） 来 近 似 页 数 。 对 于 分 段 顺 序 扫 描 ， 不 利 用 索 引 ， 需 读 取 表 的 所 有 页 并 评 估 所 有 行 ： C o s t = T C A R D + W × N C A R D \ \ t e x t = \ \ t e x t + W \ \ t i m e s \ \ t e x t C o s t = T C A R D + W × N C A R D ， 其 中 T C A R D 为 全 表 页 数 ， N C A R D 为 元 组 总 数 ； 顺 序 扫 描 的 I / O 可 享 有 预 取 （ p r e f e t c h ） 与 缓 冲 优 势 ， 故 只 计 算 页 面 读 取 的 总 数 。 接 着 ， 我 们 来 看 J O I N 的 成 本 计 算 ， 以 嵌 套 循 环 连 接 （ N e s t e d L o o p J o i n ） 为 例 。 它 的 总 代 价 公 式 ： C o s t N L J ( A , B ) = C o s t ( A ) + N C A R D ( A ) × C o s t ( B ) \ \ m a t h r m _ } ( A , B ) = \ \ m a t h r m ( A ) \ \ ; + \ \ ; \ \ m a t h r m ( A ) \ \ t i m e s \ \ m a t h r m ( B ) C o s t ​ N L J ​ ​ ( A , B ) = C o s t ( A ) + N C A R D ( A ) × C o s t ( B ) ， 其 中 A 为 外 层 计 划 ， B 为 内 层 基 表 ， N C A R D ( A ) 为 外 层 输 出 元 组 数 。 为 了 控 制 连 接 顺 序 的 枚 举 复 杂 度 ， S y s t e m R 优 化 器 仅 考 虑 左 深 树 ： 每 一 步 连 接 的 右 子 树 B 必 须 为 尚 未 使 用 的 基 表 ， 而 非 先 前 连 接 出 的 中 间 子 树 。 这 样 能 保 证 枚 举 过 程 中 只 需 维 护 基 表 之 间 的 累 积 连 接 ， 而 无 需 考 虑 更 复 杂 的 树 形 拓 扑 ， 大 幅 减 少 计 划 数 量 （ 从 $ O ( N ! ) $ 降 到 约 $ O ( 2 ^ N ) $ ) 。 [ ! N O T E ] 之 前 例 子 中 的 图 就 是 一 棵 左 深 树 。 对 于 谓 词 形 如 B . k e y = A . k e y ， 且 在 B 的 k e y 列 上 存 在 唯 一 或 聚 簇 索 引 ， 优 化 器 近 似 认 为 ： 一 次 B + T r e e 索 引 查 找 需 “ 1 页 ” I / O （ 从 根 到 叶 路 径 平 均 代 价 ） 。 根 据 索 引 返 回 的 行 定 位 信 息 ， 再 一 次 H e a p F i l e l o o k u p 也 需 “ 1 页 ” I / O 。 最 后 对 该 行 执 行 谓 词 或 投 影 等 操 作 ， 产 生 W 单 位 的 C P U 代 价 。 综 合 得 到 ： C o s t ( B ) = 1 + 1 + W \ \ m a t h r m ( B ) = 1 \ \ ; + \ \ ; 1 \ \ ; + \ \ ; W C o s t ( B ) = 1 + 1 + W ， 该 模 型 忽 略 了 缓 存 预 取 及 并 行 扫 描 等 复 杂 因 素 ， 但 其 简 洁 性 足 以 支 撑 海 量 计 划 的 快 速 比 较 。 若 内 层 无 可 用 索 引 ， 则 只 能 顺 序 扫 描 整 个 表 ： I / O 代 价 ： 需 读 取 T C A R D ( B ) 页 （ 表 在 磁 盘 上 的 总 页 数 ） ； C P U 代 价 ： 对 N C A R D ( B ) 条 元 组 逐 一 评 估 谓 词 和 产 生 输 出 ， 共 W × N C A R D ( B ) W \ \ t i m e s \ \ m a t h r m ( B ) W × N C A R D ( B ) 。 因 此 ： C o s t ( B ) = T C A R D ( B ) + W × N C A R D ( B ) \ \ m a t h r m ( B ) = \ \ m a t h r m ( B ) \ \ ; + \ \ ; W \ \ , \ \ t i m e s \ \ m a t h r m ( B ) C o s t ( B ) = T C A R D ( B ) + W × N C A R D ( B ) ， 该 模 型 同 样 简 化 了 缓 冲 与 批 量 读 写 等 优 化 手 段 ， 但 体 现 了 顺 序 扫 描 的 典 型 开 销 。 如 果 是 S o r t M e r g e J o i n 的 话 ， 代 价 模 型 ： C o s t = C o s t ( A ) + C o s t ( B ) + s o r t c o s t C o s t = C o s t ( A ) + C o s t ( B ) + s o r t \ \ : c o s t C o s t = C o s t ( A ) + C o s t ( B ) + s o r t c o s t C o s t ( A ) ： 外 层 子 计 划 （ 子 树 ） A 的 总 代 价 ； C o s t ( B ) ： 内 层 子 计 划 B （ 可 以 是 基 表 或 中 间 结 果 ） 的 总 代 价 ； s o r t c o s t ： 对 A 和 B 各 自 执 行 排 序 的 代 价 之 和 。 排 序 — 归 并 连 接 是 一 种 基 于 将 两 输 入 关 系 各 自 按 连 接 键 排 序 ， 随 后 线 性 归 并 扫 描 输 出 匹 配 对 的 算 法 。 阶 段 一 ： 排 序 （ S o r t ） 对 输 入 关 系 A 、 B 按 连 接 属 性 （ p r e d 中 指 定 的 字 段 ） 各 自 进 行 排 序 。 如 果 输 入 已 经 部 分 或 完 全 有 序 ， 则 可 跳 过 或 简 化 排 序 步 骤 。 阶 段 二 ： 归 并 （ M e r g e ） 维 护 两 个 游 标 ， 分 别 指 向 A 、 B 的 当 前 最 小 键 值 记 录 。 比 较 当 前 A 、 B 键 值 ： 若 A . k e y 若 A . k e y > B . k e y ， 则 将 B 游 标 前 移 ； 若 相 等 ， 则 输 出 所 有 相 同 键 值 的 配 对 （ 可 能 需 要 在 一 个 输 入 保 留 缓 冲 区 中 暂 存 重 复 键 值 ） ， 并 前 移 游 标 。 该 归 并 过 程 只 需 一 次 顺 序 扫 描 ， 两 边 各 推 进 ， 故 I / O 和 C P U 都 相 对 高 效 。 适 用 场 景 两 输 入 均 可 顺 序 访 问 或 已 排 序 ， 且 连 接 键 上 无 合 适 哈 希 索 引 时 最 优 ； 特 别 适 合 大 批 量 数 据 输 出 且 需 要 顺 序 结 果 的 场 景 。 如 果 后 续 操 作 涉 及 选 取 最 大 最 小 值 ， 那 么 最 好 使 用 S o r t M e r g e J o i n 先 得 出 排 序 后 的 J O I N 结 果 。 第 五 步 ， 选 出 成 本 最 低 的 执 行 计 划 ： 若 对 所 有 可 能 的 联 接 树 与 交 叉 产 品 一 一 枚 举 ， 计 划 数 目 将 呈 阶 乘 级 增 长 ， 无 法 承 受 。 S y s t e m R （ S e l i n g e r 优 化 器 ） 的 核 心 思 想 是 ， 通 过 启 发 式 剪 枝 大 幅 减 少 搜 索 空 间 ， 同 时 用 自 底 向 上 动 态 规 划 保 证 在 受 限 空 间 内 选 出 最 优 左 深 计 划 。 全 空 间 规 模 ： 对 n 个 基 表 ， 所 有 可 能 的 联 接 树 数 约 为 n ! （ 叶 深 树 ） 。 例 如 6 表 联 接 时 有 6 ! = 7 2 0 种 联 接 顺 序 ； 1 0 表 时 增 至 3 6 2 8 8 0 0 种 。 启 发 式 目 标 ： 在 保 证 生 成 足 够 优 质 计 划 的 前 提 下 ， 剪 掉 绝 大 多 数 计 划 ， 避 免 枚 举 交 叉 组 合 、 子 查 询 作 为 内 层 的 树 形 连 接 等 无 效 情 况 。 这 里 展 示 三 大 启 发 式 规 则 ： 谓 词 下 推 越 早 执 行 过 滤 谓 词 ， 可 最 大 程 度 减 少 后 续 算 子 的 输 入 规 模 与 I / O 或 C P U 代 价 。 在 构 建 执 行 计 划 时 ， 把 每 个 谓 词 $ \ \ s i g m a $ 尽 可 能 下 推 到 最 接 近 基 表 扫 描 或 索 引 扫 描 的 层 面 ， 不 把 过 滤 延 迟 到 后 面 再 算 。 避 免 笛 卡 尔 积 对 无 关 联 谓 词 的 表 进 行 笛 卡 尔 积 会 产 生 极 大 中 间 结 果 ， 通 常 不 可 接 受 。 仅 在 所 有 过 滤 条 件 均 已 消 耗 殆 尽 （ 即 查 询 本 质 需 要 交 叉 连 接 ） 时 ， 才 枚 举 产 生 交 叉 产 品 的 计 划 ； 否 则 只 枚 举 带 有 有 效 联 接 谓 词 的 表 对 。 仅 枚 举 左 深 树 在 左 深 树 中 ， 每 次 联 接 的 右 子 树 必 须 是 一 个 基 表 ， 而 不 能 是 先 前 联 接 所 得 的 中 间 子 树 。 这 样 可 以 使 得 搜 索 空 间 大 幅 缩 减 ： 从 全 空 间 的 O ( n ! ) 降 至 约 O ( 2 ⁿ ) 或 更 小 ； 以 及 流 水 线 执 行 ： 左 深 树 可 实 现 完 全 流 水 线 （ p i p e l i n i n g ） ， 中 间 结 果 无 需 写 入 磁 盘 临 时 表 ； 对 大 多 数 算 子 （ N L J 、 H a s h J o i n 、 M e r g e J o i n ） 均 适 用 。 自 底 向 上 的 动 态 规 划 以 上 的 三 种 启 发 式 规 则 带 来 的 提 升 有 限 ， 所 以 S y s t e m R 还 引 入 了 动 态 规 划 。 动 态 规 划 算 法 利 用 了 最 优 子 结 构 的 性 质 ： 如 果 在 所 有 包 含 关 系 集 的 计 划 中 ， 连 接 A 、 B 、 C 最 优 的 顺 序 是 ( A ⋈ B ) ⋈ C ， 那 么 无 论 这 个 三 表 子 集 在 更 大 计 划 中 如 何 出 现 ， ( A ⋈ B ) 必 然 是 的 最 优 子 计 划 之 一 ， 不 需 要 再 次 枚 举 . 由 于 子 计 划 不 依 赖 于 外 部 上 下 文 ， 其 最 优 性 是 全 局 性 的 ， 只 需 计 算 一 次 ， 即 可 复 用 到 所 有 包 含 该 子 集 的 更 大 计 划 中 。 这 一 思 想 即 “ 不 要 在 更 大 的 计 划 中 重 新 考 虑 子 计 划 ” 。 S y s t e m R 优 化 器 按 照 子 计 划 包 含 的 基 表 数 目 ， 从 小 到 大 分 层 枚 举 ： 第 1 轮 （ 1 表 计 划 ） ： 分 别 为 每 个 基 表 $ R _ i $ 选 择 成 本 最 低 的 访 问 路 径 （ 全 表 扫 描 或 索 引 扫 描 ） 并 记 录 其 成 本 与 输 出 行 数 。 第 2 轮 （ 2 表 计 划 ） ： 对 第 1 轮 中 的 每 个 单 表 计 划 P （ 作 为 外 层 ） ， 将 尚 未 使 用 的 每 个 基 表 $ R _ j $ 作 为 内 层 ， 计 算 连 接 成 本 ， 并 在 所 有 方 案 中 保 留 最 优 者 。 … 第 k 轮 （ k 表 计 划 ） ： 对 所 有 包 含 k 1 表 的 最 优 子 计 划 S ， 尝 试 将 每 个 剩 余 基 表 R 连 接 进 来 ， 更 新 并 保 留 每 个 大 小 为 k 的 子 集 的 最 优 左 深 计 划 ， 直 至 包 含 所 有 n 张 表 。 如 此 ， 算 法 以 n 轮 完 成 枚 举 ， 每 轮 仅 对 上 一 轮 的 最 优 子 计 划 进 行 扩 展 ， 不 必 遍 历 所 有 O ( n ! ) 种 联 接 树 ， 空 间 和 时 间 复 杂 度 可 控 制 在 指 数 级 但 远 低 于 阶 乘 级 别 。 用 伪 代 码 来 表 示 就 是 ： 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 R ← s e t o f r e l a t i o n s t o j o i n f o r i i n : / / 按 子 集 大 小 自 底 向 上 f o r S i n : o p t c o s t _ S = ∞ o p t j o i n _ S = ∅ f o r a i n S : / / 枚 举 将 a 作 为 最 后 连 接 的 基 表 c _ s a = o p t c o s t _ } + m i n _ c o s t _ t o _ j o i n ( ( S – ) , a ) + m i n _ a c c e s s _ c o s t ( a ) i f c _ s a o p t c o s t _ S = c _ s a o p t j o i n _ S = o p t j o i n _ } ⨝ a / / 计 算 并 缓 存 S 的 最 优 子 计 划 ， 包 括 o p t c o s t _ * 和 o p t j o i n _ * 该 算 法 默 认 只 搜 索 左 深 树 ， 因 为 可 以 在 子 集 拆 分 的 时 候 采 用 S a + a 的 方 式 来 选 取 已 有 的 子 树 和 要 J O I N 的 基 表 ， 并 大 幅 减 小 搜 索 空 间 。 以 P o s t g r e S Q L 中 的 最 优 子 计 划 复 用 为 例 ： 1 2 3 4 5 6 第 一 次 ： e m p ⋈ k i d s 的 最 低 成 本 执 行 计 划 H a s h J o i n ( c o s t = 3 4 7 2 9 2 . 5 9 . . 4 9 8 0 1 9 . 6 0 r o w s = 3 0 0 0 0 0 1 w i d t h = 3 6 ) H a s h C o n d : ( k i d s . e n o = e m p . e n o ) S e q S c a n o n k i d s ( c o s t = 0 . 0 0 . . 4 9 0 9 9 . 0 1 r o w s = 3 0 0 0 0 0 1 w i d t h = 1 8 ) H a s h ( c o s t = 1 6 3 6 9 6 . 1 5 . . 1 6 3 6 9 6 . 1 5 r o w s = 1 0 0 0 0 1 1 5 w i d t h = 2 2 ) S e q S c a n o n e m p ( c o s t = 0 . 0 0 . . 1 6 3 6 9 6 . 1 5 r o w s = 1 0 0 0 0 1 1 5 w i d t h = 2 2 ) 1 2 3 4 5 6 7 8 9 第 二 次 ： d e p t ⋈ ( e m p ⋈ k i d s ) 的 最 低 成 本 执 行 计 划 H a s h J o i n ( c o s t = 3 5 0 3 7 6 . 6 1 . . 5 5 6 2 4 5 . 9 6 r o w s = 3 0 0 0 0 0 1 w i d t h = 4 0 ) H a s h J o i n ( c o s t = 3 4 7 2 9 2 . 5 9 . . 4 9 8 0 1 9 . 6 0 r o w s = 3 0 0 0 0 0 1 w i d t h = 3 6 ) 最 优 子 结 构 复 用 H a s h C o n d : ( k i d s . e n o = e m p . e n o ) S e q S c a n o n k i d s H a s h S e q S c a n o n e m p 最 优 子 结 构 复 用 结 束 H a s h ( c o s t = 1 4 4 3 . 0 1 . . 1 4 4 3 . 0 1 r o w s = 1 0 0 0 0 1 w i d t h = 8 ) S e q S c a n o n d e p t 假 设 有 四 个 表 A 、 B 、 C 、 D ， 它 们 通 过 动 态 规 划 选 出 最 优 执 行 计 划 的 步 骤 如 下 ： 当 前 计 算 出 A 的 最 优 执 行 计 划 是 索 引 扫 描 ， B 是 顺 序 扫 描 （ C 和 D 这 里 不 展 示 ） ， 那 么 = A B o r B A ， = A C o r C A ， = B C o r C B 。 经 过 一 系 列 计 算 ， 我 们 可 以 在 动 态 规 划 中 得 出 如 下 的 备 忘 录 ： R e l a t i o n s B e s t P l a n C o s t A I n d e x S c a n 5 B S e q S c a n 1 5 … … … B ⨝ A 7 5 A ⨝ C 1 2 C ⨝ B 2 2 … … … 之 后 ， 我 们 要 计 算 ， 那 么 就 是 要 计 算 ： 不 包 含 A 的 ： 比 较 A ( ) 和 ( ) A ； 不 包 含 B 的 ： 比 较 ( ) B 和 B ( ) ； 不 包 含 C 的 ： 比 较 C ( ) 和 ( ) C 。 这 个 时 候 我 们 发 现 、 、 的 最 优 执 行 计 划 已 经 被 缓 存 起 来 了 ， 可 以 直 接 复 用 。 p e r f e c t o ！ 最 终 ， 我 们 可 以 得 出 如 下 的 备 忘 录 表 ： R e l a t i o n s B e s t P l a n C o s t A I n d e x S c a n 5 B S e q S c a n 1 5 … … … B ⨝ A 7 5 A ⨝ C 1 2 C ⨝ B 2 2 … … … ( C B ) ⨝ A 3 5 ( C B ) ⨝ D 4 2 … … … ( ( C B ) ⨝ D ) ⨝ A 5 7 因 此 ， 我 们 可 以 知 道 J O I N A B C D 这 四 个 表 的 最 低 成 本 和 最 优 执 行 计 划 了 。 并 且 该 算 法 在 最 差 情 况 下 需 要 枚 举 所 有 表 子 集 并 对 每 个 子 集 尝 试 所 有 可 能 的 最 后 加 入 表 ， 因 此 具 有 指 数 级 时 间 复 杂 度 ： O ( n · 2 ⁿ ) 。 我 们 可 以 将 该 问 题 等 价 成 类 似 0 1 子 集 问 题 ， 也 就 是 n 张 表 对 应 一 串 长 度 为 n 的 二 进 制 串 ， 第 i 位 为 1 代 表 关 系 i 已 经 被 J O I N 了 ， 因 此 有 2 ⁿ 1 个 子 集 。 而 且 每 个 子 集 要 进 行 n 次 状 态 转 移 计 算 ， 也 就 是 尝 试 去 除 集 合 中 的 某 一 个 表 来 构 建 连 接 计 划 。 最 终 两 者 相 乘 可 得 出 如 上 的 时 间 复 杂 度 。 有 趣 排 序 （ i n t e r e s t i n g o r d e r ） 查 询 优 化 器 在 枚 举 左 深 执 行 计 划 时 ， 除 了 比 较 不 同 访 问 路 径 和 连 接 算 法 的 代 价 外 ， 还 要 考 虑 输 出 结 果 的 排 序 属 性 — — 若 某 计 划 天 然 生 成 了 对 后 续 算 子 （ 如 M e r g e J o i n 、 O R D E R B Y 、 G R O U P B Y 、 去 重 等 ） 有 用 的 顺 序 ， 则 称 该 排 序 为 有 趣 排 序 。 优 化 器 会 为 每 个 子 集 在 每 种 有 趣 排 序 下 各 自 缓 存 最 优 子 计 划 ， 从 而 保 证 后 续 算 子 能 够 直 接 利 用 已 有 排 序 ， 避 免 额 外 排 序 或 物 化 开 销 ， 但 这 也 会 使 枚 举 空 间 按 有 趣 排 序 数 量 k 成 倍 增 长 ， 总 体 复 杂 度 增 加 k + 1 倍 。 尽 管 枚 举 空 间 增 加 ， 优 化 器 借 此 能 提 前 利 用 排 序 属 性 ， 减 少 后 续 全 局 排 序 及 临 时 物 化 ， 往 往 在 整 体 查 询 时 间 上 取 得 收 益 ， 尤 其 在 多 级 排 序 或 多 次 归 并 连 接 链 中 更 为 明 显 。 1 2 3 4 f o r e a c h s u b s e t S o f r e l a t i o n s : f o r e a c h i n t e r e s t i n g o r d e r o i n ∪ O r d e r s ( S ) : c o m p u t e m i n c o s t p l a n p r o d u c i n g S w i t h o r d e r o k e e p p l a n i f c o s t s m a l l e r t h a n p r e v i o u s b e s t f o r ( S , o ) 基 数 估 算 基 数 估 算 （ C a r d i n a l i t y E s t i m a t i o n ） 是 成 本 模 型 的 核 心 环 节 ， 优 化 器 需 要 对 每 一 种 可 能 的 关 联 操 作 都 进 行 行 数 估 算 ； 当 查 询 涉 及 8 – 1 6 张 表 关 联 时 ， 由 于 关 联 顺 序 的 组 合 数 呈 指 数 级 增 长 ， 可 能 需 要 上 百 到 上 千 次 估 算 ； 为 了 避 免 优 化 阶 段 延 迟 过 大 ， 估 算 器 通 常 要 在 毫 秒 级 完 成 一 次 估 算 ； 因 此 ， 各 数 据 库 系 统 普 遍 采 用 各 种 快 速 而 简 化 的 假 设 或 采 样 策 略 ， 在 估 算 精 度 与 执 行 开 销 之 间 做 权 衡 。 P o s t g r e S Q L 在 p g _ s t a t i s t i c 系 统 目 录 中 ， 为 表 的 每 一 列 收 集 的 两 大 核 心 统 计 ： 直 方 图 边 界 （ h i s t o g r a m _ b o u n d s ） ： 按 等 频 原 则 划 分 的 区 间 边 界 ， 用 于 估 算 范 围 查 询 的 选 择 性 。 最 常 见 值 列 表 （ m o s t _ c o m m o n _ v a l s ） ： 出 现 频 率 最 高 的 一 组 值 及 其 对 应 频 率 ， 用 于 快 速 处 理 等 值 查 询 。 查 询 优 化 器 在 生 成 执 行 计 划 时 ， 会 结 合 这 两 类 统 计 信 息 来 估 算 谓 词 的 行 数 （ s e l e c t i v i t y ） ， 进 而 比 较 不 同 执 行 策 略 的 成 本 。 下 面 将 介 绍 这 两 种 方 案 。 直 方 图 又 分 为 等 宽 和 等 深 两 种 类 型 ： 等 宽 直 方 图 （ E q u a l W i d t h H i s t o g r a m ） 是 最 简 单 的 直 方 图 类 型 ， 它 将 数 据 值 范 围 等 分 成 若 干 个 固 定 宽 度 的 桶 （ b i n s ） ， 并 统 计 每 个 桶 内 数 据 所 占 的 比 例 （ s e l e c t i v i t y ） 。 下 图 将 总 共 7 8 5 4 条 记 录 分 入 等 宽 的 若 干 个 区 间 （ 比 如 0 – 5 K 、 5 K – 1 0 K 等 ） ， 并 在 每 个 桶 上 方 标 注 该 区 间 内 记 录 占 总 量 的 比 例 （ 如 0 – 5 K 桶 占 6 1 % ） 。 查 询 优 化 器 可 以 利 用 这 些 比 例 估 算 范 围 查 询 或 不 在 最 常 见 值 列 表 中 的 等 值 查 询 的 行 数 ， 从 而 评 估 不 同 执 行 计 划 的 成 本 。 根 据 上 图 ， 如 果 我 们 要 选 取 小 于 5 0 0 0 的 数 据 ， 那 么 操 作 的 范 围 只 局 限 于 第 一 个 桶 中 ， 因 此 估 算 的 基 数 为 0 . 6 1 * 7 8 5 4 = 4 7 9 6 。 但 这 里 会 有 个 问 题 ： 如 果 范 围 查 找 的 数 值 不 是 某 个 同 的 边 界 呢 ？ 也 就 是 比 如 我 们 想 查 找 小 于 7 5 0 0 的 数 据 ， 而 这 个 值 刚 好 在 第 二 个 桶 的 正 中 间 。 这 个 时 候 我 们 只 能 假 设 数 据 为 均 匀 分 布 ， 但 是 实 际 情 况 并 不 总 是 如 此 ： 可 能 大 部 分 数 据 都 集 中 在 第 二 个 桶 的 5 6 K 这 一 部 分 ， 也 可 能 集 中 在 9 1 0 K 这 一 部 分 ， 因 此 会 存 在 较 大 误 差 。 同 时 为 了 减 少 误 差 ， 我 们 又 不 可 能 无 限 制 地 缩 小 每 个 桶 的 宽 度 ， 因 为 最 终 会 导 致 大 量 的 桶 ， 反 而 会 加 剧 查 询 和 存 储 的 开 销 。 因 此 我 们 需 要 等 深 直 方 图 。 等 深 直 方 图 （ E q u a l D e p t h H i s t o g r a m ） 通 过 保 证 每 个 桶 内 的 行 数 （ 频 数 ） 大 致 相 同 来 划 分 数 据 范 围 。 下 图 仍 然 是 针 对 7 8 5 4 条 记 录 使 用 1 0 0 个 桶 来 划 分 ， 每 个 桶 含 有 相 似 数 量 的 值 ， 因 此 即 使 值 域 跨 度 不 均 ， 桶 高 （ s e l e c t i v i t y ） 也 差 不 多 （ ≈ 0 . 0 0 8 ） ， 更 能 反 映 底 层 数 据 分 布 的 真 实 密 度 。 在 上 图 中 ， 如 果 我 们 要 选 取 小 于 1 9 5 . 5 K 的 数 据 ， 那 么 操 作 范 围 在 最 后 两 个 桶 中 ， 因 此 估 算 的 基 数 为 ( 0 . 0 0 8 + 0 . 0 0 8 ) * 7 8 5 4 = 1 2 6 。 通 常 来 说 ， 等 深 直 方 图 由 于 等 宽 直 方 图 ， 因 为 它 保 证 了 每 个 桶 的 选 取 性 的 一 致 ， 从 而 导 致 数 据 分 布 更 密 集 的 桶 更 窄 ， 数 据 分 布 更 稀 疏 的 桶 更 宽 ， 这 更 好 地 反 映 出 了 数 据 分 布 。 但 是 这 样 的 维 护 成 本 也 会 更 高 ， 尤 其 是 某 些 D M L 操 作 导 致 一 个 桶 的 高 度 变 化 时 ， 它 之 后 的 桶 需 要 不 断 地 移 动 一 些 数 据 到 这 个 桶 直 到 选 取 性 达 到 0 . 0 0 8 ， 之 后 的 每 个 桶 需 要 不 断 往 前 一 个 桶 移 动 数 据 来 保 证 每 个 桶 的 高 度 达 到 0 . 0 0 8 ， 每 个 桶 的 在 X 轴 上 的 范 围 也 可 能 会 因 此 变 化 ， 甚 至 某 些 情 况 下 的 工 作 量 不 亚 于 从 头 构 建 。 此 外 ， 每 个 桶 中 的 数 据 倾 斜 仍 然 无 法 被 避 免 。 也 就 是 ， 如 果 我 们 要 选 取 小 于 3 4 7 8 6 6 的 数 据 ， 那 么 仍 然 需 要 假 设 为 均 匀 分 布 ， 这 个 时 候 遇 到 的 问 题 和 等 宽 直 方 图 的 是 一 样 的 。 通 常 情 况 下 导 致 数 据 倾 斜 的 大 概 率 是 一 些 极 端 离 群 值 （ o u t l i e r s ） ， 我 们 可 以 通 过 下 面 这 个 方 案 来 处 理 它 。 等 深 直 方 图 + 最 常 见 值 （ M o s t C o m m o n V a l u e s ） 这 个 方 案 中 ， 对 于 出 现 极 高 频 率 或 明 显 偏 斜 的 值 ， 等 深 直 方 图 会 将 它 们 剔 除 到 最 常 见 值 列 表 ， 以 免 扭 曲 桶 的 划 分 边 界 和 高 度 。 V a l u e S e l e c t i v i t y 0 0 . 0 7 1 0 . 0 0 4 8 2 0 . 0 0 4 0 7 … … 9 4 0 . 0 0 0 2 8 5 0 0 . 0 0 0 7 T o t a l 0 . 1 4 上 面 这 个 表 格 就 是 最 常 见 值 列 表 。 如 果 我 们 要 选 取 等 于 0 的 数 据 ， 那 么 直 接 从 最 常 见 值 的 表 里 获 取 0 . 0 7 ， 然 后 0 . 0 7 * 7 8 5 4 = 5 5 0 就 是 预 估 的 基 数 。 如 果 我 们 要 选 取 大 于 8 1 2 且 小 于 8 6 0 的 数 据 ， 那 么 估 算 的 基 数 为 ( 0 . 0 0 8 + 0 . 0 0 0 7 ) * 7 8 5 4 = 6 8 . 4 5 。 但 是 这 个 方 案 仍 然 存 在 问 题 ： 当 我 们 对 多 字 段 （ 列 ） 的 谓 词 过 滤 进 行 基 数 预 估 的 时 候 ， 往 往 会 低 估 基 数 ， 也 就 是 预 估 的 基 数 往 往 会 比 真 实 操 作 的 元 组 的 基 数 要 低 。 这 是 因 为 不 同 列 的 过 滤 谓 词 被 假 设 彼 此 独 立 ， 即 联 合 选 择 性 等 于 各 单 列 选 择 性 的 乘 积 。 这 种 做 法 在 实 际 数 据 分 布 中 往 往 并 不 成 立 ： 当 列 之 间 存 在 相 关 性 时 ， 单 列 乘 积 往 往 远 小 于 真 实 的 联 合 选 择 性 ， 导 致 估 算 行 数 被 严 重 低 估 ， 从 而 可 能 选 择 次 优 的 执 行 计 划 。 为 了 克 服 完 全 独 立 性 假 设 在 多 谓 词 估 算 中 严 重 低 估 结 果 的 问 题 ， S Q L S e r v e r 引 入 了 三 种 谓 词 相 关 性 假 设 ： 完 全 独 立 ： 各 谓 词 假 设 互 不 相 关 ， 联 合 选 择 性 直 接 相 乘 。 完 全 相 关 ： 各 谓 词 假 设 完 全 相 关 ， 联 合 选 择 性 取 最 小 者 。 部 分 相 关 ： 折 中 假 设 ， 既 不 完 全 独 立 也 不 完 全 相 关 ， 通 过 对 较 低 的 选 择 性 取 根 号 后 再 相 乘 ， 减 缓 低 估 程 度 。 而 多 列 M C V 是 将 单 列 M C V 的 思 路 扩 展 到 多 列 组 合 上 ： 在 统 计 收 集 阶 段 ， 为 常 一 起 出 现 在 W H E R E 条 件 中 的 列 组 建 立 一 个 联 合 M C V 列 表 ， 记 录 这 些 组 合 值 及 其 联 合 频 率 ； 查 询 时 ， 若 谓 词 中 出 现 该 组 合 值 ， 优 化 器 即 可 直 接 使 用 其 真 实 联 合 选 择 性 ， 而 无 需 依 赖 独 立 性 假 设 或 柱 状 图 估 算 ， 从 而 显 著 提 升 多 谓 词 过 滤 的 准 确 性 。 b a l a n c e a g e s e l e c t i v i t y 4 7 7 6 3 4 0 . 0 0 9 7 6 3 2 5 4 1 0 . 0 0 0 5 … 但 是 这 种 方 案 的 构 建 成 本 会 随 着 查 询 涉 及 的 列 数 的 增 长 而 增 长 。 同 样 ， 多 列 直 方 图 也 面 临 多 个 列 的 组 合 的 爆 炸 式 增 长 问 题 。 最 后 一 种 方 案 是 B a y e s C a r d ： 传 统 查 询 优 化 器 常 用 独 立 直 方 图 ， 对 每 列 单 独 建 模 并 将 联 合 选 择 性 取 乘 积 P ( A ) P ( B ) P ( C ) ， 这 种 方 法 速 度 极 快 但 在 列 高 度 相 关 时 严 重 低 估 真 实 结 果 ； 若 对 多 列 直 接 建 立 三 维 直 方 图 ， 空 间 开 销 将 成 指 数 级 O ( ∣ N ∣ 3 ) \ \ m a t h c a l ( | N | ^ 3 ) O ( ∣ N ∣ ​ 3 ​ ​ ) ， 也 无 法 在 生 产 环 境 中 普 及 。 图 形 模 型 （ 如 B a y e s i a n 网 络 ） 通 过 学 习 列 间 条 件 依 赖 ， 并 将 联 合 分 布 因 子 化 为 若 干 局 部 条 件 概 率 ： P ( A ) P ( B ∣ A ) P ( C ∣ A , B ) P ( A ) \ \ , P ( B \ \ m i d A ) \ \ , P ( C \ \ m i d A , B ) P ( A ) P ( B ∣ A ) P ( C ∣ A , B ) ， 在 保 留 关 联 性 的 前 提 下 ， 将 参 数 规 模 控 制 到 O ( 2 ∣ N ∣ 2 ) \ \ m a t h c a l ( 2 | N | ^ 2 ) O ( 2 ∣ N ∣ ​ 2 ​ ​ ) ， 从 而 在 毫 秒 级 完 成 联 合 S e l e c t i v i t y 推 断 ， 并 在 多 项 基 准 测 试 中 显 著 降 低 估 算 误 差 ， 实 现 了 精 度 与 性 能 的 平 衡 。 关 于 B a y e s C a r d 的 具 体 内 容 可 参 考 ： h t t p s : / / a r x i v . o r g / p d f / 2 0 1 2 . 1 4 7 4 3 传 统 关 系 型 数 据 库 对 等 值 和 范 围 谓 词 均 有 成 熟 的 统 计 信 息 （ 如 直 方 图 、 最 常 见 值 列 表 ） 支 持 ， 但 对 于 L I K E 和 U D F 这 两 类 黑 箱 谓 词 ， 数 据 库 优 化 器 往 往 难 以 利 用 现 有 统 计 直 接 估 算 、 只 能 退 而 求 其 次 使 用 启 发 式 规 则 或 假 定 常 数 选 择 性 ， 导 致 估 算 误 差 大 、 执 行 计 划 次 优 。 近 年 来 ， 研 究 界 针 对 L I K E 查 询 提 出 了 模 式 / 序 列 模 型 （ p a t t e r n b a s e d 或 p o s i t i o n a l h i s t o g r a m s ） 来 改 善 精 度 ， 而 U D F 则 几 乎 无 法 通 过 统 计 建 模 ， 只 能 依 赖 运 行 时 采 样 或 成 本 抑 制 策 略 。 模 式 / 序 列 直 方 图 方 法 S P H （ S e q u e n t i a l P a t t e r n b a s e d H i s t o g r a m ） ： 通 过 挖 掘 字 符 串 的 频 繁 子 序 列 ， 将 常 见 的 子 串 模 式 构 建 成 模 式 直 方 图 ， 在 优 化 时 根 据 查 询 模 式 匹 配 度 快 速 估 算 s e l e c t i v i t y ， 从 而 显 著 优 于 传 统 直 方 图 和 常 数 假 定 。 P o s i t i o n a l S e q u e n c e P a t t e r n s ： 针 对 S P H 偶 尔 会 高 估 的 问 题 ， 引 入 位 置 序 列 模 式 区 分 相 邻 匹 配 与 可 插 入 匹 配 ， 通 过 信 息 熵 剔 除 冗 余 模 式 ， 再 结 合 分 区 匹 配 策 略 ， 使 L I K E 查 询 的 平 均 误 差 率 降 低 约 2 0 % 。 深 度 学 习 方 法 ： 近 期 有 工 作 利 用 神 经 网 络 对 L I K E 模 式 进 行 表 征 和 回 归 预 测 ， 能 够 学 习 复 杂 通 配 符 下 的 非 线 性 分 布 ， 但 目 前 仍 处 于 研 究 阶 段 ， 工 业 界 应 用 有 限 。 样 本 采 样 （ S a m p l i n g ） 样 本 采 样 是 一 种 简 单 直 接 的 基 数 估 算 方 法 ： 在 数 据 库 中 为 每 张 表 维 护 一 个 小 规 模 的 随 机 样 本 （ 例 如 ， 1 % 的 行 ） 并 常 驻 内 存 ； 在 优 化 阶 段 ， 针 对 查 询 谓 词 仅 在 样 本 上 执 行 过 滤 ， 计 算 样 本 命 中 率 ， 然 后 将 其 外 推 到 全 表 数 据 ， 得 到 整 体 选 择 性 和 估 算 行 数 。 该 方 案 的 优 点 是 ： 支 持 任 意 谓 词 ： 由 于 直 接 在 样 本 上 运 行 过 滤 运 算 ， 不 依 赖 预 先 计 算 的 直 方 图 或 分 布 假 设 ， 对 任 何 运 算 符 或 U D F 都 有 效 。 摆 脱 独 立 性 等 假 设 ： 无 需 假 设 列 间 相 互 独 立 ， 也 无 需 假 设 值 在 桶 内 均 匀 分 布 ； 样 本 大 致 反 映 真 实 分 布 ， 即 可 获 取 估 算 。 易 于 集 成 ： 只 要 在 优 化 器 中 加 入 样 本 访 问 路 径 ， 就 能 在 编 译 阶 段 快 速 完 成 过 滤 并 计 算 比 例 ， 无 需 维 护 复 杂 的 统 计 结 构 。 缺 点 是 ： 可 能 遗 漏 极 端 值 ： 如 果 查 询 谓 词 对 应 的 行 在 样 本 中 未 出 现 （ 例 如 极 端 离 群 值 或 低 频 组 合 ） ， 会 导 致 估 算 为 零 或 极 小 ， 严 重 低 估 真 实 行 数 。 编 译 时 开 销 ： 需 要 在 优 化 阶 段 执 行 过 滤 运 算 ， 若 样 本 量 或 谓 词 复 杂 度 较 高 ， 编 译 时 间 可 能 显 著 增 加 ； 采 样 比 例 若 过 低 ， 则 准 确 度 下 降 ， 否 则 延 迟 上 升 。 不 适 用 于 多 表 连 接 ： 在 多 表 连 接 查 询 中 ， 需 要 对 多 个 表 的 样 本 进 行 笛 卡 尔 组 合 或 联 动 抽 样 ， 开 销 与 实 现 复 杂 度 呈 指 数 级 增 长 ， 因 此 通 常 不 对 连 接 使 用 样 本 采 样 估 算 ， 只 针 对 单 表 谓 词 有 效 。 下 面 展 示 P o s t g r e S Q L 中 是 如 何 进 行 基 数 估 算 的 ： P o s t g r e S Q L （ 沿 用 S y s t e m R 的 经 典 做 法 ） 对 单 列 等 值 联 结 R ₁ ⋈ R ₂ O N R ₁ . a = R ₂ . a 估 算 行 数 时 ， 先 分 别 估 算 表 过 滤 后 行 数 | R ₁ | 、 | R ₂ | 及 各 自 该 列 的 基 数 ( d ₁ 、 d ₂ ) ， 然 后 假 定 联 结 属 性 在 两 表 中 同 构 分 布 并 采 用 最 保 守 的 分 母 ： ∣ R 1 ⋈ R 2 ∣ ≈ ∥ R 1 ∥ × ∥ R 2 ∥ m a x ( d 1 , d 2 ) . \ \ b i g l | R _ 1 \ \ J o i n R _ 2 \ \ b i g r | \ \ ; \ \ a p p r o x \ \ ; \ \ f r a c . ​ ∣ ​ ∣ ​ ​ R ​ 1 ​ ​ ⋈ R ​ 2 ​ ​ ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( d ​ 1 ​ ​ , d ​ 2 ​ ​ ) ​ ​ ∥ R ​ 1 ​ ​ ∥ × ∥ R ​ 2 ​ ​ ∥ ​ ​ . ， 其 中 m a x ( d ₁ , d ₂ ) 是 两 表 中 该 列 唯 一 值 数 量 的 较 大 者 ， 用 作 平 均 每 个 值 匹 配 行 数 的 分 母 ， 以 避 免 乘 积 模 型 在 高 度 偏 斜 场 景 下 的 严 重 低 估 。 假 设 有 三 个 表 e m p ， d e p t ， k i d s ： e m p ： e i d e m p l o y e e 1 L e e 2 K i m 3 S a m d e p t ： e i d d e p a r t m e n t 1 财 务 部 2 财 务 部 3 行 政 部 k i d s ： e i d n a m e 1 N e i l 1 L e b r o n 2 J u s t i n 3 T o m 如 果 执 行 S E L E C T * F R O M e m p , d e p t , k i d s W H E R E e i d = e i d A N D e m p . e i d = k i d s . e i d ; ， 也 就 是 没 有 过 滤 条 件 的 情 况 ， 那 么 ∣ e m p ∣ = 3 ∣ d e p t ∣ = 3 ∣ k i d s ∣ = 4 \ \ l v e r t e m p \ \ r v e r t = 3 \ \ q u a d \ \ l v e r t d e p t \ \ r v e r t = 3 \ \ q u a d \ \ l v e r t k i d s \ \ r v e r t = 4 ∣ e m p ∣ = 3 ∣ d e p t ∣ = 3 ∣ k i d s ∣ = 4 d e , e i d = 3 d d , e i d = 3 d k , e i d = 3 d _ } = 3 \ \ q u a d d _ } = 3 \ \ q u a d d _ } = 3 d ​ e , e i d ​ ​ = 3 d ​ d , e i d ​ ​ = 3 d ​ k , e i d ​ ​ = 3 ∣ e m p ⋈ d e p t ∣ ≈ 3 × 3 m a x ( 3 , 3 ) = 3 × 3 3 = 3 \ \ b i g l | \ \ t e x t \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 3 ​ ∣ ​ ∣ ​ ​ e m p ⋈ d e p t ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 3 , 3 ) ​ ​ 3 × 3 ​ ​ = ​ 3 ​ ​ 3 × 3 ​ ​ = 3 ∣ e m p ⋈ k i d s ∣ ≈ 3 × 4 m a x ( 3 , 3 ) = 3 × 4 3 = 4 \ \ b i g l | \ \ t e x t \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 4 ​ ∣ ​ ∣ ​ ​ e m p ⋈ k i d s ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 3 , 3 ) ​ ​ 3 × 4 ​ ​ = ​ 3 ​ ​ 3 × 4 ​ ​ = 4 ∣ ( e m p ⋈ d e p t ) ⋈ k i d s ∣ ≈ 3 × 4 m a x ( 3 , 3 ) = 3 × 4 3 = 4 \ \ b i g l | ( \ \ t e x t \ \ J o i n \ \ t e x t ) \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 4 ​ ∣ ​ ∣ ​ ​ ( e m p ⋈ d e p t ) ⋈ k i d s ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 3 , 3 ) ​ ​ 3 × 4 ​ ​ = ​ 3 ​ ​ 3 × 4 ​ ​ = 4 ， 如 果 执 行 S E L E C T * F R O M e m p , d e p t , k i d s W H E R E d e p t . d e p a r t m e n t = 财 务 部 A N D e m p . e i d = d e p t . e i d A N D e m p . e i d = k i d s . e i d ; ， 那 么 ∣ e m p ∣ = 3 ∣ d e p t ∣ = 1 ∣ k i d s ∣ = 4 \ \ l v e r t e m p \ \ r v e r t = 3 \ \ q u a d \ \ l v e r t d e p t \ \ r v e r t = 1 \ \ q u a d \ \ l v e r t k i d s \ \ r v e r t = 4 ∣ e m p ∣ = 3 ∣ d e p t ∣ = 1 ∣ k i d s ∣ = 4 d e , e i d = 3 d d , e i d = 1 d k , e i d = 3 d _ } = 3 \ \ q u a d d _ } = 1 \ \ q u a d d _ } = 3 d ​ e , e i d ​ ​ = 3 d ​ d , e i d ​ ​ = 1 d ​ k , e i d ​ ​ = 3 ∣ e m p ⋈ d e p t ∣ ≈ 3 × 1 m a x ( 3 , 1 ) = 3 × 1 3 = 3 \ \ b i g l | \ \ t e x t \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 3 ​ ∣ ​ ∣ ​ ​ e m p ⋈ d e p t ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 3 , 1 ) ​ ​ 3 × 1 ​ ​ = ​ 3 ​ ​ 3 × 1 ​ ​ = 3 ∣ e m p ⋈ k i d s ∣ ≈ 3 × 4 m a x ( 3 , 3 ) = 3 × 4 3 = 4 \ \ b i g l | \ \ t e x t \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 4 ​ ∣ ​ ∣ ​ ​ e m p ⋈ k i d s ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 3 , 3 ) ​ ​ 3 × 4 ​ ​ = ​ 3 ​ ​ 3 × 4 ​ ​ = 4 ∣ ( e m p ⋈ d e p t ) ⋈ k i d s ∣ ≈ 1 × 4 m a x ( 1 , 3 ) = 1 × 4 3 = 1 . 3 \ \ b i g l | ( \ \ t e x t \ \ J o i n \ \ t e x t ) \ \ J o i n \ \ t e x t \ \ b i g r | \ \ a p p r o x \ \ f r a c = \ \ f r a c = 1 . 3 ​ ∣ ​ ∣ ​ ​ ( e m p ⋈ d e p t ) ⋈ k i d s ​ ∣ ​ ∣ ​ ​ ≈ ​ m a x ( 1 , 3 ) ​ ​ 1 × 4 ​ ​ = ​ 3 ​ ​ 1 × 4 ​ ​ = 1 . 3 。 思 考 ： 这 里 出 现 小 数 点 有 影 响 么 ？ 实 际 上 是 没 有 影 响 的 ， 这 个 指 标 只 用 于 基 数 评 估 并 最 终 用 于 确 定 执 行 计 划 ， 实 际 的 操 作 执 行 和 这 个 无 关 。 基 数 的 低 估 和 高 估 问 题 基 数 估 算 问 题 可 分 为 低 估 （ U n d e r E s t i m a t e s ） 和 高 估 （ O v e r E s t i m a t e s ） 两 类 。 两 者 均 会 导 致 选 错 执 行 计 划 ， 但 低 估 往 往 更 具 破 坏 性 ： 当 优 化 器 低 估 中 间 结 果 行 数 时 ， 可 能 选 择 内 存 嵌 套 循 环 而 不 是 外 部 哈 希 连 接 ， 导 致 大 量 磁 盘 溢 写 和 I / O 阻 塞 ， 从 而 极 度 拖 慢 查 询 。 独 立 性 假 设 是 导 致 低 估 的 主 要 根 源 之 一 ， 因 为 真 实 数 据 中 列 间 高 度 相 关 时 ， 简 单 的 乘 积 模 型 会 大 幅 低 估 联 合 选 择 性 。 1 2 … 9 文 章 目 录 站 点 概 览 Y i h a n g W e i 聚 焦 于 个 人 的 学 习 与 成 长 历 程 ， 旨 在 系 统 记 录 在 后 端 开 发 、 数 据 库 等 领 域 的 探 索 与 实 践 。 4 5 日 志 3 分 类 简 体 中 文 简 体 中 文 E n g l i s h 京 I C P 备 2 0 2 5 1 3 1 8 8 0 号 1 © 2 0 2 5 Y i h a n g W e i 由 H e x o & N e x T . M u s e 强 力 驱 动

关于www.ethanweee.online说明：

www.ethanweee.online由网友主动性提交被520网址导航-自动秒收录整理收录的，520网址导航-自动秒收录仅提供www.ethanweee.online的基础信息并免费向大众网友展示，www.ethanweee.online的是IP地址：47.97.39.166 [中国浙江杭州 阿里云]，www.ethanweee.online的百度权重为0、百度手机权重为0、百度收录为0条、360收录为0条、搜狗收录为0条、谷歌收录为0条、百度来访流量大约在-之间、百度手机端来访流量大约在-之间、www.ethanweee.online的备案号是-、备案人叫-、被百度收录的关键词有0个、手机端关键词有0个、该站点迄今为止已经创建16天。

内容声明：

1、本站收录的内容来源于大数据收集，版权归原网站所有！
2、本站收录的内容若侵害到您的利益，请联系我们进行删除处理！
3、本站不接受违规信息，如您发现违规内容，请联系我们进行清除处理！
4、本文地址：https://www.sj520.cn/bianchengdh/10458.html，复制请保留版权链接！

---