Chapter 14 Query Planning & Optimization

Note

Since this part is of special difficulty in CMU-15445, I choose to use UCB CS186 instead.

This part is copied from UCB-CS186 notes

Here we ignored numerous process graphs which are essential for you to deeply understand the exact course, you can learn the details from here

Introduction

When we covered SQL, we gave you a helpful mental model for how queries are executed. First you get all the rows in the FROM clause, then you filter out columns you don’t need in the WHERE clause, and so on. This was useful because it guarantees that you will get the correct result for the query, but it is not what databases actually do.

Databases can change the order they execute the operations in order to get the best performance. Remember that in this class, we measure performance in terms of the number of I/Os.

Query Optimization is all about finding the query plan that minimizes the number of I/Os it takes to execute the query. A query plan is just a sequence of operations that will get us the correct result for a query. We use relational algebra to express it.

This is an example of a query plan:

First it joins the two tables together, then it filters out the rows, and finally it projects only the columns it wants. As we’ll soon see, we can come up with a much better query plan!

Iterator Interface

The expression tree above is representative of some query plan, where the edges(边) encode the “flow” of tuples, the vertices(顶点) represent relational algebra operators, and the source vertex(源顶点) represents a table access operator.

For some SQL query, there may be multiple ways to receive the same output; the goal of a query optimizer is to generate a sequence of operators that returns the correct output efficiently. Once this sequence is generated, the query executor then creates instances of each operator, each of which implements an iterator interface. The iterator interface is responsible for efficiently executing operator logic and forwarding relevant tuples to next operator.

Every relational operator is implemented as a subclass of the Iterator class, so in executing a query plan, we will call next() on the root operator, and recurse down until the base case. For example, in the diagram below, the root operator (SELECT sname) will call next(), which will recursively call next() for the join iterator, which recursively calls next() down the query until we reach the base case. We call this a pull-based computation model.

Each time we call next(), we will either perform a streaming ("on-the-fly") or blocking ("batch") algorithm on the operator instance. Streaming operators use a small amount of work to produce each tuple, like a SELECT statement. Blocking operators like sort operations, on the other hand, do not produce output until they consume their entire input.

batch 批量

In this way, we can see how query plans are single-threaded: we simply recursively call next() on the query plan until we reach our base operator.

Selectivity Estimation

An important property of query optimization is that we have no way of knowing how many I/Os a plan will cost until we execute that plan. This has two important implications. The first is that it is impossible for us to guarantee that we will find the optimal query plan - we can only hope to find a good (enough) one using heuristics and estimations. The second is that we need some way to estimate how much a query plan costs. One tool that we will use to estimate a query plan’s cost is called selectivity estimation. The selectivity of an operator is an approximation for what percentage of pages will make it through the operator onto the operator above it. This is important because if we have an operator that greatly reduces the number of pages that advance to the next stage (like the WHERE clause), we probably want to do that as soon as possible so that the other operators have to work on fewer pages.

Most of the formulas for selectivity estimation are fairly straightforward. For example, to estimate the selectivity of a condition of the form \(X = 3\), the formula is 1 / (number of unique values of X). The formulas used in this note are listed below, but please see the lecture/discussion slides for a complete list. The last section of this note also contains the important formulas. In these examples, capital letters are for columns and lowercase letters represent constants. All values in the following examples are integers, as floats have different formulas.

• X = a: 1/(unique vals in X)
• X = Y: 1/max(unique vals in X, unique vals in Y)
• X > a: (max(X) - a) / (max(X) - min(X) + 1)
• cond1 AND cond2: Selectivity(cond1) * Selectivity(cond2)

Note

这些选择性估算公式是基于统计学和概率论原理设计的，用于在查询优化过程中进行合理的近似估算。下面解释每个公式背后的原因：

1. X = a: 1/(unique vals in X)

   • 解释：假设列X中有N个不同的唯一值，那么对于某个特定值a，被选中的概率是1/N。这个公式假设值是均匀分布的，因此每个唯一值的概率是相等的。选择性的定义就是符合条件的记录占总记录的比例。
   • 例子：如果X有100个唯一值，那么选择性估算为1/100。

