Home > fundamental > Index Design的一点点点想法

Index Design的一点点点想法

February 12th, 2012 Leave a comment Go to comments

之前一段时间断断续续的看完了《Reational Database Index Design and the Optimizers》这本书,整体来说这本书还是很不错的,特别是应付日常索引相关的调优工作足够了,也强烈推荐开发童鞋去看这本书,以减轻我们的工作压力。。。

这本书纯粹是从方法论的角度去告诉读者如何去设计一个好的索引以及为什么要这么设计,不针对单独某个DB,也没有对索引内部结构进行深究,不过不影响它成为一本好书。

个人感觉这本书的前半部分讲得很好,后几章讲索引维护、限制、优化器的部分对我来说倒是没有太大收益,有点炒冷饭+过于理论化的感觉而且实际意义并不大,或者说,我没有完全看懂:)

 

  • 基本概念

首先是几个基本概念:Matching Columns,Screening Columns,Filter Factor,Result Rows Materialization,

Matching Columns, Screening Columns:匹配列跟筛选列。定义见下图:

image

简单翻一下:

从前往后检查索引的列:

1. 如果WHERE的条件中,有一个列走上了索引,那么这个列就是MATCHING COLUMN,否则,这个列以及之后的列都不是。(注意不限定是一个)

2. 如果一个WHERE条件是范围,那么它之后的列都不是MATCHING COLUMN

3. 任何在最后一个MATCHING COLUMN 之后的列都是SCREENING COLUMN(前提是要优化器认为条件足够简单)。

从图上的例子看,MATCHING :A,B SCREEN :C.

作者的这个定义其实挺蛋疼的,没有完全说清楚,不过换做我的话我也不太好解释,举几个事例吧:

Index SQL predicates Matching columns Screening columns
A,B,C,D A=:A AND B=:B AND C>:C AND D=:D A,B,C D
A,B,C,D A>:A AND C=:C A C
A,B,C,D B=:B AND C>:C(针对ORACLE INDEX SKIP SCAN的情况) B,C -

可以认为,MATCHING COLUMN定义了要扫的INDEX slice的大小,而SCREEN COLUMN则是筛选INDEX的每条记录是否符合条件。

可以近似认为Oracle的access跟filter跟这两个概念分别对应,但是Oracle的access跟它有点区别,access包括了matching columns+screen columns。

Filter Factor:过滤因子,代表了一个列值(也可以是多个列)的过滤性,

Filter factor (FF)= Number of result rows/ Number of source rows

等于条件的平均FF可以这样认为:1/ the number of distinct values,事实上也是上个公式的化简。Matching column的FF会影响index slice的大小,而matching+screen column的FF会影响扫完index后的结果集大小。

Result Rows Materialization:结果集生成。这个包含2种情况:

1. The DBMS materializes the whole result table at OPEN CURSOR (or at least at the first FETCH).

2. Each FETCH materializes one result row.

第一种是指,cursor第一次fetch的的时候,就生成好完整的结果集,然后再从结果集里面一条条fetch出来。

第二种是指, fetch一次生成一条,没必要是整个结果集先生成。

具体见事例1.

 

  • Preactive index design

1. THREE-STAR INDEX—THE IDEAL INDEX FOR A SELECT

所谓三级索引,每个级别大概可以这么概括:

假如有个CURSOR如下:

DECLARE CURSOR41 CURSOR FOR
SELECT CNO, FNAME
FROM CUST
WHERE LNAME = :LNAME
AND
CITY = :CITY
ORDER BY FNAME

First Star Index:所有等于条件都在索引的最开始。在这个例子中也就是(LNAME,CITY…)或者(CITY,LNAME…),满足这个条件的索引就是一星级。

Second Star Index:在一级的基础上增加order by 的列,顺序不变,同时忽略之前已存在过的列。也就是(LNAME,CITY,FNAME…)或者(CITY,LNAME,FNAME…),这样保证不需要多余的sort开销。

Third Star Index:在二级的基础上,将所有涉及到的列都加到索引中,保证不需要回表(fat index)。也就是(LNAME,CITY,FNAME,CNO)或者(CITY,LNAME,FNAME,CNO)。

如果三个条件都满足了,恭喜你,成功晋级到三级演员。这是理想情况,而且没有涉及到范围条件。

