Class Note for EECS 647 with Professor Huan at KU
Class Note for EECS 647 with Professor Huan at KU
Popular in Course
Popular in Department
This 19 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 23 views.
Reviews for Class Note for EECS 647 with Professor Huan at KU
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
EECS 647 Introduction Database Systems Instructor Luke Huan pring 2009 Query optimization 0 One logical plan best physical plan 0 Questions 0 How to enumerate possible plans a How to estimate costs a How to pick the best one o Often the goal is not getting the optimum plan but instead avoiding the horrible ones Any of these will do I O O O i 1 second 1 minute 1 hour 4152009 Luke Huan Univ of Kansas Cost estimation Physical plan example PROJEICT title MERGEJOIN CID SORCID SCAN Course Input to SORTCID MERGEJOINSD FILTER name Bart SORQSID SCAN Enroll I SCAN Student 0 We have cost estimatIen39fereaeheperator quot 0 Example SORTCID takes log2Binput gtlt Binput 0 But What is Bz nput c We need size of intermediate results 4152009 Luke Huan Univ of Kansas Review DBMS Architecture UserWeb FormsApplicationsDBA query Query Parser Query Rewriter Files amp Access Methods Buffer Manager Storage Manager g transaction Lock Tables Main Memory 4152009 Luke Huan Univ of Kansas 4 1 I 43 7 r Transaction Data Definitio Query Compiler Transaction Manager Schema Manager Execution En ine V ging Recovery Concurrency Control V V Buffer Manager g E LOCK TABLE Storage Manager BUFFERS BUFFER POOL DBMS a set of cooperating software modules Luke Huan Univ of Kansas Transactions 0 A program may carry out many operations on the data retrieved from the database 0 However the DBMS is only concerned about What data is readwritten fromto the database 0 database a xed set of relations A B C o transaction a sequence of read and write operations readA writeB o DBMS s abstract View of a user program 4152009 Luke Huan Univ of Kansas 6 Correctness criteria The ACID properties A tomicity A11 actions in the Xact happen or none happen C onsistency If each Xact is consistent and the DB starts consistent it ends up consistent I solation Execution of one Xact is isolated from that of other Xacts D urability If a Xact commits its effects persist An Example about SQL Transaction 0 Consider two transactions Xacts T1 BEGIN AA100 BB100 END T2 BEGIN A106A B106B END 1st xact transfers 100 from B s account to A s 2nd credits both accounts with 6 interest Assume at first A and B each have 1000 What are the legal outcomes of running T1 and T2 1100 106 1166 There is no guarantee that T1 will execute before T2 or Viceversa if both are submitted together But the net effect must be equivalent to these two transactions running serially in some order 4152009 Luke Huan Univ of Kansas 8 Example Contd 0 Legal outcomes A1166B954 or A1160B960 0 Consider a possible interleaved schedule T1 AA100 BB1OO T2 A106A B106B ozo This is OK same as T1 T2 But what about T1 AA100 BB1OO T2 A106A B106B Result A1166 B960 AB 2126 bank loses 6 The DBMS s view of the second schedule T1 RA WA 123 WB T2 RA WA 123 WB 4152009 Luke Huan Univ of Kansas SQL transactions Syntax in pgSQL BEGIN ltdatabase operationsgt COMMIT ROLLBACK A transaction is automatically started when a user executes an SQL statement begin is optional Subsequent statements in the same session are executed as part of this transaction 0 Statements see changes made by earlier ones in the same transaction 0 Statements in other concurrently running transactions do not see these changes COMMI T command commits the transaction ushing the update to disk ROLLBACK command aborts the transaction all effects are riggame Luke Huan Univ of Kansas 10 Atomicity 0 Partial effects of a transaction must be undone when 0 User explicitly aborts the transaction using ROLLBACK o Eg application asks for user con rmation in the last step and issues COMMIT or ROLLBACK depending on the response 0 The DBMS crashes before a transaction commits 0 Partial effects of a modification statement must be undone when any constraint is violated 0 However only this statement is rolled back the transaction continues 0 How is atomicity achieved 0 Logging to support undo 4152009 Luke Huan Univ of Kansas 11 Isolation o Transactions must appear to be executed in a serial schedule with no interleaving operations 0 For performance DBMS executes transactions using a serializable schedule 0 In this schedule only those operations that can be interleaved are executed concurrently 0 Those that can not be interleaved are in a serialized way 0 The schedule guarantees to produce the same effects as a serial schedule 4152009 Luke Huan Univ of Kansas 12 Concurrency control 0 Goal ensure the I isolation in ACID T1 T 2 readA readA writeA writeA readB readC writeB writeC commit commit 4 ABC 4152009 Luke Huan Univ of Kansas 13 Good versus bad schedules Good Bad Good But Why T1 T 2 T1 T 2 T1 T 2 rA d 1 A 1 04 WA Rea 400 IA WA rltBgt Writeww W400 rltAgt WB 400 100 Write rA rB 400 50 rB WA 1 C 1 C 1 C W03 W03 WC WC WC 4152009 Luke Huan Univ of Kansas 14 Serial schedule o Execute transactions in order with no interleaving of operations 0 T1rA T1WA T1rB T1WB T2rA T2WA T2rC T2WC o T2rA T2WA T2rC T2WC T1rA T1WA T1rB T1WB Isolation achieved by de nition 0 Problem no concurrency at all 0 Question how to reorder operations to allow more concurrency 4152009 Luke Huan Univ of Kansas 15 Conflicting operations 0 Two operations on the same data item con ict if at least one of the operations is a write 0 rX and WX con ict a wX and rX con ict a wX and WX con ict a rX and rX do not a rWX and rWY do not 0 Order of con icting operations matters a Eg if T1rA precedes T 2WA then conceptually T1 should precede T 2 4152009 Luke Huan Univ of Kansas 16 Precedence graph o A node for each transaction 0 A directed edge from T I to if an Operation of TI precedes and con icts with an Operation of in the schedule T1 T2 a T1 T2 6 rA r04 e e wA wA rB Good rB Bad rC rC MB n0 cycle MB cycle 4152009 WC Luke Huan Univ of Kansas WC 17 Conflictserializable schedule o A schedule is con ictserializable iff its precedence graph has no cycles 0 A con ictserializable schedule is equivalent to some serial schedule and therefore is good 0 In that serial schedule transactions are executed in the topological order of the precedence graph 0 You can get to that serial schedule by repeatedly swapping adjacent noncon icting operations from different transactions 4152009 Luke Huan Univ of Kansas 18 Summary 0 Transaction View of DBMS o ReadX o WriteX o ACID 0 Atomicity TX s are either completely done or not done at all 0 Consistency TX s should leave the database in a consistent state 0 Isolation TX s must behave as if they are executed in isolation o Durability Effects of committed TX s are resilient against failures 0 SQL transactions Begins implicitly SELECT UPDATE ROLLBACK I COMMIT 4152009 Luke Huan Univ of Kansas 19