2. X = Y: 1/max(unique vals in X, unique vals in Y)

   • 解释：假设X和Y中的唯一值分别为N和M。为了计算X和Y相等的概率，我们考虑在最大值情况下，这意味着取两者中唯一值较大的那个。因为X和Y的唯一值可能不完全匹配，采用最大值是一个保守估计，确保结果不会被低估。
   • 例子：如果X有100个唯一值，Y有200个唯一值，那么选择性估算为1/200。

3. X > a: (max(X) - a) / (max(X) - min(X) + 1)

   • 解释：这个公式计算X大于某个值a的选择性。分子部分(max(X) - a)表示X中比a大的值的范围。分母部分(max(X) - min(X) + 1)表示X的总范围，加1是因为范围包含了两个边界值。这样计算出的比例就是大于a的值在所有可能值中的占比。
   • 例子：如果X的范围是从1到100，a为50，那么选择性估算为(100-50)/(100-1+1)=50/100=0.5。

4. cond1 AND cond2: Selectivity(cond1) * Selectivity(cond2)

   • 解释：假设条件cond1和cond2是独立的（即它们不相互影响），那么两个条件同时成立的概率就是两个条件各自成立概率的乘积。这是基于概率论中独立事件的概率乘法规则。
   • 例子：如果cond1的选择性为0.1，cond2的选择性为0.2，那么cond1 AND cond2的选择性估算为0.1 * 0.2 = 0.02。

这些公式提供了一种简单但有效的方法来估算选择性，使得查询优化器能够基于这些估算进行合理的计划选择。虽然它们是近似的，但通常在实际应用中足够准确。

Selectivity of Joins

Let’s say we are trying to join together tables A and B on the condition A.id = B.id. If there was no condition, there would be \(|A| \times |B|\) tuples in the result, because without the condition, every row from A is joined with every row from B and all the rows will be included in the output.

However, taking the join condition into account, some of the rows will be not be included into the output. In order to estimate the number of rows that will be included in the output after the join condition X=Y, we use the selectivity estimation: 1/max(unique vals for A.id, unique vals for B.id), meaning that the total number of tuples we can expect to move on is:

\(\frac{|A| \times |B|}{ max({unique vals for A.id, unique vals for B.id})}\)

To find a join’s output size in pages, we need to follow 3 steps:

1. Find the join’s selectivity. For a join on tables A and B on the condition A.id = B.id, we can refer to the formula above for this.

2. Find the estimated number of joined tuples in the output by multiplying the selectivity of the join by the number of joined tuples in the Cartesian Product (笛卡尔积) between the two tables.

3. Find the estimated number of pages in the join output by dividing by the estimated number of joined tuples per page.

Note that we cannot directly multiply the selectivity by the number of pages in each table that we are joining to find the estimated output size in pages. To see why, suppose we had two relations, \(R\) and \(S\), with only 1 page each and 5 tuples per page (\([R] = [S] = 1, |R| = |S| = 5\)). For simplicity, let’s also assume that the join’s selectivity is \(1\) (i.e. all the tuples in the Cartesian Product between \(R\) and \(S\) are in the output).

Then, the number of output tuples would equal the number of tuples in the Cartesian Product: \(|R| \times |S| = 5 \times 5 = 25\). In this example, \(25\) joined tuples would take up more space than the \([R] \times [S] = 1\) page estimate we would get if we directly multiplied the number of pages in each relation!

Common Heuristics

Heuristics 启发式

There are way too many possible query plans for a reasonably complex query to analyze them all. We need some way to cut down the number of plans that we actually consider. For this reason, we will use a few heuristics:

1. Push down projects (\(\pi\)) and selects (\(\sigma\)) as far as they can go
2. Only consider left deep plans
3. Do not consider cross joins (=Cartesian Product) unless they are the only option

The first heuristic says that we will push down projects and selects as far as they can go. We touched on why pushing down selects will be beneficial. It reduces the number of pages the other operators have to deal with. But why is pushing projects down beneficial? It turns out this also reduces the number of pages future operators need to deal with. Because projects eliminate columns, the rows become smaller, meaning we can fit more of them on a page, and thus there are fewer pages! Note that you can only project away columns that are not used in the rest of the query (i.e. if they are in a SELECT or a WHERE clause that hasn’t yet been evaluated you can’t get rid of the column).

The second heuristic says to only consider left deep plans. A left deep plan is a plan where all of the right tables in a join are the base tables (in other words, the right side is never the result of a join itself, it can only be one of the original tables). The following diagram gives some examples of what are and what are not left-deep plans.

