Projection ($\pi$)

Key Attribute:

• Table Scan 因为没有重复

Non-key Attribute:

• Sort 然后 Table Scan 因为要去重

Selection ($\sigma$)

单点/区间查询

• Linear Search (No index, unsorted data)
• Binary Search (No index, sorted data)
  • Works for point query (e.g., $\sigma_\text{age=21}$)
  • Works for range query (e.g., $\sigma_\text{age>21}$)
    • 先二分找到 起始点，然后再扫
• Using index (e.g., B+ tree)
  • Flexible: Can create B+ tree index on key/non-key, sorted/unsorted attributes

使用优先级：

1. Index (if indexed)
2. (else) Binary Search (if sorted)
3. (else) Linear Search

复合查询（多条件）

考虑：$\sigma_\text{age < 25 AND gender = F}\ (\text{students})$

如果只有 age 有 index：

• 先按 age 的 index 搜一遍
• 再对新表筛选 gender = F