数据库索引设计与优化06-星型连接

介绍

  1. 位于星型结构中心位置的表称为事实表,它的数据量远大于它周围的表---维度表。
  2. 最佳的访问路径通常是包含维度表的笛卡尔积,这意味着他们没有相同的冗余列,满足本地谓词的维度表数据行都会参与连接。

假设事实表SALES有100万行记录,每行代表一条销售记录。4张维度表(DATE,1000行;STORE,10000行;CUST,1000000行;ITEM,100000行)。每行代表一条销售记录。4张维度表提供了每条销售记录的详细信息 : 哪家店的那件商品在何时销售给了哪位客户。为了更好的理解,我们使用SQL 9.1展示一个示例,这个示例简化了场景,只使用除客户信息表以外的三个维度表的信息(我们假设并不需要获取客户的信息)。
SQL 9.1

SELECT SUM(EUR)
FROM SALES, DATE, ITEM, STORE
WHERE ITEM.GROUP = 327
      AND
      DATE.WEEK = 327
      AND
      STORE.REGION = 101
      AND
      SALES.ITEMPK = ITEM.ITEMPK
      AND
      SALES.DATEPK = DATE.DATEPK
      AND
      SALES.STOREPK = STORE.STOREPK

这个星型连接很简单 : 某种商品在某个地区的周销售总额。ITEM表中包含产品码,DATE表中包含日期,STORE表中包含地区码。

在数据仓库环境中,星型模型(和星型连接)比较普遍,因为终端用户只需要一条简单的SELECT语句,就可以从n个维度的数据立方体中获取期望的结果集。

在星型连接中,事实表的数据量通过都比较大。在这种情况下,至少依据经验法则,事实表应该作为嵌套循环连接方式中最内层的表。一般情况下未读表都没有共同的列,所以这种链接顺序意味着是笛卡尔连接。

接下来将讨论影响连接性能的两个主要因素 : 所以设计和表访问顺序。随着讨论的展开,笛卡尔连接的概念将逐渐清晰起来。我们将首先讨论维度表的索引设计,然后讨论表的访问顺序,最后讨论事实表的索引设计。

维度表的索引设计

索引的顺序访问次数等于维度表的行数乘以匹配谓词的过滤因子(FF),比如

WHERE DOB BETWEEN :BDATE1 AND :BDATE2      FF = 10%
      AND
      SEX = :SEX                           FF = 50%

维度表CUST的这些本地谓词会产生0.1 x 1000000 = 100000次对索引(DOB, ...)的顺序访问,因为只有一个匹配列;根据QUBE规则,范围谓词DOB是最后有一个匹配列。根据QUBE算法,这一步将花费1s时间。

为了最大化任意WHERE条件的匹配数量,针对4个列DOB,SEX,A和B的查询大约需要4 x 3 x 2 x 1 = 24个宽索引。但事实是,通过对终端用户的调查或通过跟踪用户的查询语句,对于大多数的查询,我们有可能做到使用几个索引就为大部分查询实现多个匹配列。举个例子 : 一个用户可能对不同年龄段(FF = 10%)的不同性别的客户的销售情况感兴趣,那么索引(SEX, DOBM, A, B, CNO)就要优于其他所有,因为相同年龄段相同性别的用户,比如三十多岁的男性,在索引结构上是相邻的。按照QUBE算法,两个匹配列的过滤因子是0.05(不是0.1),所以扫描这个索引片段只需要0.5s。

表访问顺序的影响

表的访问顺序在星型连接中比在普通的表连接中更为重要。假设我们在从DATE维度表开始查询,在该表中通过给定的星期号,来确定属于这个星期的所有日期。在DATE表中,我们有跨度为三年的记录,每天对应一条记录。我们只对其中一个星期感兴趣,所以DATE表访问的过滤因子就是7/1000 = 0.7%---只需访问表中的7行数据。按常理判断,需要访问0.7%的的SALES表行,这意味着将进行7000000次的SALES表访问和索引访问(如果索引设计良好那就只需进行索引访问)

如果使用STORE或者ITEMS表作为驱动表,则相应的表或者索引访问的计数可能更为庞大,所以现在我们来考虑一下在访问事实表SALES之前访问所有维度表的可能性,如下所示,尽管每个维度表都有本地谓词,但维度表之间并没有关联谓词。

DATE(1000行,FF = 0.7%) -> STORE(10000行,FF = 10%) -> TEMP1(7000行) -> ITEM(100000行,FF = 1%) -> TEMP2(7000000行) -> SALES(1000000000行)

如果事实表作为星型连接中最内层的表,那么数据为这个查询必须建立一张包含所有的有效外键组合的中间表。这个中间表是三个维度表中满足本地谓词的主键的笛卡尔积,如果主键比较短,那么上述例子中的中间表大小可能不超过100MB,也许能够被直接保存在数据库的缓冲池中。