如果涉及到range predicates,三级索引就比较难构建了。这时候,就引申出Best index的概念,仅次于Ideal index。IDEAL是理想,BEST是最好的现实。

2. Then how to derive the best index for a SELECT?

假如有这样一个CURSOR:

DECLARE CURSOR43 CURSOR FOR
SELECT CNO, FNAME
FROM CUST
WHERE LNAME BETWEEN :LNAME1 AND :LNAME2
AND
CITY = :CITY
ORDER BY FNAME

有两种最好索引的选择,不想翻译了,写字太累,上原文:

Candidate A

1. Pick the equal predicate columns that are not too difficult for the optimizer (discussed in Chapter 6). These are the first index columns—in any order.

2. The next index column is the column in the most selective range predicate, if any. Most selective means the lowest filter factor with the worst input. Only consider the range predicates that are not too difficult for the optimizer (discussed in Chapter 6).

3. Add the ORDER BY columns in the correct order (and with DESC if an ORDER BY column has DESC). Ignore columns that were already picked in step 1 or 2.

4. Add all remaining columns referred to by the SELECT statement, in any order (but start with the nonvolatile columns).

Candidate B

1. Pick the equal predicate columns that are not too difficult for the optimizer. These are the first index columns—in any order

2. Add the ORDER BY columns in the correct order (and with DESC if an ORDER BY column has DESC). Ignore columns that were already picked in step 1.

3. Add all remaining columns referred to by the SELECT statement, in any order (but start with the nonvolatile columns).

其实也就是thin index slice+sort跟thick index slice without sort两者资源消耗的权衡问题,如果你评估下来认为A比B多,那么就设计一个B的索引,反之亦然,没有一个定论。

上面这些,都是理想情况,适合在应用上线前去做(Preactive index design),因为这时候的索引调整代价对整个系统来说是最低的,也是平时最基本的SQL REVIEW工作。其次,我们不可能为每个SQL去设计一个ideal index,因为过多的index会带来过多的DML开销。

所以,如果是个DML频繁的表,一个索引应该尽可能的被多个SQL使用,前提是这个SQL的性能对应用来说是可以接受的(adequate),不一定要是最理想的索引,所以,我们需要的是一个最好的索引,但不一定是最理想的索引,最好的索引是我们在各种开销之间权衡后的一个最好结果。

 

  • Reactive index design

如果一个应用已经上线了,SQL性能出现了问题,这时候就需要另外一套方法(Reactive index design):

1. Basic Question (BQ)

2. Quick Upper-Bound Estimate (QUBE)

Basic Question (BQ):

针对出现问题的SQL,按照BQ的方法基本都可以解决的,同样的,上原文:

For each SELECT statement the answer to the following question must be considered as shown in the following steps:

Is there an existing or planned index that contains all the columns referenced

by the WHERE clause (a semifat index)?

1. If the answer is no, we should first consider adding the missing predicate columns to an existing index. This will produce a semifat index where, even if the matching index process is inadequate (the first star), index screening will take place to ensure table access will only occur when it is known that all the selection criteria have been met.

2. If this does not result in adequate performance, the next alternative is to add enough columns to the index to make the access path index only. This will produce a fat index that will eliminate all table access.

3. If the SELECT is still too slow, a new index should be designed using the two-candidate algorithm introduced in Chapter 4. This, by definition, will be the best index possible.

Quick Upper-Bound Estimate (QUBE):

按照上面BQ的方法,出现问题的SQL可以得到解决,但是BQ过程中如果想精确的算出不同索引的方式带来的处理时间,也就是将adequate这个空洞的词量化,那么就可以用到QUBE的方法。

其实这个方法所谓的精确也是建立在一堆假设的基础之上的(基于一般的CPU,MEM,DISC来计算的),比如这本书上假设的就是:BLOCK的一次random touch算10ms,sequential touch算0.01ms,一次fetch算0.1ms,然后算出一个local response time(LRT)。而现实中的DB,一般的经常使用的索引的非叶子节点会保留在内存中,storage一层也有一个cache,不同的硬件配置响应时间也不一样,而且这个方法忽略了各个队列的时间(queuing time在后来的章节中有做讲解)开销,认为service time≈local response time.所以这个方法其实也是个粗略计算的方法。感兴趣的童鞋可以去看看这边书,我这边不想写了。

