高級數(shù)據(jù)庫技術(shù)-TheTukwilaDataIntegrationSystem

1、The Tukwila Data Integration System,University of Washington,Content,Tukwila Architecture Adaptive Query Execution The Need for Adaptivity Interleaving Planning and Execution Adaptive Query Operators Implementation The work next,Tukwila Architecture,Tukwila Architecture,Client/user interface User po

2、ses queries in terms of mediated relational schema. The querys are fed to the reformulator,Tukwila Architecture,Reformulator MiniCon, mapping the input query from the mediated schema to the data sources . Use data source catalog.,Tukwila Architecture,Data source catalog Mappings from the available d

3、ata sources to the mediated schema. Overlap information about pairs of Data Sources. Estimated access costs, sizes of relations, etc.,Tukwila Architecture,Optimizer Specify partial plans Incrementally re-optimize a query Generates event-condition-action rules,Tukwila Architecture,Adaptive query exec

4、ution engine Operator Execution processes query plans Event Handler for dynamically interpreting rule,Tukwila Architecture,Wrappers Available for ODBC-compliant. Translate data formats Location-independent,Adaptive Query Execution,The Need for Adaptivity Absence of statistics Cardinalities/histogram

5、s Unpredictable data arrival characteristics Initial delays before data arrival Bursty arrivals of data thereafter Overlap and redundancy among sources slow or unavailable data sources can often be replaced by overlapping or mirrored sources,Adaptive Query Execution,Interleaving Planning and Executi

6、on Query Plans Query Execution Event Handling,Adaptive Query Execution,Query Plans Makeup A partially-set of fragments A global rule Process Fragments in partial order execute in the order Fragments unrelated in partial order execute in parallel The end of a fragment Results are materialized The res

7、t of the plan can be re-optimized or rescheduled Choose next fragment by rule or partial order,Query Plans,Fragments and Operators Fragment A fully pipelined tree of physical operators A set of local rules Operator Algebraic: selection, join Chosen physical implementation: double pipelined join chil

8、dren the node: Memory allocated:,Query Plans,Rules Re-optimization Cardinality estimate significantly differ from actual size End of a fragment Contingent planning Which fragment to select End of a fragment Adaptive operators Policy of Memory overflow resolution in Double Pipelined Join Policy of so

9、urce selection in Dynamic Collector Rescheduling When a plan should be rescheduled a source times out (as in query scrambling),Query Plans,Rule Owner: Operator or Fragment Trigger When: active rule with active owner Example: when closed(frag1) if card(join1) 2 * est_card(join1) then replan,Query Pla

10、ns,Rule Event open, closed: fragment/operator starts or completes error: operator failure timeout(n): data source cannot response in n msec out_of_memory: join has insufficient memory threshold(n): n tuples processed by operator Condition: Comparator terms state(operator): Current state card(operato

11、r): Number of tuples produced time(operator): Time waiting since last tuple memory(operator): memory used so far,Query Plans,Rule Action Set the overflow method for a double pipelined join Alter a memory allotment Deactivate an operator or fragment Reschedule the query operator tree Re-optimize the

12、plan Return an error to user Attention All Actions executed before another event fired Rules with inactive owner is inactive,Event Handling,Event Generated at any time Event queue Event handling For each event, uses hash table to find all matching rules in active set All Actions executed before anot

13、her event fired,Adaptive Query Operators,Dynamic collectors Double Pipelined join Double Pipelined join Handling Memory Overflow Incremental Left Flush (fewer I/O) Incremental Symmetric Flush (reduced latency),Dynamic collectors,Task Perform a Union over overlapping sources Disjunction on leaves Han

14、dle errors Deciding to ignore slow mirror source by rules Operators information A set of children (sources) A Policy for contact the sources a set of triples , actually event-condition-action rule: i: ith child ai: activation condition ti: a termination condition,Dynamic collectors,Example when open

15、d(coll1) if true then activate(coll1,A); activate(coll1,B) when threshold(A,10) if true then deactivate(coll1,B) when threshold(B,10) if true then deactivate(coll1,A) when timeout(A) if true then activate(Coll1,C);deactivate(Coll1,B); deavtivate(Coll1,A),Double Pipelined join,Character Symmetric and

16、 Incremental Join Produces tuples almost immediately Mask the slow data source transmission rate Data-driven Process Each of join relations sends tuples as quick as possible Use tuple to probe the hash table for the other relation and add the tuple to the hash table for current relation Tuple is out

17、put immediately if Joined,Double Pipelined join,Advantage Time to first output is minimized Tuples are output as quickly as data source allow Optimizer doesnt need to choose “inner” relation The operator is symmetric Compensate(mask) the slow data source Data-driven, process the other source more qu

18、ickly Make efficient use of CPU, process one waiting the other,Double Pipelined join,Disadvantage and solution Disadvantage 1: Data-dirven and bottom-up model but system is top-down and iterator-based Solution: Use multithreading: Output Left Child Right child Tuples from children are put into the t

19、uple transfer queue.,Double Pipelined join,Disadvantage and solution Disadvantage 2: Requires memory for both two join relations Solution: Trade off some total execution time to get first tuples sooner Optimizer may use conventional joins Several strategies for efficiently dealing with memory overfl

20、ow,Double Pipelined join,Incremental Left Flush: Essential: Reading only tuples from right-side relation Flush a bucket from the left-side relations hash table Gradually degrade into hybrid hash ushing buckets lazily,Double Pipelined join,Incremental Left Flush: Process: (1)Pause reading from A( A l

21、eft B right) (2)Flush Some buckets from As hash table (3)Read tuple from B, probe As (partial)hash table; mark the tuple if its match bucket have been flushed. (4)Bhash table runs out of memory, flush some buckets (5)All of B read, resume processing tuples from A, like (3), tuples are probed or mark

22、ed (6)A and B processed, do a recursive hybird hash join. Unmarked tuples from A with marked tuples from B Marked tuples from A with unmarked and marked tuples B,Double Pipelined join,Incremental Symmetric Flush Essential: Flush a bucket from the both side relations hash table Gradually degrade into

23、 hybrid hash ushing buckets lazily,Double Pipelined join,Incremental Symmetric Flush: Process: (1)Flush a bucket from A or Bs hash table (2)Continue reading tuples from A and B (3)For newly tuple, probe the opposite hash table; mark the tuple if its match bucket have been flushed. (4)A and B process

24、ed, do a recursive hybird hash join. Unmarked tuples with marked tuples Marked tuples with unmarked and marked tuples Unmarked have been joined with unmarked,Implementation,Implementation: Communication: Pre-existing Standards such as Socket, XML, Unicode TCP Socket interface between modules Characters