4/19/10&1&Storage&and&Indexing&CISC437/637,&Lecture&#11&Ben&Cartere=e&1&Copyright&©&Ben&Cartere=e&Physical&Layer&• So&far&we&have&focused&on&highHlevel&database&layers&– Conceptual:&&EHR&model,&EHR&diagrams&– Logical:&&relaNonal&model,&SQL&• UlNmately&the&logical&layer&needs&to&be&implemented&in&data&structures&and&stored&in&files&on&disk&– The!physical!layer!• Understanding&how&the&files&are&organized&is&essenNal&to&using&a&DBMS&effecNvely&Copyright&©&Ben&Cartere=e& 3&4/19/10&2&Physical&Storage&Media&• The&actual&physical&objects&that&data&is&stored&in&• It&is&convenient&to&classify&media&according&to&characterisNcs:&– Speed&of&access&– Cost&per&unit&of&storage&– Reliability&• Loss&of&data&on&power&outage&or&crash&• Failure&of&device&– VolaNlity&• VolaNle&storage&loses&contents&when&shut&down&• NonHvolaNle&persists&during&shut&down&period&Copyright&©&Ben&Cartere=e& 4&Physical&Storage&Media&• Cache&–&very&fast;&very&expensive;&volaNle;&managed&by&hardware/OS&• Main!memory!–&fast;&comparaNvely&expensive;&volaNle&– Usually&too&expensive&to&allow&storage&of&enNre&DB&• Flash!memory&–&fast&read,&slower&write;&roughly&as&costly&as&main&memory;&nonHvolaNle!Copyright&©&Ben&Cartere=e& 5&4/19/10&3&Physical&Storage&Media&• Magne3c!disk!–&slow;&cheap;&nonHvolaNle&– This&is&where&the&full&DB&would&be&stored&– DBMS&must&move&data&from&disk&to&memory&for&access,&and&from&memory&to&disk&for&storage&• Doing&this&efficiently&is&the&driving&force&behind&storage&decisions&• Op3cal!storage&–&slow;&cheap;&nonHvolaNle&– CDs,&DVDs&• Tape&–&very&slow;&very&cheap;&nonHvolaNle&– Only&allows&sequen3al!access:&&data&accessed&in&storage&order&from&beginning&• Compare&to&direct!access&offered&by&magneNc&disks&– Used&for&backups&and&archives&Copyright&©&Ben&Cartere=e& 6&Physical&Storage&Hierarchy&Copyright&©&Ben&Cartere=e& 7&primary&secondary&(onHline)&terNary&(offHline)&4/19/10&4&MagneNc&Disk&Mechanism&Copyright&©&Ben&Cartere=e& 8&MagneNc&Disk&Details&• Read<write!head&reads&and&writes&magneNcallyHencoded&informaNon&from&conNnuouslyHspinning&pla>ers!• A&pla=er&is&divided&into&circular&tracks&– 50,000&–&100,000&tracks&per&pla=er&• Tracks&are&divided&into&sectors&– The&smallest&unit&of&informaNon&that&can&be&stored&(typically&512&bytes)&– 500&sectors/track&on&inner&tracks;&1000&on&outer&• When&a&read/write&operaNon&executes,&head&goes&to&correct&track&and&reads/writes&data&from/to&sectors&as&they&pass&underneath&&Copyright&©&Ben&Cartere=e& 9&4/19/10&5&Measuring&Disk&Performance&• Access!3me&–&Nme&from&issue&of&read/write&request&to&when&data&transfer&begins&– Seek!3me&–&Nme&to&posiNon&the&read/write&head&over&the&correct&track&• Worst&case&=&Nme&to&move&from&innermost&track&to&outermost&• Average&case&=&½&worst&case&• 4&–&10&ms&on&typical&disks&– Rota3onal!latency&–&Nme&for&sector&being&accessed&to&appear&under&head&• Worst&case&=&full&rotaNon&• Average&case&=&½&worst&case&• 4&–&11&ms&on&typical&disks&Copyright&©&Ben&Cartere=e& 10&Measuring&Disk&Performance&• Data<transfer!rate&–&the&rate&at&which&data&can&be&retrieved&from&o r&stored&to&disk&– 25&–&100&MB&per&second&max;&lower&for&inner&tracks&• Mean!3me!to!failure&–&average&Nme&the&disk&is&expected&to&run&conNnuously&with&no&fail ure&– 3&–&5&years&Copyright&©&Ben&Cartere=e& 11&4/19/10&6&Disk&Blocks&and&Pages&• A&page&or&block&is&a&logical&unit&consisNng&of&a&fixed&number&of&conNguous&sectors&– Data&is&transferred&from&disk&to&main&memory&in&pages&– Usually&4KB&to&8KB&pages&• Smaller&&more&transfers&from&disk&• Larger&&more&wasted&space&from&parNallyHused&blocks&• Access&pa=erns:&– Sequen3al&–&successive&requests&fo r&successive&pages;&requires&only&one&disk&seek&– Random&–&successive&requests&for&pages&at&arbitrary&posiNons;&each&request&requires&a&seek!Copyright&©&Ben&Cartere=e& 12&OpNmizing&Page&Access&• Keeping&disk&access&fast&is&imperaNve&for&large&databases&• At&the&hardware/OS&level:&– Buffering&of&pages&stored&temporarily&in&memory&while&not&used&(also&done&by&DBMS)!– Read<ahead&of&pages&in&case&they&might&be&used&– Scheduling&of&page&access&to&minimize&disk&arm&movement&– File!organiza3on&to&place&pages&on&disk&that&corresponds&to&expected&access&pa=ern&– Nonvola3le!write!buffers&for&temporary&storage&– Log!disk&devoted&to&recording&page&updates!Copyright&©&Ben&Cartere=e& 13&4/19/10&7&File&OrganizaNon&• A&database&is&stored&on& dis k&in&a&collecNon&of&files&that&span&one&or&more&pages&• Each&file&contains&a&sequence&of&records&• Pages&may&contain&one&or&more&records&• The&DBMS&can&insert&and&update&records&in&files,&and&scan&through&records&in&a&file&one&at&a&Nme&– Note&that&we&have&not&specified&that&all&records&are&from&the&same&relaNon&• How&these&files&are&structured&and&stored&on&disk&can&have&a&big&impact&on&data&access&speed&Copyright&©&Ben&Cartere=e& 14&OrganizaNon&of&Records&in&Files&• Simplest&organizaNon&scheme&is&a&heap!file&– Records&are&stored&in&random&order&across&pages&• Indexed&organizaNons&are&the&alternaNve&– The&idea&of&an&index&is&to&efficiently&locate&all&records&matching&a&parNcular&search!key&• Search&keys&correspond&to&[sets&of]&fields/a=ributes/columns&• They&do&not&need&to&be&keys&in&the&relaNonal&sense&Copyright&©&Ben&Cartere=e& 15&4/19/10&8&Indexes&• An&index!file&consists&of&a&series&of&data!entries!with&one&of&three&forms:&– k*:&a&record&or&search&key&value&– Pairs&(k,&r):&&a&search&key&value&with&a&pointer&to&a&record&– Pairs&(k,&{r1,&…,&rn}):&&a&search&key&value&with&a&list&of&pointers&• Three&basic&kinds&of&indexes:&– Ordered!indexes&in&which&search&keys&are&stored&in&sorted&order&– Hash!indexes&in&which&search&keys&are&distributed&uniformly&in&“buckets”&– Tree!indexes!in&which&search&keys&are&organized&in&a&tree&structure!Copyright&©&Ben&Cartere=e& 16&Ordered&Indexes&• A&clustered!index&is&an&ordered&index&to&a&file&of&records&in&the&same&order&•