上面都是单表SQL的调优,还有很多表关联的情况,方法也类似,此外还有遇到or,between ,in,not in的时候如何去Index design,具体可以参考这本书的Indexing for Table Joins Multiple Index Access章节。

 

  •  conclusion

 

 

最后附上作者的一个总结:

NINE STEPS TOWARD EXCELLENT INDEXES

1. When the first version of the table design is completed (primary keys, foreign keys, table row order), create the version 0 indexes: primary key indexes, foreign key indexes, and candidate key indexes, if any.

2. Check the performance of the first version of the table design: Using the UBE, estimate the elapsed time of a few heavy transactions and batch rograms with ideal indexes. If the estimates are not satisfactory, combine ables that have a 1 : 1 or 1 : C (1 to 0 or 1) relationship and add redundant ata to the dependent tables in a 1 : M (one to many) relationship.

3. when the table structure appears stable, you may add any obvious indexes—based on knowledge of the application.

4. If a table is extremely volatile (say, more than 50 rows inserted, replaced, or deleted per second), you should estimate, using the QUBE, how many indexes the table tolerates.

5. When the database processing of a program (transaction or batch) is known, calculate the worst input QUBE using the latest database version. If the estimated local response time of a transaction exceeds the application-specific alarm limit (e.g., 2 s), the current database version is not satisfactory for that program. The acceptability of the estimated elapsed time for a batch program must be evaluated case by case; but, to prevent long lock waits, the alarm limit for the elapsed time between two commit points should be the same as the alarm limit for local response time. When an alarm limit is exceeded, you should improve the indexing (semifat index, fat index, or ideal index). If the estimate (QUBE) is unsatisfactory even with ideal indexes (or if the number of required indexes exceeds the table-specific maximum number of indexes, set in step 4), you should make a more accurate estimate of the slow SELECTs, based on the issues discussed in Chapter 15. If the estimated elapsed time is then still too long you must resort to changing the table design as in step 2. In the worst case, you must negotiate the specifications with the users or the hardware configuration with the management.

6. When the SQL statements are written, the programmer should apply the basic question (BQ) or, if applicable, the basic join question (BJQ).

7. When the application is moved to the production environment, it is time to do a quick explain review: analyze all SQL calls that cause a full table scan or a full index scan. This review may reveal inadequate indexing or optimizer problems.

8. When production starts, create an LRT-level exception report (spike report or equivalent) for the first peak hour. When a long local response time is not due to queuing or an optimizer problem, you should proceed as in step 5.

9. Produce an LRT-level exception report at least once a week.

 

  • 实例

给几个有代表性的优化的例子(Oracle,待更新,欢迎补充):

1.常见分页

select *
  from (select T1.*, rownum rno
          from (select a.*
                  from a
                 where a.c_date > :1
                   and a.c_date < :2
                   and a.status = :3
                 order by a.id desc) T1
         where rownum <= :6)
 where rno >= :7

这是一个很常见的分页SQL,参照前面给的设计方法,一般情况下,为了得到一个尽量小的index slice,索引会这样设计:(status,c_date,id),这样经过status+c_date的过滤之后,需要再根据id做次排序生成一个结果集(第一种Result Rows Materialization的情况),然后再获取某个分页,比如前20条。如果status_c_date过滤后的结果集不大还好,如果很大的话,比如3W条,而分页其实只需要前20条,这样很大一部分性能就消耗在了index大范围的range scan+id的排序上了。这时候,(status,id,c_date)的索引也许是个更好的选择,首先,id的sort开销省掉了,index range scan的范围由(stauts,c_date)变成(status),看似增大了,但是index range scan的时候是按照id的顺序来扫的,当找到满足条件的20条(COUNT STOPKEY)就可以返回了(第二种Result Rows Materialization的情况),没必要完全扫完,所以性能也可以提高很多。但是这种索引一直存在一个比较大的隐患(pitfall),如果符合条件(c_date)的记录分布不均,假设都在索引的开头,这样desc扫的话,还是要扫很大一个范围的。其次,如果符合c_date条件的记录数根本就不足20条或者是空的,会造成status这么大范围的range scan,性能不如第一种索引,其实这时候就是符合第一种索引的情况了,status+c_date过滤性很好。这是在索引调整时候需要考虑的地方。

Categories: fundamental Tags:
  1. No comments yet.
  1. No trackbacks yet.