列存储系统中并行查询处理的研究与实现.doc

号 ： 列存储 系统 中 并 行 查 询 处理的 研 究与实 现 东 华 大 学计 算机科 学与技 术 学院 东 华 大 学学位 论 文 原创 性 声 明 年 解 密 后 适用 本 版权 书 。不 保密 五 列存储 系统 中 并 行 查 询 处理的 研 究与实 现多 个 查 询 阶 段 的 查 询 优 化 做 出 并 行 化 分 析 。 查 询 性 能 。关 键字： 列存储 ， 多 核 处理器 ， 传 递 块 缓冲 区 ， 并 行 化 设 计 ， 多 线程 崦 第 孪 喙 丶际 跹 芯 俊 技 术 参 考 文 献 本 文 的 研 究目的 是 通 过 对 列存储 系统 的 查 询 引 擎 的 重 新 设 计 ， 使 其支持多 线程 方 式 查 询 ， 以 加 快查 询 速度 。 在引 入多 线程 查 询 之 前， 中 查 询 过程 是 单个 线程 自 底 向 上 逐 个 节 点地进 行 查 询 处理， 最后 输出 查 询 结 果 。 在对 查 询引 擎 进 行 重 新 设 计 之 后 ， 查 询 的 各 个 阶 段 采用 了 不 同的 多 线程 设 计 ， 比 如 一 个 线程 从 磁 盘读取 数 据 之 后 ， 进 行 数 据 处理的 同时另 一 个 线程 可 以 继 续读取 磁 盘数 据 ， 还 有 操作 的 左 右 节 点可 以 使 用 两 个 线程 同时进 行 处理等 。通 过 对查 询 引 擎 的 重新 设 计 ， 使 用 多 线程 查 询 ， 提高 了 多 核 处理器 的 利用 率，缩 短 了 列存储 数 据 分 析 型应 用 的 响应 时间。 因 此， 列存储 系统 中 并 行 查 询 的 设 计是 一 个 非常 有 意 义的 研 究方 向 。 ”中 提出 了 一 种 的 新 的 存储 模型 分 解 存储 模型 ， 稹 】 等列存不 同的 角 度 提高 数 据 库 系统 的 查 询 效 率。 性 能 将 有 较大 的 提升， 而 对 列存储 提升的 性 能 有 限 ， 文 献中 也说 明了 这 一 点。 主当多 个 查 询 对 同一 个 数 据 库 系统 进 行 查 询 时， 如 果 每 次 只运 行 一 个 查 询 其他多 线程 缓冲 区 是 提高 数 据 库 系统 查 询 效 率的 又 一 种 方 式 ， 这 样 能 充 分 利用 现论 文 的 组织结 构 如 下： 研 究工 作 ， 列存储 系统 开 始 逐 步 走向 成 熟 ， 随 后 实 现 了 多 种 类型列存储 系统 ， 比展 望 未 来 姆 狗 较蛭 7植际 胶 透 卟小 有 三 种 实 现 在列存储 系统 的 方 式 中 有 三 种 存储 模型， 一 种 是 用 行 存储 来 模拟列存储 ， 这 其实 不 能 算作 是 列存储 ， 因 为 它他 的 底 层依 然 是 行 存储 ， 只是 使 用 存储 管 理器 来 模拟 列存储 。 第 二种 是 底 层采用 真 正的 列存储 ， 而 它的 查 询 引 擎 则使用 行 存储 的 查 询 引 擎 ， 这 就 要 求 数 据 读取 之 后 立即 要 合并 为 行 存储 形 式 的 元 组，这 样 我们才 能 使 用 行 存储 查 询 引 擎 来 进 行 查 询 执 行 。 第 三 种 是 底 层存储 和 查 询 引擎 都 采用 列存储 的 方 式 ， 这 样 我们就 可 以 充 分 利用 列存储 的 优 势 ， 包括 避 免 早 期的 元 组构 造 ， 最大 限 度 地提高 列存储 系统 的 查 询 效 率。 狿 架 构 ， 主 要 是 针 对 服 务器 单个 处理器 的 处理能 力 不 。 同步 多 线程 际 跏侵 冈 谝 桓 龀 炅看 砥 髦 兄 窒叱 碳兜 牟校 琁 超线程 技 术 闕 就 无 法获 得良 好的 扩展 性 和 系统 的 可 用 性 。 近年 来 ， 分 布式 处理技 术 框架 开 图 两 种 结 构 处理器理器 虲 嗪 舜 砥 。 数 据 库 查 询 的 并 行 方 式 可 以 分 为 以 下几种 ：图 疧并 行 的 两 种 方 式两 个 或 多 个 查 询 语 句 之 间本 来 就 是 相 互 独立 的 主 体， 之 间并 没 有 直接的 相 互图 多 查 询 并 行 用 户之 问并 行 性 是 指操 作 数 据 库 的 每 一 个 用 户的 操作 行 为 相 互 独立 。 用 户之 技 术 谐 绦虼 肭 ！未 舜攀 荕 并 行 执 行 的 区 域 。 些 后 处理， 也可 以 做 一 些 普 通 的 运 算处理。 猂 甋 本 章 小结 为 了 实 现 在 多 核 处理器 平 台下进 行 并 行 查 询 处理的 能 力 ， 本 章 对 基本 概 念作 节 点的 结 构 。 ； 结 构 中 是 以 函 数 指针 的 形 式 来 表 现 的 。 这 是 因 为 每 一 个 不 同类型的 节 点都 有 不 同可 以 选 择 不 同的 操作 函 数 琯 琧 埃 涮 赜 械氖 萁峁 。 在数 据 。 这 就 是 上 下操 作 节 点进 行 数 据 传 递 的 方 式 。 递 ， 每 一 组数 据 被称为 传 递 块 。 这 一 组数 据 要 多 于一 条 数 据 ， 因 为 每 次 只调 用 一条 数 据 被证 明是 非常 低 效 的 ， 我们的 系 统 的 实 验也证 明了 这 一 点。传 递 块 的 设 计 在行 存储 和 列存储 有 明显 不 同， 行 存储 中 数 据 的 读取 是 以 行 为单位 的 ， 每 次 读取 都 将 记 录 中 所 有 值读取 到 内 存， 节 点每 次 向 它父节 点传 递 的 数据 是 真 正所 需 的 数 据 值。 而 列存储 则不 同， 列存储 的 特 点是 按 列存储 和 按 需 提取 。查 询 的 时候 只提取 与操 作 相 关 的 列， 不 相 关 的 列则 不 读入内 存， 当查 询 引 擎 需 要某些 列的 时候 再 根 据 行 号 读入内 存即 可 。 由 于每 列数 据 均以 ， 的 形 式存储 在磁 盘上 ， 所 以 在列存储 中 ， 传 递 块 中 传 递 的 数 据 可 以 是 所 需 的 数 据 或 者所需 数 据 的 行 号 。在列存储 中 ， 传 递 块 的 定义如 下： 木 ； ： 传 递 块 中 最大 的 蛌 的 个 数 ： 传 递 块 中 已存在 的 蛌 的 个 数 中 元 素为 第 二元 素构 成 的 有 序 对 ， 将 所 有 这 样 的 有 序 对 组成 的 集 合叫 做 隑 的 语 句 调 度 ， 及 其在 多 线程 系统 中 对 负载 均 衡 的 影 响。的 执 行 提前接受并 空 闲 等待， 造 成 任务分 配 不 均等。 甹 个 线程 以 为 单位 分 配 ， 最后 的 相 差循环 次 数 可 能 为 。 调 度 由 于每 次 循环 任务量 很可 能 相 差很大 ， 所 有 采用 静态 调 度 很可 能 使大 的 优 势 。 调 度 态 调 度 的 一 种 ， 只是 动 态 调 度 中 每 次 申 请 获 取 指定的 次 循环 ， 而 调 度每 次 申 请 获 取 的 循环 次 数 越 来 越 小， 直到 最小为 。 诵 惺 调 度 之 后 的 结果 交 给查 询 执 行 模块 执 行 。 这 里主 要 包括 以 下五 个 阶 段。辑计 划 ， 最终 生 成 逻 辑执 行 计 划 。查 询 执 行 模块 的 输入是 查 询 编译生 成 的 物理执 行 树， 最终 用 户得到 的 结 果 就 在 中 我们使 用 后 者作 为 中 间结 果 的 存储 ， 并 且通 过 合理的 设 计 使 得对列数 据 的 访 问只有 一 次 ， 这 是 因 为 只要 某一 节 点对 某一 列数 据 读取 进 行 操作 之 后 ，它的 中 间结 果 就 存放 在缓冲 区 中 ， 将 来 它的 祖先节 点要 访 问这 列的 话 ， 直接从 缓冲 区 读取 它即 可 ， 而 无 需 读取 再 次 读取 磁 盘， 然 后 这 个 祖先节 点处理完 之 后 再 次形 成 中 间结果 ， 将 其放 入缓冲 区 。到 此结束。 要 的 调 整来 得到 随 后 的 传 递 块 。 对 于一 个 操作 节 点来 说， 它要 调 用 一 次 或 多 次传 递 块 的 甧 木 甦 畄 ； 紫扰 卸 蟁 和 拇 笮 。 饫颯 为 小表 。 由 上 述处理过 程 可 知 ， 这 种 多 线程 设 计 不 用 为 每 一 个 桶 加 锁， 这 是 因 为 每 一 谛 菁疭 的 粜 陨鲜褂煤 齢 恚 治 猲 个 桶 ， 每 个 桶标 记 为 、 。立 表 ， 同样 分 为 鐾 埃 扛 鐾 氨昙俏 猂 、 璕 。由 上 述处理过 程 可 知 ， 这 种 设 计 克 服 了 占用 内 存过 多 的 弊 端仅仅占用 内 存大 使 用 多 线程 进 行 聚 集 操作 相 加即 可 。 上 面 多 线程 的 聚 集 设 计 中 可 以 看 出 ， 多 线程 聚 集 的 效 率和 传 递 块 的 大 小有 密传 递 块 。 使 用 多 线程 进 行 排 序 快速排 序 的 一 趟 排 序 算法如 下： 馗 吹 、 剑 钡 絠 。 玨 的 值赋值给 。具 体程 序 代码如 下： 婊 覣 醒 个 数 。 褂妹 芭 菖 判 蚨詍 个 数 进 行 排 序 ， 排 序 到 第 个 数 为 止 。 页 龅趍 鍪 魑 ?焖倥 判 虻 膋 。右 边 部 分 。 跏蓟 镕 。 衏次 基于样 本 的 划 分 ， 得到 部 分 。 愿 镕 进 行 排 序 饫锶 。 处理器 有 两 个 处理器 核 心， 在测 多 核 对 快速排 序 影 响的 时候 ， 我们必图 多 线程 对 快速排 序 的 影 响 技 术 对 快速排 序 的 影 响 阕阚阕懑藤 图 多 查 询 的 强 并 行 与弱并 行在 中 ， 我们选 择 使 用 弱并 行 而 非占用 内 存较大 的 强 并 行 ， 这 样 可 以 再内 存有 限 的 情 况 下进 一 步 加 快查 询 速度 。 是 临 时存放 传 递 块 的 一 片连 续的 内 存区 域 ， 是 为 了数 型变 量 ： 蟣 竞 蛂 右 唬 琻 加 一 ， 每 次 从 缓冲 区 读取 传 递 块 的 时候 环 境， 设 置特 定的 循环 数 组的 大 小， 灵活 支 持多 种 并 再妄 毒。 研 峨珀 夕 瓴任处理是 镜 逝饰4菘檠肥 椋 美 创娣 糯菘椋 籔帅就“” 姚 主线程 与辅 助 线程 函 数 向 子 节 点请 求 数 据 ， 将 得到 的 传 递 块 存入缓冲 区 中 ， 而 同时主 饔 胑 头 庞 伤 唇母 叱 蘌 岩 流 水 线最早来 源 于工 业生 产 过 程 的 思 想 ， 是 将 一 个 产 品 的 生 产 分 为 多 个 阶 段 ，每 一 个 阶 段 有 特 定的 工 人生 产 ， 这 样 当多 个 产 品 生 产 的 时候 ， 每 个 阶 段 的 工 作 都在工 作 ， 提高 了 工 业生 产 效 率。 在计 算机方 面 最早 将 流 水 线技 术 用 于处理器 的 指令 级 并 行 ， 处理器 执 行 指令 的 过 程 分 为 执 行 的 预取 、译码、执 行 、写 回 等 阶 段 ，当处理器 的 译码模块 对 某一 指令 译码的 同时处理器 的 预取 模块 可 以 预取 下一 指令 ， 这 样 单个 处理器 就 可 以 同时处理多 个 指令 ， 处理器 的 处理能 力 提升很大 。在数 据 库 系统 中 ， 最终 会 生 成 一 个 查 询 执 行 树， 从 底 层磁 盘取 出 数 据 到 查 询由 图 所 示 的 数 据 流 转 图 可 知 ， 数 据 是 至 底 向 上 逐 块 地传 递 ， 操作 节 点从 节 点从 左 孩 子 节 点中 读取 全 部 数 据 建 立 。重置为 。 缓蟠 恢 媒 衕 操作 。将 结 果 以 传 递 块 的 形 式 传 递 给 诘 悖 锹 绻 佑 液 拥玫降拇 菘 椴皇 亲 詈笠 桓 鲈 蚣 绦 ， 否则 结 束。 节 中 介绍的 传 递 块 结 构 。为 了 能 进 行 流 水 线并 行 化 操作 ， 我们将 节 中 设 计 的 传 递 块 缓冲 区 用 于以 上查 询 设 计 。 加 入传 递 块 缓冲 区 之 后 ， 查 询 处理过 程 发 生 了 较大 的 变 化 。 未 加 入缓冲 区 之 前， 操作 节 点直接从 孩 子 节 点请 求 获 取 传 递 块 。 加 入缓冲 区 之 后 ， 父节 点从 传 递 块 缓冲 区 中 请 求 获 取 传 递 块 ， 传 递 块 缓冲 区 从 孩 子 节 点请 求 获 取 传 递 块 。程 ： 节 点从 左 孩 子 节 点中 读取 全 部 数 据 建 立 表 。 叱 蹋 苯 和 。 却 饬 縲 。 东 华 大 学硕 士 研 究生 学位 论 文 重置为 。则将 结 果 以 传 递 块 的 形 式 传 递 给 诘 悖 锹糽 如 果 传 递 块 不 是 最后 一 个 传 递 块 继 续 ， 否则 结 束。整