Transcript CS 440: Database Management Systems

CS 540
Database Management Systems
Lecture 4: DBMS Architecture, storage, and
access methods
1
The advantage of RDBMS
• It separates logical level (schema) from physical
level (implementation).
• Physical data independence
– Users do not worry about how their data is stored and
processes on the physical devices.
– It is all SQL!
– Their queries work over (almost) all RDBMS
deployments.
2
Challenges in physical level
•
•
•
•
Processor: 10000 – 100000 MIPS
Main memory: around 10 Gb/ sec.
Secondary storage: higher capacity and durability
Disk random access
– Seek time + rotational latency + transfer time
– Seek time: 4 ms - 15 ms!
– Rotational latency: 2 ms – 7 ms!
– Transfer time: at most 1000 Mb/ sec
– Read, write in blocks.
3
Random access versus sequential access
• Disk random access : Seek time + rotational
latency + transfer time.
• Disk sequential access: reading blocks next to
each other
• No seek time or rotational latency
• Much faster than random access
4
DBMS Architecture
User/Web Forms/Applications/DBA
query
transaction
Query Parser
Transaction Manager
Process manager
Query Rewriter
Query Optimizer
Lock Manager
Logging &
Recovery
Query Executor
Files & Access Methods
Buffer Manager
Buffers
Lock Tables
Main Memory
Storage Manager
Storage
5
DBMS Architecture
User/Web Forms/Applications/DBA
query
transaction
Query Parser
Transaction Manager
Process manager
Query Rewriter
Query Optimizer
Lock Manager
Logging &
Recovery
Query Executor
Files & Access Methods
This lecture
Buffer Manager
Buffers
Lock Tables
Main Memory
Storage Manager
Storage
6
A Design Dilemma
• To what extent should we reuse OS services?
• Reuse as much as we can
– Performance problem (inefficient)
– Lack of control (incorrect crash recovery)
• Replicating some OS functions (“mini OS”)
– Have its own buffer pool
– Directly manage record structures with files
–…
7
OS vs. DBMS Similarities?
• What do they manage?
• What do they provide?
8
OS vs. DBMS: Similarities
• Purpose of an OS:
– managing hardware
– presenting interface abstraction to applications
• DBMS is in some sense an OS?
– DBMS manages data
– presenting interface abstraction to applications
• Both as API for application development!
9
OS vs. DBMS: Related Concepts
 What DB concepts?
• Process Management
– process synchronization
– deadlock handling
• Storage management
– virtual memory
– file system
10
 What DB concepts?
