Performance Analysis of Temporal QueriesAbstractAbstract, continuedIntroductionIntroduction, continuedSlide 6Slide 7Slide 8The New ModelThe New Model, continuedSlide 11The Algebraic ExpressionConventional Algebraic OperatorsTemporal Algebraic OperatorsAuxiliary Algebraic OperatorsTQuel Algebraic xform’s: Example 1Example 1, continuedTQuel Algebraic xform’s: Example 2Example 2, continuedXform to File Primitive ExpressionFile Primitive Expression, example 2Characteristics of DB RelationsSteps of TransformationAccess Path ExpressionAccess Path Expression ModesAPE Subcomponent ParametersInverted & Multi-List File structuresAPE for Inverted FilesAPE for Multilist FilesTransform FPE Access CostAccess-Time CalculationsPerformance Analysis SummaryPerformance Analysis of Temporal Queries(Information Sciences #49, 1989)(Information Sciences #49, 1989)by by Ilsoo AhnIlsoo Ahn, , AT&T Bell Laboratories, Columbus, OhioAT&T Bell Laboratories, Columbus, Ohioand and Richard SnodgrassRichard SnodgrassDept. of Computer ScienceDept. of Computer Science, , University of ArizonaUniversity of ArizonaCommunicated by Ahmed ElmagarmidCommunicated by Ahmed Elmagarmid~ * ~~ * ~Presented by Barry Klein for CS-599, 10/26/2000Presented by Barry Klein for CS-599, 10/26/2000AbstractTemporal databases that maintain history data Temporal databases that maintain history data add historical queries and rollback operations add historical queries and rollback operations to conventional db’s. This paper proposes a to conventional db’s. This paper proposes a model for analyzing the performance of model for analyzing the performance of temporal queries over a range of access temporal queries over a range of access methods.methods.Abstract, continuedModelModel: : 4 transformations through a series of 4 transformations through a series of formal expressions common to all phases of query formal expressions common to all phases of query processing.processing.InputInput: : Temporal Query + DB schemaTemporal Query + DB schemaOutputOutput: : Estimated I/O cost for it.Estimated I/O cost for it.ValidationValidation: : Compare estimated cost from model Compare estimated cost from model with actual cost from a prototype.with actual cost from a prototype.IntroductionFactors affecting performance of a Factors affecting performance of a Temporal DBMSTemporal DBMS::Access methods availableAccess methods availableQuery-processing strategiesQuery-processing strategiesSize and composition of the dataSize and composition of the dataIntroduction, continuedMethods for describing TDBMS effectiveness:Methods for describing TDBMS effectiveness:Empirical approach – actual performance is Empirical approach – actual performance is measured. measured. AdvantageAdvantage: Results are reliable.: Results are reliable.Analytical approach – develop a math model Analytical approach – develop a math model of the performance, which can predict of the performance, which can predict performance in controlled context. performance in controlled context. AdvantageAdvantage: less effort, but results are : less effort, but results are questionable.questionable.Introduction, continuedThree orthogonal types of Time:Three orthogonal types of Time:Valid time, Transaction time, User-definedValid time, Transaction time, User-defined4 categories of DBs defined in terms of4 categories of DBs defined in terms of support for valid/transaction time:support for valid/transaction time:Snapshot – conventional, no temporal support.Snapshot – conventional, no temporal support.Rollback – support transaction time.Rollback – support transaction time.Historical – support valid time (real-world history)Historical – support valid time (real-world history)Temporal – support both valid and txn time.Temporal – support both valid and txn time.Introduction, continuedTQuel—TQuel—non-proceduralnon-procedural language based on language based on tupletuple calculus—is chosen here to express calculus—is chosen here to express historical queries and rollback operations:historical queries and rollback operations:Augments Augments retrieveretrieve statement with statement with whenwhen predicate predicate – temporal relations among tuples.– temporal relations among tuples.ValidValid clause specifies how implicit time attributes clause specifies how implicit time attributes are computed for result tuples.are computed for result tuples.Rollback operations implemented with Rollback operations implemented with as ofas of clause (in either rollback or temporal db’s).clause (in either rollback or temporal db’s).Introduction, continuedTemporal relations used Temporal relations used with the added with the added constructs:constructs:PrecedePrecedeOverlapOverlapExtendExtendBegin ofBegin ofEnd ofEnd ofTQuel augments valid TQuel augments valid and when clauses to:and when clauses to:AppendAppendDeleteDeleteReplaceReplaceCreateCreate statement statement supported for supported for temporal relations.temporal relations.The New ModelPerformance analysis based on these givens:Performance analysis based on these givens:A set of temporal queriesA set of temporal queriesSome query-processing/optimization strategySome query-processing/optimization strategyFile structure(s) to implement the TDBFile structure(s) to implement the TDBA set of parameters characterizing the storage A set of parameters characterizing the storage devices.devices.The New Model, continuedAssumptions and decisions for this model:Assumptions and decisions for this model:Disk I/O traffic is used as measurement Disk I/O traffic is used as measurement key: ~proportional to performance;key: ~proportional to performance;Inputs must be flexible;Inputs must be flexible;Resulting estimate must be accurate.Resulting estimate must be accurate.The New Model, continuedThe 4 transformations of the model use:The 4 transformations of the model use:Algebraic expressions;Algebraic expressions;File-primitive expressions;File-primitive expressions;Access-path expressions.Access-path expressions.The Algebraic ExpressionSince TQuel is non-procedural, the algebraic Since TQuel is non-procedural, the algebraic expression is defined first:expression is defined first:Algebraic operatorsAlgebraic operatorsConventional: Conventional: select, project, join, union,
View Full Document
Unlocking...