大数据中数据库是如何工作的（二）

　　数据库是可以轻松访问和修改的信息的集合，但是一堆简单的文件也可以做到这一点。实际上，最简单的数据库(如SQLite)仅是一堆文件，你知道大数据中数据库是如何工作的吗?
 

　　SQLite是一堆精心设计的文件，因为它允许你执行以下操作：使用确保数据安全和连贯的交易，即使你正在处理数百万个数据，也可以快速处理数据，数据库可以如下图所示：
 

　　将数据库分为相互交互的多个组件。
 

　　核心组件：
 

　　进程管理器：许多数据库都有一个需要管理的进程/线程池。而且，为了获得纳秒级的性能，某些现代数据库使用其自己的线程而不是操作系统线程。
 

　　网络管理员：网络I / O是一个大问题，尤其是对于分布式数据库。这就是为什么某些数据库拥有自己的管理器的原因。
 

　　文件系统管理器：磁盘I / O是数据库的第一个瓶颈。重要的是拥有一个能够完美处理操作系统文件系统甚至替换它的管理器。
 

　　内存管理器：为避免磁盘I / O损失，需要大量的内存。但是，如果你处理大量内存，则需要高效的内存管理器。尤其是当你有多个查询同时使用内存时。
 

　　安全管理器：用于管理用户的身份验证和授权
 

　　客户经理：用于管理客户连接
 

　　…
 

　　工具：
 

　　备份管理器：用于保存和还原数据库。
 

　　Recovery Manager：用于在崩溃后以一致的状态重新启动数据库
 

　　监视管理器：用于记录数据库的活动并提供监视数据库的工具
 

　　管理管理器：用于存储元数据(如表的名称和结构)，并提供工具来管理数据库，模式，表空间.....
 

　　查询管理器：
 

　　查询解析器：检查查询是否有效
 

　　查询重写器：预优化查询
 

　　查询优化器：优化查询
 

　　查询执行器：编译并执行查询
 

　　数据管理器：
 

　　交易经理：处理交易
 

　　高速缓存管理器：在使用数据之前先将其放入内存中，然后在将其写入磁盘之前先将其放入内存中
 

　　数据访问管理器：访问磁盘上的数据
 

　　对于本文的其余部分，我将重点介绍数据库如何通过以下过程来管理SQL查询：
 

　　客户经理
 

　　查询管理器
 

　　数据管理器(在这一部分中，我还将包括恢复管理器)
 

　　客户经理
 

　　客户经理是处理与客户通信的部分。客户端可以是(Web)服务器或最终用户/最终应用程序。客户端管理器提供了通过一组著名的API访问数据库的不同方法：JDBC，ODBC，OLE-DB…
 

　　它还可以提供专有的数据库访问API。
 

　　当你连接到数据库时：
 

　　管理员首先检查你的身份验证(你的登录名和密码)，然后检查你是否具有使用该数据库的授权。这些访问权限由你的DBA设置。
 

　　然后，它检查是否有一个进程(或线程)可用于管理你的查询。
 

　　它还会检查数据库是否不处于高负荷状态。
 

　　它可以等待片刻以获取所需的资源。如果此等待达到超时，它将关闭连接并给出可读的错误消息。
 

　　然后它将你的查询发送到查询管理器并处理你的查询
 

　　由于查询处理不是“全有或全无”的事情，因此，一旦它从查询管理器获取数据，它将部分结果存储 在缓冲区中并开始将其发送给你。
 

　　出现问题时，它将停止连接，为你提供易于阅读的解释并释放资源。
 

　　查询管理器
 

　　这是数据库功能所在的地方。在这一部分中，将写得不好的查询转换为快速的可执行代码。然后执行代码，并将结果返回给客户管理器。这是一个多步骤操作：首先解析查询以查看其是否有效，然后将其重写以删除无用的操作并添加一些预优化，然后对其进行优化以提高性能，并将其转变为执行和数据访问计划，然后编制计划，最后执行。
 

　　PostgreSQL的如何优化一个很好的演示查询这里。这是最易访问的文档，因为它比“让我们看看PostgreSQL使用的算法”更多地是关于“让我们看看PostgreSQL在这些情况下给出的查询计划”。
 

　　有关优化的官方SQLite文档。它很容易阅读，因为SQLite使用简单的规则。而且，这是唯一真正说明其工作原理的官方文档。
 

　　查询解析器
 

　　每个SQL语句都发送到解析器，在该处检查语法是否正确。如果你在查询中输入错误，则解析器将拒绝该查询。例如，如果你写的是“ SLECT…”而不是“ SELECT…”，那么故事到此结束。
 

