ࡱ> []Zbc~M pabjbj== WWH8lTTT ^ BBBD.!.!.!!D!9""""#)))M9O9O9O9O9O9O9$: <s9EB)~(0)))s9R-jj"#v9R-R-R-)>j "^B#M9R-)M9R-RR-2r3vB4#" Pw.!+f}449094>R->4R-jjjjThe Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb Jim Gray, Goetz Graefe Microsoft Research, 301 Howard St. #830, SF, CA 94105 {Gray, GoetzG}@Microsoft.com Abstract: Simple economic and performance arguments suggest appropriate lifetimes for main memory pages and suggest optimal page sizes. The fundamental tradeoffs are the prices and bandwidths of RAMs and disks. The analysis indicates that with today's technology, five minutes is a good lifetime for randomly accessed pages, one minute is a good lifetime for two-pass sequentially accessed pages, and 16 KB is a good size for index pages. These rules-of-thumb change in predictable ways as technology ratios change. They also motivate the importance of the new Kaps, Maps, Scans, and $/Kaps, $/Maps, $/TBscan metrics. 1. The Five-Minute Rule Ten Years Later All aspects of storage performance are improving, but different aspects are improving at different rates. The charts in Figure 1 roughly characterize the performance improvements of disk systems over time. The caption describes each chart. In 1986, randomly accessed pages obeyed the five-minute rule [1]: pages referenced every five minutes should have been kept in memory rather than reading them from disk each time. Actually, the break-even point was 100 seconds but the rule anticipated that future technology ratios would move the break-even point to five minutes. The five-minute rule is based on the tradeoff between the cost of RAM and the cost of disk accesses. The tradeoff is that caching pages in the extra memory can save disk IOs. The break-even point is met when the rent on the extra memory for cache ($/page/sec) exactly matches the savings in disk accesses per second ($/disk_access/sec). The break even time is computed as: BreakEvenReferenceInterval (seconds) = PagesPerMBofRAM x PricePerDiskDrive (1) AccessPerSecondPerDisk PricePerMBofDRAM The disk price includes the cost of the cabinets and controllers (typically 30% extra.) The equations in [1] were more complex because they did not realize that you could factor out the depreciation period. The price and performance from a recent DELL TPC-C benchmark [2] gives the following parameters for Equation 1: PagesPerMBofRAM = 128 pages/MB (8KB pages) AccessesPerSecondPerDisk = 64 access/sec/disk PricePerDiskDrive = 2000 $/disk (9GB + controller) PricePerMBofDRAM = 15 $/MB_DRAM  Evaluating Equation 1 with these values gives a reference interval of 266 seconds -- about five minutes. So, even in 1997, data referenced every five minutes should be kept in main memory. Prices for the same equipment vary enormously, but all the categories we have examined follow something like a five-minute rule. Server hardware prices are often three times higher than "street prices" for the same components. DEC Polaris RAM is half the price of DELL. Recent TPC-C Compaq reports have 3x higher RAM prices (47$/MB) and 1.5x higher disk prices (3129$/drive) giving a two-minute rule. The March 1997 SUN+Oracle TPC-C benchmark [3] had prices even better than DELL (13$/MB of RAM and 1690$ per 4GB disk and controllers). These systems all are near the five-minute rule. Mainframes are at 130$/MB for RAM, 10K$/MIPS, and 12k$/disk. Thus, mainframes follow a three-minute rule. One can think of the first ratio of Equation 1 (PagesPerMBofRAM/AccessesPerSecondPerDisk) as a technology ratio. The second ratio of Equation 1 (PriceofDiskDrive/PriceOfMBofRAM) is an economic ratio. Looking at the trend lines in Figure 1, the technology ratio is shifting. Page size has increased with accesses/second so the technology ratio has decreased ten fold (from 512/30 = 17 to 128/64 = 2). Disk drive prices dropped 10x and RAM prices dropped 200x, so that the economic ratio has increased ten fold (20k$/2k$=10 to 2k$/15$=133). The consequent reference interval of equation (1) went from 170 seconds (17x10) to 266 seconds (2x133). These calculations indicate that the reference interval of Equation (1) is almost unchanged, despite these 10x, 100x, and 1,000x changes. It is still in the 1-minute to 10-minute range. The 5-minute rule still applies to randomly accessed pages. The original paper [1] also described the 10-byte rule for trading CPU instructions off against DRAM. At the time one instruction cost the same as 10 bytes. Today, PCs follow a 1-byte rule, mini-computers follow a 10 byte rule, while mainframes follow a kilobyte rule because the processors are so over-priced. 1.2. Sequential Data Access: the One-Minute Sequential Rule The discussion so far has focused on random access to small (8KB) pages. Sequential access to large pages has different behavior. Modern disks can transfer data at 10 MBps if accessed sequentially (Figure 1a). That is a peak value, the analysis here uses a more realistic 5 MB/s as a disk sequential data rate. Disk bandwidth drops 10x (to 0.5 MBps) if the application fetches random 8KB pages from disk. So, it should not be surprising that sequential IO operations like sort, cube, and join, have different RAM/disk tradeoffs. As shown below, they follow a one-minute-sequential rule. If a sequential operation reads data and never references it, then there is no need to cache the data in RAM. In such one-pass algorithms, the system needs only enough buffer memory to allow data to stream from disk to main memory. Typically, two or three one-track buffers (~100 KB) are adequate. For one-pass sequential operations, less than a megabyte of RAM per disk is needed to buffer disk operations and allow the device to stream data to the application. Many sequential operations read a large data-set and then revisit parts of the data. Database join, cube, rollup, and sort operators all behave in this way. Consider the disk access behavior of Sort in particular. Sort uses sequential data access and large disk transfers to optimize disk utilization and bandwidth. Sort ingests the input file, reorganizes the records in sorted order, and then sequentially writes the output file. If the sort cannot fit the file in main memory, it produces sorted runs in a first pass and then merges these runs into a sorted file in the second pass. Hash-join has a similar one-pass two-pass behavior. The memory demand of a two pass sort is approximately given in equation 2: Equation 2 is derived as follows. The first sort pass produces about File_Size/Memory_Size runs while the second pass can merge Memory_Size/Buffer_Size runs. Equating these two values and solving for memory size gives the square root term. The constants (3 and 6) depend on the particular sort algorithm. Equation 2 is graphed in Figure 2 for file sizes from megabytes to exabytes. Sort shows a clear tradeoff of memory and disk IO. A one-pass sort uses half the disk IO but much more memory. When is it appropriate to use a one-pass sort? This is just an application of Equation 1 to compute the break-even reference interval. Use the DEC TPC-C prices [2] and components in the previous section. If sort uses to 64KB transfers then there are 16 pages/MB and it gets 80 accesses per second (about 5 MB/s). PagesPerMBofRAM = 16 pages/MB AccessesPerSecondPerDisk = 80 access/sec/disk Using these parameters, Equation 1 yields a break-even reference interval of 26 seconds (= (16/80) x (2,000/15)). Actually, sort would have to write and then read the pages, so that doubles the IO cost and moves the balance point to 52 seconds. Anticipating higher bandwidths and less expensive RAM, we predict that this value will slowly grow over time. Consequently, we recommend the one-minute-sequential rule: hash joins, sorts, cubes, and other sequential operations should use main memory to cache data if the algorithm will revisit the data within a minute. For example, a one-pass sort is known to run at about 5 GB/minute [4]. Such sorts use many disks and lots of RAM but they use only half the IO bandwidth of a two-pass sort (they pass over the data only once). Applying the one-minute-sequential rule, below 5 GB a one-pass sort is warranted. Beyond that size, a two-pass sort is warranted. With 5GB of RAM a two-pass sort can sort 100 terabytes. This covers ALL current sorting needs. Similar comments apply to other sequential operations (group by, rollup, cube, hash join, index build, etc). In general, sequential operations should use high-bandwidth disk transfers and they should cache data that they will revisit the data within a minute. In the limit, for large transfers, sequential access cost degenerates to the cost of the bandwidth. The technology ratio of equation 1 becomes the reciprocal of the bandwidth (in megabytes): TechnologyRatio = (PagesPerMB)/(AccessesPerSecond) = (1E6/TransferSize)/ ( DiskBandwidth/TransferSize) for purely sequential access = 1E6/DiskBandwidth. (3) This is an interesting result. It gives rise to the asymptote in Figure 3 that shows the reference interval vs. page size. With current disk technology, the reference interval asymptotically approaches 40 seconds as the page size grows. 1.4. RAID and Tape RAID 0 (striping) spreads IO among disks and so makes the transfer size smaller. Otherwise, RAID 0 does not perturb this analysis. RAID 1 (mirroring) slightly decreases the cost of reads and nearly doubles the cost of writes. RAID 5 increases the cost of writes by up to a factor of 4. In addition RAID5 controllers usually carry a price premium. All these factors tend to increase the economic ratio (making disks more expensive, and raise the technology ratio (lower accesses per second). Overall they tend to increase the random access reference interval by a factor of 2x to 5x. Tape technology has moved quickly to improve capacity. Today the Quantum DLTstor"! is typical of high performance robots. Table 4 presents the performance of this device.  Accessing a random data record on a tape requires mounting it, moving to the right spot and then reading the tape. If the next access is on another tape and so one must rewind the current tape, put it away, pick the next one, scan to the correct position, and then read. This can take several minutes, but the specifications above charitably assumed it takes 30 seconds on average. When should you store data on tape rather than in RAM? Using Equation 1, the break-even reference interval for a 8KB tape block is about two months (keep the page in RAM rather than tape if you will revisit the page within 2 months). Another alternative is keeping the data on disk. What is the tradeoff of keeping data on disk rather than on tape? The tradeoff is that tape-space rent is 10x less expensive but tape accesses are much more expensive (100,000x more for small accesses and 5x more for large (1GB) accesses). The reference interval balances the lower tape rent against the higher access cost. The resulting curve is plotted in Figure 3. 1.5. Checkpoint Strategies In Light of the 5-minute Rule Buffer managers typically use an LRU or Clock2 (two round clock) algorithm to manage the buffer pool. In general, they flush (write to disk) pages when (1) there is contention for cache space, or (2) the page must be checkpointed because the page has been dirty for a long time. The checkpoint interval is typically five minutes. Checkpoint limits recovery to redoing the last five or ten minutes of the log. Hot-standby and remote-disaster-recovery systems reduce the need for checkpoints because they continuously run recovery on their version of the database and can take over within seconds. In these disaster-tolerant systems, checkpoints can be very infrequent and almost all flushes are contention flushes. To implement the N-minute rule for contention flushes and evictions, the buffer manager keeps a list of the names of all pages touched within the last N minutes. When a page is re-read from disk, if it is in the N-minute list, it is given an N-minute lifetime (it will not be evicted for N-minutes in the future). This simple algorithm assures that frequently accessed pages are kept in the pool, while pages that are not re-referenced are aggressively evicted. 1.6. Five-Minute Summary In summary, the five-minute rule still seems to apply to randomly accessed pages, primarily because page sizes have grown from 1KB to 8KB to compensate for changing technology ratios. For large (64KB pages) and two-pass sequential access, a one-minute rule applies today. 2.How Large Should Index Pages Be? The size of an internal index page determines its retrieval cost and fan-out (EntriesPerPage). A B-tree indexing N items will have a height (in pages) of: Indexheight ~ log2(N)/log2(EntriesPerPage) pages (4). The utility of an index page measures how much closer the index page brings an associative search to the destination data record. It tells how many levels of the binary-tree fit on a page. The utility is the divisor of the Equation 4: IndexPageUtility = log2(EntriesPerPage) (5) For example, if each index entry is 20 bytes, then a 2 KB index page that is 70% full will contain about 70 entries. Such a page will have a utility of 6.2, about half the utility of a 128 KB index page (see Table 6). Reading each index page costs a logical disk access but each page brings us IndexPageUtility steps closer to the answer. This cost-benefit tradeoff gives rise to an optimal page size that balances the IndexPageAccessCost and the IndexPageUtility of each IO. Reading a 2 KB page from a disk with a 10 ms average access time (seek and rotation) and 10 MB/s transfer rate uses 10.2 ms of disk device time. So the read cost is 10.2 milliseconds. More generally, the cost of accessing an index page is either the storage cost in main memory if the page is cached there, or the access cost if the page is stored on disk. If pages near the index root are cached in main memory, the cache saves a constant number of IOs on average. This constant can be ignored if one is just optimizing the IO subsystem. The index page disk access cost is IndexPageAccessCost = Disk Latency + PageSize / DiskTransferRate (6) The benefit-cost ratio of a certain page size and entry size is the ratio of the two quantities. IndexPageBenefit/Cost = IndexPageUtility / IndexPageAccessCost. (7) The right column of Table 6 shows this computation for various page sizes assuming 20-byte index entries. It indicates that 8 KB to 32 KB pages are near optimal for these parameters. Figure 7 graphs the benefit/cost ratios for various entry sizes and page sizes for both current, and next-generation disks. The graphs indicate that, small pages have low benefit because they have low utility and high fixed disk read costs. Very large pages also have low benefit because utility grows only as the log of the page size, but transfer cost grows linearly with page size. Table 6 and Figure 7 indicate that for current devices, index page sizes in the range of 8 KB to 32 KB are preferable to smaller and larger page sizes. By the year 2005, disks are predicted to have 40 MB/s transfer rates and so 8 KB pages will probably be too small. Table 6 and Figure 7 indicate that for current devices, index page sizes in the range of 8 KB to 32 KB are preferable to smaller and larger page sizes. By the year 2005, disks are predicted to have 40 MB/s transfer rates and so 8 KB pages will probably be too small. 3. New Storage Metrics These discussions point out an interesting phenomenon -- the fundamental storage metrics are changing. Traditionally, disks and tapes have been rated by capacity. As disk and tape capacity approach infinity (50 GB disks and 100 GB tapes are in beta test today), the cost/GB goes to zero and the cost/access becomes the dominant performance metric. The traditional performance metrics are: GB: storage capacity in gigabytes. $/GB: device price divided by capacity. Latency: time between issue of IO and start of data transmission. Bandwidth: sustained transfer rate from the device. The latter two are often combined as a single access time metric (time to read a random KB from the device). Kaps : kilobyte accesses per second. As device capacities grow, additional metrics become important. Transfers become larger. Indeed, the minimum economical tape transfer is probably a one MB object Increasingly, applications use a dataflow style of programming and stream the data past the device. Data mining applications and archival applications are the most common example of this today. These suggest the following two new storage metrics. Maps: Megabyte accesses per second. Scan: how long it takes to sequentially read or write all the data in the device?  These metrics become price/performance metrics when combined with the device rent (depreciated over 3 years). The Scan metric becomes a measure of the rent for a terabyte of the media while the media is being scanned. Table 8 displays these metrics for current devices: 4. Summary The fact that disk access speeds have increased ten-fold in the last twenty years is impressive. But it pales when compared to the hundred-fold increase in disk unit capacity and the ten-thousand-fold decrease in storage costs (Figure 1). In part, growing page sizes sixteen-fold from 512 bytes to 8 KB has ameliorated these differential changes. This growth preserved the five-minute rule for randomly accessed pages. A one- minute rule applies to pages used in two-pass sequential algorithms like sort. As technology advances, secondary storage capacities grow huge. The Kaps, Maps, and Scans metrics that measure access rate and price/access are becoming increasingly important. 5. Acknowledgments Paul Larson, Dave Lomet, Len Seligman and Catharine Van Ingen helped us clarify our presentation of optimum index page sizes. The Kaps, Maps, and Scans metrics grew out of discussions with Richie Larry. 6. References [1] J. Gray & G. F. Putzolu, "The Five-minute Rule for Trading Memory for Disc Accesses, and the 10 Byte Rule for Trading Memory for CPU Time," Proceedings of SIGMOD 87, June 1987, pp. 395-398. [2] Dell-Microsoft TPC-C Executive summary: http://www.tpc.org/results/individual_results/Dell/dell.6100.es.pdf [3] Sun-Oracle TPC-C Executive summary: http://www.tpc.org/results/individual_results/Sun/sun.ue6000.oracle.es.pdf [4] Ordinal Corp. http://www.ordinal.com/  The current 2 KB page-size of Microsoft SQL Server 6.5 gives a reference interval of 20 minutes. MS SQL is moving to an 8 KB page size in the 1998 release. ACM COPYRIGHT NOTICE. Copyright 2000 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or  HYPERLINK "mailto:permissions@acm" permissions@acm.org. For definitive copy see:  HYPERLINK "http://www" http://www.acm.org/pubs/citations/proceedings/mod/191839/p243-gray/. This copy is posted by permission of ACM and may not be redistributed.  EMBED Equation.3  Table 8: Performance Metrics of high-performance devices circa 1997.RAMDiskTape robotUnit capacity1GB9 GB14 x 35 GBUnit price $15,000$2,000$10,000$$/GB15,000 $/GB222$/GB20 $/GBLatency (ms)0.1 micro sec 10 milli sec30 secBandwidth500 MBps5 MBps5 MBpsKaps500,000 Kaps100 Kaps.03 KapsMaps500 Maps4.8 Maps.03 MapsScan time2 seconds30 minutes27 hours$/Kaps0.3 nano $0.2 micro $3 milli $$/Maps.3 micro $4 micro $3 milli $$/TBscan.32 $4.23$296$ Table 6: Tabulation of index page utility and benefit/cost for 20 byte index entries assuming each page is 70% full and assuming a 10ms latency 10 MBps transfer rate.page size KBentries per page Fan-outIndex Page UtilityIndex Page Access Cost (ms)Index Page Benefit/ Cost (20B)2686.110.20.6041357.110.40.6882708.110.80.75165419.111.60.7832108110.113.20.7664216311.116.40.68128432512.122.80.53  Figure 1: Performance of magnetic storage disks over time. The first two graphs show that accesses and access times improved 10x or 100x while capacity grew 100x. The third graph shows that prices improved 1,000x in the same time. We have compensated for the changing ratios among accesses, capacity, and cost by using larger RAM buffers and larger pages. That is one theme of this paper.  Figure 7. (a) The left graph shows the utility of index pages versus page size for various index entry sizes using a high-performance disk (10ms latency, 10 MB/s transfer rate). (b) The graphs at right use a fixed-sized 16-byte entry and show the impact of disk performance on optimal page size. For high-performance disks, the optimum index page size grows from 8KB to 64KB. Table 4: Tape robot price and performance characteristics (source Quantum DLTstor"!).Quantum DLT Tape Robot9,000$ priceTape capacity35 GB Number of tapes14Robot Capacity490 GBMount time (rewind, un-mount, put, pick, mount, position)30 secondsTransfer rate5 MBps  Figure 5: The utility of an index page is the number of levels of the binary tree that it traverses. The utility rises as the log of the page size. The cost of the access goes up linearly with page sizeConsequently, for a particular disk latency and transfer rate, there is an optimal index page size. The tree at left shows just the search path (it is not balanced because the drawing would be too cluttered).  EMBED Excel.Sheet.8  Figure 3: The break-even reference interval for disk vs. DRAM asymptotically approaches something like one minute for current technology. The asymptote is the product of the technology ratio (which becomes 1e6/bandwidth) and the economic ratio. A later section discuses the disk-tape tradeoff. Fundamentally, tape technology is VERY expensive to access. This encourages very large tape page sizes and very cold data on tape. The tape asymptote is approached at 10 GB (tape hardware is described in Table 4).  EMBED Excel.Sheet.8  Figure 2: A two-pass sort can process 100 terabyte files with a 5 GB DRAM buffer. The two pass sort balances the run length against the number of runs to merge in the second pass. If it generates a thousand runs of 100 MB each, it can merge them using 100 MB of merge buffers in phase 2. This is a 100 GB sort. With current technology, use a 1-pass sort up to 5GB files. For larger files, do a 2-pass sort.  '1Yoz   < P S T Y m u  3 M a ɾԺ۲j0JUhjUmHnHu OJQJhCJOJQJh6CJOJQJh6CJNHhCJh6CJH*OJQJh5CJH*OJQJh 6>*CJh 6CJh mHnHuCJh6hNHh5CJCJCJh4Qk1YLN  9 v z {  M  ~ 1$$a$$a$$a$MVN^Noa mn+,'|}PQ"V } 1$1$^\`aQR[m'P^_"#i~PQV m } ШCJOJQJh6CJOJQJh)jB*CJOJQJUmHnHphuB*NHhph B*hph5OJQJh 56NHh 56h5h 6NHh6hNHhh? """"$$%%t&&&&&& '(#(**, ,- ^``$$`$$ $ 1$a$ 1$1$ !!7"Q"""""$$$$%%%%&&t&&& 'V'W'''(#(((Y)Z)@+B+,,,,,,`-a-//801!1K1U1n2o22222 3 3S3U3334454Ӥ5jB*UmHnHphu6NH56CJOJQJ5B*hphB*NHhph B*hphB*OJQJhphjUmHnHu6h 56hNHhh@-..80q0 22A3B35-5?6b66=7)8c8?9C:<<J==v>? AB0B5464c4d45555'5(566666667 7777797=7A7H788?8@8596999 ::::%:5:s:t:X<Y<<<f=g===> >j>k>>>??@@AAB0BaBbBBB1C2CCCCCDD5B*hphB*NHhph B*hphjUmHnHu6NHH* 6CJH*CJ6CJhNH6L0BCCCCDHD}D~DDEEEEFF%G&G'G(G*G9HDHJ KKK h^h`DIDSDDDDDDEEFFFF(G)G9HDHEHIIIIJJKJJJJJJJJJJJJJbKcKKKKKKKLLLM>MMMMMMMMNTNZN[N^NTP۹CJ 0JCJCJh j0JU OJQJhB*OJQJhph6hNHhjB*UmHnHphuhjUmHnHuB*NHhph5B*hph B*hph>KLMMMMMUNVNYNZN\N]N^NRR5R6R7R|R $$Ifa$  L^`L$ L1$^`La$ FL1$^`LTPUPPPQQAQBQCQRQSQsQtQQQQQQRRR1R2R3R4R7R?R~RRRRRRRRRRRRR S.S8SPSUSuSzSSSSSSSSSTT+T-T6T^T_TžB*NHhph5B*NHhph B*hph5B*hph jfEHUjT7 UVmHnHu jUjCJ U0JCJ jCJ U jCJ UCJ CJ NH=|R}R~RRRRX $$Ifa$X$$Ifl4 04 laRRRRRRRRRRRRoffffoffffo $$Ifa$$$Ifl\F F04 la RRRRRR SS&S-S.S8Sff$$Ifl\F F04 la $$Ifa$ 8SASHSOSPSUSbSkStSuSzSSff$$Ifl\F F04 la $$Ifa$ SSSSSSSSSSSSff$$Ifl\F F04 la $$Ifa$ SSSSSTTTTT%T*Tffl$$Ifl\F F04 la $$Ifa$ *T+T,T-TTTommX-*$$If4a$$VE$If]V^`E$$Ifl\F F04 la_TTKU^U_UsUtUUUUUUUUUUUUUUUxWyWzWWXX&YZ~[[[[[[J\K\S\T\\\\\W]X]]]]]]]]]]^^____jz7 UVmHnHu jVUj7 UV jUNH jO5UB*NHhph j=U5h jOUhB*OJQJhphB*CJOJQJhph5B*hph B*hph;TTTTTUUU+U?UJUKUMUPUTU|Pw$$Ifr*T~  ***a $$$$Ifa$TUYU^U_UaUeUiUnUsUtUvUzU~UUU|T|Tw$$Ifr*T~  ***a $$$$Ifa$UUUUUUUUUUUUUUUX|||||`|||||`| $$$$Ifa$w$$Ifr*T~  ***aUUUUUUUUUUU|dw$$Ifr*T~  ***a $$$$Ifa$ UUUUUUUUwWxWzWXXJZ{$If$a$w$$Ifr*T~  ***a JZLZzZZZZ4Xi$$Ifl0L , T04 la $$Ifa$X$$Ifl4L,04 laZZZZZZ[[[[[[[[[[[P\Xi$$Ifl0L , T04 la $$Ifa$[[[T\]]]]__iajakalamanaoapaxB$$Ifl0H6 l 4 la$If____``gahapaB*OJQJhphB*NHhph B*hph5B*hph jU jlgU'0P/R / =!"#$%. 00P/R / =!"#$% P. 00P/R / =!"#$% P. 00P/R / =!"#$% P`!-u2tA&/ wGxM(xeSkQ7.r3TN !X u)䄽xue.ZH#X?!(B@@BIBB7wfvvfV ? \-Yݮbn GGz9H3ּ9R ,49r<`xbAWƜ"՞/xd[ =1&~5ybgN}lo} O;|ªA1,l;OJЮ߱s>K3zxs=-<3zwTO}fܝ  fLjQjly.QƺӮ987۬L |WU.-Gl盕0jE[Q{fs@ѲQR Dh=͝$p?.iDLfK3zxs=-<3zwTO}fܝ  fLjQjly.QƺӮ987۬L |WU.-Gl盕0jE[Q{fs@ѲQR Dh=͝$p?.iDLf}t}eizؼ#J|]~KRj߉M9k/8~]9^x{qSpdpWCTsw^R/[}LS#D֚Mc2}5V7|M U[=7lxeߤYݰ7}:izű?k} :ΓU-z#8!~Twy o.3ʌzUW{uj}35CsrUV?ݜ(k_3Fak#?/_Z 縿j/8㶪[c*N>jO4M-++VmԳ`S&Dآrrr\8op]6ez{VO%uXzW>n/3 ҿ+溾ً5o9*^@iؿI'^ͮfȻĝcO6A59 ɱWsT~~I+*rh1Uͥ_G >{UO{U]e̱?Mu- \ya#Jhux\5X~+7\<[ӛsm+Gko~Bh/T'tUU tmb78M4:(ЛqM/-B t31o745]k".B *ڂ9Gs y w1e42ۇ݊7Z(+/qf"EE3!~c׬i4kڃ P51փc/5m`~cٟh&h`dQ9>>zV}  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQSTUVWXYG\_`aefghijklmnopqrstuvwxyz{|}~Root Entry F`)^Data RwWordDocumentObjectPool `)_937394516FuȦ0֦Ole CompObjfObjInfo  !#$%&'()+,-./012356789:;<=>?A FMicrosoft Equation 3.0 DS Equation Equation.39qG)H MemoryForTwoPassSortH"6Buffer_Size+ 3Buffer_SizeFilEquation Native E_936952034 F@V/Ole  CompObj be_Size..  ...(2) FMicrosoft Excel ChartBiff8Excel.Sheet.89qOh+'08@Th  Jim GrayObjInfo Workbook d>SummaryInformation(DocumentSummaryInformation8E"      !{$%&'()*+,-./0123456789:;<=>?@ABCDF|HIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz}  Ba=  f'7 =I8X1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial14FAbadi MT Condensed14FAbadi MT Condensed1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial1FArial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_) 0.0\ \G\B 0.E+000.0 #,##0.0 "$"#,##0 "$"#,##0.00 0.0E+00 0.E+0 0E+0                + ) , *      1( *   " " "        ( "          %  `$Chart43Figure4}Figure2Tape&SequentialTable4figure 1-CjimPAPERSTEMP.xlsSheet1Sheet2Y ZDRAMDISKTAPEZ0 unit price($)L@@@@Z/ capacity(gB)?"@y@Z'$/GBL@rqk@9@Z. latency(ms)-C6?$@L@Z2bandwidth(MBps)@@@@Z'KapsyyAX@V ?Z'Maps 隙?@0 0 @@.?Z'Gaps} (?u,zt? o?Z* Scanspd@H@HzG?YdDCjimPAPERSKOX_MOX_GOX_SCANGoetz Graefe Index Utility Graphs.xlsSheet1Sheet2Sheet3Y(Zbenefit/ cost (20B)Z @Z ḁ?Z {Gz?Z @Z S?Z AZ  @Z ?Z 0@Z }3(?Z 0@Z @@Z ۮ F?Z ffffff?Z P@Z )?bS?Z `@Z  ?Z1@Ol? ?ЬD#?Z S?Z1 @)Xh?ЬD#?wu.?Vi9?Z hy+Up?cln?QT?Z ?Z10@N=t?QT?u|є? ?Z m" ,?1ib?Y?Z }3(?Z1@@0+|E?Y?T:7s?@ ?Z La?ExF?}T=D?Z ۮ F?Z1 P@ك\3?}T=D?]5V??J>g?Z  ȀH?\V%?-w?Z )?bS?Z1!`@KIZJ?-w?n)脞 ?%Y~E?Z !2T?0!V?O?Z ! ?YYB4CjimPAPERSKOX_MOX_GOX_SCAN2 Pass Sort Sheet.xlsSheet1Y Z&power file sizeMem SizeZ @חA0Qq.RAZ @@Z"@eA}ռR)kAZ$@ _B|dAZ&@vH7Bn6[AZ(@mB#AZ*@@0BʆCAZ,@ļBI^(SAZ.@4&k C|hn BZ 0@7yACpg$BZ 1@؅W4vCN؊!@BZ 2@NgmC ^YB>  buff_Size: entry_size:# file_size;'index_elemet_size:+index_page_utilizaton:" Mem_Size; power;! rotate_seek:# transfer_rate:$ unit_price;H(9       3  @@  nXyear access time transfer rate1K8 KB64 KB1 MB $/MB DRAM $/MB Disk capacity (GB)power file sizeMem Size buff Sizerotate+seek(sec)transfer rate (B/sec)index elemet sizeindex page utilizaton page size KBIndex Page Utilityentries per page]Table showing benefit (log(index entries)) vs cost (access time) of various index page sizes)benefit/ cost (20B) benefit/ cost (64B)benefit/ cost (128B)benefit/ cost (32B)benefit/ cost (16B)disk page read time (ms)'benefit/ cost slow disk (15 ms, 2MB/s)'benefit/ cost slow disk (12 ms, 5MB/s)(benefit/ cost slow disk (10 ms, 10MB/s)'benefit/ cost slow disk (12 ms, 3MB/s)(benefit/ cost slow disk (10 ms, 40MB/s) page sizeKBentries per pageFan-out Index Page UtilityAccess Cost (ms) entres/page utility access cost benefit/cost 20 b entriy disk latencydisk bandwidth entry size fill factordisk unit price($)KapsMapsGapsDRAM capacity(gB) latency(ms)bandwidth(MBps)DISKTAPE$/GBScanspd ref_intervaltape ref_inteval drive price $/MB_DRAMdisk Econmic ratioppmdramDisk Apstape apstratio tratio_Taperent disk accesstimecost disk space tape space$/access (3 years) tape accesstotaltape (t = (TAT * 9000 - DAT*2000) /size(13e-6)= 8e7 (9TAT-2DAT)/sizetR $gX?h_l8r$ɩrbZ+}  .MMN 0w4;T0r0`T0 x`T0Ir0&& 0@S0t00(t^n00 00Ԣ00@4C:\jim\PAPERSunit_priceateilizatonass Sort Sheet.xlsility Graphs.xls0ZT0 {0ZT0 {{L00{{{0]0 {{ NJT0e0YT0}L0@,|0@B<@B~0BT0L@B`@Bu0(1T0|0@B0@B 0E 0 F00FX <X0u  "@B)D f??iz3` ;` <` =` >` ? ( 3f3f3 ~  <@IH GHY @ |P ]`@IH ]`,JHEJ <1 min asymtpote<?Q8?03d23 M NM4  3Q:   ref_intervalQi ; &Q ; &Q3_  NM ]  4E4  3Q:   ref_intevalQi ; &Q ; &Q3_  NM ]  4E4D$% M 3O&>Q4$% M 3O&=Q4FA 13Ow T 3*(@@@0N#M43*@?? N#M! M4% } M 3OU&<Q &Page Size (bytes)'4% M Z3Og?&<Q <Reference Interval (minutes)'4523   f V @43d" 3_ M NM ] MM<444% p [M:3O $&;Q >Reference Inverval vs Page Size (DRAM vs disk or tape storage)'44 e??$@$@Y@Y@@@@@@@j@j@.A.AcAcAחAחA eA eA _B  _B vH7B vH7B mB mBe@8WC޳AVUUUU]@7xAUUUUUk@qknIA6@98^XAVUUUUU@qF@UUUUUU?qq@?8t@b/?rqA@D-ku?88@ _Q$r? qq@ -nq? ` ` @ q? zV4@ ,N4q? ;5@e> ;5    dMbP?_*+%"??U} I } $ } "  T0          G   w  G w w T0 f]Table showing benefit (log(index entries)) vs cost (access time) of various index page sizes) page size KBentries per pageIndex Page Utility"disk page read time (ms)benefit/ cost (20B) ~ @+ffffffV@CDC'^0@DBmBm1C6$@CDC !ḁ? DDrotate+seek(sec)~ ?@ D+fffffff@CDC8^0@"CDCBmBm18m4$@CDC !S? DDtransfer rate (B/sec)~ A @ D+ffffffv@CDC8/v݉ @"CDCBmBm1 qh$@CDC !? DD 0@ D+ffffff@CDC8.v݉"@"CDCBmBm1X$@CDC !}3(? DDindex elemet size~ 0@@@ D+ffffff@CDC8/v݉$@"CDCBmBm13ı.n%@CDC !ۮ F? DDindex page utilizaton~ Q@P@ D+ffffff@CDC8/v݉&@"CDCBmBm1fc]F'@CDC !)?bS? DD `@ D+ffffff@CDC8/v݉(@"CDCBmBm1Ǻ*@CDC ! ? DD               page size KB benefit/ cost (16B) benefit/ cost (32B) benefit/ cost (64B) benefit/ cost (128B)  page size KB0 'benefit/ cost slow disk (15 ms, 2MB/s)0 'benefit/ cost slow disk (12 ms, 3MB/s)0 'benefit/ cost slow disk (12 ms, 5MB/s)1 (benefit/ cost slow disk (10 ms, 10MB/s)1 (benefit/ cost slow disk (10 ms, 40MB/s)~ @!Ol? ? ЬD#? !Q? !S? @ D!)Xh?!ЬD#?!wu.?!Vi9?! @ D!hy+Up?cln? QT? !)Xh? !?0@ D!N=t?!QT?!u|є?! ?!0@ D!m" ,?1ib? Y? !N=t? !}3(?@@ D!0+|E?!Y?!T:7s?!@ ?!@@  D!La?ExF? }T=D? !0+|E? !ۮ F?,%|"".... T0!  P@! D !ك\3? !}T=D? !]5V? !?J>g? ! P@! D !ȀH? \V%? -w? !ك\3? !)?bS?!`@ D !!KIZJ?!!-w?!!n)脞 ?!!%Y~E?!!!`@ D !!2T?!0!V?! O?! !KIZJ?! ! ? (( @A@A (p ( 6NMM? <0]`D  "D??3` i`  `  ` i@3d23 M NM4 3Q: *benefit/ cost (20B)Q ;Q ;Q3_43_4E4 3Q: Q ;Q ;Q3_43_4E4D$% M 3O&Q4$% M 3O&Q4FAj* 3OLI > 3 b#M&43*333333?@??N#M&4523  O43" 44% k/ M:3Og&Q <Index Page Size benefit/cost'44e@@@@ @ @0@0@@@@@P@P@`@`@eḁ?S??}3(?ۮ F?)?bS? ?e xp ( 6NMM?" 9]`$  "$??3`  `  !`  "`  #` ;H$n 4V( P 4l 4 s *(a  @ ](a <16 byte entries<$^ff 4 c $xa ]xa0 <32 byte entries<$; ll 4 s *a ]aج <64 byte entries<$; ll 4 s *b ]b <128 byte entries<$> ll 4 s *hb  @5 ]hb( <32 byte entries<$^ll 4 s *b  @ n L]bЮ <64 byte entries<$^ll 4 s *c  @GR 0 ]cx <128 byte entries<$f03d $23 M NM4 3Q  16 BQ ;!Q ;!Q3_ O   MM<4E4 3Q  32 BQ ;!Q ;!Q3_ O +  MM<4E4 3Q  64 BQ ;!Q ;!Q3_ O -  MM<4E4 3Q 128 BQ ;!Q ;!Q3_ O ̙.  MM<4E4D$% M 3O&#Q4$% M 3O&"Q4FAX 3O+ 3 b#M43*????#M! M4% Q ZM3Oo&!Q  Page Size (KB)'4% ZMZ3O,&!Q Utility'4523  O43" 44c31 y?3O% M3OQ444% Q M3O2& Q n5Index Page Utility vs Page Size and Index Elemet Size'44e@@@@@@@@ @ @ @ @0@0@0@0@@@@@@@@@P@P@P@P@`@`@`@`@eOg?KIZJ?-w?n)脞 ?%Y~E?e xp ( 6NMM? " 9]@  M\\BARCSUP\HP1W odXLetterPRIV''''"dXX??3` I4%` I4&` I4'` I4(` ;H)` $*0 8( Z 8l 8 s *l[  @ h]l[, <10 MB/s<)3ff 8 c $[ ][Բ <5 MB/s<) ll 8 s * \ afaf] \| <3 MB/s<) ll 8 s *\\ %%]\\$ <1MB/s<) ~~ 8 <\ @AA? 2; ]\̴ $<40 MB/s<*1$Dll 8 s *\  @[C!]\t <3 MB/s<)+ll 8 s *L]  @!Q]L] <1 MB/s<)+ll 8 s *]  @  ]]Ķ <5 MB/s<)+п03d23 M NM4 3Q 40 MB/sQ ;! Q ;!Q3_ O ̙̙.. f- %..i@zar%KP)sp:"M( UUUU50% MM<4E4 3Q 10 MB/sQ ;!Q ;!Q3_ O   MM<4E4 3Q 5 MB/sQ ;! Q ;!Q3_ O +  MM<4E4 3Q 3 MB/sQ ;!Q ;!Q3_ O -  MM<4E4 3Q 1 MB/sQ ;!Q ;!Q3_ O ̙.  MM<4E4D$% M 3O&(Q4$% M 3O&'Q4FA} 3O* 3 b#M43*????#M! M4%  NM3Oo&&Q  Page Size (KB)'4% WMZ3O,&&Q Utility'4523  O43" 44c31 LW?3O% M3OQ444% x M3Oz2&%Q l4Index Page Utility vs Page Size and Disk Performance'44e@@@@@@@@@@ @ @ @ @ @0@0@0@0@0@@@@@@@@@@@P@P@P@P@P@`@`@`@`@`@eḁ?Ol??)Xh?QT?cln?hy+Up?}3(?N=t?Y?1ib?m" ,?ۮ F?0+|E?}T=D?ExF?La?)?bS?ك\3?-w?\V%?ȀH? ?KIZJ?O?0!V?2T?e >@    dMbP?_*+%"??lU}   T0   power file sizeMem Size buff Size~  @חA  D30Qq.RACCA@@"@ DeA  D3}ռR)kACCA@@$@ D _B  D3|dACCA@@&@ DvH7B  D3n6[ACCA@@(@ DmB  D3#ACCA@@*@ D@0B  D3ʆCACCA@@,@ DļB  D3I^(SACCA@@.@ D4&k C  D3|hn BCCA@@ 0@ D 7yAC   D 3 pg$BCCA  @@  1@ D  ؅W4vC   D 3 N؊!@B CCA  @@  2@  D  NgmC   D 3  ^YB CCA  @@D]@ ( @A@A  v  <NMM?P PK]`(  MNHP LaserJet 4pcXXLetter %''''"dX??3` *Y` U`  `  ` *` )PHP$0( @A@A $3d23 M NM4  3QQ ; Q ; Q3_  NM   d4E4D$% M 3O&Q4$% M 3O&Q4FAe-r 3Op 3*@2@@@0#M&43*@(@@@0#M&! M4%  M 3OY&Q (Size of input file'4%  rM Z3O l&Q $DRAM size needed'4523  O43d" 3_ M NM  MM<444% M kM03O0&Q x:DRAM needed for a 2-pass Sort Gigabytes can Sort PetaBytes'44 eחAeA _BvH7BmB@0BļB4&k C7yAC ؅W4vC NgmCe0Qq.RA}ռR)kA|dAn6[A#AʆCAI^(SA|hn Bpg$B N؊!@B  ^YBe >@    dMbP?_*+%"??rU} } } } } m KT0   ~ disk DRAM DISK TAPE unit price($)#L@@@@ capacity(gB)?"@~@ # $/GB!%L@ DD!%rqk@ DD!%Cc}h4@; DD latency(ms)$-C6?$@L@bandwidth(MBps)@@@@ Kaps9$yyA#D@D@.A9$X@#D@D@.A9$j}4 ? #D@D@.A Maps?$ 隙?@)D@.AD@.A?$0 0 @)D@.AD@.A?$C!?)D@.AD@.A Gaps?$} (?)D@eAD@.A?$u,zt?)D@eAD@.A?$q?)D@eAD@.A Scanspd3 $ @ <<DD3 $@ <<DD3 $Q΢?; <<DD $/access (3 years)3 $c-^=:DDm3 $(.9Y>DDm3 $\.$> DDm ' 88;@ @A #$;WA; 'eRC>    disk tape disk  tape  page size ref_interval ref_inteval drive price%@@%@ppmdram Disk Aps tape aps tratio  tratio_Tape~ ?+@DD D@<,8WC޳ADD D@<'у@D<m $/MB_DRAM%.@%.@%.A.AD? M;X@)D@DD@.A@? e(?)D@DD@.A@! $@> DD  ~ $@+VUUUU]@DD D@<,7xA DD D@<'O@D<m Econmic ratio!%`@& DD!%UUUUUՄ@ DD%j@.AD? 㠱bX@)D@DD@.A@? AY?)D@DD@.A@! $A@ DD  ~ Y@+UUUUUk@ DD D@<,qknIA DD D@<'Fs+^@D<m%@.AD? 9X@)D@DD@.A@? q-R?)D@DD@.A@! $ Y@ DD  ~ @@+6@ DD D@<,98^XADD D@<' Z]K?D<m%@@.AD? X@)D@DD@.A@? j}4 ?)D@DD@.A@! $gfffff$@ DD  ~ @+"VUUUUU@ DD D@<,qF@DD D@<'$t? .A  D + "?D D D@<, 8t@!D D D@< % ? .AD ? 0 0 @ )D@D D@.A@? C!? )D@D D@.A@! $zG?! D D !cA! D  +!"b/? D!D! D@<,!rqA@"D!D! D@<!%!?! .AD!?! bph>?! )D@D!D@.A@?! ?!)D@D!D@.A@!! $|?5^?" D!D! "חA" D! +""D-ku?!D"D" D@<,"88@#D"D" D@<"%"{Gz?" .AD"?" C(S?" )D@D"D@.A@?" {Gz?")D@D"D@.A@!" $#u?# D"D" #eA# D" +#"_Q$r?"D#D# D@<,#qq@$D#D# D@<#%#MbP?# .AD#?# u,zt?# )D@D#D@.A@?# q?#)D@D#D@.A@!# $'o|?$ D#D# $ _B$ D# +$"-nq?#D$D$ D@<,$` ` @%D$D$ D@<$%$-C6?$ .AD$?$ ˳tHb@?$ )D@D$D@.A@?$ ҲݷQ$@?$)D@D$D@.A@!$ $i?% D$D$ %vH7B% D$ +%" q?$D%D% D@<,%zV4@&D%D% D@<%%%h㈵>% .AD%?% K56 ?% )D@D%D@.A@?% J6, ?%)D@D%D@.A@!% $p.Yp?& D%D% &mB& D% +&",N4q?%D&D& D@<,&;5@ D&D& D@<&%&ư>& .AD&?& ~Kw>& )D@D&D@.A@?& >h>&)D@D&D@.A@!& $|(? D&D& 5 15 (t = (TAT * 9000 - DAT*2000) /size(13e-6) 5  6  6 = 8e7 (9TAT-2DAT)/size6 8 8 disk space8 tape space8 disk access 8tape8 disk access8 tape access8 8disk8 tape 8  18 (t = (TAT * 9000 - DAT*2000) /size(13e-6)89 page size 9rent 9rent 9time 9time 9%cost 9%cost99total9 total9  9 t 9   9= 8e7 (9TAT-2DAT)/size~ :&?,:˜VӍ>:D:eAD@,:KeU>: D:eAD@6:"8z?; D@D:D@.A6:"SZ>@J D@D:D@.A3:\k_>:D:mD@3:jii?;D:mD@:!:<2>  D:D:!: Ivi?: D:D:: :: $uB;$A D:D:D:: $333tA; D: < : ~ ;&$@,;y/><D;eAD@,;~b1d>; D;eAD@6;"({?< D@D;D@.A6;"A!>@< D@D;D@.A3;\X a><D;mD@3;i?<D;mD@;!;Tr@j> D;D;!; S,ti?< D;D;; :; $nA< $A D;D;D;; $4*A< D; < ; ~ <&Y@,<(X{;M>=D<eAD@,<">< D<eAD@6<"/r]?= D@D<D@.A6<"XO>@= D@D<D@.A3< ߖ n>=D<mD@3< i?=D<mD@<!<P>< D<D<!< UHOi?= D<D<< :< $OA= $A D<D<D<< $vKA= D< < < ~ =&@@,=1.Z -?>D=eAD@,=LFf>= D=eAD@6="ZӼ?> D@D=D@.A6="uq >@> D@D=D@.A3=>>D=mD@3=^i?>D=mD@=!=.pq'-?= D=D=!= Xd$j?> D=D== := $tA> $A D=D=D== $̜A> D= < = >&@? D= ,>༚xV4b??D>eAD@,>/<׿*?> D>eAD@6>"~jt?? D@D>D@.A6>"n>@? D@D>D@.A3>Nb)>?D>mD@3>wi??D>mD@>!>4b?> D>D>!> zuk?? D>D>> :> $z@A? $A D>D>D>> $efff@? D> < > ?&j@@ D> ,?ll?@D?eAD@,?ȝ%`?? D?eAD@6?"Q?@ D@D?D@.A6?"Q>@@ D@D?D@.A3?gfG>@D?mD@3?Jnui?@D?mD@?!?8(?? D?D?!? -X-.[u?@ D?D?? :? $a A@ $A D?D?D?? $33333#@@ D? < ? &@jjjjjjjeR2@T0ABCDEFJ@&.AA D? ,@qq?AD@eAD@,@9/?@ D@eAD@6@"zG?A D@D@D@.A6@"333333>@A D@D@D@.A3@Ú>AD@mD@3@M[&j?AD@mD@@!@SYq?@ D@D@!@ ێ #*?A D@D@@ :@ $3@A $A D@D@D@@ $> ףpv@A D@ <A&cAB D@ ,Arq@BDAeAD@,AX?A DAeAD@6A"Gz@B D@DAD@.A6A"@@B D@DAD@.A3A4G?BDAmD@3AfB\k?BDAmD@A!Aָ2@A DADA!A  xB.?B DADAA :A $Hz@B $A DADADAA $Reference Inverval vs Page Size (DRAM vs disk or tape storage)'44 eee ~v \ <NMM??J`Y]`Ţ  "??3` 2` 3` 4` 5(  ~  <I @AA? ]IȢ $<the<5$?3d23 M NM4  3QQ ; :CQ% ; :CQ3_  NM ]  4E4  3QQ ; :C Q% ; :CQ3_  NM ]  4E4D$% M 3O&4Q4$% M 3O&3Q4FA !  3Opz0 3*@"@@@0N#M43*@?? #M! M4% XmHM 3Oac&2Q &Page Size (bytes)'4% 'MZ3O&2Q 8total cost (rent + access)'4523   f V @43d" 3_ M NM ] MM<4444 e  e  e ~v \ <NMM?I YZ]`pʢ  "p??3` 6` 7` 8` 9` :(  ~  <K G\HG @   y ]`K͢ <2 min asymtpote<:N@3d23 M NM4  3QQ ; :F Q ; :FQ3_  NM ]  4E4D$% M 3O&9Q4$% M 3O&8Q4FA   3O%q / 3*@(@@@0N#M43* @@? N#M! M4% XHM 3Oac&7Q &Page Size (bytes)'4% miMZ3O$i&7Q <Reference Interval (minutes)'4523   f V @43d" 3_ M NM ] MM<444% N3M03O$&6Q p6Reference Inverval vs Page Size (Disk vs tape storage)'44 e    e    e \\>@4 44    dMbP?_*+%" ??rU} $  T0     page size KBentries per pageFan-out Index Page Utility Index PageAccess Cost (ms) 20 b entriy entry size~ 4@ page size entres/page utility access cost benefit/cost fill factor~ P@~ @+L7A`P@DD@D@"ѨP@ DBm'ffffff$@D@DD@!"@? DD disk latency~ $@~ @+L7A``@DD@D@"ѨP@ DBm'$@D@DD@!"c:? DDdisk bandwidth~ $@~  @+L7A`p@DD@D@"iTZ?( @ DBm'%@D@DD@!"q?  DD ~ 0@+ L7A`@ D D@D@" iTZ?("@  D Bm' 333333'@ D@D D@! "-z` ?  D D  ~ @@+ L7A`@ D D@D@" iTZ?($@  D Bm' ffffff*@ D@D D@! "2n?  D D  ~ P@+ L7A`@ D D@D@" iTZ?(&@  D Bm' ffffff0@ D@D D@! "j?  D D  ~ `@+ L7A`@ D D@D@" hTZ?((@  D Bm' 6@ D@D D@! "L? D D  .BABlPHX0(  X>@    dMbP?_*+%"??U  T0    year access time transfer rate 1K 8 KB64 KB 1 MB $/MB Disk $/MB DRAM   capacity (GB)  @I@?*3@DD*m۶m1@DD*b:!@D@D*yy?DDY@@ ~  $@   @9@@*k(C@DD*Lh/B@DD*` .5@D@D*5eMYS@DD$@i@ ~  ?   @@$@$@*+7X@DD*萚`W@DD*~ |N@D@D*/袋."@DD@@ ~  $@   d<0 ( =s0!>Jy v  <NMM?p ]`Ӣ  M\\BARCSUP\HP1W odXLetterPRIV''''"dX??3` >h` >h` h ` h `   (      T" WG0*?Access Time (ms)Arial~]`բ   p* WG0*?Transfer Rate (MB/s)Arial ]`ע3dQ23 M NM4 3Q:  access timeQ ;Q ;Q3_  NM ]  4E4 3Q:  transfer rateQ ;Q ;Q3_ ! NM ] !!4E4D$% M 3O&Q4$% M 3O&Q4FA S 3O\ _ 3*@@@$@$@@#M43*?#M! M4% & {,M3O& Q  Year'4% Z MZ3Og&Q $access time (ms)'4523   f  d@43d" 3_ M NM ] MM<444A S 3O3*! M43*@=4%  iMZ3Od& Q $bandwidth (MB/s)'43d" 44% VIM03O& Q 4Disk Performance vs Time'44eee |  BNMM? ]`Hբ  M\\BARC-RAS\HP LaserJet 4Si/4Si W odXLetterPRIV''''"dX??3` h` >h ` >h ` h` h` hv(     Z  WG0*?1 MB access/secArialg @ ]`ۢ   * WG0*?1 KB access/secArial|^]`Pܢ   ., WG0*?Typical Disk CapacityArial5A )]`ݢ   " WG0*?64 KB access/secArial8)]`ޢ3d23 M NM4 3Q: 1KQ ;Q ;Q3_      "4E4 3Q: 64 KBQ ;Q ;Q3_ $ ff  $N4E4 3Q:  1 MBQ ;Q ;Q3_     4E4 3Q (Unit Capacity (GB)Q ; Q ;Q3_ % NM  %%4E4D$% M 3O& Q4$% M 3O& Q4FAu 3OK 3 b#M43*@,#M! M4%  {,M 3O&Q  Year'4% ' 3MZ3O&Q *Accesses per Second'4523   f  d@43" 3_ M NM  MM<444Au 3O3 b! M43*???0N4%  ZMZ3Ok&Q (Disk Capackty (GB)'43" 44%  ;M:3O(&Q p6Disk Performance vs Time (accesses/ second & Capacity)'44eee ~v  <NMM? p]`ڢ  "??3` h` >h ` >h` %h` I( UCc?    2i* WG0*?DRAM $/MBArial ]`d   - WG0*?Disk $/MBArial  q ]`3dUU 23 M NM4 3Q:  $/MB DiskQ ;Q ;Q3_  NM   4E4 3Q:  $/MB DRAMQ ;Q ;Q3_ ! NM  !!4E4D$% M 3O& Q4$% M 3O&Q4FAX 3OZ  3 b#M43*@,#M! M4% S {,M3O&Q  Year'4% y MZ3O &Q  $/MB'4523   f  d@43" 44% #VZIM03O&Q .Storage Price vs Time'44eee >@  Jim Gray Microsoft Excel@7՜.+,D՜.+,h$ PXh px MSFTCh  Figure4Figure2Tape&SequentialTable4 figure 1Chart4  WorksheetsCharts 6> _PID_GUIDAN{9D8082DD-A3F1-11D0-AD34-0080C7F3EC95} FMicrosoft Excel WorksheetBiff8Excel.Sheet.89qOh+'08@Th  Jim Gray_936868491 Fp*Ole PRINTp4CompObjf( 4   z ''   Abadi MT CondensedwgwN  - Arial !w*wgw  ----- Arial Z!w*wgw Z - Arial| !w*wgw|  ------"System  -'- z -- mY !!---'--- z -  &- -&&- $DkbD-  $DD-  $DkDt-  $DtkD"-  $D"D -  $D tD} -  $D} ttD} &&&-  & $kCkCtt&&- && &&-  &&uDk&&- $DkbD-  $DD-  $DkDt-  $DtkD"-  $D"D -  $D tD} -  $D} ttD} &-  - -&-$kCkCttk-- ---'---  xCg CkkC---'---  z -  k kCtCtk-  kt-tt33  \\77``EE00nnYYHH::--""qqccWWLLBBuukkttkkttCtntn t tCtC---'---  lY !!---'---  dN---'---  aN--  < < ff00##C- t[[nn- |n|n- - $0---'-- -  aN $d---'-- -  aN<  $ (< Y< ---'-- -  aN $w---'-- -  aNf $I:ffI---'-- -  aN $---'-- -  aN0 $0rM00r---'-- -  aN# $#@#---'-- -  aNC $C`C&C---'-- -  aNt- -   W---'---  aN[ x>---'---  aN ---'---  aNn  Q---'---  aN 6---'---  aN- -  $---'-- - aN|n $ng|nY|ng---'-- - aN $ (---'-- - aN---'-- - dN---'-- - z --------'-- - jFj 92 _x!DRAM Needed for a Two-pass SortGGCSG77<7<!<&7<N<!<777A<&!12 Gigabytes Can Sort PetaBytesL<7<5!77G7<A<&!A7!7G5!77----'-- - z ---'-- - z ----'-- - z  2 I1.E+06 - 2 1.E+09 - 2 @1.E+12 - ---'-- - z ---'-- - z  2 t1.E+06 - 2 1.E+09 - 2 1.E+12 - 2 I1.E+15 - 2 1.E+18 - ---'-- - z --------'-- - X -- $2 Size of input file P7*.3333.-2 (bytes).'.*----'-- - z -----'-- - g  Arial{ !w*wgw{ - 2 zzDRAM size needed- ----'-- - z ---'-- - z - -  mY !!- -  -4&Nri- - "$Hc=61 )  2FHJ8D1O^L`HcN$%jK[+K ORZc+i:i8h5h0g)ebfiq y|#)~!~|y|7:<w(nlj m(pGmIjKp8"$%$!  \88=    !"#%'$    $D'*-/36:>@A@?=:5.*&$"  {"x#t&q(o-m1l5m8o:s=y75{2x/w+y(|&%&'')+-18<?BDFHHFDA=630.+'$IKQTWY[_cefeca_ZVSNKH}FyDtDoCjDfEaF^H[JXMURSVRYT\V_Za`^c\fZaW_V^T^P_LcKgJkJoKqLrNsPtRtVs]sardtgvizkllkifb^[XURPMK- -  &&m%}- - 8"ndzYvOsFr=s5t.x(}"! "$'05;HUbhnxxnngnswz{{yvrmg`YRJB92.,-~1{:{F}MU^ggT$(]? #    ,>BE2"&*/5FWZ]|8.  &*,,+)%   !!   ^8     8>???=;641,)&$!    "#')('%# ~ywusr s#u&x)|-26;>ACFJHEB??.-*(''(*+.1479:9851..$FACDIMQTVVU}SxQuNtKuGwA{=|9|6z2w/s-o+k)g)b)_*[+W-T0P3N7M;O?RCVAZ?^<Z9Y5Y3\1a0e1i3l4n6o8o9o;n?lEiIhLhPiSlWpZv\|^]\ZWTQNHEA$DZk\g]cbhfijimfobp]nXlTjQgPeQ`SZVVXSWOVLSHOFKDFCBB=B:C6E3F/I,M*Q)T*X-\2[6Y9V6R4O5L8J<I@JDLHOKQKSKTJXH^EbCfCiEmGpLsQvXw^wdujsontkuhuar^oZk- -  & - ' z  '  'ObjInfoWorkbook#|BSummaryInformation(DocumentSummaryInformation8"  \pJim Gray Ba=f=w<X@"1Arial1Arial1Arial1Arial1Arial1Arial1Arial14Abadi MT Condensed14Abadi MT Condensed1Arial1Arial1Arial14Abadi MT Condensed14Abadi MT Condensed1Arial1Arial1Arial1Arial1Arial14Abadi MT Condensed14Abadi MT Condensed1Arial1Arial1Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_) 0.E+00                + ) , *       `Chart2 Chart2 (2)8,Sheet1 buff_Size:# file_size;" Mem_Size; power;T 3  @@ >power file sizeMem Size buff Sizeone passn T*PП Print_Area_Area+(((g9w4((Ftw( : s դw bT00(4( ɩw bT04( \(\(3  b 3*@2@@@0#M& 43*@(@@?0#M&! M4% @m,M 3Ogt&PQ 8Size of input file (bytes)'4% }M Z3O ]&Q $DRAM size needed'4523  ) f )d @43d" 3_ M NM  MM<444% ;X) M03O&&Q >DRAM Needed for a Two-pass Sort Gigabytes Can Sort PetaBytes'44 e _B.AחAvH7BcAeAmBחA _B@0BeAļB _B4&k C7yAC؅W4vCNgmCe|dA.A0Qq.RAn6[AcA}ռR)kA#AחA|dAʆCAeAI^(SA _B|hn Bpg$BN؊!@B ^YBe>    M\\BARCSUP\HP1W odXLetterPRIV''''"dX??3` ;` U`  `  ` *` )` ; P(  Pr P 0H @ ]`HHR <One Pass Region<}#*3dI23 M NM4  3QQ ; Q ; Q3_  NM   4E4 3QQ ;Q ;Q3_  NM   4E4 3QQ ;Q ;Q3_  NM  d4E4D$% M 3O&Q4$% M 3O&Q4FA|X 3OD> b 3*@2@@@0#M&43*@(@@?0#M&! M4% ' M 3OG&Q (Size of input file'4% VM Z3O S&Q $DRAM size needed'4523  ) f )d @43d" 3_ M NM  MM<444% sX M03O&&Q z;DRAM Needed for aTwo-pass Sort Gigabytes Can Sort PetaBytes'44 e _B.AחAvH7BcAeAmBחA _B@0BeAļB _B4&k C7yAC؅W4vCNgmCe|dA.A0Qq.RAn6[AcA}ռR)kA#AחA|dAʆCAeAI^(SA _B|hn Bpg$BN؊!@B ^YBe>      dMbP?_*+%"??U}   T0         ~  @חA  D30Qq.RACCA@@חAD~ .A.AD"@ DeA  D3}ռR)kACCA@@eADcA D cAD$@ D _B  D3|dACCA@@ _BDחA D חAD&@ DvH7B  D3n6[ACCA@@eA D eAD(@ DmB  D3#ACCA@@ _B D  _BD*@ D@0B  D3ʆCACCA@@ ,@ DļB  D3I^(SACCA@@ .@ D4&k C  D3|hn BCCA@@   0@ D 7yAC   D 3 pg$B CCA  @@   1@ D  ؅W4vC   D 3 N؊!@B CCA  @@   2@ D  NgmC   D 3  ^YB CCA  @@ K ^0(  v  <NMM?P PK]`R  MNHP LaserJet 4pcXXLetter %''''"dX??3`  `  ` U` )` * ` *Y PH@0(  oF3d23 M NM4  3QQ ; Q ; Q3_  NM   d4E4D$% M 3O&Q4$% M 3O&Q4FA* ] 3Om 3*@2@@@0#M& 43*@(@@@0#M&! M4%  M 3OD&Q (Size of input file'4% FM Z3O R&Q $DRAM size needed'4523  O43d" 3_ M NM  MM<444% T `M03O$& Q x:DRAM needed for a 2-pass Sort Gigabytes can Sort PetaBytes'44 e  e  e >@  Jim Gray Microsoft Excel@f#՜.+,D՜.+,< PXh px MSFT(  Sheet1Chart2 Chart2 (2)  WorksheetsCharts 6> _PID_GUIDAN{21AA34A2-8F5A-11D0-ACCB-0080C7F3EC95}Oh+'0,`l      $In 1986, Gray and Putzolu observed that if a page were referenced more frequently than every five minutes, it made sense to keep the page in memory rather than reading it from bXȘEEbu1`:;l|7wј-+yܬXx_оl?ʓ2ɡoV~vT Z]y"aiǓ N'n{>a9h&fV%ؖS2Ɨ %By8vDjrŰKh݆؅=||œx3e^Gu[G]IԷ >AE/4Gv>55[jW #. $I'Nحgum Թ^(2O4W(|Jc-  }@%3G dalD@뙍fv Y3!\b-6H؄fٌBJ] C(_|v v,Ƴ?<;ǧ@m!6Mn;ޭh鼚|Nl:sICk0 GY;C|wOl4B iRc.>#z|C{~/V=f7KF&+ِ! ^½ 9\79to\N;Zh'A?OrjfK!]Z\;0 k`z@{#l=v3p2@VƘ& t2% +  `=cL!:;gcafO&.Z#T颧q d<ΞqpJ˱pJa3dH)}'?sW;SgOr=5s\):^`q\G  (c(Dq? xτblz.)!k)Q8[8ܡoUA :Fw =:@]!n"F0{U0uS{AX7C Q{05jt^+^ ۇ~|ul!쥽[c:K-ng yV 4ьwnw b -Fo9Z`_N>25Qcc7Nxj410VX `%f1F(GpZ,İXA#-Dc03b #wo}4qr@] Ԙ\Siuи@Xt#xD"?5!|&16V3xf1H%ѝݝtם<1$$|[~9{'ɮ]; ^m{SAUWTSD $Lu$u67ޕxz 9|(Bg>΅dye/Gs._PDnBW1Pe!JƧɅ<,f[ecof eB=j#L죚~ S&G뙶g^}$)_#G(usJ%Qe!ˠOxgϗ#%Zy]49ѩ3:3)3)-Kr$wMPΘwgBX.gk ɐ"rqƗɧǦV'j-'G K"瓗Ƙئ 5BP)S!!!CX|+OTA|ڴ7VY\UrYUD_]h'#KናLF\ UX1reUrM\4մUq &^ ~jU] uB\9iS \-kbB; :Ha\cF'2鯗Bu݈ŋd(kz!XQr'$؄-C0Na܄9wp'zj6t+ưLF[<:@4za)s,H7o{k SD(OQÝ= "$8$p5voX}X'wʽJH=>/=ºQ5Wbްںެk nWg}7=~:oU_{7o}|UShuߺY8[])iόLFU3zT=f?Wm9e5oOH=e5o# ofm$1H Y +6N1o2 ʬ?ʬ?ʬ?VaeF+İ2k#aXNJ6HcVfm$Vfm$R +6XYʬ?VaeF*1HcVfm$2\rj +6Xk +6X g}v^4Hcm5Hc0HcdXkX:`Xj5HcuVfm$Vfm$NVfm$ +6Xg +6q~ͬ?ͬ?xu7!w?W6c֣Q% uzX:e<#Kߵ:?w=S:;G2ޖwu:A^^'Q?=nYGGG <:QO=8ڦ'5cow6Rw{NM}vu>R9]Ǻk>>9泧,a=9 htMϚWQjݾ#kr챸W}*U5I5XsT ד*]V}]?QtLz1>?)`p,,TtL_c۹,؇s쿞\Fts\rćpĿ\~}WJ|%VJJծ[:kZt6dRXVu3JշDk%;ٝU~7_otp3ҝE'e/|у|OPk<ލj@7awShƬYs=dנx@y+#zSTx; WPϺAgF|OGLQ\Sɞ/aW(T,YG[s+%fĮN%u}Ut룬/V ݞn&6Ugu>w.lUS}ƍ*AYFS{sR*%}=N5}1'ț.Yw}ҿKׯ)gugp .PP N}"? لZŇI*:behv #jޖJI^ӴOB`JT$ R7UuښRXm*K^O&;jb* !r9,Gֹ!m*1a!YA!sQH0|F9Jd` YȆAlf_ӄn6g?=IJNq8GCȅȆ,䙐q7JjQ/JX~rS|S9cZѴ`ӌA&4߄~4BG^G]-#&ȵZU-Ԓ*ƭ%ϕZj!hÿݡ4G=~C\=mpXFXZȺkM-ZeexIY=#Nmb{Y+}m赡jAf(݂Umbl,@"6zkP/&ڛmo #,|7 /a2&׌N :n3Ƭ;v/{T ioCHV56kF./!{<46tkv;a'15{'6񻋱Nk;g'=w{ًt1Mf?^4M0{WdA#l-5l"&l7c34[m#2}Cj;f4~8@.ݪɿq43fo?4>؋=[nvCl Ol;0}D Ȭšl #8h2ڃza#z6mЎt۱ѴnCvZ}Ͱ pXئ6 [ Ѐۜuo˛u\ϐr?8d>d$VJUjtWb*W*߇h]2y8}|~_+s :=QFXh#j5fL5̚f ӑMo LBFkMssyxZtkaW3ai9B5fYUS8l-@aC'ǹX!xkSj,E $r 5&̂SD fAD " kЛ[ qlc LBG<D ,0梫hg1" 䠙3aLG>MXD a0O%4?aⰍG 1(bDDA#H,a|(CαOcG4㉂%5El<8hƓak0 f^ hϢO3SbG4S;ifLgǯѶaLX {4dY`u3t/eF2FÊi4Yn k7k,l*}Йf*S$/mB0dSYULc1TV+X<`A6:F7؍~e#˂L`?y:٦mfm1%d$9i^<1W.r9/ J)y'|  CgñXq< /_!E,_-e%.#qF[ϩD&¦V"[IJ2`*"p b*TA FR*g ſM5ga ja[LS lF (tlVB-y،e2Ӟz,}?h:a k0x7YhƱ* chQBg0 0x 3iilzFh@z CazC V, s.qX ȡFhM"zџ/s>-ng#7Z?cyxdCyBVG#aѬ`F͊f0fY !ڞi?$_`;@ىNtwbCx'mVixar/`9tENmb d,c߱n ~Fh̕e>aFnŚek O@ tcKx{3ȇ3a0?#`=}݃M~1}ދ=_%<%zU8, ,a1b럡'a0{5c==a0~OzO/)CYt\PIs{ c¬ !V)V AhCT@JXAzؔc?U*g#xJ:g0Ca1H_z ߅ WE&_<cg qe? y:a<J!%jX)~4O9㾏>Y,D3}$0QV9;tw4ܱ hqw_yzZ_lVHu(q'h)J3h2d)=62_g͆e?v>pW)R(c*_^%>*Y%4B>t4ِ<KC? 4l7m}UWM9læJ܋v!W1+}v->k :u^ h"[IJWg%>kɫr&,t@iMdB~kiA*TRO.TrKt̀LȆ\wPĽX'uBW>rwSE u2m[#x7*.@V6a"lh 7y#i`D97XIoKD? dS٦I/)itb?y>ƛn%ِ,{^>|uyrEA2$![N2 %p\rl & y"$bmS٦9碗~ِ%yi̊CY#p=.Z*HdRqǡ2l Yhb^Av>į& y}~ӄ}WbX Q4޿5Z֊CDkv R KB' $lf6`)ijB#ZEc5ma*aKVi9ta8L>!Ì0CB r=~wFbyLHTpWᤐND;IWcdvTXJxXhO]M$vGg 41«ؽv'9Ev>8dx8W$9ir;M48ŨO2; 8ǐk߯_iۼAox-%s>O l/ }G_:bM:C3 r9:cE@8}aY+T8\D~K^Apβ KќĽyh&mq\bL9.0_55C|!%ޣ.ߡmzqk-FLBCdlЉF'V2\Џw+\Vv!Xa!z51WD Lxo'#W)|f-B?@ W0,Y0}A§p?!JOċFIs3uԚiZ߷~ߺZw77f7rOM{ _{&7ۜm@!.@N':okkC C!^V._@6@]&n6@=ݍg ofmsV# +_!|0ְ2kCc`X!ka6X3 +6Xs +_!|ZhX!aa6X!Y" +_!|NJ6cVjCܰ2kCWm߱ +6qeVjCoX!*6._| ?&ʰUwY +_!|Ǫ7cm4|Նkaeֆ? +_!|eX!Wm߱ +6X͆cVfmsxİUw㆕YNVjCF7볆76.]Ûs>F)rs;[jCLt=\}MV6D'J!>'6QuG-9ieYG6#=鹸#U3޳sN@nV޳kc p^Sc]yd~w$twXݥz>;-jK1M-qt~VqAtyj:^K ޞ7S* Qp:wzVn{~Ƞ>x=뜞^~23tgE{VnJV vN]w<+qWJ,xs~?4P}Kf^x>E˕{>ٹ^s@sowz3Mu}s|`Q\{zgΜoZjP]jLms.XtWv~+q U P `5:XZtת\[[ৎ:tV*PU@2lJ-%R)#r+RiW!#mhɭm_s?q2}0f6wfFۂ!hshGցM9eBVhf8(ġtt=M>6CBmZ״nƏ >Šڠvp|l*`T" jl9xSzL, $t,VGuҟ2S9Edq cd̏!; 1_ϺR՛[8u޵\"CROP\Qlg W a+F=2|ו~STuѕSS_/ld+B} s%O*Y} կ׮XxX 合^6OsO(% N& 05m|L)>#kB:y0XHEı ,b)Ko_1>5s.+*׉N2O43`&YvQCA""yKЉ&j,Qb I#$," wxR䤢02ZѲ9̑5^.W|(U^!) |yeClWt|YĴ|*!Z1QB9W XPUdPŵlXuP} 0g5\ӫɦ ^Ũ*a#*#VC)veP XW|PPeKXcJ_ :)'c&49$з] (GV*$?ϵdkjUdP+xOk񳖱As:sV c=w QȢiǫM"nU~=WO_=cY'm#߼6bՈV## [6ixAţ,~MEc&W@ta&@hmlGww܍ Dzz G7!'ydq,E7rAۂٌwc.b}Gӎ%-_$>u:Nfۙ3lrw;>g{uzsW1Sp,&DdQ'<  C A2錈"8'2 r:>A`!j錈"8'2 fa';8x\UݽBz+Jgp;XBH@6m1Z($ii!FJh&B[CI)?%(N *ȶߛy͟y7;{7vf7ޟ޼4d9H׈ Mx +\"7)Y#k2]jMN:]Y7tjZ!i)^s`[qT\St}3cj>LjxwfF kW K~?s?>CCyxcM3Ί%=\mnh3mzZQO-33GcBu)ʢ۶l4`qs?zFG;_蹔L٦Ϻ+T& Z4>nTG4-`2JfI݊I/ѣG,64M%3 -Mh:!`20EZfr2WdI=9syrRYiOOt3!Fm$[M$ːF+5[)غux2d3Lθ3J|fVUO! 'Mx"\jY~?M~v46#>6pi~t܂}8 ނ=ڎᯈE1ޢOT݋mqp cJDc6\/gP!g+m| ppU>uӬ&P+9>W2nublҵx\AA1_`~P_wd3dF"Q_k:se'IvdHdHdI!Yd_qٶfذ\vqD7=_B k^枡º¦-ݛ7j׷nĹeڀ0R"*k&ڞ&ٕjnWm0lXۭuC6yOTm漸9Цd諅sz7m oWk=*k?-$m)RJʖ0m)wPJƖG)YJ=;ݼYovYS=\Zl;=n͹Bk!2mjO _S,#j#mцG*ƅ*F5 kn66zZJ|Wcn.q_2+XuYld{HdGHvdgHvdLucFkeg̾엷S۬Nk?ޏ>C>:axUcO,n<{F2V%VMe`i,c^UD00w)s?bvfU7_̴ޜȦכ^H9uBNzTW5<͝S?\ʩ NM%f 9u@ʩ9D<_uˀSsĩXJNćSsĩl걶>0F2NXX2©z~Gox4-ԼSu:0TΩCȩ_pT]މeX;gռWWh |2L^0wW$_51˘u`h_ FJv˔6x/vqmjVZeiwHE$àpC>HAaG_@<HL*LLc/e\;z֚.>YݼIMk_R>Y' =+J`Z/]ׯ+l0U{\C>ݶT.s]mFC Z=q/jEWA ܛڲi{hæFõU;Ǝ&hzʸ\ymsmgXZmm6vC<6v8 {;2J̼!oC dT;ws_Z ZcKbnȦi;ƻ6ӾЈcY'B:J4t ǫbvbgھrG1XGPdz.L[!7ؘVV,L%& B]_ -SR2Kq<Wm |71qq6U,AD]$EQ,O<2$v񷥚+X[5Rerk83P쫨mFlm9Bmߋq]sio=|>oQuhK,J`v[qyx{l?wY)BF>|Vn8lqw6V6jV\?kjo~yYR 8}u3GQz+nEi#6\⊘p JyEg1gQߓw߁<\at՗ye Ǜkhy~z_|Nb~|/bWee{|{+etˬF?8C sS9㰗Yωtq$A".ldyI!YdbfBphiۙuU9Fvn}̍jnA Z̍ ^94:|5#nD,zQs#tVozJN+F_Yrq{maZxG)o㻔bR6F(ocdK"qh)ѫQ~K ^'#qM_$m~Kn6E∴r7~x8ۙHi'l\x<vˬ\dAOa#1Mld]6'Y?ɆI6L]QZٳv*f6O;3 ӑ器m!znf9fF͆-LV+xv3rl|26D_:VˊE.{wPScGq8q'Ꟑ">+g@ ^5pC|!Φ@eചj]ɝ*Ȭ Z̨F}c2jV v0vOAu=>O bv12F"FMg@ ;3j@11_^ÈVƦ]Ħl0w'"ii*6-3Zߦ]26M)jTOv呻A6uRdSu]R% Ȥ=R&548)=R&%&Mec@I{ &ex"䛦hÈXƦĦl:w"bg6Dr{O:PGy?ZzQQa u@ʨ9bd4ZeؙQl[V1wel#6MSeXƦ9bDZnÈXƦ9bxS} މel#6ӈ؛iS=wVkR6Si40i4/eAbDtjAOU=_&Վ=x"1 1j< ÈؙQOشIMMdk=?'ϳ>Y(Kleώd~DOle$#JW}7F?U.P(U`>JW}noVW>ݽQN}Qʷc/Ki·GjjtIdeoF˕ X_I'ze QZ=g[ީQyŊ٣/&e:r;\V$VZ*r;1E'_7Xx -ax9չs#xu{^)8N¯:m `2`)>إ'117c86S+t OtDd:q<  C A24הjDTRxv`OA`!4הjDTRxv*1  uxmlEǟ{ݩb)UPy 1`Z@? $5H J(~ AO)B)c ~8bm5FFCEj"Xgvw{wtng}:@`x :#\ ``8 0 6nd]rՂYc%/nkn@&3GnI*,Q\FWSbC)Us+>Ő7wcNa-βccLx 0ܲn MFXC2\I &"IUF&ɳU{{1Ņ=+]E5RQ8;7% E ĝN|U;nJ}䆑\w {]A^Fm{W uIn!p/֐;~Iл@&{κ!=?%p$B>u]6_IAI=@C~Km] uEZa${=a]$W=EYAWI{WanICEi'w{a2uAZ ;w6ea$W]@~eֻR+' +/>iWKr(FS+|B~b*1O&p%suFP+z6INE ]E Kp[69lMV8oaXuʃv$}cN`V zRΖ67'%NQZ|GN{T0lTUv\7cU #_omJKҜq+76MYk ud>62C)rރJ*.Q1wɣaNIS3r{\ã|:dڐ*m 7TY,U^ru1G4_ Ohǵ5Y _bv/9K'k =kD.C;0܋i(x3iwz0jx_[hʹ,geWۨxQR=>vvln aS3qX>Nq37oɿ;oObMBZ|q5E;3B;#&^ x٩廊C=|9`՞?ֵ {Ĕ2dj2^ԜoμδGq{L(G#nWε&Vfֲׯ@K ~75z)LHdYeDkߗ *M"IH"=Z<n+Wtj;LLߘ455iOVocҕ䞉,FIl-b(& fNN5[破ADz/>Rt|to_f6X ֐5tu7+9!).iO>^|eA|"8'e&xW-K1El_llߢJP&B⾬ln.񣍢 UQQUAUFٹzF` FH,"Eu"0BqBѨ\}uK+ UQٹ5\Ns]FHv`ğ5Mڹ& 5 Ԩj;ם`DŽQ۹f^u/!wBѨv9`?5_ڹ"BdZFH|AFH|MG5jQ0BB-֨v`AB-Ѩv%`rXQ7عVebFsVIk2Nع)$OXQ7ڹ+D5f;WBH%{Fع6*D{7k8;f8-ukBH5je {Fڹ)ędoר:;vL5BHt%{FεC!$MNfکUdQwعUd֨v !ћ4j=ukBH!CBzL|Q\)D5{5jkBH\Ngu3@>cڧޯQs\Bb0ٟk<; !14j+Fu@!$FF-s}"D=hcNiT+%!qX0B[i#vV>Nhq}>^udQc8Q0Bb*U.!1S5q;ש3o>;>C=3#$fIc$!q/]4j`Өev#$]o`B{Җc!!@v/Za`ģd_B>d_K[i%dWObtiXMe.XGv]j{l#$֓}u$K[cm`Fv`fFC$=\<\0BeGFJ)'1>dg"`dD5};Zgxկ@ eεVNE(CX6xN^'3eЧiB)83<E5:VUQ[ OaJ )="L\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nL\nUgbpk}&.g*\3L1>[3qbpk} L1b+\3Vgk}TwZ~/ټ'kvO2S|i|b~J1x' K,OEQtR+}]ѷ%#ڒoTC_u}F3=?)sɍ]&vD,] i`LEkh|%s_ {#57=M}BߨWC_5Μ_}}kCз' }6=Q>Q*)#)7NgcV8IzqtYv/rF{ e~ƹpIA+͙53cЊX~)br;ZvdL-s,紊-XVK,1pWLlÖX~Kk@LuXѪkV`Zk=GXޥX^-=X>X>-}XX>-Xs8[,ުXNXZZ8Xz[T_vz< uXhO,-s]yfݛiO,-s]yj^ƘbYlSu F1Ų2וo,bc)b)ls8LOd -KTגc>zgju%ءpb/?)ƳMŴ=V%8* dJ3(Khf_ٞ V|Mǰ~f²nlA)8]>}cFn#a[{-Ti؛m7;v~ qTB wxÄ ^K n4j;C?ۨ^#TšbC'`McK&|U1wY Gy[3h4f\o q).C/\T5^2iG`(biv7}OidN)I5`fL/q}Ofg*' [illMxb[,=m>Xދ-۞ S,mOD:Xl{&H,hvV+Cb[;PIBb m bžLsbž&k=S, .X{ߧW1cž݀/h7Xl{ H*X9Kr? <5GH޿;G^с2[f*uJvS&W\3Lŵ52"JI$}+MԱz*0jof򸊉u'e*&M%.)mA;S]^2,/ n9]~;ml{U<o4.Zڎj?_Imy*(zq*"ANM#?gq+? u( Ӳf4~iq;؋8p8gu] ZR>EH}/O|"C[M ɗ/mKF߆m%IȽ ywxyOt!8;?b:t5@OYϢfOȞ~& ?F=~ZDi9zJ#UZXE)Փ[OS{CIMmj ELyp=!`X7i0r+Qw*=jgx=}m'i+(OiB=݈F`-獔j𜟶RڭҍF?SNOGnO` S{WfOx!޽~~n1 sv,(;\)mӋ^m~MAkJ tN?m~:*&Õiln***FO}Bݤu}U%l J+VlΉ=pM30^!DdB  S A? 25/ ׇ(ggA`!_5/ ׇ(V95d8,-xś pTǿɒjYR[ǎϪ>:iv&`P$51! y? m|Q `VN[GIwnr& ܻ %l.1Anh&Z-`ND}38YěGtD[H'r,%/Ew~,tuUclzs]&?F7F9Wt\'DEK!/Lw,\='hO]8J2oynWĺi i)LT1izX Sewqvf[V#Z^DxaULlaUV}1r%Xվډ-!zz-%zjXaJA{Z#^b0Z#րXL?S1b}&aJG;`\b +'VoLju\kaj5#֩-43lbPwcĺ°EjѾ^ޏzajG;[#Va0H>ka0]VƈUa"L{n5jX 9tgh?qZ-Ӽ>ۋ-\+uLrk[͹X9o9q8Dꛯq'3Nј ?/f@z;"W{.I\G%GG%O>*j_}}'}Ǫ}ڻ; 6몽>[ݪTmj;TۡvնjϩjϪ֫Zj[U۪ڃ=ݯf6֥ZjT۠ZjSmj֢ZjuթVZjUVZjvjwVZjŪVZj6OyUmjYe6[٪ݤMݨڍTmje6]]5]ڕe4զvjvjZjsMD}r!WkZj^=tk@Є jUSOZi':wc^. '[JFswݵ)_J>Erk0ES?;fVKxT-qKG=<ƿy~o_hœYq]0e_Cq{ 8c}B1Ћ)'t ZW̘6= ]04+te-,T&DJW*+EHW~N$^E 椈2^^ #O9*gمY"t]vYJ?jc޸匦F:rpc3ҵ~8~$y-9?g8H D\񋇏1~ιG{Msj.99K5wΙ;0:~x7~Q<ϹS31bKLy fr߫GIHIg~[1,3o8MޛI3 ̜۳CysB9 ܚD|ޓmuMW8# )?$r=M8 C}ϯw%%kowL鏼v];X9o>oRl2|fhN[l}Nߥ:^Vgѳ< (adQb)RC4!y俒r#*nx/`+ѐ&bW;C~6co8nB~g~уԉzz6#b_cF!}(=p|[c'N`#=O wG!m ݠ lO=u`$ƟD')E?Zz?B{O/7a|3GO4F7@y< lw@ob@27Z#g)ˋ%jMvR+X߃ka َ9/ȼ VA^ПLB\߇{s/ap/}wa.?6a^S@#1i]3hŸ x5{^iMȕigMk0sWnahk>^9 ۯ@r4m_hW-ׅVא;*؏+BfAfѮ簟jWԂ:]j1:e|][^ׅFz84jײ Vcj1dr..9B&o  ȉyDPxL-⭴ԀjhUpљ7TjSVq&o ,ԃhӌy-;YAΒN3/Nxz̻/RNYY٨|sP0C}C <\[-`쇹5~-A.ڹsa;>ns |C7`A!\+W{MnM|Abl, 1a6/@H|p`lYrM`3Caǭ'~ -Ee 8K%}v`~փuZ;jǜcNab-Kv]a @>,q!|_|OTBT\pU.Wqvs'^O|wwb(Fb,bvT;dnhE4CoxThH-hˆ]"G9|c˄5T }7 K sAJ:K,7,]cEW3w (!:g3rn;D]2[&96K c*s(C ceK&ǡJ>? BR,re9z}fj[5Tbvc̡ TW)|zrhB5<25Z+A-zox5I΃{NV] xΫޘ*;RTxUZ ,LJ*l,*q*r@✵R=kiܾ*#XRm3RJ{f@5AFuVRV8*{qfnf^r1Table>SummaryInformation(*\DocumentSummaryInformation84CompObj@jdisk each timen 1 Jim GrayGraim  Normal.dota Jim Grayta7m Microsoft Word 9.0u@d@bм@*B*ph Z W {34567Z    W {34567:      Z)YQk1YLN9vz{ M m n + , '|}PQ"V} !!t"""""" #$#$q&r&' '())8+q+ --A.B.0-0?1b11=2)3c3?4C577J88v9: <=0=>>>>?H?}?~??@@@@AA%B&B'B(B*B9CDCE FFFGHHHHVIYIZI\I]I^IMM5M6M7M|M}M~MMMMMMMMMMMMMMMMMMMM NN&N-N.N8NANHNONPNUNbNkNtNuNzNNNNNNNNNNNNNNNNNOOOOO%O*O+O,O-OOOOOOOPPP+P?PJPKPMPPPTPYP^P_PaPePiPnPsPtPvPzP~PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPwRxRzRSSLTMTdTqTrTTTTTTTTTTTTTUUUUUUUVVVXXZZZZZZZ000000000000000000000000`@0@@@@@@08+8+8+8+8+0?1?1?1 )3)3 7 K8K8==@=@=@==@=@=@=0FFFFF0@0@@0@ 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000@0000000000000000000000  54DTP_T_pa268:<>FO -0BK|RRR8SSS*TTTUUUUJZZ[pa3579;=?@ABCDEGHIJKLMNoa4/:\ s u {:XX:::  ?2$9H2) EF 3#A2$=,S03#A2$u2tA&/ wGx5A@H 0(  H (  \  S A ?",V   # "7  \  3  "-  b  C  333"A  V  # "$ V  # "! V  # "  V  # "M V  # " ' H  #  B S  ? "':?(BDCZ}3#CT ##P5,HZ4 T%4pT 4 TTd T %4( T!',=LZky 3 M ^   \ i~Ve}t""""""""&&12)39344 55%555777777J8Z8b8r888FFHVI]I^IN!NNNNNO OOOATHTUUZ 4 < a h in yX^""""-- 22<3A3c5i577s8w8??BBFFHVI]I^IJ KSLWLLLOOOOOOVVZ333333333333333333333333333Jim Gray?C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5-min_rule_SIGMOD_DRAFT_2col.docJim Gray?C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5-min_rule_SIGMOD_DRAFT_2col.docJim Gray?C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5-min_rule_SIGMOD_DRAFT_2col.docJim Gray4C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5-min_rule_SIGMOD.docJim Gray4C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5_min_rule_SIGMOD.docJim Gray2C:\TEMP\AutoRecovery save of 5_min_rule_SIGMOD.asdJim Gray4C:\jim\PAPERS\KOX_MOX_GOX_SCAN\5_min_rule_SIGMOD.docJim Gray=\\research\root\Web\External\Users\gray\5_min_rule_SIGMOD.docJim Gray=\\research\root\Web\External\Users\gray\5_min_rule_SIGMOD.docJim Gray=\\research\root\Web\External\Users\gray\5_min_rule_SIGMOD.docc# 3& ?1 *hh^h`. hh^h`OJQJo( hh^h`OJQJo(3&?1c# @h OJQJo(HUIVI]I^I6M7M|M}M~MMMMMMMMMMMMMMMMMMMM NN&N-N.N8NANHNONPNUNbNkNtNuNzNNNNNNNNNNNNNNNNNOOOOO%O*O+O-OOOOOP+PJPKPMPPPTPYP^P_PaPePiPnPsPtPvPzP~PPPPPPPPPPPPPPPPPPPPPPPPPPPPzRSSLTMTdTqTrTTTTTTTTTTTTTUUUUUU{UVVZ@@&''T'UZp@p*pX@pZp@UnknownG: Times New Roman5Symbol3& : Arial"qhDHF ;Y20dI2QIn 1986, Gray and Putzolu observed that if a page were referenced more frequently than every five minutes, it made sense to keep the page in memory rather than reading it from disk each timeJim GrayJim Gray  FMicrosoft Word Document MSWordDocWord.Document.89q