Left deep plans are beneficial for two main reasons. First, only considering them greatly reduces the plan space. The plan space is factorial in the number of relations, but it is a lot smaller than it would be if we considered every plan. Second, these plans can be fully pipelined, meaning that we can pass the pages up one at a time to the next join operator – we don’t actually have to write the result of a join to disk.

The third heuristic is beneficial because cross joins produce a ton of pages which makes the operators above the cross join perform many I/Os. We want to avoid that whenever possible.

Pass 1 of System R

The query optimizer that we will study in this class is called System R. System R uses all of the heuristics that we mentioned in the previous section. The first pass of System R determines how to access tables optimally or interestingly (we will define interesting in a bit).

We have two options for how to access tables during the first pass:

1. Full Scan
2. Index Scan (for every index the table has built on it)

For both of these scans, we only return a row if it matches all of the single table conditions pertaining to its table because of the first heuristic (push down selects). A condition involving columns from multiple tables is a join condition and cannot yet be applied because we’re only considering how to access individual tables. This means the selectivity for each type of scan is the same, because they are applying the same conditions!

The number of I/Os required for each type of scan will not be the same, however. For a table P, a full scan will always take [P] I/Os; it needs to read in every page.

For an index scan, the number of I/Os depends on how the records are stored and whether or not the index is clustered.

Alternative 1 indexes have an IO cost of: (cost to reach level above leaf) + (num leaves read)

You don’t necessarily have to read every leaf, because you can apply the conditions that involve the column the index is built on. This is because the data is in sorted order in the leaves, so you can go straight to the leaf you should start at, and you can scan right until the condition is no longer true.

详细解释

1. 全表扫描

   • 全表扫描：扫描整个表的每一页。
   • 成本：总是等于表P的页数，即[P]个I/O。
   • 应用：适用于没有合适索引或查询需要访问表的很大一部分记录的情况。

2. 索引扫描

   • 索引扫描：通过索引访问记录。
   • 聚簇索引：数据物理上按照索引顺序存储。
     • 成本较低，因为相关记录在物理上接近，读取效率高。
   • 非聚簇索引：数据物理上不按照索引顺序存储。
     • 成本较高，因为可能需要多次随机访问磁盘。
   • Alternative 1 索引的I/O成本：
     • 到达 叶子层以上层级 的成本：读取索引的非叶子层，找到目标叶子。
     • 读取的叶子数量：根据索引条件扫描叶子，直到条件不再满足。

举个例子

假设我们有一个表P，它有1000页，且有一个在列A上的索引。

1. 全表扫描：

   • 需要读取所有1000页，成本为1000个I/O。

2. 索引扫描（假设索引是聚簇索引）：

   • 到达叶子层的成本：例如需要读取3层索引的节点，每层1个I/O，总共3个I/O。
   • 读取的叶子数量：假设索引扫描条件筛选出10%的记录，则只需要读取100页。
   • 总成本：3（索引层）+ 100（数据页）= 103个I/O。

通过这种方法，我们可以有效地减少需要读取的页数，从而优化查询性能。

Example-1: Important information:

• Table A has [A] pages
• There is an alternative 1 index built on C1 of height 2
• There are 2 conditions in our query: C1 > 5 and C2 > 6
• C1 and C2 both have values in the range 1-10

The selectivity will be 0.25 because both conditions have selectivity 0.5 (from selectivity formulas), and it’s an AND clause so we multiply them together.

However, we can not use the C2 condition to narrow down what pages we look at in our index because the index is not built on C2. We can use the C1 condition, so we only have to look at 0.5[A] leaf pages. We also have to read the two index pages to find what leaf to start at, for a total number of 2 + 0.5[A] I/Os.

For alternative 2/3 indexes, the formula is a little different. The new formula is: (cost to reach level above leaf) + (num of leaf nodes read) + (num of data pages read).

We can apply the selectivity (for conditions on the column that the index is built on) to both the number of leaf nodes read and the number of data pages read.

For a clustered index, the number of data pages read is the selectivity multiplied by the total number of data pages. For an unclustered index, however, you have to do an IO for each record, so it is the selectivity multiplied by the total number of records.

Example: Important information:

• Table B with B data pages and |B| records
• Alt 2 index on column C1, with a height of 2 and [L] leaf pages
• There are two conditions: C1 > 5 and C2 < 6
• C1 and C2 both have values in the range 1-10

