Chapter 9c: Disk Scheduling, Metadata, Records, and Pages
Ed Knorr, Slides from Sept-Dec 2020
Based on:
Sections 8.2 & 8.2.1 (pages 275-277) and Sections 9.3-9.32 & 9.5-9.7.2 (pages 316- 318 & 324-333, respectively) of our textbook:
• Ramakrishnan, Raghu and Gehrke, Johannes. Database Management Systems. McGraw-Hill, 2003.
• IBM Corporation. Db2 11 for z/OS: SQL Reference. September 10, 2018. (Part of the large set of IBM DB2 (rebranded to “Db2”) documentation.)
• Mullins, Craig. Database Administration. Addison-Wesley, 2013.
• Silberschatz, Abraham; Galvin, Peter Baer; and Gagne, Greg. Operating System Concepts. Wiley, 2002.
1
Learning Goals
Explain why page requests from disk may not be serviced immediately. List some of the reasons for contention.
Explain the relationship among disk geometry, buffer pool management, and disk scheduling in providing good performance for data requests from a user of a DBMS. List the bottlenecks that may contribute to poor I/O performance in this disk “chain”.
Compute the service order for a queue of track/cylinder/page requests using each of these disk scheduling algorithms: FCFS (First Come, First Serve), SSTF (Shortest Seek Time First), and Elevator (Scan with, and without, Look).
Give at least ten examples of the kinds of metadata stored for a DBMS.
Justify the use of metadata from the perspective of both a DBMS and a DBA.
2
Learning Goals (cont.)
Write simple SQL queries (on paper) to query an RDBMS catalog for metadata that is of interest to a DBA. For example, write simple SQL queries to join catalog tables and gather information from selected DB2 catalog tables.
Provide arguments for storing RDBMS metadata as a table rather than as a flat file or some other data structure.
Compare and contrast the record layouts for fixed-length and variable-length records in a DBMS. Provide an advantage for each.
Explain why rows on a page might be relocated.
Compare and contrast the page layouts for fixed-length and variable-
length records in a DBMS. Provide an advantage for each.
Justify the use of free space within a page, and intermittent free pages within a file, for an RDBMS table.
Given probabilities of average string lengths, determine whether it makes more sense to use a fixed-length field, rather than a variable- length field.
3
Link to Previous Units
Recall from previous units the relationship between disk pages and buffer pool pages.
A page is chosen for replacement using a page replacement algorithm (PRA), of which there are many: FIFO, LRU (including several variants), MRU, Clock, Extended Clock, Working Set, etc.
The optimal PRA is unachievable for most workloads. Why?
Another topic that involves disks and RAM is Disk Scheduling. We’ll briefly touch upon it in the next few slides.
4
Disk Service Time (to Fetch Pages)
DBMSs read and write disk pages frequently.
The fact that you request disk page p does not necessarily mean that you’ll get service quickly—even after considering seek, rotation, and transmission latencies. Why not?
Contention, including nearly simultaneous requests, from:
• Many DB users wanting access to the objects on the disk drive
• Non-DB users wanting access to files on the same disk drive
• Single user, but many processes/applications requesting service • Overhead service routines (DBMS, OS, anti-virus, etc.)
Disk scheduling
There are a number of different disk scheduling algorithms. In this course, we will only briefly touch upon them …
5
Disk Scheduling Algorithms
Suppose user(s) make the following nearly simultaneous requests for pages from these cylinders, and the head is currently on cyl. 165, having just come from cyl. 164:
1400, 2500, 170, 160, 161, 3500, 162
Here is the service order for the following disk scheduling algorithms:
FCFS: First Come, First Served: 1400, 2500, 170, 160, 161, 3500, 162
SSTF: Shortest Seek Time First: 162, 161, 160, 170, 1400, 2500, 3500
Which is more “efficient”? How can we measure efficiency? •
Is there any “unfairness” in any of these algorithms? Explain.
6
Disk Scheduling Algorithms (cont.)
Assume we’re on cyl. 165, having just come from cyl. 164, and all of a sudden, we get these requests:
1400, 2500, 170, 160, 161, 3500, 162
What is the service order for the popular Elevator Algorithm?
It sweeps back and forth, servicing requests as they are encountered, in both directions.
Source: Jim Unger, Herman cartoon
7
Disk Scheduling Algorithms (cont.)
For the Elevator Algorithm:
We can use the “SCAN with (or without) LOOK” option
• “LOOK” means only go as far as needed (elevator analogy: don’t go to the extreme floors unless a user request has been made).
• Service Order: 170, 1400, 2500, 3500, 162, 161, 160
What is the service order if: while servicing cyl. 1400, we suddenly get these new requests: 1250, 1400, and 1500?
• Answer: 170, 1400, 1400, 1500, 2500, 3500, 1250, 162, 161, 160
More examples are online in the practice questions and answers.
Another Variant: C-SCAN (Circular Scan)
Here, we don’t service new requests on the return trip; instead, we zoom back to the beginning, and then service requests in one direction only. Why might this be advantageous?
8
Indexes
In a file system, we can retrieve records by:
Scanning all records in a file sequentially, or
Specifying the rid (record ID), if known. • Each record has a unique rid.
Sometimes we want to retrieve records by specifying search criteria: the values in one or more fields. For example:
Find the name of the student with student ID 86753091.
Find all 1st year female students with the last name “Lee”.
Find all 4th year students in the CPSC department who have not taken CPSC 304.
Find all students in MATH with a GPA ≥ 85%.
9
Indexes (cont.)
Indexes are file structures that enable us to answer such value-based queries efficiently.
Think back to a data structures course like CPSC 221 that introduced:
• Key/Value pairs in hash structures and trees (e.g., binary trees, binary search trees, B+ trees, AVL trees)
Dense indexes store one key/value pair per record in the table. Often the value is a rid pointer, which points to the full record on disk corresponding to the key.
Clustering indexes are especially useful when retrieving multiple records that qualify (e.g., meet the WHERE-clause condition for an attribute on which the data table is clustered).
See the PDF handout entitled “Indexes: Example” for a good example of the relationship between indexes and (DB2) tables.
10
Metadata is “data about data”. Examples of metadata:
Metadata
For an e-mail message:
• The actual “data” is the main body/text of someone’s e-mail.
• It might be confidential, in which case it should be encrypted. Often, it isn’t. Think of e-mail as a postcard in a mail system. It can be read throughout the Internet by routers.
• The metadata for a piece of e-mail includes: • Length of the message
• To: address (receiver)
• From: address (sender, but it can be spoofed) • Date/Time
• Length of message
• Routing information
• Message ID (a unique identifier of your message on the Internet) • (maybe) the Subject line
11
Metadata (cont.)
Examples of metadata (cont.)
For a photo taken by your cell phone or digital camera, the “data” of interest is the image, but metadata usually comes with it. So, be careful when you post it somewhere, or e-mail it to someone. The metadata often includes:
• Serial number (unique identifier) of the camera
• Location: the GPS coordinates of where you took the photo, assuming your camera has GPS
• Type of camera
• Date and time
• Camera settings
• Size of the photo in MB
For a detective doing surveillance, maybe the actual conversation wasn’t recorded, but the detective knows: who, where, what time, how long, etc.
12
Metadata (cont.)
“As former NSA general counsel Stewart Baker said, ‘Metadata absolutely tells you everything about somebody’s life. If you have enough metadata you don’t really need content. In 2014, former NSA and CIA director Michael Hayden remarked, ‘We kill people based on metadata.’” [Bruce Schneier, Data and Goliath, Norton, 2015, p. 23]
Source: schneier.com
Connections and metadata: Your cell phone can be tracked. You may meet with other people who also have cell phones. Sometimes people turn their phones off, or remove the SIM card before a confidential meeting. Afterwards, people go off to meet other people.
Source: www.amazon.com
13
System Catalogs
Extremely useful!
Catalog tables contain metadata.
Lots of info about databases, tables, indexes, rows, keys, etc.
• e.g., # of records, # of unique keys, record layouts, column names, data types, field size, flags, permissions, creation times, creator IDs
Plus all kinds of statistics like authorization levels, buffer pool sizes, B+ tree stats (e.g., # of leaf pages, height of the tree, average distance between leaf pages), etc.
14
SYSIBM.SYSTABLES SYSIBM.SYSINDEXES SYSIBM.SYSKEYS
er/SSEPEK/pdf/db2z_11_sqlrefbook.pdf
In the LHS Table of Contents:
Find and expand the Appendix.
DB2 Catalog
There are about 140 catalog tables in Db2 Version 11. For example:
See IBM’s DB2 SQL Reference manual at: https://www.ibm.com/support/knowledgecent
Then, expand the DB2 Catalog Tables (found starting on page 2579 of the manual (or PDF page 2609)).
15
• This is part of the first page
of 8 pages’ worth of metadata from the SYSIBM. SYSTABLES catalog table.
DB2 Catalog: Example
16
DB2 catalog.
DB2 Catalog (cont.)
A statistics collection utility is run to update the metadata. e.g., DB2’s RUNSTATS utility updates most of the tables in the
RUNSTATS is run periodically on specific tables/indexes, by a DBA.
• The DBA decides when in conjunction with the development team.
• Why are these statistics not kept up-to-date all the time?
Important: Try the DB2 SQL exercises from your practice questions (old assignments and exams). Solutions are provided.
DB2 V9.1 had about 80-90 catalog tables. The DB2 SQL Reference is at: http://publib.boulder.ibm.com/epubs/pdf/dsnsqk18.pdf.
17
System Catalogs (cont.)
The catalog itself is stored as a set of relational tables. DBAs can access it via SQL.
Users are usually not allowed. Why not?
Utility products exist that download DBMS catalog data daily, populate tables with it, and present this metadata in a nice format. DBAs use it throughout the day to perform their work … assuming they’re OK with nearly real-time data.
What are the “system catalog” names according to the major DBMS vendors?
DB2:
Oracle:
SQL Server: MySQL:
DB2 Catalog or the System Catalog Data Dictionary
System Catalog
Information Schema
18
Record Formats: Fixed Length
F1 F2 F3 F4 L1 L2 L3 L4
Base address (B) Address = B+L1+L2
The information about field types is the same for all records in the table.
Schema information (column names, data types, lengths, order, etc.) is stored in the DBMS’s catalog.
Finding the i’th field does not require scanning the whole record. Why not?
19
Page Formats for Fixed Length Records
Slot 1 Slot 2
Slot 1 Slot 2
Slot N
Slot N Slot M
… Free Space
…
PACKED
number of records
UNPACKED, BITMAP
number of slots
N
1 . . . 0 1 1M M … 3 2 1
Record id =
20
Field Count
F1 F2 F3 F4
Record Formats: Variable Length
Two alternative formats (# fields is fixed): F1 F2 F3 F4
4$$$$ Fields Delimited by Special Symbols
Array of Field Offsets
The second case offers: direct access to i’th field, efficient storage of nulls (a special don’t know value), and small amount of directory overhead.
21
Page Formats for Variable Length Records
Rid = (i,N)
Page i Rid = (i,1)
Rid = (i,2)
20 16 24 N … 2 1
N
You can move records on a page without changing the rid. This is attractive for fixed length records, too.
SLOT DIRECTORY
of free space
Pointer # slots to start
22
Modifying Variable-Length Rows
Can be done in place if no variable-length field changes its length
What if the row increases in size due to an update?
Solutions (in preferred order):
• Try to update the row in place, if there is room.
• Relocate the row on the page, perhaps after compaction (defragmentation).
• Relocate the row to a “near” page (e.g., in DB2: within 16 pages of the current page).
• Relocate the row to a “far” page.
23
Planning for Updates, Insertions, and Deletions in DB2
For tables that contain fixed-length or variable-length rows:
At CREATE TABLESPACE time, DB2 allows a DBA to specify both the initial amount of free space on each page and how often to leave a completely blank page.
• e.g., PCTFREE 15
• e.g., FREEPAGE 10 (after every 10 pages, leave a blank page)
In the catalog table SYSIBM.SYSTABLEPART (see the next few
slides on System Catalogs), you’ll find: • PCTFREE
• FREEP AGE
• NEARINDREF
• FARINDREF
• NEARINDREF + FARINDREF = # of relocated rows
Over time, a REORG may be necessary for a table, and metadata can help you to decide when.
24
char( ) vs. varchar( ) Fields in DB2 Compare a char(20) field to a varchar(20) field in
DB2. Which takes up more space?
Suppose 80% of the time, we use 15 characters, and the other 20% of the time, we need 20 characters. Compare the space usage for 100,000 rows.
25
Summary
There are many page replacement algorithms that deal with moving pages to/from disk.
Contention and disk scheduling are additional factors to consider when determining disk service times.
Indexes support efficient retrieval of records based on the values in some fields.
Metadata is “data about data”.
Catalog relations store information about relations, indexes,
views, buffer pools, columns, backups (image copies), etc.
Such information is extremely useful to DBAs, and more importantly, to the DBMS!
26
Summary (cont.)
Fixed-length and variable-length records are supported in DBMSs.
There are different ways of managing the space on a data page. Rows can be relocated. There are good reasons to do so.
Free space on a page, and free pages, are useful in helping to manage the growth of tables, especially to support clustering.
Different kinds of database pages have various overhead bytes (e.g., identifiers, version number, sibling pointers, type of page (e.g., for indexes in DB2: header page, space map page, root page, non-leaf page, leaf page)).
To simplify our calculations, we don’t account for them in this course.
27