-
SQL可以运用嵌套语句进行查询，类似复合函数。
-
SQL: workhorse: SFW block; Set operators are powerful; Nested queries also allowed
-
Relational algebra: 从描述到精确表述
-
Basic operator: 选择$\sigma$，投射$\prod$，笛卡尔积$\times$，并∪，差$-$，交∩，连接$\Join$
-
可以对SQL表达式进行推导和化简，可以把SQL表达式表达成一棵树的形式，希望选择和投影越靠近树的根部越好（越早执行越好）。
- Buffer: a part of physical memory used to store temporary data.
- Page: fixed-sized array.
- File: a variable-length list of pages.
- 将两个有序的输入序列进行合并，输出一个合并的有序序列
- Input -> Buffer(select minimum) -> Output 3 buffer pages are needed.
- 在内存中可以把数据分成小块，把每个小块排序后合并。
- B+1页缓存的优化：
- 1.一次排序B+1的数据，
- 2.一次合并B组数据。IO Cost:
$2N(\log_B\frac{N}{B+1}+1)$ -
- Repacking
- 映射结构：把key映射到相应的table上
- B+树索引：根据B+树中数据的大小关系进行索引
- B+ Tree: High fanout = Smaller & lower IO
- 聚集索引：Clustered Indexing：有顺序的IO，比随机索引快得多。