If the index is clustered, the scan will take 2 I/Os to reach the index node above the leaf level, it will then have to read 0.5[L] leaf pages, and then 0.5[B] data pages. Therefore, the total is 2 + 0.5[L] + 0.5[B]. If the index is unclustered, the formula is the same except we have to read 0.5|B| data pages instead. So the total number of I/Os is 2 + 0.5[L] + 0.5|B|.

The final step of pass 1 is to decide which access plans we will advance to the subsequent passes to be considered. For each table, we will advance the optimal access plan (the one that requires the fewest number of I/Os) and any access plans that produce an optimal interesting order. An interesting order is when the table is sorted on a column that is either:

• Used in an ORDER BY
• Used in a GROUP BY
• Used in a downstream join (a join that hasn’t yet been evaluated. For pass 1, this is all joins)

The first two are hopefully obvious. The last one is valuable because it can allow us to reduce the number of I/Os required for a sort merge join later on in the query’s execution. A full scan will never produce an interesting order because its output is not sorted. An index scan, however, will produce the output in sorted order on the column that the index is built on. Remember though, that this order is only interesting if it used later in our query!

Example: Let’s say we are evaluating the following query:

SELECT * 
FROM players INNER JOIN teams
ON players.teamid = teams.id
ORDER BY fname;

And we have the following potential access patterns:

1. Full Scan players (100 I/Os)
2. Index Scan players.age (90 I/Os)
3. Index Scan players.teamid (120 I/Os)
4. Full Scan teams (300 I/Os)
5. Index Scan teams.record (400 I/Os)

Patterns 2, 3, and 4 will move on. Patterns 2 and 4 are the optimal pattern for their respective table, and pattern 3 has an interesting order because teamid is used in a downstream join.

• 模式1：全表扫描players，需要100 I/O，不会产生有趣的顺序。
• 模式2：索引扫描players.age，需要90 I/O，是players表的最佳访问计划，但没有产生有趣的顺序。
• 模式3：索引扫描players.teamid，需要120 I/O，虽然不是players表的最佳访问计划，但产生了有趣的顺序，因为teamid在后续的连接中使用。
• 模式4：全表扫描teams，需要300 I/O，是teams表的最佳访问计划。
• 模式5：索引扫描teams.record，需要400 I/O，不是teams表的最佳访问计划，也没有产生有趣的顺序。

Obviously, if there is a scan at "fname", it will be regarded as "interesting" as well.

Passes 2..n

The rest of the passes of the System R algorithm are concerned with joining the tables together. For each pass i, we attempt to join i tables together, using the results from pass i-1 and pass 1.

For example, on pass 2 we will attempt to join two tables together, each from pass 1. On pass 5, we will attempt to join a total of 5 tables together. We will get 4 of those tables from pass 4 (which figured out how to join 4 tables together), and we will get the remaining table from pass 1. Notice that this enforces our left-deep plan heuristic. We are always joining a set of joined tables with one base table.

Pass i will produce at least one query plan for all sets of tables of length i that can be joined without a cross join (assuming there is at least one such set). Just like in pass 1, it will advance the optimal plan for each set, and also the optimal plan for each interesting order for each set (if one exists). When attempting to join a set of tables with one table from pass 1, we consider each join the database has implemented.

Only one of these joins produces a sorted output - sort merge join (SMJ), so the only way to have an interesting order is by using SMJ for the last join in the set. The output of SMJ will be sorted on the columns in the join condition.

这段文字解释了System R算法在处理多表连接时的步骤和策略。以下是详细解释：

System R算法的多表连接过程

1. Pass 1

在第一步（pass 1）中，我们决定如何访问每一个单独的表。可能的访问方式包括全表扫描（full scan）和索引扫描（index scan）。每个表的最佳访问计划（即I/O最少的计划）以及每个表的有趣顺序都会被保留用于后续步骤。

2. 后续的各步（pass i）

在后续的每一步中，System R算法试图将多个表连接起来。具体来说：

• 在第i步（pass i），我们试图将i个表连接在一起。
• 这些表的连接方式使用的是第i-1步（pass i-1）的结果和第一步（pass 1）的结果。
• 例如，在第2步（pass 2），我们会尝试将两个表连接在一起，每个表都来自第一步（pass 1）的结果。
• 在第5步（pass 5），我们会尝试将总共5个表连接在一起。我们从第四步（pass 4）中获得4个表（即已经确定了如何连接这4个表），剩下的一个表来自第一步（pass 1）。

