查询优化与并发控制[姊妹篇.第六弹]

 

前面我们聊过优化的思想和连接查询的最优方式。本次呢我们来谈谈查询优化的整体策略，就是在开发当中，当我们需要调度数据的时候我们的脑海里就需要优先考虑这些策略来达到程序上的优化。

 

所谓的查询优化呢，就算我们想要提高查询效率，查询占用时间及空间越少，查询的效率越高。所以呢，我们需要有一套行之有效的策略按照关系代数等价变化规则对查询表达式进行变换，来实现优化代价合理、查询效率高的查询计划。

 

 

01【查询优化的一般策略】

 

选择运算尽早执行。前面我们提到过，选择运算就是加条件筛选，在面对数据比较大的表数据时根据条件来命中需要的数据避免无关数据也进行查询。

 

投影运算与选择运算同时进行。投影运算即选择列查询，在查询关系表时需要的列进行查询避免 “*” 查询 同时配合选择运算一起。

 

将笛卡尔积与随后的选择运算合并为连接运算。因为连接运算（尤其是自然连接）要比笛卡尔积所花费的时间要少很多。

 

投影运算与其他运算同时进行。即投影运算可以搭配任意的运算同时进行。无论如何查询，选择需要的列进行查询往往很有效的一种方式。不必为了删除关系的某些属性值而把关系属性再扫描一遍。

 

将笛卡尔积与随后的选择运算合并为连接运算。因为连接运算（尤其是自然连接）要比笛卡尔积所花费的时间要少很多。

 

寻找公共子表达式并将结果加以存储。如果有一个频繁出现的子表达式，其结果关系并不大，从磁盘读入这个结果关系所花的时间要比计算该子表达式所花的时间少，那么先计算该公共子表达式并将结果存储在磁盘上就能对查询起到优化作用。当查询的对象是视图时，定义视图的表达式就可看作是公共子表达式。

 

对文件进行预处理。对适当的属性预先进行排序或者建立索引将有助于快速有效地找到适当的元组。只要预处理所花费的时候仍然合算，是对查询优化有作用的。

 

以上的6种优化策略，在开发的过程中，涉及与数据库交互时可以优先考虑这6种策略。当然，在面对庞大的数据时，需要另作其他策略，例如分库分表策略，nosql策略，配合分布式缓存等等，这些将在后续分享。

 

 

 

02 【查询优化步骤】

把查询转换成一种内部表示。经常采用树的方式。

 

利用关系代数等价变换规则以及查询优化的一般策略，将语法树进行优化。

 

选择适当的底层存取路径，要充分利用数据库中已有的索引等信息。

生成一组查询计划，从中选择一个代价最小的。

例如我们以一个例子来说明：

 

对学生-课程数据库，查询信息系学生选修了的所有课程名称。

 

例如我们以一个例子来说明：

对学生-课程数据库，查询信息系学生选修了的所有课程名称。

SELECT course_name FROM student,course,elective_course AS ec  WHERE student.sno=ec.sno AND ec.cno=course.cno AND student.sdept=’IS’;

 

试画出查询树图、关系代数语法树图、优化后的查询树。

先选择，后投影，按照查询语句的顺序 先写project(cname)，也就是最终查询结果，然后按照条件语句where从后面往前写，遇到两个表相关联的字段时，可以看看是否这个表后面还有查询，如果没有，则表作为叶端，有的话，就继续连接(join)条件，直到所有的查询条件都连接完毕，剩下的叶端就是表了。

 

进行优化语法树的时候，要全部都转为选择σ和投影∏来表示，σ一般表示除了父节点以外的结点，∏ 表示父节点。

查询语句转关系代数表达式为：∏ cname(σstudent.sdept=’IS’(student ⋈ course ⋈ ec))

 

 

 

03【 并发调度】

事务：在数据库上的一个或多个操作的序列，它必须以原子的方式执行，也就是说，所有的操作要么都做，要么都不做。

 

1. SQL语句COMMIT(提交)使事务成功的结束。

2. SQL 语句ROLLBACK(退回)使事务不成功地终止。

 

