第1章 分布式数据库和查询优化理论基础 1
1.1 分布式数据库系统概论 1
1.1.1 分布式数据库概述 1
1.1.2 分布式数据库系统的结构特点 3
1.1.3 分布式数据库系统类型分析 5
1.1.4 分布式数据库系统的主要技术分析 6
1.2 查询优化理论基础 8
1.2.1 查询处理器 8
1.2.2 查询优化 10
1.2.3 查询优化研究的主要内容 12
1.3 分布式数据库查询优化理论研究 13
1.3.1 分布式查询优化的目标 13
1.3.2 分布式查询优化的代价估算 14
1.3.3 分布式查询优化处理的层次模式 16
1.4 本章小结 17
第2章 分布式查询优化处理算法研究 18
2.1 分布式查询优化的一般过程 18
2.2 基于关系代数等价变换的查询优化处理 19
2.2.1 关系代数的等价变换 19
2.2.2 全局查询到片段查询的转换 19
2.2.3 基于关系代数等价变换的查询优化 22
2.3 基于半连接算法的查询优化处理 22
2.3.1 半连接算法的查询优化 23
2.3.2 半连接算法的改进 26
2.4 基于直接连接算法的查询优化处理 31
2.4.1 直接连接操作的常用策略分析 31
2.4.2 基于站点依赖信息的算法 33
2.4.3 分片与复制算法 35
2.4.4 hash划分算法 36
2.4.5 一种改进的直接连接查询优化算法 37
2.5 典型的分布式查询优化策略和算法分析 43
2.5.1 SDD-1中的查询优化算法 43
2.5.2 R＊中的查询优化算法 45
2.6 本章小结 46
第3章 多连接查询优化模型的分析与研究 48
3.1 多连接查询问题的数学模型 48
3.1.1 多连接查询的问题描述 48
3.1.2 多连接查询的表现形式 49
3.1.3 将查询图生成有效连接树的算法 51
3.2 多连接查询的搜索空间 51
3.2.1 逻辑优化的策略空间 52
3.2.2 物理优化的策略空间 52
3.3 多连接查询的代价评估模型 54
3.3.1 查询计划的代价构成 54
3.3.2 查询计划代价估算中的统计信息 55
3.3.3 连接运算结果的代价估计 55
3.3.4 连接运算不同取值个数的估计 56
3.3.5 代价评估数学模型的建立 56
3.4 本章小结 57
第4章 多连接查询搜索算法的应用研究 58
4.1 多连接搜索算法的研究现状分析 58
4.1.1 确定性搜索算法 58
4.1.2 随机搜索算法 59
4.2 动态规划算法在MJQO问题中的应用研究 60
4.2.1 动态规划算法的基本思想 60
4.2.2 基于动态规划算法的MJQO问题的设计与处理流程 61
4.3 贪婪算法在MJQO问题中的应用研究 63
4.3.1 贪婪算法的基本思想 63
4.3.2 基于贪婪算法的MJQO问题的设计与处理过程 64
4.4 模拟退火算法在MJQO问题中的应用研究 69
4.4.1 模拟退火算法的基本思想 69
4.4.2 模拟退火算法的处理流程 69
4.4.3 基于模拟退火算法的MJQO问题的设计与处理过程 70
4.5 遗传算法在MJQO问题中的应用研究 71
4.5.1 遗传算法的基本思想 71
4.5.2 遗传算法的处理流程 75
4.5.3 基于遗传算法的MJQO问题的设计与处理过程 77
4.6 仿真实验与结果分析 78
4.6.1 实验设计 78
4.6.2 实验结果分析 78
4.6.3 算法的对比分析 79
4.7 本章小结 81
第5章 组合遗传退火算法在分布式MJQO中的应用研究 82
5.1 组合遗传退火算法的分析 82
5.2 MJQO问题中组合遗传退火算法的设计 83
5.2.1 搜索空间的选择 83
5.2.2 染色体编码方案 84
5.2.3 适应度函数的分析与设计 86
5.2.4 初始种群的生成 88
5.2.5 选择策略的分析与确定 89
5.2.6 遗传算子的设定 90
5.2.7 个体的模拟退火操作 95
5.2.8 自适应的交叉、变异概率 96
5.2.9 终止条件的设定 97
5.3 组合遗传退火算法的实现 97
5.3.1 算法的流程实现 97
5.3.2 算法实现结构 99
5.4 仿真实验设计及结果分析 99
5.4.1 算法的设计 99
5.4.2 实验结果分析 100
5.5 本章小结 101
第6章 基于分布式编程框架MapReduce的连接优化算法 102
6.1 大数据处理架构 102
6.1.2 数据处理架构 102
6.1.1 并行数据库 102
6.1.2 MapReduce 103
6.1.3 混合数据处理平台 106
6.2 基于MapReduce的连接优化算法 107
6.2.1 基于传统的MapReduce连接优化算法 107
6.2.2 基于改进的MapReduce连接优化算法 111
6.2.3 基于数据索引的连接优化算法 112
6.2.4 基于MapRecuce的文献研究总结 114
6.3 基于MapReduce的等值连接算法的设计 114
6.3.1 算法设计背景及相关介绍 115
6.3.2 基于MapRecuce的BloomFilter构建算法 118
6.3.3 基于BloomFilter的两表等值连接算法设计 123
6.3.4 基于BloomFilter的多表等值连接算法设计 128
6.4 基于BloomFilter的连接算法代价模型 131
6.4.1 BloomFilter建立的代价模型 131
6.4.2 两表等值连接的代价模型 132
6.4.3 多表等值连接的代价模型 134
6.4.4 模型验证 135
6.5 本章小结 136
第7章 数据倾斜的连接算法的设计与优化 137
7.1 MapRecuce环境下的数据倾斜问题 137
7.1.1 数据倾斜问题描述 137
7.1.2 研究现状 138
7.2 两表数据倾斜情况下的等值连接算法 139
7.2.1 两表倾斜的连接问题 139
7.2.2 利用Range Partition方法处理两表倾斜连接 140
7.2.3 改进的两表倾斜的等值连接算法设计 142
7.2.4 与Range Partition分区方法对比 143
7.2.5 算法实现 144
7.2.6 实验设计和结果分析 145
7.3 多表数据倾斜情况下的等值连接算法 149
7.3.1 多表倾斜的连接问题 149
7.3.2 多表倾斜的等值连接算法设计 149
7.3.3 与多表等值连接算法对比 150
7.3.4 算法实现 150
7.3.5 实验设计和结果分析 152
7.4 本章小结 154
第8章 任意连接算法的设计与优化 155
8.1 相关研究背景 155
8.2 Strict-Even-Join的算法设计 156
8.2.1 算法设计 156
8.2.2 数据分区 160
8.2.3 完整算法描述 160
8.2.4 数据集倾斜时的分析 161
8.2.5 与1-Bucket-Theta算法对比 162
8.2.6 与多表等值连接算法对比 162
8.3 基于MapReduce多表任意连接算法优化 163
8.3.1 算法描述 163
8.3.2 MapReduce的并发控制 165
8.4 基于MapReduce的任意连接的代价模型 165
8.4.1 任意连接的代价模型 165
8.4.2 等值连接的代价模型 166
8.5 实验设计与结果分析 167
8.5.1 一轮MapReduce任意连接算法实验 167
8.5.2 优化多表任意连接实验 169
8.6 本章小结 170
参考文献 171
附录 Hadoop 0.20.2安装与配置 187