这个过程遵循了左深树（left-deep tree）计划的启发式方法。即我们总是将已经连接的一组表与一个基础表进行连接。

连接表的策略

• 第i步（pass i）会为所有可以在不使用交叉连接（cross join）的情况下连接的表集生成至少一个查询计划（假设至少存在一个这样的集合）。
• 和第一步一样，第i步会将每个集合的最佳计划（最少I/O的计划）以及每个集合的有趣顺序的最佳计划（如果存在）保留用于后续步骤。

有趣顺序和连接方法

• 当试图将一组表与来自第一步（pass 1）的一个表进行连接时，我们会考虑数据库中实现的每个连接操作。
• 只有一种连接操作会产生有序的输出——排序合并连接（Sort-Merge Join, SMJ）。所以，有趣顺序的唯一方法是使用SMJ作为集合中的最后一个连接。
• SMJ的输出将根据连接条件中的列进行排序。

具体例子

假设在某一步，我们有以下的表连接情况：

• 从第四步（pass 4）中获得的4个表已经连接在一起。
• 第五步（pass 5）需要将这4个表与来自第一步（pass 1）的一个新表连接。
• 使用SMJ连接这些表，将会产生一个有序的输出，排序顺序基于连接条件中的列。

这个过程确保了每一步的输出都是左深树结构，并且在可能的情况下利用有序性来优化查询计划。

System R算法通过逐步连接表，并在每一步保留最佳计划和有趣顺序来优化查询。这种方法确保了查询计划的有效性，并利用有序性来减少后续步骤的I/O开销。

为什么这个新表来自pass1而不是pass5（上例）

Review: Left-deep tree

在System R算法中，每一步的连接操作遵循左深树（left-deep tree）结构，这是为了简化查询计划的空间并提高执行效率。左深树结构意味着在每一次连接操作中，左侧的输入总是一个已经连接好的子树（由之前的连接步骤产生），而右侧的输入总是一个基础表（即原始的单个表）。这有助于避免复杂的笛卡尔积，并允许流水线处理（pipelining），从而减少中间结果的存储开销。

左深树结构的优点

1. 简化查询计划空间：左深树结构减少了可能的查询计划数量，因为我们只考虑左深的连接树，而不考虑更复杂的树形结构。
2. 支持流水线处理：左深树允许我们将中间结果直接传递给下一个操作，而不需要将中间结果全部写入磁盘。这可以显著减少I/O开销。

第五步（pass 5）中的连接操作

假设在第四步（pass 4），我们已经连接了4个表。现在在第五步（pass 5），我们需要将这4个表与另一个表连接起来。这时，我们按照左深树结构的原则：

1. 从第四步（pass 4）中获得的4个表已经连接在一起，形成一个子树（连接好的部分）。
2. 我们需要选择一个基础表与这4个表连接。

按照左深树的策略，右侧的输入应当是一个基础表，即最初在第一步（pass 1）中单独考虑的表。这是因为：

• 基础表的选择：从第一步（pass 1）中选择基础表可以确保我们总是将一个已经连接好的子树与一个基础表连接，保持左深树结构的简单性和一致性。
• 连接顺序的优化：这样做可以利用基础表的索引和排序特性来优化连接操作，尤其是使用排序合并连接（SMJ）时，基础表的排序特性可以帮助减少I/O开销。

有趣顺序的应用

当我们在第五步（pass 5）使用排序合并连接（SMJ）时，左侧的4个表已经连接在一起，并且可能已经按照某种顺序排序。如果这个排序是有趣的（例如，用于后续的ORDER BY、GROUP BY或连接条件），那么SMJ可以利用这个有序性来提高连接效率。

综上所述，选择基础表总是来自第一步（pass 1）而不是来自已经连接的表集（例如第四步（pass 4）中的部分）是为了保持左深树结构的简单性，支持流水线处理，并优化查询计划的执行效率。

However, both simple nested loop join (SNLJ) and index nested loop join (INLJ) can preserve a sorted ordering of the left relation. Since both of these perform all the joins on an individual tuple from the left relation before moving to the next tuple from left relation, the left relation’s ordering is preserved.