　　但这更深了，它还检查是否以正确的顺序使用了关键字。例如，SELECT之前的WHERE将被拒绝。然后，分析查询中的表和字段。解析器使用数据库的元数据来检查：如果这些表存在;如果表的字段存在;如果可以对字段类型进行操作(例如，你不能将整数与字符串进行比较，则不能对整数使用substring()函数)。然后，它检查你是否具有读取(或写入)查询中的表的权限。同样，这些对表的访问权限由你的DBA设置。
 

　　在此解析期间，SQL查询将转换为内部表示形式(通常为树)，如果一切正常，则将内部表示形式发送到查询重写器。
 

　　查询重写器
 

　　在此步骤中，我们具有查询的内部表示。重写器的目的是：预优化查询，避免不必要的操作，帮助优化器找到最佳解决方案
 

　　重写器在查询中执行已知规则的列表。如果查询符合规则的模式，则将应用规则并重写查询。以下是(可选)规则的详尽列表：
 

　　视图合并：如果你在查询中使用视图，则将使用该视图的SQL代码转换该视图。
 

　　子查询展平：很难优化子查询，因此重写器将尝试使用子查询修改查询以删除子查询。
 

　　删除不必要的运算符：例如，如果使用DISTINCT却有一个UNIQUE约束来防止数据不唯一，则DISTINCT关键字将被删除。
 

　　冗余联接消除：如果由于一个联接条件被隐藏在视图中而使你拥有两次相同的联接条件，或者由于传递性而存在无用的联接，则将其删除。
 

　　恒定算术评估：如果编写需要演算的内容，则在重写过程中将对其进行一次计算。例如，将WHERE AGE> 10 + 2转换为WHERE AGE> 12，然后将TODATE(“ some date”)转换为datetime格式的日期
 

　　(高级)分区修剪：如果你使用的是分区表，重写器将能够找到要使用的分区。
 

　　(高级)实例化视图重写：如果你具有与查询中的谓词子集匹配的实例化视图，则重写器将检查该视图是否为最新视图，并将查询修改为使用实例化视图而不是原始表。
 

　　(高级)自定义规则：如果你具有用于修改查询的自定义规则(例如Oracle策略)，则重写器将执行这些规则
 

　　(高级)Olap转换：分析/窗口函数，星型连接，汇总……也都进行了转换(但是我不确定是由重写器还是优化器完成的，因为这两个过程都非常接近，它必须取决于数据库)。然后，这个重写的查询将发送到查询优化器。
 

　　统计数据：在我们看到数据库如何优化查询之前，我们需要先谈谈统计信息，因为没有统计信息，数据库是愚蠢的。如果你不告诉数据库分析自己的数据，它将不会这样做，并且会做出(非常)错误的假设。
 

　　数据库和操作系统如何存储数据?他们利用所谓的最小单位一个 页面或块(4或8千字节默认情况下)。这意味着，如果你只需要1 KB，则将花费你一页。如果页面占用8 KB，那么你将浪费7 KB。
 

　　当你要求数据库收集统计信息时，它计算的值如下：表中的行数/页数;对于表中的每一列：不同的数据值，数据值的长度(最小值，最大值，平均值)，数据范围信息(最小值，最大值，平均值)，有关表索引的信息。
 

　　这些统计信息将帮助优化器估计查询的 磁盘I / O，CPU和内存使用率。
 

　　每列的统计信息非常重要。例如，如果需要在2列上联接表PERSON：LAST_NAME，FIRST_NAME。根据统计信息，数据库知道FIRST_NAME上只有1000个不同的值，而LAST_NAME上只有1000万个不同的值。因此，数据库将联接LAST_NAME，FIRST_NAME而不是FIRST_NAME，LAST_NAME上的数据，因为它产生的方式比较少，因为LAST_NAME不太可能相同，因此大多数情况下，比较数据库的第2个(或3个)首字符LAST_NAME就足够了。
 

　　但是这些是基本统计数据。你可以要求数据库计算称为直方图的高级统计信息。直方图是统计信息，用于通知列中值的分布。
 

　　这些额外的统计信息将帮助数据库找到更好的查询计划。特别是对于相等谓词(例如：WHERE AGE = 18)或范围谓词(例如：WHERE AGE> 10和AGE <40)，因为数据库会对这些谓词所涉及的行数有更好的了解(请注意：这个概念就是选择性)。
 

