Measures of Query Cost Many factors contribute to time cost disk access,CPU,and network communication Cost can be measured based on response time,i.e.total elapsed time for answering query,or total resource consumption We use total resource consumption as cost metric Response time harder to estimate,and minimizing resource consumption is a good idea in a shared database We ignore CPU costs for simplicity Real systems do take CPU cost into account Network costs must be considered for parallel systems We describe how estimate the cost of each operation We do not include cost to writing output to disk Database System Concepts-7th Edition 15.7 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.7 ©Silberschatz, Korth and Sudarshan th Edition Measures of Query Cost ▪ Many factors contribute to time cost • disk access, CPU, and network communication ▪ Cost can be measured based on • response time, i.e. total elapsed time for answering query, or • total resource consumption ▪ We use total resource consumption as cost metric • Response time harder to estimate, and minimizing resource consumption is a good idea in a shared database ▪ We ignore CPU costs for simplicity • Real systems do take CPU cost into account • Network costs must be considered for parallel systems ▪ We describe how estimate the cost of each operation • We do not include cost to writing output to disk
Measures of Query Cost Disk cost can be estimated as: ·Number of seeks average-seek-cost Number of blocks read average-block-read-cost Number of blocks written average-block-write-cost For simplicity we just use the number of block transfers from disk and the number of seeks as the cost measures f-time to transfer one block Assuming for simplicity that write cost is same as read cost ·ts-time for one seek Cost for b block transfers plus S seeks b *t+S *ts 加 fs and f depend on where data is stored;with 4 KB blocks: High end magnetic disk:ts=4 msec and f=0.1 msec SSD:ts 20-90 microsec and t=2-10 microsec for 4KB Database System Concepts-7th Edition 15.8 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.8 ©Silberschatz, Korth and Sudarshan th Edition Measures of Query Cost ▪ Disk cost can be estimated as: • Number of seeks * average-seek-cost • Number of blocks read * average-block-read-cost • Number of blocks written * average-block-write-cost ▪ For simplicity we just use the number of block transfers from disk and the number of seeks as the cost measures • tT – time to transfer one block ▪ Assuming for simplicity that write cost is same as read cost • tS – time for one seek • Cost for b block transfers plus S seeks b * tT + S * tS ▪ tS and tT depend on where data is stored; with 4 KB blocks: • High end magnetic disk: tS = 4 msec and tT =0.1 msec • SSD: tS = 20-90 microsec and tT = 2-10 microsec for 4KB
Measures of Query Cost(Cont.) Required data may be buffer resident already,avoiding disk l/O But hard to take into account for cost estimation Several algorithms can reduce disk IO by using extra buffer space Amount of real memory available to buffer depends on other concurrent queries and OS processes,known only during execution Worst case estimates assume that no data is initially in buffer and only the minimum amount of memory needed for the operation is available But more optimistic estimates are used in practice Database System Concepts-7th Edition 15.9 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.9 ©Silberschatz, Korth and Sudarshan th Edition Measures of Query Cost (Cont.) ▪ Required data may be buffer resident already, avoiding disk I/O • But hard to take into account for cost estimation ▪ Several algorithms can reduce disk IO by using extra buffer space • Amount of real memory available to buffer depends on other concurrent queries and OS processes, known only during execution ▪ Worst case estimates assume that no data is initially in buffer and only the minimum amount of memory needed for the operation is available • But more optimistic estimates are used in practice
Selection Operation ■File scan Algorithm A1 (linear search).Scan each file block and test all records to see whether they satisfy the selection condition. Cost estimate b,block transfers+1 seek b,denotes number of blocks containing records from relation r If selection is on a key attribute,can stop on finding record cost=(b,/2)block transfers+1 seek Linear search can be applied regardless of selection condition or ordering of records in the file,or availability of indices Note:binary search generally does not make sense since data is not stored consecutively except when there is an index available, and binary search requires more seeks than index search Database System Concepts-7th Edition 15.10 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.10 ©Silberschatz, Korth and Sudarshan th Edition Selection Operation ▪ File scan ▪ Algorithm A1 (linear search). Scan each file block and test all records to see whether they satisfy the selection condition. • Cost estimate = brblock transfers + 1 seek ▪ br denotes number of blocks containing records from relation r • If selection is on a key attribute, can stop on finding record ▪ cost = (br /2) block transfers + 1 seek • Linear search can be applied regardless of ▪ selection condition or ▪ ordering of records in the file, or ▪ availability of indices ▪ Note: binary search generally does not make sense since data is not stored consecutively • except when there is an index available, • and binary search requires more seeks than index search
Selections Using Indices Index scan-search algorithms that use an index selection condition must be on search-key of index. A2(clustering index,equality on key).Retrieve a single record that satisfies the corresponding equality condition ·Cost=(h+1)*(tr+ts) A3(clustering index,equality on nonkey)Retrieve multiple records. Records will be on consecutive blocks Let b number of blocks containing matching records Cost=hi *(tr+ts)ts +tr*b Database System Concepts-7th Edition 15.11 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.11 ©Silberschatz, Korth and Sudarshan th Edition Selections Using Indices ▪ Index scan – search algorithms that use an index • selection condition must be on search-key of index. ▪ A2 (clustering index, equality on key). Retrieve a single record that satisfies the corresponding equality condition • Cost = (hi + 1) * (tT + tS) ▪ A3 (clustering index, equality on nonkey) Retrieve multiple records. • Records will be on consecutive blocks ▪ Let b = number of blocks containing matching records • Cost = hi * (tT + tS) + tS + tT * b