Skip to main content

ucb cs186 课程笔记(更新中)

· 8 min read
ayanami

lec2​

join: inner join, natural join, outer join

sql 实际执行模型 写起来是 SELECT - FROM - GROUP BY - HAVING - WHERE - DISTINCT - ORDER BY

实际是 FROM(table过滤) - GRUOP BY(行分组) - HAVING(组过滤) - WHERE(行过滤) - DISTINCT(行去重) - SELECT(行内列过滤)

inner join:叉积，对AB所有行组合

SELECT * FROM TABLE1 t1, TABLE2 t2 
	WHERE t1.id = t2.id
	AND ...
-- 等效于
SELECT * FROM 
	TABLE1 t1 INNER JOIN TABLE2 t2
    ON t1.id = t2.id
    WHERE ...
-- 下面这种更加清晰一点
-- 等效于
SELECT * FROM 
	TABLE1 t1 NATURAL JOIN TABLE2 t2
    WHERE ...
-- natural join就是在组合的基础上自动用了一个过滤，要求table所有相同名字的列的值都相同

outer join:

Left Outer join:

A LEFT OUTER JOIN B ON cond 如果cond满足的话，得到的是AB的组合（一行有A的列+B的列）;如果不满足，得到A的列+空

Right Outer Join 同理

Full Outer Join 同理 例如ON A.id = B.id

如果有A没有对应的B, 那就是是 A + 空

如果有B没有对应的A, 那就是 空 + B

非常好的图

db-join

alias

简化 + 看起来更清楚（尤其是self-join）

FROM TABLE1 AS x, TABLE1 AS y

String Comp

LIKE或者正则S.name ~ '^B.*' (等效于S.name LIKE 'B_%')

AND OR 做条件交并

EXCEPT UNION (ALL) INTERSECT做子查询结果集合的交并差

IN EXISTS用于子查询 (NOT IN, NOT EXIST) EXISTS是判空

SELECT S.sname FROM Sailors S WHERE S.sid IN 
	(SELECT R.sid FROM Reserves R WHERE R.bid=102)

还有ANY ALL

ARGMAX?

SELECT * FROM Sailors S WHERE
	S.rating >= ALL
		(SELECT S2.rating FROM Sailors S2)

View: Named Queries

CREATE VIEW xxx
  AS ...

SELECT * FROM xxx;

cache and reuse

或者

WITH [viewname] AS [statement]创建一个临时view

NULL 参与的运算大多是NULL, 除了IS NULL，False AND NULL这种

lec3​

Disk & Buffer

整体架构

SQL client-> Query Parsing & Optimization->Relational Operators-> Files and Index Management->Buffer Management->Disk Space Management

Concurrency Control & Recovery

磁盘太慢，需要尽量减少读写，且寻道和旋转时间是大头

"block" && "page": 一个意思，磁盘上的块状读写最小单元 一般64KB-128KB

为了重用硬件驱动，经常会将磁盘空间管理器建立在文件系统API上，但带来了一些大数据库多文件系统的问题，也有直接建立在设备上的，更快但是移植性问题

给上层的抽象是一个巨大的文件

DB file: page的集合，每个page又包含了许多records

给上层提供：CRUD on records

record解构成一个"指针" {pageID, location on page}

structures

  • Unordered Heap Files(和数据结构heap没啥关系，无序records)
  • Clustered Heap Files
  • Sorted Files
  • Index Files

如何组织page呢？

链表？ 想想就知道效率很差

类似目录的形式？ 部分page只存到其他page的指针，并且始终放在缓存之中

page解构

Page Header:

  • Number of records
  • Free space
  • Mayba a last/next pointer
  • Bitmaps, slot table

record 中间留不留空？

不留空：Fixed Length Records, Packed

header后面跟紧密定长records, 因此可以有 record id = {pageId, record number in page}， 简单运算得到location

加很简单，直接append

删，全移一遍？->O(N),自然想到能不能lazy delete或者soft delete

方法是在header里面放一个delete bit的bitmap

变长？

slotted page

将信息存在footer（称为slot directory）, record从头部开始存

由record id得到dir中位置，位置里面是pointer + length，

删，将slot dir中的项置空

插入，插在空位上，更新slot dir

fragmentation?

什么时候reorganize?->设计取舍，大部分时候没有那么多删除（乐）

slot不够->从page尾部向前增长

lec4​

cost model for ayalysis

B, D, R

  • the number of data blocks
  • the number of records per clock
  • avg time to r/w disk block
  • opt: index

indexes:

大幅度降低range操作耗时

An index is data structure that enables fast lookup and modification of data entries by search key

区间查找 & 子集搜索, 可以复合, 不需要唯一

2-d box 2-d circle n-d indexes都有

kd树啊R树啊

postgres 的 GiST index

left key opt: 最小的key是不需要的,直接拿-inf当下界就行

处理相等:>= 向右走就行

B+树

  • 叶子不一定是连续的-动态分配,指针连接以支持range scan

  • 阶数d, fan-out 2d+1 典型的fan-out 为2144()

  • 删除, 理论上来说, 可能涉及到重新平衡等操作 但实际的操作之中, 只需要删除即可, 原因是平衡太慢了,并且删了也能再插

叶子放什么?

  1. 数据

pros:

  • 快

cons:

  • 想要在另一列构建索引只能重新复制文件(文件只能按照一种方式实际排序存储)
  • 即使真复制了,同步问题也很寄
  1. 指向数据的指针 (key, page id+list of record id)

在b+树里面有重复项

  1. 指向同一个键的所有records (key, list of (page id + list of record id))

减少冗余,增加复杂性

clustered: index指向的数据块在磁盘上是按照这个index排序或者近似排序的

非常大影响性能 顺序比随机快100倍

对于一个有变化的数据,例如插入或者删除,需要一些成本进行磁盘数据的重新排序来维持clustered

B+树的平衡性:

使用字节数半满(占页面容量)就行, 甚至实际上更低, 按照实际性能来决定,不严格

变长key: 前缀压缩 trie

性能的常数:

由于顺序读写比随机读写快100倍

B+树比全表扫描差不多也是涉及到1%以下的表才有显著优势

所以例如对一个非聚簇索引进行一个跨越半个表的range的扫描, 那还不如直接把全表取出来

优化

由于B+树效率真的很低,所以有很多优化策略

  • bulk loading 批量装载
  1. Sort the data by a key.
  2. Fill leaf pages up to size f (the fill factor).
  3. If the leaf page overflows, then use the insertion split algorithm from a normal B+ tree.
  4. Adjust pointers to reflect new nodes if needed.
Loading Comments...