　　统计信息存储在数据库的元数据中。该统计数据必须是最新的。没有什么比数据库认为表只有500行而表有1 000 000行更糟糕的了。统计信息的唯一缺点是计算它们需要时间。这就是为什么在大多数数据库中默认情况下不会自动计算它们的原因。数以百万计的数据很难对其进行计算。在这种情况下，你可以选择仅计算基本统计信息或计算数据库样本的统计信息。
 

　　查询优化器

　　所有现代数据库都使用基于成本的优化(CBO)来优化查询。这样做的目的是为每次操作增加成本，并通过使用最便宜的操作链来获取结果，从而找到降低查询成本的最佳方法。
 

　　为了理解成本优化器的工作原理，最好有一个示例来“感觉”该任务背后的复杂性。即使是简单的联接查询也是要优化的噩梦。
 

　　对于这些连接，专注于自己的时间复杂度，但一个数据库优化计算的CPU成本，磁盘I / O成本和存储空间需求。时间复杂度和CPU成本之间的区别在于，时间成本非常近似。对于CPU成本，应该将每个操作都算作加法，“ if语句”，乘法，迭代…等等。此外：每个高级代码操作都有特定数量的低级CPU操作。
 

　　无论你使用的是Intel Core i7，Intel Pentium 4，AMD Opteron…，CPU操作的成本(在CPU周期方面)都不相同。换句话说，它取决于CPU体系结构。使用时间复杂度更容易，并且有了它，我们仍然可以得到CBO的概念，瓶颈通常是磁盘I / O而不是CPU使用率。
 

　　指标
 

　　看到B + Trees时谈到索引，这些索引就已经排序了。还有其他类型的索引，例如位图索引。在CPU，磁盘I / O和内存方面，它们提供的成本与B + Tree索引所提供的成本不一样。此外，如果可以提高执行计划的成本，许多现代数据库可以仅为当前查询动态创建临时索引。
 

　　存取路径：在应用联接运算符之前，你首先需要获取数据。这是获取数据的方法。
 

　　全面扫描：如果你曾经阅读过执行计划，那么你肯定已经看到“完全扫描”(或仅扫描)一词。完全扫描只是数据库完全读取一个表或一个索引。就磁盘I / O而言，表完全扫描显然比索引完全扫描更昂贵。
 

　　范围扫描：还有其他类型的扫描，例如索引范围扫描。例如，当你使用“ WHERE AGE> 20 AND AGE <40”这样的谓词时，将使用它。你需要在AGE字段上有一个索引才能使用此索引范围扫描。
 

　　范围查询的时间成本类似于log(N)+ M，其中N是此索引中的数据数，而M是对该范围内的行数的估计。由于统计信息，N和M值都已知(注意：M是谓词AGE> 20 AND AGE <40的选择性)。而且，对于范围扫描，你不需要读取完整索引，因此就磁盘I / O而言，它比完整扫描便宜。
 

　　独特扫描：如果你只需要索引中的一个值，则可以使用唯一扫描。
 

　　按行ID访问：在大多数情况下，如果数据库使用索引，则它将不得不查找与索引关联的行。为此，它将使用按行ID进行的访问。
 

　　如果你有一个列年龄的人的索引，那么优化器将使用该索引查找所有28岁的人，然后它会询问表中的关联行，因为索引仅包含有关年龄的信息，并且你想知道姓氏和名字。
 

　　SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
 

　　WHERE PERSON.AGE = TYPE_PERSON.AGE
 

　　PERSON上的索引将用于与TYPE_PERSON联接，但是行ID将无法访问表PERSON，因为你没有在该表上询问信息。
 

　　尽管它对于某些访问非常有效，但此操作的真正问题是磁盘I / O。如果你需要通过行ID进行太多访问，则数据库可能会选择完全扫描。
 

　　3个常见的联接运算符：合并联接，哈希联接和嵌套循环联接。
 

　　当你连接两个关系时，连接算法对两个关系的管理方式不同。在本文的其余部分，假定：外部关系是左数据集，内部关系是正确的数据集。A JOIN B是A和B之间的联接，其中A是外部关系，B是内部关系。在大多数情况下，A JOIN B的成本与B JOIN A的成本不同。在这一部分中，假设外部关系具有N个元素 ，内部关系具有M个元素。真正的优化程序可以通过统计信息了解N和M的值，N和M是关系的基数。
 

　　嵌套循环联接是最简单的一种。
 

　　对于外部关系中的每一行，你查看内部关系中的所有行以查看是否存在匹配的行。
 

　　nested_loop_join(array outer, array inner)
 