数据不一致性：如果对并发操作不进行合理的调度，就有可能导致数据库中数据的不一致性。

 

丢失修改：事务T1和T2从数据库中读入了同一数据并各自进行修改，在两个人事务都完成了读入数据的操作以后，T1先完成修改操作，并将更新的数据写回数据库，随后T2也完成了修改，并将结果写回数据库，从而覆盖了T1的操作结果，导致T1对该数据的修改好像没有发生。

 

读 “脏” 数据：事务T1修改了耨数据并将其写回数据库，事务T2随之读入这个被T1修改过的数据，之后T1又出于某种原因被撤销，它修改过的数据恢复原值。这时T2所读取的数据就与数据库中的数据不同，就称为“脏”数据。

 

不可重复读：事务T1按一定条件从数据库读入某些数据，随后事务T2对其进行更新并将更新结果写回数据库，当T1再次按同一条件读入数据时，结果发现跟刚才的不一样。可能有的数据值改变了，也可能有的数据已经删除，还可能增加了某些数据。

 

可串行化调度：当且仅当多个事务并发执行的结果与按某一次序串行其结果相同，则认为并发操作是正确的，并称这种调度策略为可串行化调度。

 

 

 

04 【 封锁管理】

所谓封锁，指的是事务在对某数据对象（如关系）进行操作之前，先请求系统对其加锁，成功加锁之后该事务就对该数据对象有了控制权，只有该事务对其进行解锁之后，其他的事务才能更新它。

 

数据库管理系统提供基本的封锁类型有两种：排它锁（X锁）以及共享锁（S锁）

 

若事务T1对数据对象A加了X锁，则T就可以对A进行读取以及更新（X锁因此又称为写锁），在T释放A上的X锁以前，任何其他事务都不能再对A加任何类型的锁，从而也不能读取和更新A。

 

若事务T对数据A加上S锁，则T就可以对A进行读取，但不能进行更新（S锁因此又称为读锁），在T释放A上的S锁以前，其他事务 可以再对A加上S锁，但不能加X锁，从而可以读取A，但不能更新A。

 

加锁的数据对象可以大到整个关系、整个数据库，也可以小到一个元组、一个元组的某个分量。封锁对象的大小称为封锁的粒度。

 

封锁协议：为了保证并发控制正确,在运用封锁机制时必须遵从一定的规则,例如什么时候应该申请X锁或S锁、什么时候释放锁等等。

 

不同的封锁协议( locking protocol)约定了不同的规则,为并发控制提供了不同程度的保证。下面将分别介绍能够保证数据一致性的三级封锁协议和保证并行调度可串行性的两段锁协议。

 

1级封锁协议约定: 事务T在修改数据A之前必须先对其加X锁,直到事务结束(提交或退回)才释放该锁。由于X锁保证两个事务不能同时对数据A进行修改,从而使丢失修改的前提条件不可能出现,杜绝了丢失修改的发生。但是1级封锁协议不要求事务在读取数据之前加锁,这样“不可重复读”和“读脏数据”的前提条件仍然成立。

 

2级封锁协议：是在1级封锁协议的基础上加上这样的约定:事务T在读取数据A之前必须对其加S锁,读入该数据后即可立即释放S锁。

 

2级封锁协议不仅避免了丢失修改,还防止了读“脏”数据其事务T修改数据A之前对其加X锁,修改后的结果写回数据库,事务T2要想读入数据A,只能等待T1释放X锁以后才能对A加S锁,之后T1出于某种原因被撤销,它所修改过的数据恢复原值。

 

3级封锁协议：在1级封锁协议的基础上加上了这样的约定:事务T在读取数据A之前必须对其加S锁,直到事务结束(提交或退回)才能释放S锁。

3级封锁协议除了避免丢失修改、读“脏”数据之外,又解决了不可重复读的问题。

 

事务T1对数据A加S锁并从数据库读入A,随后事务T2欲对A加X锁以进行更新操作,然而事务T1尚未释放S锁,所以T2不能对A加X锁,也就是不能修改A,所以T1再次读入数据A的时候,A的值和刚才一样