Database Mgt Syst
Database Mgt Syst EECS 484
Popular in Course
Popular in Engineering Computer Science
This 25 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 484 at University of Michigan taught by Kristina Lefevre in Fall. Since its upload, it has received 57 views. For similar materials see /class/231523/eecs-484-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Database Mgt Syst
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
5 Storage and Indexing Chapter 8 zmM m m mum M2mmerl Syslemx Kvixlen Lekquot Data on External Storage Review a File contains a multiset of records 0 Each record has a unique RID sufficient to locate record on disk Data read and written to disk by buffer manager 0 Main unit of transfer is a page File made up of many pages each page contains multiple records 0 Last class mum in m mum M2mmerl Syslemx Kvixlen Lekquot File Organization 0 Method of arranging file of records on disk 0 File typically shares a relation 0 Many alternatives with different strengths and weaknesses Hag random order les No particular order de ned for records Sorted Files Records sorted based on one or more attributs Indexes Organize records using trees or hashing zmna m m mum M2mmerl Syslemx Kvixlen Lekquot SLgyyagnggs on FHe Exanu e Employees Name Age Salary Operations 0 Scan Fetch all employees from disk 0 Equality Search age 21 0 Range Selection age gt 18 AND age lt 65 0 Insert a record 0 Delete a record How do we organize the le to accomplish these tasks ef ciently zmM m m mum Mmemm System Kvixlen Lekquot Indexes o A data structure that organizes data records on disk to optimize certain operations 0 Speed up selections on the search key field of the index denoted k Any subset ofthe elds ofa relation can be the search key for an index on the relation Search key is Lot the same as key minimal set of elds that uniquely identify a record in a relation zmM m m mum M2mmerl System Kvixlen Lekquot Indexes Index conmins a collection of data entries ans n y or search key k denomd M D e ltemative ways m store data k g a lt is an acmai record Wim Search key k Index File I 2 Data enuy kquot is k rid pair Where rid is reiers to a record We search key k Actual data records stored 3 Data ermy k We search ke in a different file is k ridslist pair where ridslist refers to list ofreoords y k choice ofaltemative for data eniries is orthogonal m me index39ng ted1nique used m locam data eniries W h a 939 en key value k Exarrplesiriclude 5 trees hashsbaed structures zmns m m mum Mmemm System Kvixlen Lekquot rgIndexes Can search key k be a pair of Values atlributs Can a le relation have more than one index Can a le relation have more than one index using dala enlry alternative 1 zmnq m m mum M2mmerl Sy emx Klelen law 7 39gIndexing Terminology Primary vs secondary Ifsmrch key contains primary key then called primary index Otherwise called secondary index 0 Clustered vs unclusterai If order of dala records is the same as or close to39 order of data entris then called clustered index Almrnative 1 implies clusmred but not vicerversa Alternauve 1 wclusteed index also called a clustered le A le can be Custered on at most one seard1 key Cost of rehie39ving data records lhrough 39ndex varies greedy based on whether the index is clusmred or not Zl i m m mum M2mmerl Sy emx Klelen lam x Clustered vs Unclustered Index Suppose data records in hmp le index with Alt 2 0 To build clustered index rst sort the Heap le Suppose you have an index on Age and you want to do a range selecu39on eg Age gt 18 Which index would you prefer Why zmna m m mum M2mmerl Sy emx Klelen lam B Tree Indexes quotan In noes r il lfmilalrillt l noes Leaf pages contain data entries and are chained prev amp next Nonleaf pages contain index entries and Index entry zlnM m m mum Mmemen stem men Leave in r l gExamQIe B Tree MN I I mil 0 Find 28 29 All gt 15 and lt 30 a Insertdelete Find data entry in leaf then change it N d to adjust parent sometim And change sometimes bubbles up lhe tree zlnna m m mum Msmemen stem men Lekquot n or more over ow pages Hadr39ng JncD39an h hr bucket in which record r belongs h looks at lhe search key elds of r hkey mod N key ckes contaln lr39Allernswe or is Used a daze lEEDrdS Ernatlve 2 AltV2y rm Aiterrlatlve 3 s ltkey i ld39ilstgt oars mm ary bucket pages over ow pages zmns m m mum Mmemen stem men Leave 12 Comparing File 1 Indexes Exam le Employees Name Age Salary Operations 0 Scan Fetch all employees from disk 0 Equality Search age 21 0 Range Selection age gt 18 AND age lt 65 0 Insert a record 0 Delete a record zmM m m mum M2mmerl System Kvixlen up g malysis of IO Cost For simplicity ignore CPU cost Important Factors for IO Cost 0 How many pages do we need to read 0 Are IOs sequential or nonsequential Textbook contains a slightly different analysis more detail but ignores distinction between sequential amp non sequential IO mum in m mum M2mmerl System Kvixlen up Heap File Scan Read all pages in file 0 sequential Equality Search Read all pages in file 0 sequential 0 worst case Range Selection Read all pages in file 0 sequential Insert Easy Delete Searching Easy zmna m m mum M2mmerl 5we Clustered File on Age 0 Scan Slightly more than heap file clue to page occupancy o Equality Search Traverse height of tree 0 nonsequential 0 Range Selection 0 Traverse height oftree non sequential 0 Scan Iaf records sequential 0 Insert Traverse height of tree nonsequential write 0 Delete Traverse height of tree nonsequential write zmM m m mum M2mmerl Syslemx Kvixlen Lekquot ls eap File 39gw Unclustered Tree Index on Age 0 Scan Same as heap file 0 Equality Search Traverse height of tree 0 Non sequential 0 Can be more costly if many records satisfy equality 0 Range Selection 0 Traverse height oftree non sequential u Scan Iaf records nansequential 0 Can be very expensive if many records satisfy range exprssionl 0 Insert Update index update heap file 0 Delete Update index update heap file mum in m mum M2mmerl Syslemx Kvixlen Lekquot n Heap File w Unclustered Hash Index on Age Scan Same as heap file Equality Search Nearly constant Range Selection Hash index no use 0 Scan heap file Insert Update index update heap file Delete Update index update heap file zmna m m mum M2mmerl Syslemx Kvixlen Lekquot xx EH Concurrency Control Chapter 17 mung an m mum Mzmgemenl Syxlemx Kr m LeFewe Agenda Last time transactions schedules lock basics How can we use locking to guarantee schedules with desirable properties Serializable recoverable avoid cascading aborts ACA Lock Manager Implementation Deadlock Definition detection and prevention mung an m mum Mzmgemenl Syxlemx Kr m LeFewe TwoPhase Locking ZPL 2PL IfT wants to read modify an object rst obtains a shared exclusive lock IfT releases any lock it can aoquire no new locks Gurantees serializability growing phase Strict 2PL Hold a locks until end of Xact Guarantees serializability and ACA too Note ACA schedules are T always recoverable 39me lock point locks mung an m mum Mzmgemenl Syxlemx Kr m LeFewe Exam Ie Two accounts A and B Two transactions T1 and T2 T1 Transfer 100 from A to B T2 Add 10 interest to A and B mung an m mum Mzmgemeni Syxiemxy Ky my LeFewe Example Strict 2PL T1 acquires S lock on A T1 acquires X lock on A T1 acquires S lock on B T1 acquires X lockon B T1 releases all locks T2 acquires S lock on A mung an m mum Mzmgemeni Syxiemxy Ky my LeFewe Precedence Graph 1 Precedence or serializability graph for schedule 5 A node for each committed transaction in S An arc from 1quot to TJ ifsome action in 1quot precedes and con icts with some action in TJ 06 G mung an m mum Mzmgemeni Syxiemxy Ky my LeFewe Terminology Two schedules are conflict equivalent if involve the same transactions order each pair of conflicting transactions in the same way A schedule is conflict serializable if it is conflict equivalent to a serial schedule All conflict serializable schedules are also serializable mung an m mum Mzmgemenl Syxlemx Kv Kim LeFewe 7 Conflict Serializability amp Graphs Theorem A schedule is conflict serializable if and only if its precedence graph is acyclic Equivalent serial schedule is given by any topological sort over graph T3 mung an m mum Mzmgemenl Syxlemx Kv Kim LeFewe x 2M amp Serializability ZPL guarantees acyclic precedence graph Guarantees a conflict serializable schedule Intuitively equivalent serial schedule given by order in which transactions enter shrinking phase Why Strict ZPL Guarantees ACA read only committed values How Hold X locks until end of transaction no W or WR con icts mung an m mum Mzmgemenl Syxlemxy Ky my LeFerr Exercise Is this schedule allowed by ZPL Strict ZPL Is it serializable If so what is the corresponding serial schedule Is the schedule recoverable ACA mung an m mum Mzmgemenl Syxlemxy Ky my LeFerve Lock Manager Implementation Main data structure Lock Table Hash table with Object ID OID as key For each object List of transactions holding the lock Lock Mode Shared or Exclusive Pointer to queue of waiting requests On lock release OID XID Update list of transactions Grant request to rst transaction ofqueue Optionally prioritize upgrads mung an m mum Mzmgemenl Syxlemxy Ky my LeFerve What about deadlocks T1 gets S then X lock on A T2 gets S then X lock on B T1 waits for lock on B T2 waits for lock on A Waitsforquot Graph an m mum Mzmgemenl Syxlemx Kr m LeFewe mung eadlock Detection Observation Deadlocks are rare Often involve only a few transactions Detect rather than prevent Lock Mgr maintains waitsfor graph Periodically check graph for cycles Abort some gtltact to break the cycle Simpler hack timeouts Abort if no progress made for a while an m mum Mzmgemenl Syxlemx Kr m LeFewe mung g Deadlock Prevention Assign prioritis to transactions Use timestamp to assign priorities Ti requests a lock held by Tj in a con icting mode WaitDie If Ti has higher priority it waits else Ti aborts WoundWait If Ti has higher priority abort Tj else Ti waits After abort restart with original timestamp Guaranmes the transaction eventually runs an m mum Mzmgemenl Syxlemx Kr m LeFewe mung HashBased Indexes Chapter 11 2mm m m mum M2mmerl Swlemx Kvixlen Lekquot rglndex De ign Space Organization Structure for k Hush based r Equality Search Siuiic hashing gtData Enm k Contents Extend ble hashing 1 Aciqu Duiu record Linear hush r9 index i Tree based 2 ltkridgt kunge equality search acmai records in a diffzrzm mg 3 ltllt list of r39ds mm are 48 mm mew Swim mm Mm Static Hashing o primaw bucket pages xed allocated sequentially never deallocated over ow pags if needed 0 llkey mod N bucket to which data min with key belongs N of buckets 15F Himarybuckelpages over ow pages f hO mm m m mum M2mmerl Swlemx Kvixlen Lekquot Static Hashing Contd o uckets contain data entn s 0 Number of buckets N is M ahmd oftime 0 Static structure can be problematic Consida many insertions Long over ow d1ains can develop and degrade performmce Might consider periodically doubling N and rehashing le Entire le has to be read and written Index unavaild e while rehad1ing Exiendtble problem and Linear Hashing Dynamic techniques to x this 2mm in m mom Mmemm System Kvixlen Lekquot gExtendible Hashing 0 Main Idea Use a directory of pointers to buckets o On overflow double the directory not number of buckets 0 Why does this help 0 Directory much smaller than le 0 Only one page of data entries is split at a time o No over ow pages 2mm in m mom M2mmerl System Kvixlen Lekquot l gt Example 12232 L In 0 Directory an array 0 Search for k in Apply hash function hk 0 0 Take last global dept7 bits of k DIRECTORY 0 Insert DATA PAGES 0 Ifbucket has space insert done If bucket if full split it redistribute o Ifnecessaiy double the directory 2mm in m mom M2mmerl System Kvixlen Lekquot L gt LDCALDEPTH Example comm a gtilt Insert 13 a E 0 Suppose quotm1amp1quot a 1n h131101 n E DIRECTORV 15 139 1939 BMEKIKD DATAPABES iInsert 20 LOCAL DEPTH M L DEPTH BZ39IB39 BuckM Notice mat salitting a bucket only such a 1oo auckuc 39 4 LI 4 101 by copying it ave 110 and xing pointer to 111 Emma saint Image page DRECTORY 21 1st 1mg DATA PMES quot393 k mm m 4 mm Mzmymen Swlemx mun MW 3 90mmentsgn Extendible Hashing How many disk accesses for equality search One if directory fits in memory else two Directory grows in spurts and if the distribution of hash values is skewed directory can grow large Do we ever need overflow pages 0 Multiple entries with same hash value cause problems Delete Reverse of inserts see textbook mm m m mum M2mmerl Syslemx Kvixlen Leave a gExercise Suppose our DBMS implements extendible hash indexes and B trees both using data entry Alternative 2 We know that hash indexes are no good for range queries Can you think of a case database a one or more query where the hash index is better 0 Describe the database and queries as precisely as pOSSI e 0 Calculate the IO cost for each index 2mm an m mum imam System Klelen Leave in Linear Hashing 0 Another dynamic hashing scheme 0 Eliminates long over ow chains without using a directory 0 Main idea Use a family of hash functions IID ll IIZ 7 h doubles the rmge of n similar to direcmry doubling Hash family typically obtained by dmosing hash function h and initial number of budlte Def39ne hyaue hyaluemod2N IfN is a power of 2 apply hash function h and look at last dbi5 an nurrber orble needed to represent N d mm m m mum imam System Klelen Lekquot n Linear Hashing o Splitting proceeds in rounds 0 During round level only hm and lump are in use 0 Variables Level Initialized to 0 0 Next Pointer to the bucket being split At the beginning of round Level the buckets in the file N 2 Level N is initial number of bucke1s mm m m mum imam System Klelen Leave 12 rgBuck ats During Round i 397 lUse hm in this range Range of h Next 3 crated by splitting other buckels 0 in this round 2mm in m memmem swimmlemeu e 7 Linear Hashing Contd 0 Search Find bucket with key value k by applying IILM Iflhis leads to an unrwlit bucket all set omerwlse apply him 2mm in m mum M2mmerl Syslemx Klelen lam Linear Hashing Contd 0 Insert Find bucket by applying hLeM hyeveH o Ifbucket being inserled inn is full 0 Add over ow page and insert data ently Maybe Split Nextbucket and increment Next 0 Can choose any criterion to trigger split 0 eg split on a over ow as in example 0 eg space utilization on the page gt 90 0 Since buckets are split roundrobin long overflow chains don39t develop 0 Deletes see textbook mm m m mum Mmemm Syslemx Klelen lam gLinear Hashing Example Level D N 4 H O Next0 00 44 35 01 25 10 11 Primaty bucket Pages in the Hash File This isnat acrualiy stored as m thzbm M2mmerl System Kvixlen Lekquot 2mm gLinear Hashing Insert 43 Level 0 N 4 What happens ifwe lIL HO ow insert an entty into bucket 01 000 00 I Next1 001 01 e 010 10 011 11 100 not actually stared Primary bucket Pages in the Hash File mm m m mummwm SwemmelenLekue n Su mmary o Discussed 3 kinds of hashbased indexes 0 Static Hashing can lead to long overflow chains 0 Extendible Hashing o Directoty to keep track of buckets doubles periodically 0 Always splits the right bucket 0 Linear Hashing Split buckets roundrobin and use over ow pags o Duplicates handled easily 0 Space utilization could be lower than EH m m mum M2mmerl System Kvixlen Lekquot 2mm g Logging and Recovery Chapter 167 18 was an m mum Mzmgemenl Syxlemx Kr m LeFewe Motivation 4 Atomicity Transactions may abort need to rollback actions Durability of Committed gtltacts T1 39 C System crashs lose T2 E u I oontents 0 RAM T3 3 13 I Media failurs lose some T4 B I stable storage 39 I Desired Behavior after T5 5 system restarts T1 amp392 should be durable T4 amp T5 should be aborted was an m mum Mzmgemenl Syxlemx Kr m LeFewe Buffer Pool Stealing Forcing Can changes made to object O by xact T be written to disk before T commits If yes called a steal approach When xact T commits do we need to assume all changes immediately forced to disk If yes called a farce approach oS a Buffer Pool Stealing and Forcing o Steal es orce Paar IesJanse lime but durable No Force Problem Crash before a page is flushed to disk V Na Steal Steal p in t Problem Page being stolen and ushed was no modified by an uncommitted Xact T Key Problem How to provide atomicity and durability in a steal no force environment was an no more Mzmgemenl Syxlemx Ki leri LeFewe M Logging Record information for every change in an appendonly log Stored in stable storage to survive system crash Each log record has a log sequence number LSN Log record oontains ltprevLSN XID type and additional conhol 39nfo Note which we ll see soon was an no more Mzmgemenl Syxlemx Ki leri LeFewe Writ Ahead Logging WAL The Wr 39 39 2 Must write all log reoords fora Xact before 1 guarantees Atomicity 2 guarantees Durability Exactly how is logging and recovery done We39ll study the ARIES algorithn39s breakthrough in recovery algorithms repeating history paradigm was an no more Mzmgemenl Syxlemx Ki leri LeFewe gym amp the Log LSNS pageLSNS flushedLSN l Log Sequence Number LSN Lugrmms Unique and always increasing Ms D Sh l Each data page contains a pageLSN The LSN of the most recent log record that updated the page I System keeps track of flushedLSN The max LSN ushed so far Er Loam l WAL Before a page is written iquot RAM pageLSN s ushedLSN Q oS i EEG 0x0 Daiztme Mzmgemeni Syxiem Kr ien LeFerre 7 g Log Records Possible log record types LogRecord fields update prevLSN I Commit XID Abort tYPE l End end of commit or abort page I Compensation Log Rec CLRs F39de length For UNDO actions When records D SEl Contains undoNextLSN only bafore39mage Reverse chain of updam logs alter image Contains beforeimage u was an m mum Mzmgemenl Syxlemx Kr len LeFewe x Other LogRelated State I Transaction TableEOne entry per active Xact Contains XID Transaction identi er status runningoommitedaborted lastiSN LSN of the most recent log rec for this Xact I Dirty Page TableEOne entry per dirty page in BP Contains recLSN LSN of the log record that rst caused the page to be dirty smrt39ng po39nt for REDO was an m mum Mzmgemenl Syxlemx Kr len LeFewe a Checkpointing Checkpoint Logical Snapshot of the database Minimize recovery time Write to log beginicheckpoint record Indicates when chkpt began enchheckpoint record Record Xact table and DPT Tables accuram only as orme time of the beginicheckpoint record No attempt to force dirty pages to disk This is a fuzzy checkpoint Store LSN of beginicheckpoint record in a safe place masterreoord was an m Dalzbaxe Mzmgemenl Syxlemx Kr len LeFewe m Normal Execution of a Xact Series of reads amp writes followed by commit or a r Updates are in placequot ie data on disk is overwritten We will assume that write is atomic on disk In practice additional demils m deal with nonsammic writes Strict 2PL STEAL NOFORCE buffer management with Write Ahead Logging was an m Dalzbaxe Mzmgemenl Syxlemx Kr len LeFewe n The Big Picture What s Stored Where a Xact Table Data pages laleSN eacl l with a lengtn PageLSN Dilty Page Table recLSN beforer m age master record a el39slmage flushedLSN was an m Dalzbaxe Mzmgemenl Syxlemx Kr len LeFewe lZ Crash Recovery Big Picture oldesnog rec gt Start from a checkpoint found f X me via master record gt Three phases 7 Analysis Sl ce checkpointfind we Ear Xacts that must be aborted sis losers dirty pages at time ofcrash onservative estimate mum e REDO allactions repeat history CRASH UNDO effects of losers A R U oS a an m mum Mzmgemenl Syxlemx Kr len LeFewe gecovery The Analysis Phase Compute Set of dirty pags conservative Uncommitted transactions at the crash point Scan log forward from checkpoint End record Remove Xact from Xact table Other records Add Xact to Xact table set astLSNLSN Commit record change Xact status to commit Update or CLR reoord If P not in Dirty Page Table Add P to DPT set its recLSNLSN oS a an m mum Mzmgemenl Syxlemx Kr len LeFewe ecovery The Analysis Phase Transaction Table pdate T3 Writes Pl BOTUpdate T2 Writes P5 X CRASH RESTAPT oS a an m mum Mzmgemenl Syxlemx Kr len LeFewe Crash Recovery Big Picture oldestlog rec gt Start from a checkpoint found 3 3 9 via master record gt Three phases 7 Analysis since checkpointfind Xacts that must be aborted ers dirty pages at time ofcrash conservative eStimate e REDO allactioris repeat history CRASH A e UNDO effects or losers A R U oSni EEG om mtzbaxe Mzmgemenl Synemx Kr len LeFewe ls Recovery The REDO Phase epeat History to reconstruct state at crash Reapply all updats even ofaborted Xacts redo CLRs Bring the database to the same state as crash Scan forward from log record containing smallest recLSN in DPT Foreach update log record or CLR REDO the action unless we can verify that the change has already been written to disk A ected page is not in the Dirty Page Table or A ected page is in DPT but LSN lt recLSN or update was propagated m d39sk LSN s pageLSN in DB requires fetd1ing the page was an m mum Mzmgemenl Syxlemx Kr at LeFewe n To REDO An Action Reapply logged action Set pageLSN to LSN No additional logging Use of CLRs ensures that no change is ever carried out twice on the disk copy of an object For every DO there is one and only one UNDO At the end of REDO Write END log rets forall oommited Xacts Remove committed Xacis from the Xact table was an m mum Mzmgemenl Syxlemx Kr at LeFewe xx ecovery The REDO Phase beglnicheckpolnt 05 endicheckpolnt oi update Tl Writes P5 202 updale T2 Writes P 305Tl abort 7 40 CLR Undo Tl LSN lo End J 50update T3 Writes Pl EEOE39update T2 Writes P5 XCRASH RESTART was an m mum Mzmgemenl Syxlemxy Ky my LeFewe Crash Recovery Big Picture Oldestlog rec gt Start from a checkpoint found f X me via master record Smallest recLSN in d39 gt Three p 7 Analysis Si ce checkpolnl flnd IIquotv gamble me E Xacts that must be aborted Analysis losers E dirty pages at time ofcrash E conservative estimate Last chkpt 7 REDO all aCllOi is A R U repeat history CRASH r UNDO effects of losers was an m mum Mzmgemenl Syxlemxy Ky my LeFewe 5 Recovery The UNDO Phase ToUndo lastLSNs of all loser Xact Repeat Abort special Choose largest LSN among ToUndo case DfUNDO If this LSN is a CLR and undonextLSNNULL Write an End record for this Xact If this LSN is a CLR and undonextLSN NULL Add undonextLSN to ToUndo Else this LSN is an update Undo the update write a CLR add pneVLSN to ToUnclo Until ToUndo is empty was an m mum Mzmgemenl Syxlemxy Ky my LeFewe LOG undoNeXtLSN 70 CLR Undo TZ LSN 60 20 80 CLR Undo T3 LSN 50 null n 90 CLR UHdOTZ LSNZU null T2 End 50 update T3 Writes P1 60 i update T2 Writes P57 XCRASH RESTART was an m mom Mzmgemeni Syxiemxy Ky ien LeFewe 22 gxamgle Crash During Restart LSN LOG beginicheckpoint endicheckpoint REDO 10 to 85 UNDO39 x CRASH RESTART L 70 E CLR Undo T2 LSN so sassyew Undo T3 LSN 50 T3 end 5 CRASH RESTART 90 L CLR Undo T2 LSN 20 T2 end Undo70 CLR Undo 20 Take a ckpt was an m mom Mzmgemeni Syxiemxy Ky ien LeFewe 23 dditional Crash Issues How do you limit the amount of work in REDO Flush asynchronoust in the background Watch hot spots How do you limit the amount of work in UNDO Avoid longrunning Xacts was an m mom Mzmgemeni Syxiemxy Ky ien LeFewe 2o
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'