第一张临时表的行数将会是 : (0.7 x 1000) x (10% x 10000) = 7 x 1000 = 7000
第二张临时表的行数将会是 : 7000 x (1% x 100000) = 7000 x 1000 = 7000000

事实表的索引

创建完第二个中间临时表后,数据库系统将根据关联外键组合来读取所有与其匹配的事实表记录。一些情况下,一个组合键会对应多条事实表记录(例如一个商店在一天当中销售了多个同款商品),也可能没有关联事实表记录。所以,这里不能准确地估算事实表的记录访问次数,但该值可能高达百万。

我们需要设计一个良好的索引,它将选择性最好的列作为起始列,来满足用户对响应时间的要求。有两种理论上可行的扫描方法。

第一种,优化器选择扫描一个单一的索引片段,索引片段的大小取决于DATENO这一个匹配字段。选择这种方式的原因是我们需要扫描一个时间段的额数据,即某一周的七天,比如DATENO列的值从764到770。我们之前已经计算过这个索引片段包含0.7 x 1000000000 = 7000000条记录。

第二种,“聪明的”优化器可能会把分成多个子扫描,对于每一个日期(大约有1000000000 / 1000 = 1000000条记录),基于ITEMNO列将有1000个(100000的1%)子片段。所以,一个星期将有7000个不同的索引片段(两个匹配段),每个索引片段平均为1000000 / 100000 = 10条记录。在这一场景下,厚度为10行的7000个索引片意味着扫描70000条记录。

这两种方式的比较结果将是 :
1 MC 1 x 10ms + 7000000 x 0.01ms ≈ 70s
2 MC 7000 x 10ms + (7000 x 10 x 0.01)ms = 70s + 0.7s ≈ 71s

访问索引表时将通过宽索引进行排序,如果内存足够,那么这个操作将非常快。

在给定的过滤条件和假设的满足条件的事实表记录数下,zhiy7ao优化器选择了相同的访问路径,星型连接的响应时间很可能就是几分钟。这个时间估计包含了访问维度表,构建和读取两个中间表所花费的总时间。

如果只有4张维度表,我们可以使用任意一个维度表的外键组成的索引与事实表进行星型连接。然而,一张又有10亿条记录的表上的4个宽索引将非常大,4个索引的总磁盘空间需求大约为上百GB大小。

假设租用磁盘空间的费用是50美元/GB/月,那么4个索引每个月共需要12000美元,事实上,宽索引通常比事实表还大,原因有两个 :

  1. 表通常都进行了压缩处理,而索引没有。
  2. 新增一条记录通常都追加到表的尾部,因此事实表并不需要分散的空闲空间。但插入到索引(除了聚簇索引)上的位置是随机的。为了避免频繁的索引重组,在当前硬件条件下,通常10亿行的表将花费几个小时,大多数的索引在叶子节点上都需要留出足够的空闲空间,可能为30% ~ 40%。

然而,在性能问题上,最大的挑战还是过滤因子和匹配结果集大小的不可预知性。如果针对ITEM的查询覆盖了10%(而不是1%)的销售记录,那么临时表将会有7千万条记录,最终响应时间也将增长到不可接受的长度。如果事实表的结果集大小是1亿而不是1千万,那么即使索引行只分散在少数几个索引片上,大量对表的顺序访问也将大大增加响应时间。

汇总表

即使是在理想索引的情况下,一些针对10亿条记录的事实表进行的查询也会导致大量的I/O访问。提高这类查询的性能的唯一方式就是使用汇总表(查询表)。这类表是反范式化的事实表。如果表不是特别大(比如只包含几百万行数据),那么这是一个比较可行的方案,因为反模式化查询只需针对汇总表,而不需要多表关联。

如果频繁查询每周的销售情况,那么可以针对每周的消费记录建立一张汇总表。比较好的汇总表设计是根据周,商品,商店汇总一条记录。汇总表根据周和商品进行汇总后,数据量可以大幅度减少。在这种情况下,查询的响应时间可能降低到不到1秒钟。

汇总表上的索引通常会比较小,他唯一的显示因素就是刷新此表所需的时间。如同所有新鲜事物一样,汇总表的方案也会带来新的问题。

  1. 如果用户的查询需求多样,汇总表的设计会比索引的设计更困难,不过,已经有一些工具基于查询日志来协助汇总表的设计。
  2. 如果优化器不能选择正确的汇总表,那么汇总表的意义就不大;我们不能指望用户来指定查询使用某个合适的汇总表。最好的优化器已经在试着访问合适的表了,虽然SELECT语句实际上查询的是事实表。如果优化器不具备这个能力,或者它的正确率不够高,那么可能就不得不强制指定每个用户只能访问一个汇总表。用户不得不自己选择要使用的汇总表。优化器能自动识别的汇总表通常被称为自动汇总表或物化视图。

标签: mysql, mysql索引

添加新评论