　　for each row a in outer
 

　　for each row b in inner
 

　　if (match_join_condition(a,b))

 

　　write_result_in_output(a,b)
 

　　end if
 

　　end for
 

　　end for
 

　　由于是两次迭代，因此时间复杂度为O(N * M)。就磁盘I / O而言，对于外部关系中的N行中的每行，内部循环都需要从内部关系中读取M行。该算法需要从磁盘读取N + N * M行。但是，如果内部关系足够小，则可以将该关系存储在内存中，并且只需进行M + N次读取即可。通过这种修改，内部关系必须是最小的，因为它有更多的机会适合内存。
 

　　就时间复杂度而言，没有什么区别，就磁盘I / O而言，最好只读取一次两个关系。当然，内部关系可以用索引代替，这对于磁盘I / O会更好。由于此算法非常简单，因此如果内部关系太大而无法容纳在内存中，则这是另一个对磁盘I / O更友好的版本，不是逐行阅读两个关系。
 

　　一堆又一堆地读取它们，并在内存中保留2束行(来自每个关系)，比较两个束中的行，并保持匹配的行，然后从磁盘加载新的束并进行比较，以此类推，直到没有束要加载为止。
 

　　// improved version to reduce the disk I/O.
 

　　nested_loop_join_v2(file outer, file inner)
 

　　for each bunch ba in outer
 

　　// ba is now in memory
 

　　for each bunch bb in inner
 

　　// bb is now in memory
 

　　for each row a in ba
 

　　for each row b in bb
 

　　if (match_join_condition(a,b))
 

　　write_result_in_output(a,b)
 

　　end if
 

　　end for
 

　　end for
 

　　end for
 

　　end for
 

　　使用此版本，时间复杂度保持不变，但是磁盘访问数量减少了：在以前的版本中，该算法需要N + N * M次访问(每个访问获得一行)，在此新版本中，磁盘访问数变为number_of_bunches_for(外部)+ number_of_ bundlees_for(外部)* number_of_ bundlees_for(内部)。如果增加束的大小，则会减少磁盘访问次数。
 

　　哈希联接
 

　　在许多情况下，哈希联接比嵌套循环联接更复杂，但成本更高。

　　哈希联接的想法是：
 

　　1)从内部关系中获取所有元素
 

　　2)建立一个内存中的哈希表
 

　　3)一对一地获得外部关系的所有元素
 

　　4)计算每个元素的哈希值(使用哈希表的哈希函数)以找到内部关系的关联存储区
 

　　5)查找存储桶中的元素与外部表的元素之间是否存在匹配项
 

　　在时间复杂度方面，我需要做一些假设来简化问题：
 

　　内部关系分为X个值区，散列函数为这两种关系几乎均匀地分布散列值。换句话说，铲斗尺寸相同。外部关系的元素与存储桶中的所有元素之间的匹配会花费存储桶中的元素数。时间复杂度为(M / X)* N + cost_to_create_hash_table(M)+ cost_of_hash_function * N，如果哈希函数创建了足够多的小型存储桶，则时间复杂度为O(M + N)
 

　　哈希联接的另一个版本对内存更友好，但对磁盘I / O的友好性更低：
 

　　1)计算内部和外部关系的哈希表
 

　　2)然后将它们放在磁盘上
 

　　3)然后按桶比较2个关系桶(其中一个加载在内存中，另一个逐行读取)，合并加入，合并联接是唯一产生排序结果的联接。
 

　　合并联接可以分为两个步骤：(可选)对联接操作进行排序：两个输入都对联接键进行了排序;合并联接操作：将排序的输入合并在一起。
 

　　合并加入
 

　　这部分与我们看到的合并排序的合并操作非常相似。但是这一次，我们没有从两个关系中选择每个元素，而是仅从两个关系中选择了相等的元素。
 

　　1)比较2个关系中的两个当前元素(第一次时current = first)
 

　　2)如果它们相等，则将两个元素都放入结果中，然后转到两个关系的下一个元素
 

　　3)如果不是，则转到具有最低元素的关系的下一个元素(因为下一个元素可能匹配)
 

　　4)并重复1,2,3，直到到达其中一个关系的最后一个元素。
 

　　之所以可行，是因为两个关系都已排序，因此你无需在这些关系中“返回”。
 

　　此算法是简化版本，因为它无法处理相同数据在两个数组中多次出现(换句话说，多个匹配项)的情况。对于这种情况，实际版本“更复杂”。这就是为什么我选择了简化版本。
 

