wordpress设置下载链接,网站建设和优化的好处,360优化大师下载安装,广西远昌建设公司Lecture #10_ Sorting Aggregation Algorithms
Query Plan
数据库系统会将 SQL 编译成查询计划。查询计划是一棵运算符树。
Sorting
DBMS 需要对数据进行排序#xff0c;因为根据关系模型#xff0c;表中的tuple没有特定的顺序。排序使用 ORDER BY、GROUP BY、JOIN…Lecture #10_ Sorting Aggregation Algorithms
Query Plan
数据库系统会将 SQL 编译成查询计划。查询计划是一棵运算符树。
Sorting
DBMS 需要对数据进行排序因为根据关系模型表中的tuple没有特定的顺序。排序使用 ORDER BY、GROUP BY、JOIN 和 DISTINCT 操作符。如果需要排序的数据适合内存那么 DBMS 可以使用标准排序算法如快排。如果数据不适合在内存中进行排序那么 DBMS 就需要使用外部排序这种排序可以根据需要溢出到磁盘并且优先选择顺序 I/O而不是随机 I/O。 如果查询包含一个带 LIMIT 的 ORDER BY那么 DBMS 只需扫描一次数据就能找到前 N 个元素。这就是 top-n 堆排序。堆排序的理想情况是前 N 个元素都在内存中这样 DBMS 只需在扫描数据时维护一个内存中的优先队列即可。 外部合并排序是对大到内存无法容纳的数据进行排序的标准算法。这是一种 分而治之 的排序算法它将数据分割然后分别进行排序。 外部合并排序的一种优化方法是在后台预取下一次运行并在系统处理当前运行时将其存储在第二个缓冲区中。这样可以持续利用磁盘减少每一步 I/O 请求的等待时间。 对于 DBMS 来说使用现有的 Btree 索引辅助排序有时比使用外部合并排序算法更有优势。特别是如果索引是聚簇索引DBMS 就可以直接遍历 Btree 索引。由于索引是聚类的数据将以正确的顺序存储因此 I/O 访问将是顺序的。
Aggregations
实现聚合有两种方法排序和散列。 排序DBMS 首先根据 GROUP BY 键对图元进行排序。如果所有数据都在缓冲池中如 quicksort可以使用内存内排序算法如果数据大小超出内存可以使用外部合并排序算法。然后DBMS 会对排序后的数据执行顺序扫描以计算聚合。运算符的输出将按键排序。在执行排序聚合时必须对查询操作进行排序以最大限度地提高效率。 例如如果查询需要过滤最好先执行过滤然后对过滤后的数据进行排序以减少需要排序的数据量。 哈希
Partition使用哈希函数 h1根据目标哈希键将tuple分组到磁盘上的分区。这将把所有匹配的元组放入同一个bucket。假设共有 B 个缓冲区我们将有 B-1 个输出缓冲区和 1 个输入缓冲区。如果任何分区已满数据库管理系统就会将其溢出到磁盘。ReHash对于磁盘上的每个分区将其页面读入内存并根据第二个哈希函数 h2 建立一个内存哈希表。然后遍历哈希表中的每个桶将匹配的tuple集中起来计算聚合。假设每个分区都适合内存。 Lecture #11_ Joins Algorithms
Joins
重点讨论用于合并两张表的内部等值连接算法。等值连接算法可以连接键值相等的表。 对于在连接属性上匹配的元组 r∈R 和元组 s∈S 连接运算符会将 r 和 s 连接成一个新的输出元组。 实际上连接算子生成的输出元组内容各不相同。这取决于 DBMS 的查询处理模型、存储模型和查询本身。对于连接运算符输出的内容有多种处理方法
Dataearly materialization将外层表和内层表中的属性值复制到中间结果表中的元组中而中间结果表是专门为该算子准备的。这种方法的优点是查询计划中的未来算子无需返回原来的表中去获取更多数据。缺点是需要更多内存来实例化整个元组。DBMS 还可以进行额外的计算省略查询中以后不需要的属性从而进一步优化这种方法。Record IDlate materializationDBMS只复制连接键和匹配元组的记录 ID。这种方法非常适合列存储因为 DBMS 不会复制查询不需要的数据。
连接算法的cost主要指磁盘I/O且只考虑计算join时的 I/O而不考虑输出结果时产生的 I/O。这是因为输出成本取决于数据而且任何连接算法的输出都是相同的。
Nested Loop Join
这种连接算法由两个嵌套的 for 循环组成这两个 for 循环遍历两个表中的tuple并对每个tuple进行配对比较。外层 for 循环中的表称为外层表内层 for 循环中的表称为内层表。 DBMS 总是希望使用较少tuple或者page的表作为外层表还希望在内存中缓冲尽可能多的外层表。它还可以尝试利用索引来查找内表中的匹配项。
Naive Nested Loop Join 朴素方法Cost: M (m × N) Block Nested Loop Join 对外部表中的每个数据块从内部表中获取每个数据块然后比较这两个数据块中的所有元组Cost: M ((# of blocks in R) × N)如果 DBMS 有 B 个缓冲区可用来计算join那么它可以使用 B - 2 个缓冲区来扫描外表使用一个缓冲区扫描内表并使用一个缓冲区存储连接的输出结果 Index Nested Loop Join 如果数据库已经为其中一个表建立了关于join key的索引就可以利用它来加快比较速度。DBMS 可以使用现有索引或为连接操作建立临时索引外层表将是没有索引的表内表是有索引的表假设每个索引探针的cost是每个元组的某个恒定值 CCost: M (m × C)
Sort-Merge Join
根据两个表的连接键对两个表进行排序。DBMS 可以使用外部合并排序算法来实现这一点。 这种算法的最坏情况是两个表中所有tuple的连接属性都包含相同的值而这在实际数据库中是不太可能发生的。在这种情况下合并的成本将是 M × N。不过在大多数情况下键大多是唯一的因此合并成本大约是 M N。 假设 DBMS 有 B 个缓冲区可用。
Hash Join
使用散列表根据连接属性将tuple分割成较小的块。这减少了 DBMS 为计算连接而需要对每个tuple执行的比较次数。hash join只能用于完整join key的等值连接。 如果元组 r∈R 和元组 s∈S 满足连接条件那么它们的连接属性值相同。如果该值散列为某个值 i则 R 元组必须位于数据桶 ri 中而 S 元组必须位于数据桶 si 中。因此只需将数据桶 ri 中的 R 元组与数据桶 si 中的 S 元组进行比较即可。
Basic Hash Join 如果 DBMS 知道外层表的大小则连接可以使用静态哈希表。如果数据库管理系统不知道外层表的大小那么连接就必须使用动态哈希表或允许溢出页面探测阶段的一种优化方法是使用 Bloom 过滤器。这是一种概率数据结构可放入 CPU 缓存中并以肯定为 “否” 或可能为 “是” 来回答 “键 x 是否在哈希表中” 的问题。它可以防止磁盘读取不会导致匹配的数据从而减少磁盘 I/O Grace Hash Join / Partitioned Hash Join 当主内存无法容纳这些表时数据库管理系统就必须从磁盘读取或写入表从而导致性能低下。Grace Hash Join 是basic的扩展它将内表也散列成分区并将这些分区写入分区表中。
Conclusion Lecture #12_ Query Processing I.md
Query Plan
DBMS 将 SQL 语句转换为查询计划。查询计划中的算子以树状排列数据从树叶流向树根。树中根节点的输出就是查询结果。算子通常是二进制的1-2 个子节点。同一查询计划可以通过多种方式执行。
Processing Models
DBMS 处理模型定义了系统如何执行查询计划。它规定了查询计划的评估方向以及算子之间沿途传递的数据类型。
Iterator Model 迭代器模型也称为火山模型或管道模型是最常见的处理模型几乎所有基于行的数据库管理系统都使用这种模型迭代器模型的工作原理是为数据库中的每个算子实现一个 Next 函数。查询计划中的每个节点都会对其子节点调用 Next直到到达叶节点叶节点开始向其父节点发送tuple进行处理。然后在检索下一个tuple之前每个tuple都会在计划中尽可能向上处理。这在基于磁盘的系统中非常有用因为它允许我们在访问下一个tuple或页面之前充分利用内存中的每个tuple。 Materialization Model 物化模型是迭代器模型的一种特殊化其中每个算子一次性处理其输入然后一次性输出。每个算子每次都会返回其所有的tuple而不是使用一个返回单个tuple的Next函数。为避免扫描过多的tupleDBMS可以向下传播后续需要多少tuple如 LIMIT。 算子将其输出 具体化 为一个结果。输出可以是整个tupleNSM也可以是列的子集DSM更适合 OLTP因为查询通常一次只访问少量图元。因此检索图元的函数调用较少。物化模型不适合具有大量中间结果的 OLAP 查询因为 DBMS 可能需要将结果溢出到磁盘 Vectorized / Batch Model 与迭代器模型一样矢量化模型中的每个算子都实现了一个 Next 函数。不过每个算子发出的是a batch of data即向量而不是单个tuple适合需要扫描大量tuple的 OLAP 查询因为调用 Next 函数的次数较少 Access Methods
访问方法是指 DBMS 如何访问表中存储的数据。一般来说访问模型有两种方法要么从表中读取数据要么通过顺序扫描从索引中读取数据。
Sequential Scan 顺序扫描算子遍历表中的每一页并从缓冲池中检索。当扫描遍历每一页上的所有元组时它会评估以决定是否将元组发送给下一个运算符顺序扫描优化 预取几个page避免频繁阻塞存储I/O将从磁盘获取的page存储在内存中而不是缓冲池避免sequential flooding多线程并行扫描Late MaterializationDSM DBMS 将tuple拼接延迟每个算子将所需的最少信息传递给下一个算子如Record IDrecord在列中的偏移量。这只在列存储系统中有用使用聚类索引指定的顺序将tuple存储在堆页面中近似查询有损数据跳过在整个表的抽样子集上执行查询以产生近似结果。这通常用于在允许低误差的情况下计算聚合从而得出近似准确的答案Zone Map无损数据跳过为页面中的每个元组属性预先计算聚合然后数据库管理系统可以通过先检查页面的 Zone Map 来决定是否需要访问该页面。每个页面的 Zone Map 都存储在不同的页面中每个 Zone Map 页面通常有多个条目。因此可以减少顺序扫描中检查的页面总数 Index Scan 在索引扫描中DBMS会选择一个索引来查找查询所需的tuple更先进的 DBMS 支持多索引扫描。当查询使用多个索引时DBMS会通过每个匹配索引计算 record ID 集根据查询谓词组合这些集然后检索记录并应用可能保留的任何谓词。数据库管理系统可以使用位图、哈希表或 Bloom 过滤器通过集合交集计算 record ID。
Modification Queries
修改数据库的算子INSERT、UPDATE、DELETE负责检查约束和更新索引。对于 UPDATE/DELETE子算子传递目标tuple的record ID并且必须跟踪以前查看过的tuple。
Halloween Problem 万圣节问题是一种异常更新操作会改变tuple的物理位置导致扫描多次访问该tuple解决这个问题的办法是跟踪每次查询修改的record ID。
Expression Evaluation
DBMS 将 WHERE 子句表示为expression tree。树中的节点代表不同的表达式类型。 DBMS 会维护一个上下文句柄其中包含执行的元数据如当前元组、参数和表模式。然后DBMS 会遍历表达式树以评估其运算符并生成结果。 这种方式的速度很慢因为 DBMS 必须遍历整个树并确定对每个算子采取的正确操作。更好的方法是直接评估表达式JIT。根据内部成本模型DBMS将决定是否采用代码生成来加速查询。
Lecture #13_ Query Execution II
Background
并行执行为 DBMS 带来了许多关键优势。 DBMS 支持两种类型的并行查询间并行和查询内并行。
Parallel vs Distributed Databases
在并行和分布式系统中数据库被分散到多个 资源 中以提高并行性。这些资源可以是计算资源如 CPU 内核、CPU 插槽、GPU、附加机器或存储资源如磁盘、内存。
Parallel DBMS资源或节点在物理上彼此靠近。这些节点通过高速互连进行通信。它假设资源之间的通信不仅快速而且便宜可靠Distributed DBMS资源之间可能相距甚远因此资源使用较慢的互连通常通过公共网络进行通信。节点之间的通信成本较高而且故障不容忽视
Process Models
DBMS 流程模型定义了系统如何支持来自多用户应用程序/环境的并发请求。DBMS 由一个或多个worker组成他们负责代表客户执行任务并返回结果。应用程序可能会同时发送一个大型请求或多个请求这些请求必须在不同的worker之间进行分配。
Process per Worker 这种模式依赖于共享内存来维护全局数据结构或者依赖于消息传递而消息传递的开销更大优势在于进程崩溃不会破坏整个系统因为每个worker都在自己的OS进程中运行问题不同进程中的多个workers对同一页面进行多次复制。最大化内存使用率的解决方案是为全局数据结构使用共享内存这样不同进程中运行的worker就可以共享这些数据结构 Thread per Worker 每个数据库系统只有一个带有多个工作线程的进程而不是由不同的进程执行不同的任务。在这种环境下DBMS 可以完全控制任务和线程自己管理调度。多线程模型可以使用或不使用调度线程每次上下文切换的开销较少无需维护共享模型。不过线程崩溃有可能导致整个数据库进程瘫痪。此外并不一定意味着 DBMS 支持查询内并行 Embedded DBMS 在应用程序的同一地址空间中运行系统而不是在C/S模式中数据库独立于应用程序。在这种情况下应用程序将设置在数据库系统上运行的线程和任务。应用程序本身主要负责调度
Inter-Query Parallelism
在查询间并行中数据库管理系统会同时执行不同的查询。
Intra-Query parallelism
在查询内并行中数据库管理系统并行执行单个查询的操作。这可减少长时间运行查询的延迟。 可以从生产者/消费者模式的角度来考虑。 每个算子既是数据的生产者也是其下级算子的数据消费者。 每个关系算子都有并行算法。DBMS 可以让多个线程访问集中式数据结构也可以使用分区来划分工作。 在查询内并行中有三种并行类型算子内并行、算子间并行和总线并行。
Intra-Operator Parallelism (Horizontal) DBMS 会在查询计划中插入一个exchange算子三种类型gather、distribute、repartition以合并来自子算子的结果。交换算子会阻塞 DBMS 执行计划中高于它的算子直到它收到子算子的所有数据。 Inter-Operator Parallelism (Vertical) 数据库管理系统会重叠运算符以便将数据从一个阶段流水线输送到下一个阶段而不需要实体化。这有时被称为流水线并行 Bushy Parallelism 混合体在这种情况下算子会同时执行来自查询计划不同部分的多个算子。 DBMS 仍会使用exchange来合并这些部分的中间结果
I/O Parallelism
如果磁盘始终是主要瓶颈那么使用额外进程/线程并行执行查询并不能提高性能。因此在多个存储设备上拆分数据库非常重要。 两种方法多磁盘并行性和数据库分区。
Multi-Disk Parallelism 在多个存储设备上存储 DBMS 的文件。这可以通过存储设备或 RAID 配置来实现; Database Partitioning 数据库被分割成互不相连的子集这些子集可以分配到不同的磁盘上逻辑分区的概念是将单个逻辑表分割成互不关联的物理段分别存储/管理。理想情况下这种分区对应用程序是透明的
Lecture #14_ Query Planning Optimization.md
Overview
查询只能告诉 DBMS 要计算什么而不能告诉 DBMS 如何计算。因此数据库管理系统需要将 SQL 语句转化为可执行的查询计划。但是执行查询计划中每个算子如连接算法的方法各不相同这些计划的性能也会有差异。DBMS 优化器的工作就是为任何给定的查询选择一个最佳计划。 优化器将逻辑代数表达式映射为最佳等效物理代数表达式。逻辑计划大致等同于查询中的关系代数表达式。 物理运算符使用查询计划中不同运算符的访问路径定义了特定的执行策略。物理计划可能取决于所处理数据的物理格式如排序、压缩。 从逻辑计划到物理计划并不总是存在一对一的映射。
Logical Query Optimization
选择优化措施包括尽早执行过滤对谓词重新排序以便 DBMS 首先应用选择性最强的谓词分解复杂谓词并将其下推拆分连接谓词。 投影优化措施包括尽早执行投影以创建更小的元组并减少中间结果剔除不需要的属性。 查询重写优化包括删除不可能或不必要的谓词。在这种优化中数据库管理系统会忽略不会改变结果的谓词的评估合并谓词通过去关联化和扁平化嵌套子查询来重写查询分解嵌套查询并将结果存储到临时表中。 JOIN操作的顺序是决定查询性能的关键因素。穷举效率很低因此需要一个成本模型。不过仍然可以通过启发式优化方法消除不必要的连接。
Cost Estimations
DBMS 使用成本模型来估算执行计划的成本CPU、disk I/O、memory、network。这些模型会评估查询的等价计划以帮助 DBMS 选择最优计划。 selection cardinality可用于确定对于输入将选择的图元数量。 谓词的选择性等同于该谓词的概率。这使得概率规则可以应用于许多选择性计算中。这在处理复杂谓词时尤其有用。例如如果我们假设连接中涉及的多个谓词是独立的那么我们就可以计算连接的总 selectivity即乘积。
Histograms
真实数据通常是有偏差的要对其做出假设非常困难。然而存储数据集的每一个值都很昂贵。减少内存使用量的一种方法是将数据存储在直方图中将数值分组另一种方法是使用等深直方图改变桶的宽度使每个桶的出现总数大致相同。
Sampling
DBMS 可以使用抽样将谓词应用于具有类似分布的表的较小副本。每当底层表的变化量超过阈值时DBMS 就会更新样本。
Plan Enumeration
在执行重写后数据库管理系统将枚举查询的不同计划并估算其成本。然后它会在穷尽所有计划或某个超时后为查询选择最佳计划。
Single-Relation Query Plans
对于单相关查询计划最大的障碍是选择最佳访问方法如顺序扫描、二进制搜索、索引扫描等。大多数新数据库系统只是使用启发式方法。 对于 OLTP 查询来说很容易因为它们是可搜索的Search Argument Able这意味着存在一个可以为查询选择的最佳索引。这也可以通过简单的启发式方法来实现。
Multi-Relation Query Plans
对于多关联查询计划随着连接数的增加备选计划的数量也会迅速增加。 因此必须限制搜索空间以便能够在合理的时间内找到最优计划。
Bottom-up optimization example - System R
使用静态规则进行初始优化。然后使用动态编程用分而治之的搜索方法确定表的最佳连接顺序。
Top-down optimization example - Volcano
从希望查询的逻辑计划开始。通过将逻辑运算符转换为物理运算符执行分支和边界搜索来遍历计划树。
