数据库系统概念原书第5版(英文)第九章ppt.ppt

* * * * * * * * * Dept. of Comp. Sci. Tech., Tongji Uni. * Materialization (Cont.) Materialized evaluation is always applicable Cost of writing results to disk and reading them back can be quite high Our cost formulas for operations ignore cost of writing results to disk, so Overall cost = Sum of costs of individual operations +  cost of writing intermediate results to disk Double buffering: use two output buffers for each operation, when one is full write it to disk while the other is getting filled Allows overlap of disk writes with computation and reduces execution time * Dept. of Comp. Sci. Tech., Tongji Uni. * Pipelining Pipelined evaluation: evaluate several operations simultaneously, passing the results of one operation on to the next. E.g.in previous expression tree,don’t store result of instead, pass tuples directly to the join. Similarly, don’t store result of join, pass tuples directly to projection. Much cheaper than materialization. Pipelining may not always be possible – e.g., sort, hash-join. Pipelines can be executed in two ways: demand driven and producer driven * Dept. of Comp. Sci. Tech., Tongji Uni. * Pipelining (Cont.) In demand driven or lazy evaluation system repeatedly requests next tuple from top level operation Each operation requests next tuple from children operations as required, in order to output its next tuple Between calls, operation has to maintain “state” so it knows what to return next Each operation is implemented as an iterator implementing the following operations open() E.g. file scan: initialize file scan, store pointer to beginning of file as state E.g.merge join: sort relations and store pointers to beginning of sorted relations as state next() E.g. for file scan: Output next tuple, and advance and store file pointer E.g. for merge join: continue with merge from earlier state till next output tuple is found. Save pointers as iterator state. close() * Dept. of Comp. Sci. Tech., Tongji Uni. * Pipel