　　如果两个关系都已排序，则时间复杂度为O(N + M);如果两个关系都需要排序，那么时间复杂度就是两个关系的排序成本：O(N * Log(N)+ M * Log(M))
 

　　在可用内存量：没有足够的内存，你可以说再见了强大的散列连接(至少满内存哈希联接)。
 

　　2个数据集的大小。例如，如果一个很小的表，则嵌套循环联接将比哈希联接要快，因为哈希联接具有昂贵的哈希创建。如果你有2个非常大的表，则嵌套循环联接将占用大量CPU。该存在的指标。使用2个B + Tree索引，明智的选择似乎是合并联接
 

　　如果需要对结果进行排序：即使你正在使用未排序的数据集，你也可能希望使用代价高昂的合并联接(带有排序)，因为最后将对结果进行排序并且可以链接另一个合并联接的结果(或者可能是因为查询通过ORDER BY / GROUP BY / DISTINCT操作隐式/显式地要求排序结果)
 

　　如果关系已经排序：在这种情况下，合并联接是最佳候选者
 

　　该类型的连接，你正在做的：这是一个等值连接(即：tableA.col1 = tableB.col2)?它是一个内部联接，一个外连接，一个笛卡尔积或自连接?某些联接在某些情况下不起作用。
 

　　该数据的分布。如果在数据连接条件是倾斜的(例如你在自己的姓氏加入的人，但很多人都有相同的)，使用散列连接将是一场灾难，因为哈希函数将产生不良分布式桶。
 

　　如果我们需要联接5个表才能完整地看到一个人，一个人可以有：多个移动，多个邮件，多个地址，多个BANK_ACCOUNTS，换句话说，我们需要以下查询的快速答案：
 

　　SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
 

　　WHERE
 

　　PERSON.PERSON_ID = MOBILES.PERSON_ID
 

　　AND PERSON.PERSON_ID = MAILS.PERSON_ID
 

　　AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
 

　　AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
 

　　作为查询优化器，必须找到处理数据的最佳方法。但是有两个问题：应该为每种联接使用哪种联接?有3种可能的联接(哈希联接，合并联接，嵌套联接)，可以使用0,1或2个索引(更不用说有不同类型的索引了)。
 

　　应该选择什么顺序来计算联接?下图显示了4个表上仅3个联接的不同可能计划
 

　　所以以下是可能性：
 

　　1)使用蛮力方法
 

　　使用数据库统计信息，计算出每种可能的计划的成本，并保持最佳计划。但是有很多可能性。对于给定的联接顺序，每个联接都有3种可能性：HashJoin，MergeJoin，NestedJoin。因此，对于给定的连接顺序，存在3 4种可能性。连接排序是二叉树上的一个置换问题，有(2 * 4)!/(4 + 1)!!可能的订单。对于这个非常简化的问题，最终得到3 4 *(2 * 4)!/(4 + 1)!可能性。
 

　　用非极客术语来说，这意味着27 216个可能的计划。如果现在添加使合并联接采用0,1或2个B + Tree索引的可能性，则可能的计划数变为210000。
 

　　由于不是超人，所以无法计算每个计划的成本。相反，可以任意选择所有可能计划的子集，计算其成本，然后为你提供此子集的最佳计划。运用精明的规则来减少可能的计划数量。
 

　　有两种类型的规则：
 

　　可以使用“逻辑”规则来消除无用的可能性，但是它们不会过滤很多可能的计划。例如：“嵌套循环连接的内部关系必须是最小的数据集”
 

　　接受没有找到最佳解决方案，而是采用更具侵略性的规则来减少大量可能性的想法。例如：“如果关系很小，请使用嵌套循环联接，切勿使用合并联接或哈希联接”
 

　　在这个简单的示例中，最终有很多可能性。但是实际查询可以具有其他关系运算符，例如OUTER JOIN，CROSS JOIN，GROUP BY，ORDER BY，PROJECTION，UNION，INTERSECT，DISTINCT……这意味着更多的可能性。
 

　　强大的大数据中数据库是如何工作的?他可以承载我们无法想象的数据，并且为我们所用，因此，很多朋友对大数据抱有强烈的探究意味，甚至跃跃欲试，但是大数据专业并不是那么简单的，AAA教育的大数据分析专业课程包括数据分析、Python、机器学习和人工智能，能够进行系统全面地学习才能更好更快的理解和掌握，自我探索的道路并不是平坦的。这是大数据中数据库是如何工作的第二部分，显然并未完结，感兴趣的朋友一起接着往下看吧。