OS vs. DBMS: Differences?
11
OS vs. DBMS: Differences
• DBMS: Top-down to encapsulate high-level semantics!
– Data
• data with particular logical structures
– Queries
• query language with well defined operations
– Transactions
• transactions with ACID properties
• OS: Bottom-up to present low-level hardware
12
Problems with DBMS on top of OS
• Buffer pool management
• File system
• Process management
• Consistency control
• Paged virtual memory
13
Buffer Pool Management
• Performance of system calls
• LRU replacement
– Query-aware replacement needed for performance
– Circular access: 1, 2, …, n, 1, 2, ..
• Prefetching
– DBMS knows exactly which block is to be fetched next
• Crash recovery
– Need “selected force out”
14
Relations vs. File system
• Data object abstraction
– file: array of characters
– relation: set of tuples
• Physical contiguity:
– large DB files want clustering of blocks
• sol1: managing raw disks by DBMS
• sol2: simulate by managing free spaces in DBMS
• Multiple trees (access methods)
– file access: directory hierarchy (user access method)
– block access: inodes
– tuple access: DBMS indexes
15
Process management
• Reuse OS process management
– One process for each user
• Problem: DB processes are large
– long time to switch between processes
• Problem: critical sections
– Processes may have to wait for a descheduled process that has locks.
– n server processes that handle users’ requests
• duplication of OS multi-tasking inside servers!
• communication between processes:
– Message passing is not efficient
• Solutions: OS implements
– favored processes
• not forced out, relinquish the control voluntarily.
– faster message passing methods.
16
Consistency control
• OS provides some support for locking and recovery.
– OS provides lock on files
– DB requires lock on smaller units like tuples
• Commit point
– Buffer manager ensures all changes are flushed on disk.
– Buffer manager must know the inside of transactions.
17
State of the art
• DBMSs duplicate some OS functionalities.
• OS customized for DBMS
18
Access methods
• The methods that RDBMS uses to retrieve the
data.
• Attribute value(s)  Tuple(s)
19
Types of search queries
• Point query over Product(name, price)
Select *
From Product
Where name = ‘IPad-Pro’;
• Range query over Product(name, price)
Select *
From Product
Where price > 2 AND price < 10;
20
Types of access methods
• Full table scan
– Inefficient for both point and range queries.
• Sequential access
– Efficient for both point and range queries.
– Should keep the file sorted.
• Inefficient to maintain
• Middle ground?
21
Indexing
• An old idea
22
Index
• A data structure that speeds up selecting tuples in
a relation based on some search keys.
• Search key
– A subset of the attributes in a relation
– May not be the same as the (primary) key
• Entries in an index
– (k, r)
– k is the search key.
– r is the pointer to a record (record id).
23
Index
• Data file stores the table data.
• Index file stores the index data structure.
Index File
Data File
10
10
20
20
30
40
30
40
50
60
50
70
80
60
• Index file is smaller than the data file.
• Ideally, the index should fit in the main memory.
24
Well known index structures
• B+ trees:
– very popular
• Hash tables:
– Not frequently used
25
B+ trees
• The index of a very large data file gets too large.
• How about building an index for the index file?
• A multi-level index, or a tree
26
B+ trees
• Degree of the tree: d
• Each node (except root) stores [d, 2d] keys:
Non-leaf nodes
[A , 10)
32
[10, 32)
Leaf nodes
Records
10
12
12
28
28
94
[32, 94)
32
[94, B)
39
41
65
32
27
Example
d=2
60
19
12
12
13
13
17
50
80
19
17
19
21
21
30
30
40
50
40
50
90
52
110
60
52
60
65
65
72
72
28
Retrieving tuples using B+ tree
• Point queries
– Start from the root and follow the links to the leaf.
• Range queries
– Find the lowest point in the range.
– Then, follow the links between the nodes.
• The top levels are kept in the buffer pool.
29
Inserting a new key
• Pick the proper leaf node and insert the key.
• If the node contains more than 2d keys, split the
node and insert the extra node in the parent.
(K3,
K1
R0
K2
R1
K3
R2
K4
R3
K5
R4
R5
K1
R0
K2
R1
) parent
K4
R2
R3
K5
R4
R5
– If leaf level, add K3 to the right node
30
Example
Insert K = 18
60
19
12
12
13
13
17
50
80
19
17
19
21
21
30
30
40
50
40
50
90
52
110
60
52
60
65
65
72
72
31
Insertion
Insert K = 18
60
19
12
12
13
13
17
17
50
18
18
80
19
19
21
21
30
30
40
50
40
50
90
52
110
60
52
60
65
65
72
72
32
Insertion
Insert K= 20
60
19
12
12
13
13
17
17
18
50
18
80
19
19
20
20
21
21
30
40
30
40
50
50
90
110
52
52
60
60
65
65
72
72
33
Insertion
Need to split the node
60
19
12
12
13
13
17
17
50
18
18
80
19
19
20
20
21
21
30
40
30
40
50
50
90
110
52
52
60
60
65
65
72
72
34
Insertion
Split and update the parent node.
What if we need to split the root?
60
19
12
12
21
13
17
18
19
13
17
18
19
50
20
20
80
21
21
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
35
Deletion
Delete K = 21
60
19
12
12
21
13
17
18
19
13
17
18
19
50
20
20
80
21
21
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
36
Deletion
Note: K = 21 may still remain in the internal levels
60
19
12
12
21
13
17
18
19
13
17
18
19
50
20
20
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
37
Deletion
Delete K = 20
60
19
12
12
21
13
17
18
19
13
17
18
19
50
20
20
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
38
Deletion
We need to update the number of keys on the node:
Borrow from siblings: redistribution , rotate
60
19
12
12
21
13
17
18
19
13
17
18
19
50
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
39
Deletion
We need to update the number of keys on the node:
Borrow from siblings: redistribution , rotate
60
19
12
12
13
17
13
17
21
18
18
19
19
50
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
40
Deletion
We need to update the number of keys on the node:
Borrow from siblings: redistribution, rotate
60
18
12
12
13
17
13
17
21
18
18
19
19
50
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
41
Deletion
What if we cannot borrow from siblings?
Example: delete K = 30
60
18
12
12
13
17
13
17
21
18
18
19
19
50
80
30
30
40
40
90
50
50
110
52
52
60
60
65
65
72
72
42
Deletion
What if we cannot borrow from siblings?
Merge with a sibling.
60
18
12
12
13
17
13
17
21
18
18
19
19
50
80
40
40
90
50
50
110
52
52
60
60
65
65
72
72
43
Deletion
What if we cannot borrow from siblings?
Merge siblings!
60
18
12
12
13
17
13
17
21
18
18
19
19
50
40
40
80
90
50
50
110
52
52
60
60
65
65
72
72
44
Deletion
What to do with the dangling key and pointer? simply remove them
60
18
12
12
13
17
13
17
21
18
18
19
19
50
40
40
80
90
50
50
110
52
52
60
60
65
65
72
72
45
Deletion
Final tree
60
18
12
12
13
17
13
17
50
18
18
19
19
80
40
40
90
50
50
110
52
52
60
60
65
65
72
72
46
What You Should Know
• What are some major limitations of services
provided by an OS in supporting a DBMS?
• In response to such limitations, what does a
DBMS do?
• B+ tree indexing
47