Internals of a DBS I
Query Optimization And Execution
Relational Operators
Access Methods
Copyright By PowCoder代写 加微信 powcoder
Buffer Management
Disk Space Management
COMP 421 @ McGill 1
The very Essentials of Disk and Buffer Management
COMP 421 @ McGill 2
Memory Hierarchy
Memory Hierarchy is to obtain the highest possible
access speed while minimizing the total cost of the memory system
Magnetic tapes
Magnetic disks
I/O processor
Main memory
Cache memory
Register Cache
Main Memory Magnetic Disk
Magnetic Tape
COMP 421 @ McGill
Tape drives
https://en.wikipedia.org/wiki/9_track_tape
https://en.wikipedia.org/wiki/Tape_library
COMP 421 @ McGill 4
Disks and Main Memory
• DBMS stores information persistently on (“hard”) disks.
• Unit of transfer main-memory/disk: disk blocks or pages.
• Time to read/write data block:
– 2- 10 msec for random data block (main factor is seek time)
– If blocks are sequentially on disk, each additional block only 1 msec
– Comparemainmemoryaccess:innanoseconds
– SSD: 0.1 ms (still slower than main memory access and calculations…)
• Basic operations
– READ: transfer data from disk to main memory (RAM).
– WRITE: transfer data from RAM to disk.
• Why disks?
– Cheaper than Main Memory
– Higher Capacity
– Main Memory is volatile 5
COMP 421 @ Mc head
Why Block/Page Concept
Arm movement
B. Geometrical sector C. Disk sector
D. Cluster
https://en.wikipedia.org/wiki/Disk_sector
COMP 421 @ McGill 6
Adv. of Contiguous Access
COMP 421 @ McGill 7
Assumed Distribution
Buffer (volatile)
Secondary Storage (stable)
COMP 421 @ Mc : Faster stable storage
“Hot” Data
“Cold” Data
Register Cache
Main Memory
Solid State Drive
Magnetic Disk Magnetic Tape
Solid State Drive
Disaster Recovery
COMP 421 @ McGill 9
Trends: memory databases
Secondary Storage (stable)
COMP 421 @ Mc : large scale distribution
COMP 421 @ McGill 11
Architecture
Upper Layer
Cache/Buffer Manager
Buffer (volatile)
Secondary Storage (stable)
COMP 421 @ Mc Management in a DBMS
Page Requests from Higher Levels request: pageid
return: offset
BUFFER POOL
disk page free frame
MAIN MEMORY DISK
choice of frame dictated by replacement policy
❑ Data must be in RAM for DBMS to operate on it!
❑ Table of
13 ❑ Some more information about each page in buffer is maintained COMP 421 @ Mc a page from disk…
❑ If requested page is not in pool:
✩ Ifthereisanemptyframe ● Choose empty frame
✩ Else(noemptyframe)
● Choose a frame for replacement
● If frame is dirty (page was modified), write it to disk
✩ Readrequestedpageintochosenframe
COMP 421 @ Mc Pins
• When loading a page from disk:
– Replacement frame must have “pin counter” of 0
– Afternewpageisloaded:set“pincounter”offrameto1
• When requesting a page that is in the buffer – Increment pin counter
• After operation has finished – Decrement pin counter
– Set dirty bit if page has been modified:
• Frame is chosen for replacement by a replacement policy:
– Only unpinned page can be chosen (pin count = 0)
– Least-recently-used (LRU), Clock, MRU etc.
Pin counter
COMP 421 @ McGill
DBMS vs. OS File System
OS does disk space & buffer mgmt: why not let OS manage these tasks?
• Differences in OS support: portability issues
• Some limitations, e.g., files can’t span disks.
• Buffer management in DBMS requires ability to:
– pin a page in buffer pool, force a page to disk (important for
implementing CC & recovery),
– adjust replacement policy, and pre-fetch pages based on access patterns in typical DB operations.
COMP 421 @ Mc Format: Fixed Length
F1 F2 F3 F4
Base address (B) Address = B+L1+L2
• Length of field (attribute) depends on type • Works with fixed-length types
• Strings:padding
• Offset of each field easy to calculate
COMP 421 @ McGill 17
Variable Length
F1 F2 F3 F4
☛Second offers direct access to i’th field, efficient storage of nulls (special don’t know value); small directory overhead
COMP 421 @ McGill 18
Page Formats: Variable Length Records
Rid = (i,1)
Rid = (i,2)
length = 24
Rid = (i,N)
Pointer to start of free space
SLOT DIRECTORY Record Length ☛ Record id (rid) = internal identifier of a record:
☛ Can move records on page without changing rid; COMP 421 @ Mc relation in a file
• File:Collectionofpages
– For instance: Pages hold records of one relation
• Interface:
– Insert a record
• Returns rid
– Get a record by rid
• Returns record
– Scan all records (possibly with some condition on some attribute)
• Returns all qualifying records
COMP 421 @ McGill 20
Unordered (Heap) File
• Simplest file structure contains records in no particular order.
• As file grows and shrinks, disk pages are allocated and de-allocated.
• To support record level operations, we must: – keep track of the pages in a file
– keep track of free space on pages
– keep track of the records on a page
• There are many alternatives for keeping track of this.
COMP 421 @ McGill 21
Heap implemented as a list
Full Pages
Header Page
Pages with Free Space
• The header page id and Heap file name must be stored someplace.
• Each page contains 2 `pointers’ plus data.
COMP 421 @ McGill 22
Sorted file
• Records are sorted by one of the attributes (e.g., name).
• Each page contains 2 `pointers’ plus data.
Header Page
234, Dahli, 2015
3339, Donald, 2010
111111, Dora, 1999
COMP 421 @ McGill
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com