Distributed Database SystemsWhat is System R? R*?R* basic factsObject naming in R*Global Catalogs in R*Transaction NumberingTransaction Numbering (cont)Transaction commitTransaction commit (cont)AuthorizationCompilation, Plan GenerationBinding in compilationDeadlock detectionDeadlock ExampleChanges Made to R.New SQL instructionsR* Cost StructureIs CPU cost significant?CPU costs continuedCPU Cost EquationImprove Local JoinsOptimizer performance (Local)Optimizer (Local) cont.Distributed JoinsTuple BlockingTransfer Trade-offsTransfer Trade-offs Cont.Use W or F Option?What might be betterOuter relation shipping Cont.Distributed vs. Local JoinsDistrib vs. Local Joins Cont.Alternative Join methodsSemijoinBloom joinComparing join methodsWhy are Bloom Joins better?Commercial ProductsDistributed Database SystemsR* Optimizer Validation and Performance Evaluation for Local QueriesLothar F. Mackert, Guy M. LohmanR* Optimizer Validation and Performance Evaluation for Distributed QueriesLothar F. Mackert, Guy M. LohmanR*: An Overview of the ArchitectureR. Williams, D. Daniels, L. Haas, G. Lapis, B. Lindsay, P. Ng, R. Obermarck, P. Selinger, A. Walker, P. Wilms, and R. YostWhat is System R? R*?System R is a database system built as a research project at IBM San Jose Research (now IBM Almaden Research Center) in the 1970's. System R introduced the SQL language and also demonstrated that a relational system could provide good transaction processing performance.R* basic factsEach site is autonomous as possible.No central scheduler, no central deadlock detection, no central catalog, etc.R* uses snapshot data – a “copy of a relation(s) in which the data is consistent but not necessarily up to date.” used to provide a static copy of the databaseObject naming in R*For autonomy, no global naming system required.To keep object names unique, site name incorporated into names, called System Wide Names – SWNEX. USER@USER_SITE.OBJECT_NAME@BIRTH_SITEGlobal Catalogs in R*All Global Table names stored at all sitesCreation of a global table involves broadcasting global relation name to all sites in the network.Catalogs at each site keep and maintain info about objects in the dbase, including replicas or fragments, stored at the site.Transaction NumberingA transaction is given a number that is composed of the unique site name and a unique sequence number from that site that incorporates time of day at that site so no synchronization between sites is needed.The transaction number is both unique and ordered in the R* frameworkTransaction Numbering (cont)Numbers used in deadlock detection.Uniqueness is used for identification purposes to determine which transactions control which locks to avoid case where a transaction is waiting for itself.In case of a deadlock, R* aborts the youngest, largest numbered transaction.Transaction commitTermination must be uniform – all sites commit or all sites abortTwo phase commit protocol.One site acts as coordinator – makes commit or abort decision after all sites involved in the transaction are known to be recoverably prepared to commit or abort and all sites are waiting coordinators decision.Transaction commit (cont)While non-coordinator sites await coordinator decision, all locks held – transaction resources are sequestered.Before entering the prepare state, any site can abort the transaction – other sites will abort after a transaction timeout. After entering the prepare state, a site may not abandon the transaction.3(N-1) messages needed to successfully commit, 4(N-1) messages if a transaction must abort.AuthorizationAll sites cooperate in R* voluntarily and no site wishes to trust others with authorization.Each individual site must check remote access requests and all controls regarding accessing data are stored at that same site.Compilation, Plan GenerationR* compiles rather than interprets the query language.Recompilation may need to be done if objects change in the database during compilation – ie, table deleted.Recompilation is done at a local level with a commit process similar to a transaction.Binding in compilationWhen/where should binding occur?All binding for every request can be done at a chosen site? – no, creates a bottleneck site.All binding can be done at the site where request began? – no, compiling site should not need to remember physical details about access paths at remote sites.All binding can be done in a distributed way? Yes, requesting site can decide high level details, leave minor/ low level details to other sites.Deadlock detectionNo centralized deadlock detection.Each site does periodic deadlock detection using transaction wait-for info gathered locally or received from others. Wait-for strings are sent from one site to the next. If a site finds a cycle, youngest transaction is aborted.Deadlock ExampleChanges Made to R.Explain – writes out optimizer details such as estimated cost to temp tables.Collect Counters – dumps internal system variables to temporary tables.Force Optimizer – order optimizer to choose a particular (perhaps suboptimal) plan.New SQL instructionsEXPLAIN PLAN FOR<any valid Delete, Insert, Select, Select Into, Update, Values, or Values Into SQL Statement>R* Cost StructureCost = Wcpu(#_instructions) + Wi/o(#ios) + Wmsg(#_MSGs) + Wbyt(#_byt)Wmsg for some constant penalty for sending a communication over the networkWbyt penalty for message length.Is CPU cost significant?Both local and distributed queries found cpu cost to be important.CPU costs high in sorts1.allocating temp disk space for partially sorted strings2. Encoding and decoding sorted columns3. Quicksorting individual pages in mem.CPU costs continuedCPU costs are also high in scansAlthough “CPU cost is significant . . . [it] is not enough to affect the choice of the optimizer”CPU Cost EquationCPUsort = ACQ_TEMP + #SORT * CODINGINST + #PAGES * QUICKSORTINST + #PASS * (ACQ_TEMP + #PAGES * IO_INST + #SORT * NWAY * MERGINST)Improve Local JoinsCommunicate type of JoinAre there likely to be runs of pages to prefetch?Can choice of LRU, MRU, DBMin improve performance if Join type known.Optimizer performance (Local)Optimizer has trouble modeling unclustered indexes on smaller tables. In such cases, Optimizer actually picks worst plan, thinking it is the best and thinks the