【从零开始学习计算机科学】数据库系统（五）DBMS查询处理
- DBMS查询处理
- 选择操作的实现
- 连接操作的实现
- 在嵌套循环方法(nested loop)
- 排序-合并方法(sort-merge join 或merge join)
- 索引连接(index join)方法
- Hash Join方法
- 表达式计算(SQL查询)
- (表达式计算中的)物化计算
- (表达式计算中的)流水线计算
- 流水线的实现
- 关系数据库系统的查询优化
- 实际系统的查询优化步骤
- 关系表达式的转换
- 查询树的基本优化策略
- “选择下移”优化策略
- 应尽早执行选择操作
- “投影下移”优化策略
- “选择连接顺序”优化策略
- 执行计划
- 表达式结果集大小的估计
- 1，目录(统计)信息
- 2，选择运算结果大小的估计
- 3，连接运算结果大小的估计
DBMS查询处理
选择操作的实现
选择操作典型实现方法主要有以下两种：
简单的全表扫描方法。对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。其适合小表，不适合大表。
索引(或散列)扫描方法。其适合选择条件中的属性上有索引(例如B+树索引或Hash索引) 。其通过索引先找到满足条件的元组指针，再通过元组指针直接在查询的基本表中找到元组。
考虑以下查询Select * from student where <条件表达式>，考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝’200215121’；C3：Sage>20；C4：Sdept=‘CS’ AND Sage>20；
以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)。使用索引(或散列)得到Sno为‘200215121’ 元组的指针，然后通过元组指针在student表中检索到该学生。
以C3为例，Sage>20，并且Sage 上有B+树索引。其使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针。通过这些元组指针到student表中检索到所有年龄大于20的学生。
以C4为例，Sdept＝‘CS’ AND Sage>20，如果Sdept和Sage上都有索引：
算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage>20的另一组元组指针，然后求这2组指针的交集，在到student表中检索，最后得到计算机系年龄大于20的学生。
算法二：找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索，对得到的元组检查另一些选择条件(如Sage>20)是否满足，最后把满足条件的元组作为结果输出。
连接操作的实现
连接操作是查询处理中最耗时的操作之一。本章仅讨论等值连接(或自然连接)的最常用的实现算法。目前，等值连接的实现主要有以下几种方法：嵌套循环方法(nested loop) 、排序-合并方法(sort-merge join 或merge join)、索引连接(index join)方法 、Hash Join方法。
考虑以下语句：SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno；
在嵌套循环方法(nested loop)
首先对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc)，检查这两个元组在连接属性(sno)上是否相等，如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止
排序-合并方法(sort-merge join 或merge join)
其适合连接的诸表已经排好序的情况。
排序－合并连接方法的步骤主要有：如果连接的表没有排好序，先对Student表和SC表按连接属性Sno排序，然后取Student表中第一个Sno，依次扫描直到找到SC表中具有相同Sno的元组，当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表直到找到具有相同Sno的元组，把它们连接起来。重复上述步骤直到Student 表扫描完。
此方法的是优点是Student表和SC表都只要扫描一遍。如果2个表原来无序，执行时间要加上对两个表的排序时间。对于2个大表，先排序后使用sort-merge join方法执行连接，总的时间一般仍会大大减少。
索引连接(index join)方法
其步骤主要是：首先，在SC表上建立属性Sno的索引，如果原来没有该索引；其次对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组；然后把这些SC元组和Student元组连接起来；循环执行2，3步，直到Student表中的元组处理完为止。
Hash Join方法
其把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中。
其步骤主要分为划分阶段和试探阶段。
划分阶段(partitioning phase)。其对包含较少元组的表(比如R)进行一遍处理，把它的元组按hash函数分散到hash表的桶中。
试探阶段(probing phase)。也称为连接阶段(join phase) ，对另一个表(S)进行一遍处理。
把S的元组散列到适当的hash桶中（不需放入桶中），然后把元组与桶中所有来自R并与之相匹配的元组连接起来。
hash join算法前提是假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中。并且，以上的算法思想可以推广到更加一般的多个表的连接算法上。
表达式计算(SQL查询)
(表达式计算中的)物化计算
当采用物化方法时，我们从表达式的最底层的运算(在树的底部)开始。在该例子中，只有一个底层运算: department 上的选择运算。底层运算的输人是数据库中的关系。我们用前面研究过的算法执行这些运算，并将结果存储在临时关系中。在树的高层中，使用这些临时关系来进行计算;这时的输人要么是临时关系，要么是来自数据库的关系。
物化即是将中间计算结果作为临时关系存放，用以支持上一层计算。
(表达式计算中的)流水线计算
通过减少查询执行中产生的临时文件数，可以提高查询执行的效率。减少临时文件数是通过将多个关系操作组合成一个操作的流水线来实现的，其中一个操作的结果将传送到下一个操作。这样的计算叫做流水线计算pipelined evaluation)。
流水线作用是避免中间结果表的创建，提供执行效率。
例如，考虑表达式 ( Π a 1 , a 2 ( r ⋈ s ) ) (\Pi_{a_1,a_2}(r\bowtie s)) (Πa1,a2(r⋈s))。如果采用物化方法，在执行中将创建存放连接结果的临时关系，然后在执行投影时又从连接结果中读入。这些操作可按如下方式组合:当连接操作产生一个结果元组时，该元组马上传送给投影操作去处理。通过将连接操作与投影操作组合起来，我们可以避免中间结果的创建，从而直接产生最终结果。
流水线的实现
通过将所有操作组合起来构成流水线，构造一个单独的复合操作，我们可以实现流水线。尽管对于各种频繁发生的情况，这个方法是可行的；但一般而言，希望在构造一个流水线时能重用各个操作的代码。
在上图的例子中，三个操作均可放入一条流水线中;其中，选择操作的结果产生后传送给连接操作。接着，连接操作的结果产生后又传送给投影操作。由于一个操作的结果不必长时间保存，因此对内存的要求不高。然而，由于采用流水线，各个操作并非总是能立即获得输人来进行处理。
关系数据库系统的查询优化
查询优化在关系数据库系统中有着非常重要的地位，关系查询优化是影响RDBMS性能的关键因素。
由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。
查询优化器的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。
优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息，如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。
优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。
对于集中式数据库，执行开销主要包括：磁盘存取块数(I/O代价)、处理机时间(CPU代价)、查询的内存开销 。其中，I/O代价是最主要的。
对于分布式数据库，总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价。
查询优化的总目标是选择有效的策略、求得给定关系表达式的值以及使得查询代价最小(实际上是较小)。
实际系统的查询优化步骤
-
将查询转换成某种内部表示，通常是语法树。
-
根据一定的等价变换规则把语法树转换成标准（优化）形式，得到某一颗最优树(执行效率最佳)。
-
选择低层的操作算法。对于语法树中的每一个操作，计算各种执行算法的执行代价，选择代价小的执行算法。
-
生成查询计划(查询执行方案)。查询计划是由一系列内部操作组成的。
考虑以下查询：2009年有课的Music系的所有教师名字以及每个教师所教授的课程名称。SQL语句为：
select name,title from instuctor,teaches,course where instructor.ID=teaches.ID and teaches.course_id=course.course_id and instructor.dept_name=‘Music’ and year=2009
1，SQL转换为关系代数
Π n a m e , t i t l e ( σ d e p t _ n a m e = " M u s i c " ∧ y e a r = 2009 ( i n s t r u c t o r ⋈ ( t e a c h e s ⋈ Π c o u r s e _ i d , t i t l e ( c o u r s e ) ) ) ) \Pi_{name,title}(\sigma_{dept\_name = "Music"\land year = 2009}(instructor \bowtie (teaches \bowtie \Pi_{course\_id, title} (course)))) Πname,title(σdept_name="Music"∧year=2009(instructor⋈(teaches⋈Πcourse_id,title(course))))
2，关系代数转换为查询树(表示式树)
3，查询树变换
这两棵树为等价表达式，但它们的执行效果不同。
4，生成执行计划
优化查询树结合标注（确定复合操作及确定各基本操作的执行算法）即为执行计划。
关系表达式的转换
用于表达式转换的等价规则主要有：
1，合取选择运算可分解为单个选择运算的序列。该变换称为 σ \sigma σ的级联： σ θ 1 ∧ θ 2 ( E ) \sigma_{\theta_1\land\theta_2}(E) σθ1∧θ2(E) = σ θ 1 ( σ θ 2 ( E ) ) \sigma_{\theta_1}(\sigma_{\theta_2}(E)) σθ1(σθ2(E))
2，选择运算满足交换律( commutative )： σ θ 1 ( σ θ 2 ( E ) ) \sigma_{\theta_1}(\sigma_{\theta_2}(E)) σθ1(σθ2(E)) = σ θ 2 ( σ θ 1 ( E ) ) \sigma_{\theta_2}(\sigma_{\theta_1}(E)) σθ2(σθ1(E))
3，一系列投影运算中只有最后一个运算是必需的，其余的可省略。该转换也可称为 Π \Pi Π的级联： Π L 1 ( Π L 2 ( ⋯ ( Π L n ( E ) ) ⋯ ) ) \Pi_{L_1}(\Pi_{L_2}(\cdots(\Pi_{L_n}(E))\cdots)) ΠL1(ΠL2(⋯(ΠLn(E))⋯)) = Π L 1 ( E ) \Pi_{L_1}(E) ΠL1(E)
4，选择操作可与笛卡儿积以及 θ \theta θ连接相结合： σ θ ( E 1 × E 2 ) \sigma_{\theta}(E_1\times E_2) σθ(E1×E2) = E 1 ⋈ θ E 2 E_1 \bowtie_{\theta}E_2 E1⋈θE2
该表达式就是 θ \theta θ连接的定义。
σ θ 1 ( E 1 ⋈ θ 2 E 2 ) \sigma_{\theta_1}(E_1\bowtie_{\theta_2} E_2) σθ1(E1⋈θ2E2) = $E_1 \bowtie_{\theta_1\land\theta_2}E_2 $
5， θ \theta θ连接运算满足交换律：$E_1 \bowtie_{\theta}E_2 $ = E 2 ⋈ θ E 1 E_2 \bowtie_{\theta}E_1 E2⋈θE1
6，
a.自然连接运算满足结合律( associative )： ( E 1 ⋈ E 2 ) ⋈ E 3 (E_1 \bowtie E_2)\bowtie E_3 (E1⋈E2)⋈E3 = E 1 ⋈ ( E 2 ⋈ E 3 ) E_1 \bowtie (E_2 \bowtie E_3) E1⋈(E2⋈E3)
b. θ \theta θ连接具有以下方式的结合律： ( E 1 ⋈ θ 1 E 2 ) ⋈ θ 2 ∧ θ 3 E 3 (E_1 \bowtie_{\theta_1}E_2) \bowtie_{\theta_2 \land \theta_3} E_3 (E1⋈θ1E2)⋈θ2∧θ3E3 = E 1 ⋈ θ 1 ∧ θ 3 ( E 2 ⋈ θ 2 E 3 ) E_1\bowtie_{\theta_1 \land \theta_3} (E_2 \bowtie_{\theta_2}E_3) E1⋈θ1∧θ3(E2⋈θ2E3)
7，选择运算在下面两个条件下对 θ \theta θ连接运算具有分配律：
a，当选择条件 θ \theta θ中的所有属性只涉及参与连接运算的表达式之一(比如E)时，满足分配律： σ θ 0 ( E 1 ⋈ θ E 2 ) \sigma_{\theta_0}(E_1\bowtie_{\theta}E_2) σθ0(E1⋈θE2) = ( σ θ 0 ( E 1 ) ) ⋈ θ E 2 (\sigma_{\theta_0}(E_1))\bowtie_{\theta}E_2 (σθ0(E1))⋈θE2
b，当选择条件 θ 1 \theta_1 θ1只涉及 E 1 E_1 E1的属性，选择条件 θ 2 \theta_2 θ2只涉及 E 2 E_2 E2的属性时，满足分配律： σ θ 1 ∧ θ 2 ( E 1 ⋈ θ E 2 ) \sigma_{\theta_1\land\theta_2}(E_1\bowtie_{\theta}E_2) σθ1∧θ2(E1⋈θE2) = ( σ θ 1 ( E 1 ) ) ⋈ θ ( σ θ 2 ( E 2 ) ) (\sigma_{\theta_1}(E_1))\bowtie_{\theta}(\sigma_{\theta_2}(E_2)) (σθ1(E1))⋈θ(σθ2(E2))
8.投影运算在下面条件下对 θ \theta θ连接运算具有分配律：
a，令 L 1 L_1 L1， L 2 L_2 L2分别代表 E 1 E_1 E1， E 2 E_2 E2的属性。假设连接条件 θ \theta θ只涉及 L 1 ∪ L 2 L_1\cup L_2 L1∪L2中的属性，则： Π L 1 ∪ L 2 ( E 1 ⋈ θ E 2 ) \Pi_{L_1\cup L_2}(E_1\bowtie_{\theta}E_2) ΠL1∪L2(E1⋈θE2) = ( Π L 1 ( E 1 ) ) ⋈ θ ( Π L 2 ( E 2 ) ) (\Pi_{L_1}(E_1))\bowtie_{\theta}(\Pi_{L_2}(E_2)) (ΠL1(E1))⋈θ(ΠL2(E2))
b，考虑连接 E 1 E_1 E1， E 2 E_2 E2。令 L 1 L_1 L1， L 2 L_2 L2分别代表 E 1 E_1 E1， E 2 E_2 E2的属性集；令 L 3 L_3 L3是 E 1 E_1 E1中出现在连接条件 θ \theta θ中但不在 L 1 ∪ L 2 L_1\cup L_2 L1∪L2中的属性；令 L 4 L_4 L4是 E 2 E_2 E2中出现在连接条件 θ \theta θ中但不在 L 1 ∪ L 2 L_1\cup L_2 L1∪L2中的属性。那么：： Π L 1 ∪ L 2 ( E 1 ⋈ θ E 2 ) \Pi_{L_1\cup L_2}(E_1\bowtie_{\theta}E_2) ΠL1∪L2(E1⋈θE2) = Π L 1 ∪ L 2 ( ( Π L 1 ∪ L 3 ( E 1 ) ) ⋈ θ ( Π L 2 ∪ L 4 ( E 2 ) ) ) \Pi_{L_1\cup L_2}((\Pi_{L_1\cup L_3}(E_1))\bowtie_{\theta}(\Pi_{L_2\cup L_4}(E_2))) ΠL1∪L2((ΠL1∪L3(E1))⋈θ(ΠL2∪L4(E2)))
9，集合的并与交满足交换律。 E 1 ∩ E 2 E_1\cap E_2 E1∩E2 = E 2 ∩ E 1 E_2\cap E_1 E2∩E1， E 1 ∪ E 2 E_1\cup E_2 E1∪E2 = E 2 ∪ E 1 E_2\cup E_1 E2∪E1。但是，集合的差运算不满足交换律。
10，集合的并与交满足结合律。$(E_1\cap E_2) \cap E_3 $ = E 1 ∩ ( E 2 ∩ E 3 ) E_1\cap (E_2\cap E_3) E1∩(E2∩E3)， ( E 1 ∪ E 2 ) ∪ E 3 (E_1\cup E_2) \cup E_3 (E1∪E2)∪E3 = E 1 ∪ ( E 2 ∪ E 3 ) E_1\cup (E_2\cup E_3) E1∪(E2∪E3)
11，选择运算对并、交、差运算具有分配律： σ P ( E 1 − E 2 ) \sigma_P(E_1 - E_2) σP(E1−E2) = σ P ( E 1 ) − σ P ( E 2 ) \sigma_P(E_1) - \sigma_P(E_2) σP(E1)−σP(E2)。类似地，上述等价规则将“-”替换成 ∩ \cap ∩或 ∪ \cup ∪时也成立。
进一步地，有： σ P ( E 1 − E 2 ) \sigma_P(E_1 - E_2) σP(E1−E2) = σ P ( E 1 ) − E 2 \sigma_P(E_1) - E_2 σP(E1)−E2。
上述等价规则将“-”替换成 ∩ \cap ∩时也成立，但将“-”替换成 ∪ \cup ∪时不成立。
12，投影运算对并运算具有分配律。 Π L ( E 1 ∪ E 2 ) \Pi_L(E_1\cup E_2) ΠL(E1∪E2) = ( Π L ( E 1 ) ) ∪ ( Π L ( E 2 ) ) (\Pi_L(E_1))\cup (\Pi_L(E_2)) (ΠL(E1))∪(ΠL(E2))
查询树的基本优化策略
“选择下移”优化策略
对于查询：2009年有课的Music系的所有教师名字以及每个教师所教授的课程名称。
Π n a m e , t i t l e ( σ d e p t _ n a m e = " M u s i c " ∧ y e a r = 2009 ( i n s t r u c t o r ⋈ ( t e a c h e s ⋈ Π c o u r s e _ i d , t i t l e ( c o u r s e ) ) ) ) \Pi_{name,title}(\sigma_{dept\_name = "Music" \land year = 2009}(instructor\bowtie (teaches \bowtie \Pi_{course\_id,title}(course)))) Πname,title(σdept_name="Music"∧year=2009(instructor⋈(teaches⋈Πcourse_id,title(course))))
其使用自然连接的结合律(Rule 6a)：
Π n a m e , t i t l e ( σ d e p t _ n a m e = " M u s i c " ∧ y e a r = 2009 ( ( i n s t r u c t o r ⋈ t e a c h e s ) ⋈ Π c o u r s e _ i d , t i t l e ( c o u r s e ) ) ) \Pi_{name,title}(\sigma_{dept\_name = "Music" \land year = 2009}((instructor\bowtie teaches) \bowtie \Pi_{course\_id,title}(course))) Πname,title(σdept_name="Music"∧year=2009((instructor⋈teaches)⋈Πcourse_id,title(course)))
应尽早执行选择操作
Π n a m e , t i t l e ( ( σ d e p t _ n a m e = " M u s i c " ( i n s t r u c t o r ) ⋈ ( σ y e a r = 2009 ( t e a c h e s ) ) ) ) \Pi_{name,title}((\sigma_{dept\_name = "Music"}(instructor)\bowtie (\sigma_{year = 2009}(teaches)))) Πname,title((σdept_name="Music"(instructor)⋈(σyear=2009(teaches))))
即将选择操作下移(使关系变小)
“投影下移”优化策略
通过添加投影操作去除连接操作产生的不必要的属性，可以减少中间结果的列数，从而减少中间结果的大小。
“选择连接顺序”优化策略
优化策略是小关系的连接应优先(使得中间结果的元组数更少)。
执行计划
一个执行计划确切地定义了每个运算应使用的算法，以及运算之间的执行应该如何协调。上图表明了一个可行的执行计划。正如我们看到的，每个关系运算可以有几种不同的算法，从而可产生其他的执行计划。在上图中，连接运算中的一个选择了散列连接，另一个则在连接的ID属性上将关系排序后，选用归并连接。在凡被标记流水线的边上，生产者的输出直接流向消费者，而不会被写人磁盘。
给定一个关系代数表达式，查询优化器的任务是产生一个查询执行计划，该计划能获得与原关系表达式相同的结果，并且得到结果集的执行代价最小(或至少是不比最小执行代价大多少)。
表达式结果集大小的估计
一个操作的代价依赖于它的输入的大小和其他统计信息。比如，为计算 表达式 a ⋈ b ⋈ c a\bowtie b\bowtie c a⋈b⋈c，我们需要有一些统计信息的估计，比如 b ⋈ c b \bowtie c b⋈c的大小。
1，目录(统计)信息
数据库系统目录存储了有关数据库关系的下列统计信息：
n r n_r nr,关系r的元组数。
b r b_r br,包含关系r中元组的磁盘块数。
l r l_r lr,关系r中每个元组的字节数。
f r f_r fr,关系r的块因子，即一个磁盘块能容纳关系r中元组的个数。
V(A,r),关系r中属性A中出现的非重复值个数。该值与 Π A ( r ) \Pi_A(r) ΠA(r)的大小相同。如果A是关系r的主码，则V(A, r)等于 n r n_r nr。
目录信息在关系被修改时系统自动维护。不必精确，可以是统计得到（比如直方图），采用随机抽样法。
举一个直方图的例子来说，一个关系person的属性age的取值范围可分成0~ 9，1019，$\ldots$，9099(假设最大年龄值是99)。对每个区间，我们记录那些age值落在该区间的person元组个数，以及落人该区间的不同年龄取值的个数。如果没有这样的直方图信息，优化器将不得不假设属性值的分布是均匀的，即每个区间具有同样的计数值。
2，选择运算结果大小的估计
对于类似 σ A = v ( r ) \sigma_A=v(r) σA=v(r)的选择。如果我们假设取值是均匀分布的(即，每个值以同样的概率出现),并假设关系r的一些记录的属性A中的取值为a,则可估计选择结果有 n r / V ( A , r ) n_r/V(A,r) nr/V(A,r)个元组。这里选择操作中的值a在一些记录中出现的假设通常是成立的，而且代价估计总是默认这一假设。
对于类似 σ A ≤ v ( r ) \sigma_A\leq v(r) σA≤v(r)的选择。如果在进行代价估计时，用于比较操作的值(v)已知，则可做更精确的估计。属性A的最小值min(A , r) 和最大值max(A , r)可存储到目录中。假设值是平均分布的，我们可以对满足条件 A ≤ v A\leq v A≤v的记录数进行下列估计：若v < min(A, r)，则为0；若v ≥ \geq ≥ max(A , r)，则为 n r n_r nr；否则，为 n r ⋅ ( ( v − m i n ( A , r ) / ( m a x ( A , r ) − m i n ( A , r ) ) ) ) n_r · ((v - min(A , r)/(max(A , r) - min(A , r)))) nr⋅((v−min(A,r)/(max(A,r)−min(A,r))))。
σ A ≥ v ( r ) \sigma_A\geq v(r) σA≥v(r)与 σ A ≤ v ( r ) \sigma_A\leq v(r) σA≤v(r)类似，在此不多赘述。
3，连接运算结果大小的估计
估计自然连接的大小比估计选择或笛卡儿积的大小要更复杂一些。令r®和s(S)为两个关系。若 R ∩ S = ϕ R\cap S = \phi R∩S=ϕ，即两个关系没有共同的属性，则 r ⋈ s r\bowtie s r⋈s与 r × s r\times s r×s结果一样，我们可用估算笛卡儿积结果集大小的方法进行估计。
若 R ∩ S R\cap S R∩S是R的码，则我们可知s的一个元组至多与r的一个元组相连接。因此， r ⋈ s r\bowtie s r⋈s中的元组数不会超过s中元组的数目。 R ∩ S R\cap S R∩S是S的码的情形同上面的情形相对称。若 R ∩ S R\cap S R∩S构成了S中参照R的外码，则 r ⋈ s r\bowtie s r⋈s中的元组数正好与s中元组数相等。
最难的情形是 R ∩ S R\cap S R∩S既不是R的码也不是S的码。在这种情况下，与进行选择运算的情况一样，我们假定每个值等概率出现。考虑r的元组1，假定 R ∩ S R\cap S R∩S = {A}。我们估计元组t在 r ⋈ s r\bowtie s r⋈s中产生 n s / V ( A , s ) n_s / V(A , s) ns/V(A,s)个元组，因为该值就是关系s中在属性A上具有给定值的平均元组数目。考虑r中的所有元组.我们估计在 r ⋈ s r\bowtie s r⋈s中有 ( n s ⋅ n r ) / V ( A , s ) (n_s · n_r) / V(A , s) (ns⋅nr)/V(A,s)个元组。注意，如果将r与s角色颠倒，那么我们估计在 r ⋈ s r\bowtie s r⋈s中有 ( n s ⋅ n r ) / V ( A , r ) (n_s · n_r) / V(A , r) (ns⋅nr)/V(A,r)个元组。
在V(A,s) ≠ \neq = V(A,r)时，这两个估计是不同的。若发生这种情况，就可能有未参加连接的悬挂元组存在。因此这两个估计值中较小者可能比较准确。
