查询处理中的选择操作

在上一节中，我们了解到估算查询计划的成本应该通过衡量总资源消耗来完成。

在本节中，我们将了解选择操作是如何在查询执行计划中执行的。

通常，选择操作是通过文件扫描来执行的。文件扫描是用于定位和访问数据的搜索算法。它是查询处理中使用的最低级别操作符。

让我们看看如何使用文件扫描进行选择。

使用文件扫描和索引进行选择

在关系数据库管理系统（RDBMS）或关系数据库系统中，文件扫描仅在整个关系存储在一个文件中时才读取关系。当对元组存储在一个文件中的关系执行选择操作时，它使用以下算法

• 线性搜索：在线性搜索中，系统扫描每条记录以测试其是否满足给定的选择条件。为了访问文件的第一个块，需要进行一次初始寻道。如果文件中的块不是按连续顺序存储的，那么就需要一些额外的寻道。然而，线性搜索是用于搜索的最慢算法，但它适用于所有类型的情况。该算法不关心选择的性质、索引的可用性或文件序列。但其他算法并非适用于所有情况。

带索引的选择操作

基于索引的搜索算法被称为索引扫描。这种索引结构被称为访问路径。这些路径允许定位和访问文件中的数据。以下是在查询处理中使用索引的算法

• 主索引，键上的等值查询：我们使用索引来检索满足等值条件的单个记录以进行选择。等值比较是在带有主键的键属性上执行的。
• 主索引，非键上的等值查询：键上等值查询和非键上等值查询的区别在于，后者可以获取多条记录。当选择标准指定了在非键上的等值比较时，我们可以通过主键获取多条记录。
• 二级索引，键或非键上的等值查询：指定等值条件的选择可以使用二级索引。使用二级索引策略，当等值查询在键上时，我们可以检索单个记录；当等值条件在非键上时，可以检索多个记录。检索单个记录时，时间成本与主索引相等。在多条记录的情况下，它们可能驻留在不同的块上。这导致每个获取的记录需要一次 I/O 操作，而每次 I/O 操作都需要一次寻道和一次块传输。

带比较的选择操作

为了在关系中基于比较进行任何选择，我们可以通过使用线性搜索或通过以下方式使用索引来进行

• 主索引，比较：当用户给出的选择条件是比较时，我们使用主有序索引，例如主 B⁺-树索引。例如，当关系 R 的属性 A 与给定值 v 进行比较，如 A>v 时，我们使用 A 上的主索引直接检索元组。文件扫描从头到尾搜索，并输出所有满足给定选择条件的元组。
• 二级索引，比较：二级有序索引用于满足涉及 <、>、≤ 或 ≥ 的选择操作。在此操作中，文件扫描会搜索最低层索引的块。
  (< ≤)：在这种情况下，它从最小值扫描到给定值 v。
  (>, ≥)：在这种情况下，它从给定值 v 扫描到最大值。
  然而，二级索引的使用应仅限于选择少量记录。这是因为这种索引提供了指向每条记录的指针，因此用户可以通过分配的指针轻松获取记录。这样检索到的记录可能需要一次 I/O 操作，因为记录可能存储在文件的不同块上。因此，如果获取的记录数量很大，使用二级索引会变得昂贵。

实现复杂的选择操作

处理更复杂的选择涉及三种选择谓词，称为合取、析取和否定。

合取（Conjunction）：合取选择是具有以下形式的选择

σ _{θ1ꓥθ2ꓥ…ꓥθn} (r)

合取是满足上述选择条件的所有记录的交集。

析取（Disjunction）：析取选择是具有以下形式的选择

σ _{θ1ꓦθ2ꓦ…ꓦθn} (r)

析取是满足给定选择条件 θ_i 的所有记录的并集。

否定（Negation）：选择 σ_¬θ(r) 的结果是给定关系 r 中选择条件评估为假的元组集合。但前提是不存在空值，并且这个集合就是关系 r 中不在 σ_θ(r) 中的元组集合。

使用这些讨论过的选择谓词，我们可以通过以下算法实现选择操作

• 使用一个索引的合取选择：在这种类型的选择操作实现中，我们首先确定是否有任何属性的访问路径可用。如果找到一个，那么基于索引的算法会工作得更好。选择操作的进一步完成是通过测试每个选定的记录是否满足剩余的简单条件来完成的。所选算法的成本即为该算法的成本。
• 通过复合索引的合取选择：复合索引是在多个属性上提供的索引。对于某些合取选择，可能存在这样的索引。如果给定的选择操作在两个或多个属性上证明了等值条件为真，并且在这些组合属性字段上存在复合索引，则直接搜索该索引。这类索引会评估合适的索引算法。
• 通过标识符交集的合取选择：此实现涉及记录指针或记录标识符。它在涉及单个选择条件的字段上使用带有记录指针的索引。它扫描每个索引以获取满足单个条件的元组指针。因此，所有检索到的指针的交集就是满足合取条件的元组指针集合。该算法使用这些指针来获取实际记录。然而，如果缺少针对每个单独条件的索引，它会对检索到的记录测试其他剩余条件。
• 通过标识符并集的析取选择：该算法扫描所有索引以获取满足单个条件的元组指针。但前提是所有析取选择条件上都有可用的访问路径。因此，所有获取的记录的并集提供了指向所有满足或证明析取条件的元组的指针集。然后，它利用指针来获取实际记录。如果任何一个条件没有访问路径，我们需要使用线性搜索来找到满足该条件的元组。因此，使用线性搜索来确定此类测试是很好的选择。

成本估算

在这里，算法的总成本是通过将各个索引扫描的成本和获取检索到的指针列表交集中的记录的成本相加来构成的。我们可以通过对指针列表进行排序并获取排序后的记录来最小化成本。因此，我们发现了以下两点用于成本估算

• 我们可以使用单个 I/O 操作获取块中所有选定的记录，因为块中的每个指针会一起出现。
• 由于块是按排序顺序读取的，磁盘臂的移动被最小化了。

各种选择算法的成本估算图

在这里，b_r 是文件中的块数。

h_i 表示索引的高度

b 是持有具有指定搜索键的记录的块数

n 是获取的记录数