Grace Hash Join (GHJ), Page Nested Loop Join (PNLJ), and Block Nested Loop Join (BNLJ) never produce an interesting ordering. GHJ’s output order is based on the order of tuples in the probing relation since we iterate through each tuple in the probing relation to find matches in the other relation’s in-memory hash table. However, since the probing relation itself has been partitioned by hashing, there are no guarantees about the probing relation’s ordering across partitions, so there are no guarantees about the output’s overall ordering. PNLJ and BNLJ are similar to SNLJ, but they don’t generate all the join outputs of a single tuple in the left relation before moving to the next tuple in the left relation. Instead, they read ranges of tuples from the left relation and make matches on these ranges with chunks of tuples from the right relation, so they don’t preserve order.

Note

• SNLJ和INLJ可以保持左表的排序，因为它们在处理左表的每个元组时，会在移动到下一个元组之前完成所有的连接。
• GHJ、PNLJ和BNLJ则不能保持左表的排序，因为它们的处理方式涉及 元组块或范围，这会打乱左表的顺序。

下面的例子解释了在查询优化过程中，System R 算法如何在不同的阶段选择和处理连接计划，并说明了为什么某些连接计划会被选中进入下一阶段。以下是详细解释：

我们要执行以下查询：

SELECT * 
FROM A INNER JOIN B
ON A.aid = B.bid 
INNER JOIN C
ON B.did = C.cid
ORDER BY C.cid;

第二阶段的连接计划选择

在第二阶段，我们只考虑两个表的集合 {A, B} 和 {B, C}，不考虑 {A, C} 因为没有连接条件（我们的启发式规则告诉我们不要考虑笛卡尔积）。

假设我们的数据库中只实现了排序合并连接（SMJ）和块嵌套循环连接（BNLJ），并且第一阶段只返回了每个表的全表扫描结果。

以下是我们会考虑的连接（成本是为了问题假设而设定的）：

1. A BNLJ B (估计成本：1000)
2. B BNLJ A (估计成本：1500)
3. A SMJ B (估计成本：2000)
4. B BNLJ C (估计成本：800)
5. C BNLJ B (估计成本：600)
6. C SMJ B (估计成本：1000)

在第二阶段，我们选择以下连接计划进入下一阶段：

• 连接 1 是集合 {A, B} 的最佳连接。
• 连接 5 是集合 {B, C} 的最佳连接。
• 连接 6 是一个有趣的顺序，因为它在查询的后续部分使用了 ORDER BY 子句（使用了 C.cid）。

我们不选择连接 3，因为 A.aid 和 B.bid 在此连接之后不再使用，所以这个顺序对我们来说没有意义。

第三阶段的连接计划选择

在第三阶段，我们将考虑以下连接（成本是为了问题假设而设定的）：

1. {A, B} BNLJ C (估计成本：10,000)
2. {A, B} SMJ C (估计成本：12,000)
3. {B, C} BNLJ A (估计成本：8,000)
4. {B, C} SMJ A (估计成本：20,000)
5. {B, C} BNLJ A (估计成本：22,000)
6. {B, C} SMJ A (估计成本：18,000)

请注意，现在我们不能改变连接顺序，因为我们只考虑左深计划，所以基本表必须在右侧。

现在我们选择以下连接计划进入下一阶段：

• 连接 2 是所有三个表的集合的最佳计划，并且它具有 C.cid 的有趣顺序（因为我们还没有评估 ORDER BY 子句，所以它仍然是有趣的）。
• 连接 3 是所有三个表的集合的整体最佳计划。

连接 2 产生按 C.cid 排序的输出，因为连接条件是 B.did = C.cid，所以输出将按 B.did 和 C.cid 排序（因为它们是相同的）。连接 4 和 6 不会产生按 C.cid 排序的输出，因为它们将 A 添加到已连接表的集合中，因此条件将是 A.aid = B.bid。由于 A.aid 和 B.bid 在查询的其他地方没有使用，所以它们的排序对我们来说没有意义。

Calculating I/O Costs for Join Operations

Consideration #1

When we are estimating the I/O costs of the queries we are trying to optimize, it is important to consider the following:

• Whether we materialize intermediate relations (outputs from previous operators) or stream them into the input of the next operator.

• If interesting orders obtained from previous operators may reduce the I/O cost of performing a join.

Due to these considerations, we may not be able to directly use the formulas from the Iterators & Joins module to calculate I/O cost.

example

Consideration #2

We must also consider the effects of interesting orders from previous operators.

example