【总结】数据库查询优化技术三：物理优化
在物理优化阶段主要解决的问题：[*]选择最优的单表扫描方式
[*]如何最优的连接两个表？
[*]选择最优的多个表的连接顺序
[*]是否要对多个表链接的每种连接顺序都探索？怎么在不探索全部组合时找到最优？
基于代价的查询优化方式对查询执行计划做了定量的分析，对每一个可能的执行方式进行评估，挑出代价最小的作为最优的计划。
3.1 查询代价估算
查询代价估算的重点是代价估算模型，是物理查询优化的依据。此外，选择率也是很重要的一个概念，对代价求解起着重要作用。
3.1.1 代价模型
查询代价估算基于CPU代价和IO代价，计算公式表示：
总代价 = IO 代价 + CPU 代价
COST = P * a_page_cpu_time + W * T
其中：
[*]P为计划运行时访问的页面数，a_page_cpu_time是每个页面读取的CPU时间花费，其乘积反映了IO代价。
[*]T为访问的元组数，反映了CPU花费（存储层是以页面为单位，数据以页面的形式被读入内存，每个页面上可能有多条元组，访问元组需要解析元组结构，才能把元组上的字段读出，这消耗的是CPU）。如果是索引扫描，则还会包括索引读取的花费。
[*]W为权重因子，表明IO到CPU的相关性，又称选择率（selectivity）。
3.1.2 选择率计算的常用方法
选择率的精确程度直接影响最优计划的选取，其常用计算方法如下：
[*]无参数法（Non-Parametric Method）。使用adhoc数据结构或直方图维护属性值的分布，最常用直方图。
[*]参数法（Parametric Method）。使用具有一些自由统计参数（参数是预先估计出来的）的数学分布函数逼近真实分布。
[*]曲线拟合法（Curve Fitting）。为克服参数法的不灵活性，用一般多项式和标准最小方差来逼近属性值的分布。
[*]抽样法（sampling）。从数据库中抽取部分样本元组，针对这些样本进行查询，然后收集统计数据，只有足够的样本被测试之后，才能达到预期的精度。
[*]综合法。将以上几种方法结合起来，如抽样法和直方图法结合。
3.2 单表扫描算法
单表扫描需要从表上获取元组，直接关联到物理IO的读取，所以不同的单表扫描方式，有不同的代价。
3.2.1 常用的单表扫描算法
单表扫描是完成表连接的基础。获取单表数据的方式：
[*]全表扫描表数据。
[*]局部扫描表数据。
全表扫描通常采取顺序读取的算法。单表扫描和IO操作密切相关，所以很多算法重点在IO上。
常用的单表扫描算法：
[*]顺序扫描（SeqScan）。从物理存储上按照存储顺序直接读取表的数据；其效果受有数据量影响。
[*]索引扫描（IndexScan）。根据索引键读索引，找出物理元组的位置，再读取数据页且有序；选择率越低，越适宜使用索引扫描，读数据花费的IO越少。
[*]只读索引扫描（IndexOnlyScan）。根据索引键读索引，索引中的数据就已满足条件判断，少了读取数据的IO花费。
[*]行扫描（RowIdScan）。直接定位表中的某一行。通常为元组增加特殊的列，可以直接计算出元组的物理位置，然后直接读取数量页面。PostgreSQL中的Tid扫描就是在元组头上增加名为CTID的列，用来直接计算元组的物理位置。
[*]并行表扫描（ParallelTableScan）。并行通过顺序的方式获取同一个表的数据。
[*]并行索引扫描（ParallelIndexScan）。并行通过索引的方式获取同一个表的数据。
[*]组合多个索引扫描（MultipleIndexScan）。对同一个元组的组合条件（涉及多个索引）进行多次索引扫描，然后在内存中用位图描述索引扫描结果中符合索引条件的元组位置。本质上不是单表的扫描方式，是构建在单表的多个索引扫描基础上的。
对于局部扫描，通常采用索引，实现少量数据的读取优化。这是一种随机读取数据的方式。有的系统对于随机读做了优化，即把要读取的数据的物理位置排序，然后一批读入，保障了磁盘单次扫描获取尽可能多的数据，提高了IO效率。
在并行操作的时候，可能因不同隔离级别的要求，需要解决数据一致性的问题。因为索引扫描只在满足条件的元组上加锁，所以索引扫描在多用户环境中可能会比顺序扫描效率高。查询优化器这里倾向于选择索引扫描，这是一条启发式优化规则。
3.2.2 单表扫描代价计算
[*]单表扫描，需要考虑IO的花费。
[*]顺序扫描，主要是IO花费加上元组从页面中解析的花费。
[*]索引扫描和其他方式的扫描，需要考虑选择率的问题。
单表扫描操作的代价估算公式（表3-1）：
[*]a_page_IO_time，一个页面的IO花费。
[*]N_page，数据页面数。
[*]N_page_index，索引页面数。
[*]a_tuple_CPU_time，一个元组从页面中解析的CPU花费。
[*]N_tuple，元组数。
[*]C_index，索引的IO花费，C_index=N_page_index * a_page_IO_time。
[*]N_tuple_index，索引作用下的可用元组数，N_tuple_index=N_tuple×索引选择率。
[*]a_tuple_IO_time，一个元组的IO花费。
3.3 索引
索引是建立在表上的，本质上是通过索引直接定位表的物理元组，加快数据的读取。
3.3.1 如何利用索引
索引是提高查询效率的有效手段。通常查询优化器使用索引的原则如下：
[*]索引列作为条件出现在WHERE、HAVING、ON子句中，这样有利于利用索引过滤元组。
[*]索引列是被连接的表（内表）对象的列且存在于连接条件中。
[*]特殊情况，如排序操作、在索引列上求MIN、MAX值等。
索引可用的条件如下：
[*]在WHERE、JOIN/ON、HAVING的条件中出现“key <op> 常量”格式的条件子句（索引列不能参与带有变量的表达式的运算）。
[*]操作符不能是<>操作符（不等于操作符在任何类型的列上不能使用索引，此时顺序扫描的效果通常好于索引扫描）。
[*]索引列的值选择率越低，索引越有效，通常认为选择率小于0.1则索引扫描效果会更好。
创建如下表，便于后面示例说明：
CREATE TABLE A (
a1 INT UNIQUE,
a2 VARCHAR(9),
a3 INT
); -- 注：表会建隐含索引&#34;a_a1_key&#34;3.3.2 索引列的位置对使用索引的影响
1. 对目标列、WHERE等条件子句的影响
索引列出现在目标列，通常不可使用索引，查询执行计划只能使用顺序扫描，对查询语句的优化没有好的影响。但聚集函数MIN/MAX用在索引列上，出现在目标列，可使用索引。
SELECT A.a1 FROM A; -- 顺序扫描，不可使用索引
SELECT MAX(A.a1) FROM A; -- 可使用索引索引列出现在WHERE子句中，可使用索引。这个好理解。
SELECT A.a1 FROM A WHERE A.a1 = 1;索引列出现在JOIN/ON子句中，作为连接条件，不可使用索引。
索引列出现在JOIN/ON子句中，作为限制条件满足“key <op> 常量”格式可用索引。
SELECT A.*, B* FROM A JOIN B ON (a1=b1); -- 不可用索引
SELECT A.*, B* FROM A JOIN B ON (a1=b1) AND A.a1=1; -- 可用索引，查询优化器根据“常量传递”优化技术推知b1=1，所以表A和表B可各自使用索引扫描。索引列出现在连接的WHERE子句中，可用索引，但与子查询比较，格式上不满足“key <op> 常量”，不可用索引。
SELECT A.*, B* FROM A JOIN B ON (a1=b1) WHERE A.a1=1; -- 可用索引，查询优化器根据“常量传递”优化技术推知b1=1，所以表A和表B可各自使用索引扫描。
SELECT E.e1 FROM E WHERE E.e1 IN (SELECT A.a1 FROM A); -- 不可用索引2.对GROUPBY子句的影响
索引列出现在GROUPBY子句中，不触发索引扫描。
WHERE子句出现索引列，且GROUPBY子句出现索引列，索引扫描被使用。
WHERE子句中出现非索引列，且GROUPBY子句出现索引列，索引扫描不被使用。
SELECT A.a1 FROM A GROUP BY a1; -- 顺序扫描，不可使用索引
SELECT A.a1 FROM A WHERE a1 > 2 GROUP BY a1; -- WHERE子句中的索引列使用符合“key <op> 常量”的格式，可使用索引
SELECT A.a1 FROM A WHERE a3 > 2 GROUP BY a1; -- 不可使用索引3.对HAVING子句的影响
索引列出现在HAVING子句中与出现在WHERE子句中类似。
WHERE子句中出现非索引列，且GROUPBY和HAVING子句出现索引列，索引扫描被使用。
SELECT A.a1 FROM A WHERE a3>2 GROUP BY a1 HAVING a1>2;尽管WHERE子句使用了非索引列a3，但HAVING子句使用了索引列a1，且a1＞2表达式符合“key <op> 常量”的格式，所以会使用位图索引扫描。
4.对ORDERBY子句的影响
ORDERBY子句中出现索引列可使用索引扫描，出现非索引列不可使用索引扫描。
SELECT A.* FROM A ORDER BY a1; -- 可使用索引扫描
SELECT A.* FROM A ORDER BY a3; -- 不可使用索引扫描5.对DISTINCT的影响
DISTINCT子句管辖范围内出现索引列，不可使用索引扫描。
DISTINCT子句管辖范围内出现索引列，因WHERE子句内使用索引列，故其可使用索引扫描，但这和DISTINCT操作没有关系。
SELECT DISTINCT A.a1 FROM A; -- 不可使用索引扫描
SELECT DISTINCT A.a1 FROM A WHERE a1 > 2; -- 可使用索引扫描3.3.3 联合索引对索引使用的影响
首先创建表：
CREATE TABLE E (
e1 INT,
e2 VARCHAR(9),
e3 INT,
PRIMARY KEY(e1, e3)
); -- 注：表会创建隐含索引&#34;e_pkey&#34;
[*]使用联合索引的全部索引键，可触发索引的使用。
[*]使用联合索引的前缀部分索引键，如“key_part_1 <op> 常量”，可触发索引的使用。
[*]使用非前缀部分索引键，如“key_part_2 <op> 常量”，不可触发索引的使用。
[*]使用联合索引的全部索引键，但索引键不是AND操作，不可触发索引的使用。
SELECT E.* FROM E WHERE E.e1=1 AND E.e3=2; -- 全部索引，使用索引
SELECT E.* FROM E WHERE E.e1=1; -- 前缀部分索引，使用索引
SELECT E.* FROM E WHERE E.e3=2; -- 非前缀部分索引，不使用索引
SELECT E.* FROM E WHERE E.e1=1 OR E.e3=2; -- 全部索引键，但非AND操作，不使用索引3.3.4 多个索引对索引使用的影响
首先创建表：
CREATE TABLE F (
f1 INT UNIQUE NOT NULL,
f2 INT UNIQUE NOT NULL,
f3 INT,
PRIMARY KEY(f1, f3)
); -- 注：表会创建隐含索引f_pkey、f_f1_key、f_f2_keyWHERE条件子句出现两个可利用的索引，优选最简单的索引。
SELECT * FROM F WHERE f1=2 AND f2=1; -- 因为f1列上存在两个索引，比f2列上的索引复杂，所以会优选f2的索引。本质是取决于代价估算模型的评估。
SELECT * FROM F WHERE f1=1 AND (f1=1 AND f3=3); -- 索引重叠时，选取的是f1列上的独立索引而不是联合索引
SELECT * FROM F WHERE (f1=2 AND f3=3) AND f2=1; -- 选取的是f2列上的独立索引而不是f1和f3构成的联合索引
SELECT * FROM F WHERE f2>1 AND f2<100 AND f1=3; -- 范围扫描选择率比等值比较的选择率大，所以查询优化器选择了f1上的索引
SELECT * FROM F WHERE f2>1 AND f2<100 AND f3=3; -- 由于f3不是索引键的前缀部分，所以会选择f2上的索引3.4 两表连接算法
连接运算是关系代数的一项重要操作，多个表连接建立在两表之间连接的基础上。研究两表连接的方式，对连接效率的提高有着直接的影响。
3.4.1 基本的两表连接算法
1.嵌套循环连接算法
嵌套循环连接算法是两表做连接采用的最基本算法。算法描述：
FOR EACH ROW rl IN t1 {
FOR EACH ROW r2 IN t2 {
IF r1,r2 SATISFIES JOIN CONDITIONS
JOIN r1,r2
}
}数据库引擎在实现该算法的时候，以元组为单位进行连接。元组从一个内存页面获取来，而内存页面通过IO操作获得，每个IO申请以“块”为单位尽量读入多个页面。可以对该算法进行改进，改进后的算法称为基于块的嵌套循环连接算法。算法描述：
FOR EACH CHUNK c1 OF t1 {
IF c1 NOT IN MEMORY //系统一次读入多个页面，所以不需要每次消耗IO
READ CHUNK c1 INTO MEMORY
FOR EACH ROW rl IN CHUNK c1 {//从页面中分析出元组，消耗CPU
FOR EACH CHUNK c2 OF t2 {
IF c2 NOT IN MEMORY
READ CHUNK c2 INTO MEMORY
FOR EACH ROW r2 IN c2 { //从页面中分析出元组，消耗CPU
IF r1,r2 SATISFIES JOIN CONDITIONS
JOIN r1,r2
}
}
}
}其他一些两表连接算法，多是在此基础上进行的改进。如基于索引做改进，在考虑了聚簇和非聚簇索引的情况下，如果内表有索引可用，则可以加快连接操作的速度。另外，如果内层循环的最后一个块使用后作为下次循环的第一个块，则可以节约一次IO。如果外层元组较少，内层的元组驻留内存多一些，则能有效提高连接的效率。
嵌套循环连接算法和基于块的嵌套循环连接算法适用于内连接、左外连接、半连接、反半连接等语义的处理。
2.排序归并连接算法
简称归并连接算法。算法步骤：
[*]为两个表创建可用内存缓冲区数为M的M个子表
[*]将每个子表排序
[*]从读入每个子表的第一块到M个块中，找出其中最小的先进行两个表的元组的匹配，找出次小的匹配……依此类推
[*]完成其他子表的两表连接。
归并连接算法要求内外表都有序，所以对于内外表都要排序。如果有索引，可以利用索引进行排序。
归并连接算法适用于内连接、左外连接、右外连接、全外连接、半连接、反半连接等语义的处理。
3.Hash连接算法
基于Hash的两表连接常见的算法：
[*]简单Hash连接（Simple Hash Join，SHJ）算法，用连接列作为Hash的关键字，对内表建立Hash表，然后对外表的每个元组的连接列用Hash函数求值，值映射到内表的Hash表就可以连接了；否则，探索外表的下一个元组。
[*]优美Hash连接（GraceHash Join，GHJ）算法，改进SHJ算法，把内表和外表划分成等大小的子表，然后对外表和内表的每个相同下标值的子表进行SHJ算法的操作，可以避免因内存小反复读入内外表的数据的问题。
[*]混合Hash连接（Hybrid Hash Join，HHJ）算法，结合SHJ和GHJ算法的优点，把第一个子表保存到内存不刷出，如果内存很大，则子表能容纳更大量的数据，效率接近于SHJ。
Hash算法存在以下限制和问题：
[*]Hash连接算法只适用于数据类型相同的等值连接。
[*]对内存要求较大。
[*]如果表中连接列值重复率很高，Hash连接算法就效率不高。
[*]存在“分区溢出”问题。当内存小或数据倾斜（分布不均衡）时，通过把一个表划分为多个子表仍不能消除Hash冲突的问题，如GHJ算法。
[*]要求内表不能太大，如果超出Hash表申请的内存大小且不能继续动态申请，则需要写临时文件，会导致IO的颠簸（PostgreSQL存在此类问题）。
Hash连接算法适用于内连接、左外连接、右外连接、全外连接、半连接、反半连接等语义的处理。
3.4.2 进一步认识两表连接算法
从内存的容量角度看，两表连接算法可以分为：
[*]一趟算法
[*]两趟算法
[*]多趟算法
所谓“趟”是指从存储系统获取全部数据的次数。一趟算法因内存空间能容纳下全部数据，所以读取一次即可。两趟算法的第一趟从存储系统获取两表的数据，如做排序等处理后，再写入外存的临时文件；第二趟重新读入临时文件进行进一步处理。多趟算法的思想和两趟算法基本相同，用以处理更大量的数据。
连接算法和索引及趟数的关系表（表3-2）：
3.4.3 连接操作代价计算
两表连接算法的代价表（表3-3）：
[*]a_tuple_cpu_time，获取一个元组消耗的CPU时间。
[*]N-outer，扫描获取的外表元组数。
[*]N-inner，扫描获取的内表元组数，N-inner=N-inner-all×选择率，其中N-inner-all表示内表的所有元组数。
[*]C-outer，扫描外表的代价，C-outer=N-outer×a_tuple_cpu_time。
[*]C-inner，扫描内表的代价，C-inner=N-inner×a_tuple_cpu_time。
[*]C-inner-index，使用索引扫描内表的代价，通常C-inner-index会小于C-inner。
[*]C-outersort，外表排序的代价。
[*]C-innersort，内表排序的代价。
[*]C-createhash，创建Hash的代价。
3.5 多表连接算法
多表连接算法需要解决两个问题：
[*]多表连接的顺序：表的不同的连接顺序，会产生许多不同的连接路径；不同的连接路径有不同的效率。
[*]多表连接的搜索空间：因为多表连接的顺序不同，产生的连接组合会有多种，如果这个组合的数目巨大，连接次数会达到一个很高的数量级，最大可能的连接次数是N！（N的阶乘）。如何将搜索空间限制在一个可接受的时间范围内，并高效地生成查询执行计划将成为一个难点。
3.5.1 多表连接顺序
多表间的连接顺序表示了查询计划树的基本形态。一棵树就是一种查询路径，SQL的语义可以由多棵这样的树表达，从中选择花费最少的树，就是最优查询计划形成的过程。
一棵树包括左深连接树、右深连接树、紧密树。
不同的连接顺序，会生成不同大小的中间关系，对应CPU和IO消耗不同。PostgreSQL中会尝试多种连接方式存放到path上，以找出花费最小的路径。
人们针对树的形成及其花费代价最少的，提出了诸多算法。树形成过程有以下两种策略：
[*]至顶向下。从SQL表达式树的树根开始，向下进行，估计每个结点可能的执行方法，计算每种组合的代价，从中挑选最优的。
[*]自底向上。从SQL表达式树的树叶开始，向上进行，计算每个子表达式的所有实现方法的代价，从中挑选最优的，再和上层（靠近树根）的进行连接，周而复始直至树根。
在数据库实现中，多数数据库采取了自底向上的策略。
3.5.2 常用的多表连接算法
1.动态规划
动态规划，指决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的。
“动态规划”将待求解的问题分解为若干个子问题（子阶段），按顺序求解子问题，前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解
主要概念有：
[*]阶段。把求解问题的过程分成若干个相互联系的阶段，以便于求解。
[*]状态。表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。
[*]无后效性。状态应该具有的性质，如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。
[*]决策。一个阶段的状态确定后，从该状态演变到下一阶段某个状态的选择（行动）。
[*]策略。由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。
[*]最优化原理。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。最优化原理实际上是要求问题的最优策略的子策略也是最优的。
动态规划算法是从底向上进行的，然后由底层开始对每层的关系做两两连接（如果满足的话），构造出上层，逐次递推到树根。下面介绍具体步骤。
步骤1 初始状态
构造第一层关系，每个叶子对应一个单表，为每一个待连接的关系计算最优路径（就是单表的最佳访问方式，通过评估不同的单表的数据扫描方式花费）。
步骤2 归纳
当层数从第1到n-1，假设已经生成，则求解第n层关系的方法为：
[*]将第n-1层的（多个）关系与第一层中的每个关系连接，生成新的关系且进行估算
[*]将每一个新关系放于第n层，且均求解其最优路径。
步骤2会被多次执行，每层路径的生成都是基于上层生成的最优路径的，这满足最优化原理的要求。
PostgreSQL查询优化器求解多表连接时，采用了这种算法。
2.启发式方法
启发式算法（heuristic algorithm）是相对于最优化算法提出的，是一个基于直观或经验构造的算法。在逻辑查询优化阶段和物理查询优化阶段，都有一些启发规则可用。
启发式方法不能保证找到最好的查询计划。PostgreSQL、MySQL和Oracle等数据库在实现查询优化器时，采用了启发式和其他方式相结合的方式。
启发式是根据已知可优化规则，对SQL语句做出语义等价转换的优化，或者基于经验对某个物理操作进行改进（如物化操作）。
在物理查询优化阶段常用的启发式规则如下：
[*]关系R在列X上建立索引，且对R的选择操作发生在列X上，则采用索引扫描方式。
[*]R连接S，其中一个关系上的连接列存在索引，则采用索引连接且此关系作为内表。
[*]R连接S，其中一个关系上的连接列是排序的，则采用排序进行连接比Hash连接好。
3.贪婪算法
又称贪心算法。在对问题求解时，贪婪算法总是选择当前看来是最好的，是局部最优，不一定是整体最优。不从整体最优上考虑，省去了为找最优解要穷尽所有可能而必须耗费的大量时间（动态规划算法就是这么做的），得到的是局部最优解。
贪婪算法为了解决问题需要寻找一个构成解的候选对象集合。其主要实现步骤如下：
1）初始，算法选出的候选对象的集合为空；
2）根据选择函数，从剩余候选对象中选出最有希望构成解的对象；
3）如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；
4）如果集合中加上该对象后可行，就加到集合里；
5）扩充集合，检查该集合是否构成解；
6）如果贪婪算法正确工作，那么找到的第一个解通常是最优的，可以终止算法；
7）继续执行2，（每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个可能的整体最优解）。
MySQL查询优化器求解多表连接时采用了这种算法。
4.System R算法
System R算法对自底向上的动态规划算法进行了改进，主要的思想是把子树的查询计划的最优查询计划和次优的查询计划保留，用于上层的查询计划生成，以便使得查询计划总体上最优。
5.遗传算法
遗传算法（Genetic Algorithm，GA）是一种启发式的优化算法，是基于自然群体遗传演化机制的高效探索算法。其模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。根据预定的目标适应度函数对每个个体进行评价，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。
遗传算法中的主要概念：
[*]群体（population）。一定数量的个体组成了群体，表示GA的遗传搜索空间。
[*]个体（individual）。多个个体组成群体，在多表连接中是每个基本关系或中间生成的临时关系。
[*]染色体（chromosome）。个体的特征代表，即个体的标志，由若干基因组成，是GA操作的基本对象，所以操作个体实则是操作染色体（个体几乎可以简单理解为“等同染色体”）。染色体用字符串表示。
[*]基因（gene）。基因是染色体的片段，多段基因组成染色体，基因变异导致基因不断被优化。
[*]适应度（fitness）。表示个体对环境的适应程度，通常由某一适应度函数表示。对应执行策略的执行代价。
[*]选择（selection）。根据个体的适应度，在群体中按照一定的概率选择可以作为父本的个体，选择依据是适应度大的个体被选中的概率高。
[*]交叉（crossover）。将父本个体按照一定的概率随机地交换基因形成新的个体。
[*]变异（mutate）。按一定概率随机改变某个个体的基因值。
遗传算法涉及的关键问题。
[*]串的编码方式。本质是编码问题。一般把问题的各种参数用二进制形式进行编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
[*]适应度函数的确定。适应度函数（fitnessfunction）又称对象函数（object function）或问题的“环境”，是问题求解品质的测量函数。一般可以把问题的模型函数作为对象函数，但有时需要另行构造。
[*]遗传算法自身参数设定。遗传算法3个自身参数：群体大小n、交叉概率Pc和变异概率Pm，具体如下：
[*]群体大小n，太小时难以求出最优解，太大则增长收敛时间，一般n＝30～160。
[*]交叉概率Pc，太小时难以向前搜索，太大则容易破坏高适应值的结构，一般取Pc=0.25～0.75。
[*]变异概率Pm，太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索，一般取Pm＝0.01～0.2。
遗传算法主要步骤如下：
1）随机初始化种群；
2）评估初始的种群，即为种群计算每个个体的适应值且对所有个体排序；
3）如果没有达到预定演化数，则继续下一步，否则结束算法；
4）选择父体，随机挑选父体dad和母体mum；
5）杂交，父体和母体杂交得到新个体child；
6）变异，在某些个别条件下对新个体变异；
7）计算新个体的适应值，并把适应值排名插入到种群，种群中排名最后的则被淘汰；
8）继续步骤3）。
6.其他算法
还有其他的一些算法，都可以用于查询优化多表连接的生成，如爬山法、分支界定枚举法、随机算法、模拟退火算法或多种算法相结合等。
3.5.3 多表连接算法的比较
多表连接常用算法比较表（表3-5）：
参考
[*]《数据库查询优化的艺术：原理解析和SQL性能优化》，李海翔
页:
[1]