并行数据库.ppt

©Silberschatz, Korth and Sudarshan20.1Database System Concepts 第 20章 : 并行数据库 n 引言 n I/O 并行 n 查询间并行 n 查询内并行 n 操作内并行 n 操作间并行 n 并行系统设计 ©Silberschatz, Korth and Sudarshan20.2Database System Concepts 引言 n 并行机正成为相当普通和负担的起的机器 ê 微处理器 , 内存 , 磁盘的价格已经大幅下降 n 数据库正变得越来越大 ê 大量事务数据被收集和存储以用于将来的分析 . ê 数据库中存储的多媒体对象 (如图像 )越来越多 n 大规模并行数据库系统越来越多地用于 : ê 存储大量数据 ê 处理耗时的决策支持查询 ê 提供高吞吐量的事务处理 ©Silberschatz, Korth and Sudarshan20.3Database System Concepts 数据库中的并行性 n 数据可划分在多个磁盘上 , 导致并行 I/O. n 个别关系操作 (如排序 , 连接 , 合计 ) 可以并行执行 ê数据可划分且每个处理器可对其划分部分独立操作 . n 查询可用高级语言 (SQL, 翻译到关系代数 )表达 ê使并行化更容易 . n 不同查询可并行执行 . ê 并发控制处理冲突 . n 可见 , 数据库很自然地具有并行性 . ©Silberschatz, Korth and Sudarshan20.4Database System Concepts I/O 并行 n 通过将关系划分到多个磁盘来减少从磁盘检索关系所需的 时间 n 水平划分 – 关系的元组在多个磁盘间划分 , 每个元组只存储 在一个磁盘上 . n 划分技术 (磁盘数 = n): 循环 (Round-robin)划分 : 将关系中的第 i 条元组送到第 (i mod n)号磁盘 . 散列划分 : ê选择一个或多个属性作为划分属性 . ê选择值域为 0n -1的散列函数 h ê令 i 表示将散列函数 h作用于元组的划分属性值得到的结果 . 则该元 组送往磁盘 i. ©Silberschatz, Korth and Sudarshan20.5Database System Concepts I/O 并行 (续 ) n 划分技术 (续 ): 范围划分 : ê选择一个属性作为划分属性 . ê选择一个划分向量 [vo, v1, ., vn-2]. ê设一元组的划分属性值为 v. 使 vi  v  vi+1 的元组分到磁盘 i + 1. 使 v s.B. n 对于无法应用划分的联接 , 可以使用 分片与复制 技术来 达到并行化 ê下一页图示 n 特例 – 非对称分片与复制 : ê一个关系进行划分 , 设为 r ; 可用任何划分技术 . ê另一个关系 , 设为 s, 则 在所有处理器上复制 . ê处理器 Pi 在本地计算 ri 与 s 的联接 , 可用任何联接技术 . ©Silberschatz, Korth and Sudarshan20.25Database System Concepts 分片与复制联接 a. 非对称分片与复制 b. 分片与复制 ©Silberschatz, Korth and Sudarshan20.26Database System Concepts 分片与复制联接 (续 ) n 一般情形 : 减小各处理器上的关系的大小 . êr 划分成 n 个 分片 r0, r1, ., r n-1; s划分成 m 个分片 s0, s1, ., sm-1. Ø 可用任何划分技术 . ê至少应有 m * n 个 处理器 . Ø 记为 P0,0, P0,1, ., P0,m-1, P1,0, ., Pn-1m-1. êPi,j 计算 ri 与 sj 的 联接 . 为此 , ri 被复制到 Pi,0, Pi,1, ., Pi,m-1, 而 si 被复制到 P0,i, P1,i, ., Pn-1,i Ø 可用任何联接技术 ©Silberschatz, Korth and Sudarshan20.27Database System Concepts 分片与复制联接 (续 ) n 分片与复制的两个版本都可在任何联接条件下运行 , 因为 r 的每个元组可与 s 的每个元组测试联接条件 . n 通常比划分联接代价高 , 因为一个关系 (对 非对称分片与复 制 )或两个关系 (对 一般分片与复制 )必须复制 . n 即使可以使用划分技术 , 有时非对称分片与复制也更可取 . ê例如 , 若 s 小而 r 很大 , 且已作划分 . 可能更廉价的联接方法是将 s复 制到所有处理器 , 而不是将 r 和 s重新在联接属性上划分 . ©Silberschatz, Korth and Sudarshan20.28Database System Concepts 划分并行散列连接 Parallelizing partitioned hash join: n Assume s is smaller than r and therefore s is chosen as the build relation. n A hash function h1 takes the join attribute value of each tuple in s and maps this tuple to one of the n processors. n Each processor Pi reads the tuples of s that are on its disk Di, and sends each tuple to the appropriate processor based on hash function h1. Let si denote the tuples of relation s that are sent to processor Pi. n As tuples of relation s are received at the destination processors, they are partitioned further using another hash function, h2, which is used to compute the hash-join locally. (Cont.) ©Silberschatz, Korth and Sudarshan20.29Database System Concepts 划分并行散列连接 (续 ) n Once the tuples of s have been distributed, the larger relation r is redistributed across the m processors using the hash function h1 ê Let ri denote the tuples of relation r that are sent to processor Pi. n As the r tuples are received at the destination processors, they are repartitioned using the function h2 ê (just as the probe relation is partitioned in the sequential hash-join algorithm). n Each processor Pi executes the build and probe phases of the hash-join algorithm on the local partitions ri and s of r and s to produce a partition of the final result of the hash-join. n Note: Hash-join optimizations can be applied to the parallel case ê e.g., the hybrid hash-join algorithm can be used to cache some of the incoming tuples in memory and avoid the cost of writing them and reading them back in. ©Silberschatz, Korth and Sudarshan20.30Database System Concepts 并行嵌套循环联接 n 假定 ê关系 s 远远小于关系 r , 且 已划分存储 . ê在关系 r 的每个分片上 , r 的联接属性上存在一个索引 . n 将关系 s 复制 , 利用现有的关系 r 分片 , 采用非对称分片 与复制 . n 存有关系 s 分片的各处理器 Pj 读入存储在 Dj 上 的关系 s 的元组 , 并 复制到其他各处理器 Pi. ê本阶段结束时 , 关系 s 在所有存有关系 r 的元组的场地上得到复 制 . n 各处理器 Pi 执行关系 s与关系 r 的第 i个 分片的索引嵌套 循环联接 .