Storage and Indexes Introduction to Databases Computer Science 557AnnouncementsHard DisksOur First EquationAnatomy of a Hard DiskHard Drive GlossaryTypical Disk ParametersAccessing a Disk BlockComing soon: Solid State “Disks”?Why not store DB in main memory?Managing the Hard DiskOperations Supported by DSMSlide 13Example: Managing the Hard DiskSlide 15Slide 16Slide 17Slide 18Buffer ManagementBuffer Manager OperationsBuffer Manager ExampleSlide 22Slide 23Storage and IndexesIntroduction to DatabasesComputer Science 557Instructor: Joe BockhorstUniversity of Wisconsin - MilwaukeeAnnouncements•Any problems logging in to course accounts?•Use grid3, grid5 or weise for course work–Send bugs on weise to [email protected] •Reading Assignment: Chapter 14 in the textbook•Program 1 assigned today, due next FridayHard Disks•DBMS typically store information on “hard” disks•I/O operations (“Read” and “Write”) are costly –Should be planned carefully•A block is amount of data transferred in one operation (example block size ~ 1024 bytes)DiskMain Memory(RAM)ReadWriteOur First Equationtrs I/O_Costseek timerotational delaytransfer timeAnatomy of a Hard DiskHard Drive Glossary•Disks are divided into concentric circular tracks on each disk surface.–Track capacities vary typically from ~ 4 to 50 Kbytes•The division of a track into sectors is hard-coded on the disk surface and cannot be changed•A block is an integer number of sectors–The block size B is fixed for each system.•Typical block sizes range from B=512 bytes to B=4096 bytes.–Whole blocks are transferred between disk and main memoryTypical Disk Parameters(Courtesy of Seagate Technology)Accessing a Disk Block•to Read or Write block give block addr to disk controller –Hardware block address – cylinder #, surface #, block #–Logical block addressing allows higher levels to refer to hardware block address using a block_id•Seek time – move head to correct cylinder (~10ms)•Rotation time – rotate start of block under head–@ 15000 rpm, average rotation time is 4ms•Transfer time – transfer entire block•Accessing consecutive blocks only need to pay the seek and rotation time once•Compare to typical main memory access times which are measured in micro (10-6) or nano (10-9) secondsComing soon: Solid State “Disks”?+ Random access devices eliminate seek times+ faster startup-$$$$ much more expensive than hard disks -($8 / GB vs $0.25 / GB)-Capacities are smallerWe will assume hard disk storage inthis courseWhy not store DB in main memory?•$$$$–cost of RAM is > 100 X hard drive cost •main memory is volatile•32 bit addressingManaging the Hard DiskQuery OptimizationRelational OperatorsFiles and Access MethodsBuffer ManagementDisk Space ManagementThe DSM provides an abstraction of the block as a unit of dataDSM interface includes commands to read and write block commandsI/O requestsOperations Supported by DSM•allocate_blocks(num_blocks)–Add blocks to DB•deallocate block(blockID)–Remove block from DB•write_block(blockID, blockPtr)–Write block to disk•read_block(blockID, blockPtr)–Read block from diskManaging the Hard DiskDisk Space Manager1yes2 3block IDyes yesallocated?N-1 Nno no4 5no no792 793 794 * ** *hardware addr6no7no* *Example: Managing the Hard Diskallocate_blocks(3)write_block(5,data)read_block(5)deallocate block(2)Disk Space Manager1yes2 3block IDyes yesallocated?N-1 Nno no4 5no no792 793 794 * ** *hardware addr6no7no* *allocate_blocks(3)write_block(5,data)read_block(5)deallocate block(2)Example: Managing the Hard DiskDisk Space Manager1yes2 3block IDyes yesallocated?N-1 Nno no4 5yes yes792 793 794 * *902 903hardware addr6yes7no904 *//allocate three consecutive blocksallocate_blocks(3)write_block(5,data)read_block(5)deallocate block(2)Example: Managing the Hard DiskDisk Space Manager1yes2 3block IDyes yesallocated?N-1 Nno no4 5yes yes792 793 794 * *902 903hardware addr6yes7no904 *//write blockID 5 to diskwrite_block(903,data)allocate_blocks(3)write_block(5,data)read_block(5)deallocate block(2)Example: Managing the Hard DiskDisk Space Manager1yes2 3block IDyes yesallocated?N-1 Nno no4 5yes yes792 793 794 * *902 903hardware addr6yes7no904 *// read blockID 5 to bufferread_block(903)allocate_blocks(3)write_block(5,data)read_block(5)deallocate block(2)Example: Managing the Hard DiskDisk Space Manager1yes2 3block IDno yesallocated?N-1 Nno no4 5yes yes792 * 794 * *902 903hardware addr6yes7no904 *// read blockID 5 to bufferBuffer Management•Responsible for managing region of main memory called the buffer pool•MM pages are called frames (slots that can hold one block)•Higher levels of the DBMS need not worry if the page is in memory or not... Just ask for it.Query OptimizationRelational OperatorsFiles and Access MethodsDisk Space ManagementBuffer ManagementBuffer Manager Operations•add_blocks_to_DB(num_blocks)–add new blocks to DB•delete_block_from_DB(block_id)–delete block from the DB•pin_block(block_id)–bring block from disk to buffer pool if not in BP–increment pin count for block •unpin_block(block_id)–decrement pin count for block•mark_dirty(block_id)•Buffer Manager maintains for each frame–pin count–dirty bitBuffer Manager Examplebuffer poolwith M frames1 2 3 M-1 M- - - - -0 0 0 0 0no no no no noblock IDpin countdirtyinitial state ofbuffer manager1 2 3 N-1 NBuffer Manager Examplebuffer poolwith M frames1 2 3 M-1 M76 22 - - -2 1 0 0 0no no no no noblock IDpin countdirtyinitial state ofbuffer managerdraw on whiteboard1 2 3 N-1 NBuffer Manager Exampleadd_blocks_to_DB(3)pin_block(76)pin_block(13)mark_dirty(13)pin_block(76)unpin_block(13)// now assume all frames are filled and blk 22 // is not in the buffer poolpin_block(22)// BufMgr flushes blk w/ pin count =