Slides

S1: Csci 8701 - Week 5

Administrative
- HW 3 - DUE
Goals:
- Review of Storage Systems
- and DBMS - OS Interface
Recommended Readings:
- Stonebraker, OS Support for DBMS
- Chou, An Evaluation of Buffer Mgmt ...

S2: OS Support for DBMS

Problem Statement
- Given typical OS, typical DBMS
- Define: What DBMS needs from OS ?
- ... for performance, concurrency
Major Contributions
- DBMS needs, evaluation of OS services
- Influenced OS design in many areas

S3: OS Support for DBMS

Assumptions about OS (unix)
- Buffered I/O, LRU, prefetch
- file system - random allocation, directory tree
- Concurrency = process, disjoint address, semaphores
- Inter process communication = message
Assumptions about DBMS implementation
- 1 DBMS server process + 1 process/user
- no stable memory (battery backup)
Q? Which OS assumptions are obsolete due to :
- threads, raw devices, buffer pin/flush, shmem
- How do these affect DBMS implementation?

S4: OS Support for DBMS

Key Concepts: Buffer pool management
Key Concepts: consistency/locks
Problem 1: page I/O overhead
- Move a page from OS to user space
- system call (process switch) and a copy
Problem 2: Replacement policy LRU
- No provision for user (DBMS) defined policy
- DBMS knows access pattern in advance
Problem 3: Prefetch in physical order in a file
- DBMS may scan on any field

S5: OS Support for DBMS

Problem 4: Lack of buffer flush (*)
- Recovery algo need to guarantee logs are on disk
- Write log pages in order (flush individual pages.
- release locks after commit is logged.
Problem 5: Byte level OS recovery (fsck)
- No help for transactions
Q? Which of these problems remain with OS?

S6: OS Support for DBMS

Key Concepts: file system
Problem 1: Random disk block allocation (Unix)
- DBMS prefers clustered allocation (e.g. segments)
Problem 2: File blocks organized via a tree in Unix
- It is redundnat with DBMS indices (e.g. B tree)
- Unify? integrate RSS and file system
- put DBMS below file system (Inversion)?

S7: OS Support for DBMS

Key Concepts: process scheduling
Key Concepts: inter-process communication
Problem: process-per-user , slow context-switch
- one thread per user, threaded server is better
Problem: Expensive messages?
- context switch, buffer copy
Problem: round-robin process scheduling
- Critical sections to share buffer pools in server
- suspending a process holding locks / semaphore
- ... no other user process can proceed
- Convoy effect (recall System R ). System R's solution?
Q? Is convoy effct a problem in thread/user model? Why?
Q? How can shared memory reduce cost of messages?

S8: OS Support for DBMS

Validation Methodology
- Design issues
- Alternative resolutions with OS contraints
- Arguments showing each alternative has problems
Rewrite today
- Revise OS service descriptions
- ... Current OS's fixed many complaints
- Revise DBMS needs - Some don't need an OS!
- New needs - ORDBMS, OODBMS, Internet DBMS
- e.g. security for user defined indexing, methods
- e.g. fast backup over network for Gigabyte tables
- parallel I/O, declustering, ...

S9: An evaluation of Buffer Management ...

S10: Key Concepts in Buffer Management

Query Behaviour in accessing disk pages
- Point search query
- Scan file
- Range query (data file access)
- Range query (index tree traversal)
Q? Choose OS Buffering policy for each
- Global Deterministic: LIFO, FIFO, Priority
- Global Stochastic: MRU, LRU, Clock
- Q? Which policy suits nested loop join?
Related work - Hot Set
- Allocation - a query gets size(hot set) buffer
- ... priority, working set are f(relation)
- Replacement - LRU per query
- Load-control - process a query iff hotset fits in buffers

S11: Key Concepts in DBMIN

S12: Key Concepts in Buffer Management

DBMIN
- Allocation - buffer grouped by relations
- ... max locality set sizes = f( query plan)
- Load-control - process a query iff
- ... sum of its locality sets fits in buffers
Replacement Policy - a global free list
- SS : LocSet size = 1. Replace page as needed
- CS : FIFO or LRU
- LS: MRU, LocSet size = size of relation.
Q?: List locality set sizes and policies for
- IR , CR, H/SS, H/CS, LH, ...

S13: Validation methods for Buffer Management

S14: Validation methods for Buffer Management

Experimental Results (pp. 123-4)
- Stochastic techniques (e.g. FIFO, LRU) - worst
- OS faourite Working Set in the middle
- DBMIN best, HOT is close second
Explanation of Results
- Buffer access patterns of DB is not random
- DBMIN best predicts access patterns in benchmark
Critique of Validation - self-centered
- Only shows dominance zone of DBMIN
- Did not prove: DBMIN always dominates others!
- Did not show where DBMIN loses!
- ... Choice of parameters is limited
- Q? Do claims apply to other workloads?

S15: An evaluation of Buffer Management ...

Assumptions in System Trace
- Simple data -
- ...Consider large objects (overlapping part-of hierarchy)
- Simple single Query
- ...Consider N-table join : buffering temp results
- ...a set of queries (common sub-expressions)
- Simple Query processing strategies
- ... Consider join-index based join, tree-matching join
Assumptions in Statistical distribution:
- Ex. R-tree, mixed clustering
Rewrite today
- Update related work: LRU-K [O'Neil & O'Neil]
- Expand or Specialize to apllication domains
- ... data, queries, processing strategies

S16: Appendix: Related Work in Buffer Management

Related work - Domain Separation:
- Allocation - static groups (e.g. levels of B+tree)
- Replacement - LRU within groups
- ... steal free pages from other groups
- Load-control - none
Related work - Group LRU
- Allocation - prioritized groups of pages
- ... group size = f (working set)
- Replacement - LRU within groups
- ... - steal pages from lower priority groups
- Load-control - none of highest priority group
Related work - Ingres new
- Allocation - prioritized groups (relations)
- ... priority, working set are f(relation)
- Replacement - MRU per relation
- Load-control - a relation has > = 1 buffer