Announcements• Program 1 on web site: due next Friday• Today: buffer replacement, record and block formats• Next Time: file organizations, start Chapter 14 (indexes)• Office hours change: – Old office hours Mon 10-11, Thur 1:30-2:30– New office hours Mon 10-11, Thur 2-3• Opportunity to replace lowest HW (not program)– Create PPT slides of worked examplesOpen questions from last time• When to write dirty pages?– Dirty pages may be kept in buffer pool without being written to disk immediately but, – At conclusion of transaction the DBMS log (akajournal) is forced to disk (see Chapter 17)• How much does OS need to be concerned with hard drive architecture?– I am not certain but I would think not much• Why does pin count for a frame exceed 1?– See emailBuffer Replacement Policy• When new block is brought into full buffer pool a frame with pin_cnt = 0 is chosen for replacement• Possible policies– Least Recently Used – Most Recently Used– First In First Out (FIFO)• LRU is most common, but can be poor for some access patterns (sequential flooding)• If no blocks have pin_count = 0, return an errorBuffer Replacement ExampleSequential FloodingSequential Flooding Example• BufMgr has N frames• DB File has N+1 blocks• If file is repeatedly scanned, I/O is needed on almost every page accessRecords and FilesRecords and FilesQuery OptimizationRelational OperatorsDisk Space ManagementBuffer ManagementFiles and Access MethodsSo far we have reading and writing whole blocks.Now we will discuss how an RDBMS organizes data within a blockRecords• Higher levels see data as a collection of records:struct employee{char name[30];char ssn[9];int salary;int job_code;char deparment[20];};example of arecord description in C++File•A file is a collection of records that (in general) spans multiple blocksrecord 1 record 2 record 3record 4 record 5 record 6record N-1 record Nblock 1 of fileblock 2 of fileblock M of filefile with M blocksWe are primarily concerned with how these organizations impact the performance of various file operationsSome Issues With Records and Files• Record format– fixed length Vs variable length• Record organization within a block– Packed, unpacked• Record organization within file– ordered Vs unorderedSome Common Operations on Files• Scan– fetch all records in the file• Search with Equality Selection– find student with studentId = 85• Search with Range Selection– find all student with GPA between 3.0 and 3.3• Insert– add a record to the file• Delete– Remove a record given its RIDRecord FormatFixed length record formatVariable length record formatsReasons for variable length records• Variable length fields (most common)• Repeating groups• Optional fields• Mixed record typesBlock Formats• Figure 3.5 for Packed and Unpacked• Figure 3.6 Directory of SlotsFile Organizations (overview)• Heap Files – Unordered random sequence of records• Ordered Files– Records are ordered by some field (or combination of fields)• Hashed Files– A hash function used to quickly find records on some key.Record FormatSpanned record organization is a more efficient use of space, but accessing a record may require multiple I/O operation (may be unavoidable for large records).Allocating files on disk• contiguous allocation• linked allocation• hybrid of contiguous and
View Full Document
Unlocking...