Article

Free access

An analytical model of the working-set sizes in decision-support systems

Authors:

Magnus Karlsson,

Per StenströmAuthors Info & Claims

SIGMETRICS '00: Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 275 - 285

https://doi.org/10.1145/339331.339423

Published: 01 June 2000 Publication History

Abstract

This paper presents an analytical model to study how working sets scale with database size and other applications parameters in decision-support systems (DSS). The model uses application parameters, that are measured on down-scaled database executions, to predict cache miss ratios for executions of large databases.

By applying the model to two database engines and typical DSS queries we find that, even for large databases, the most performance-critical working set is small and is caused by the instructions and private data that are required to access a single tuple. Consequently, its size is not affected by the database size. Surprisingly, database data may also exhibit temporal locality but the size of its working set critically depends on the structure of the query, the method of scanning, and the size and the content of the database.

References

[1]

A. Agarwal, M. Horowits, and J. Hennessy. An Analytical Cazahe Model. A CM Transactions on Computer Systems, 7(2):184-215, May 1989.

Digital Library

[2]

L. A. Barroso, K. Gharachorioo, and E. Bugnion. Memory System Characterization of Commercial Workloads. In Proceedings of the 25th International Symposium on Computer Architecture, pages 3-14, June 1998.

Digital Library

[3]

T. P. P. Council. TPC Benchmark D (Decision Support) Standard 5~ecification Revision 1.1, December 1995.

[4]

Z. Cventanovic and D. Bhandarkar. Characterization of Alpha AXP Performance Using TP and SPEC Workloads. ~n Proceedings of the 21st International Symposium on Computer Architecture, pages 60-71, April 199d.

Digital Library

[5]

D. Dewitt and J. Gray. Parallel Database Systems: The Future of High Performance Database Systems. In L. Hongjun, O. Beng-Chin, and T. Klan-Lee, editors, Query Processing in Parallel Relational Database Systems, pages 4-17. IEEE Computer Society Press, 1994.

[6]

R. Eickemeyer, R. johnson, S. Kunkel, M. Squillante, and S. Liu. Evaluation of Multithreaded Uniprocessors for Commercial Application Environments. In Proceedings of the 23rd International Symposium on Computer Architecture, pages 203-212, May 1996.

Digital Library

[7]

R. Elmasri and S. B. Navathe. Fundamentals of Database Systems. The Benjamin/Cummings Publishing Company, Inc., 2 edition, 1995.

Digital Library

[8]

A. Grizzaffi Maynard, C. M. Donnelly, and B. R. Olszewski. Contrasting Characteristics and Cache Performance of Technical and Multi-User Commercial Workloads. In Proceedings of the 7th International Conference on Architectural Support .for Programming Languages and Operating Systems, pages 145-155, October 1996.

Digital Library

[9]

K. Keeton0 D. P~tterson, Y. Q. He, R. Raphaei, and W+ Baker. Performance Characterization of a Quad Pentium Pro SMP Using OLTP Workloads. In Proceedings of the 25th International Symposium on Computer Architecture, pages 15-26, June 1998.

Digital Library

[10]

M. S. Lain, E. Rothberg, and M. Wolf. The Cache Performance and Optimization of Blocked Algorithms. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 63-74, April 1991.

Digital Library

[11]

J. L. Lo, L. A. Baxroso, S. J. Eggers, K. Ghaxachorloo, H. M. Levy, and S. S. Paxekb. An Analysis of Database Workload Performance on Simultaneous Multithreaded Processors. In Proceedings of the 25th International Symposium on Computer Architecture, pages 39-50, June 1998.

Digital Library

[12]

P. S. Magnusson, F. Dahlgren, H. Grahn, M. Karlsson, F. Larsson, F. Lundholm, A. Moestedt, J. Nilsson, P. SteustrSm, and B. Werner. SimlCS/sun4m: A Virtual Workstation. In Proceedings of USENIX'98, pages 119-130, June 1998.

Digital Library

[13]

A. Mendelson, D. Thitbaut~ and D. K. Pradhan. Modeling Live and Dead Lines in Cache Memory Systems. IEEE Transactions on Computers, 42(1):1-14, January 1993.

Digital Library

[14]

R. W. Quong. Expected i-Cache Miss Rates via the Gap Model. In Proceedings of the 21st International Symposium on Computer Architecture, pages 372-383, April 1994.

Digital Library

[15]

E. R~thberg, J. P. Singh, and A. Gupta. Working Sets, Cache Sizes and Node Granularity Issues for Large-Scale Multiprocessors. In Proceedings of the 20th International Symposium on Computer Architecture, pages 14-25, May 1993.

Digital Library

[16]

D. Sorin, P. S. Vijay, S. V. Adve, M. K. Vernon, and D. A. Wood. Analytic Evaluation of Shared-Memory Systems with ILP Processors. In Proceedings of the 25th International Symposium on Computer Architecture, pages 380-391, June 1998.

Digital Library

[17]

P. Stenstr6m, E. Hagersten, D. Lilja, M. Martonosi, and M, Venugopal. Trends in Shared Memory Multiprocessing. IEEE Computer, 30(12):44--50, December 1997.

Digital Library

[18]

TcX AB, Detron HB and Monty Program KB. MySQL v3.22 Reference Manual, September 1998.

[19]

S. Thakkar and M. Sweiger. Performance of axl OLTP Application on Symmetry Multiprocessor System. In Proceedings o.f the 18th International Symposium on Computer Architecture, pages 228-238, May 1990.

Digital Library

[20]

D. Thi~baut and H. Stone. Footprints in the Cache. A CM Transactions on Computer Systems, 5(4):305-329, 1987.

Digital Library

[21]

P. Trancoso, J.-L. Larriba-Pey, Z. Zhang, and J. Torrellas. The Memory Performance of DSS Commercial Workloads in Shared-Memory Multiprocessors. In Proceedings of the 3rd International Conference on High Performance Computing, pages 250-260, February 1997.

Digital Library

[22]

A. Yu and J. Chen. The POSTGRES95 User Manual. In Computer Science Division, Department of EECS, University of California at Berkley, July 1995.

Cited By

Koller RVerma ARangaswami R(2011)Estimating Application Cache Requirement for Provisioning Caches in Virtualized SystemsProceedings of the 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2011.67(55-62)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1109/MASCOTS.2011.67
Zhang Jing Deng Lin Dou Yong (2010)Data locality characterization of OLTP applications and its effects on cache performance2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE)10.1109/ICACTE.2010.5579552(V3-580-V3-584)Online publication date: Aug-2010
https://doi.org/10.1109/ICACTE.2010.5579552
Koller RVerma ARangaswami R(2010)Generalized ERSS tree modelPerformance Evaluation10.1016/j.peva.2010.08.00467:11(1139-1154)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.peva.2010.08.004
Show More Cited By

Index Terms

Recommendations

An analytical model of the working-set sizes in decision-support systems
Special issue on proceedings of ACM SIGMETRICS 2000

This paper presents an analytical model to study how working sets scale with database size and other applications parameters in decision-support systems (DSS). The model uses application parameters, that are measured on down-scaled database executions, ...
MATLAB. Working with Data Bases
Vague Rough Set Techniques for Uncertainty Processing in Relational Database Model

The study of databases began with the design of efficient storage and data sharing techniques for large amount of data. This paper concerns the processing of imprecision and indiscernibility in relational databases using vague rough technique leading to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '00: Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

June 2000

329 pages

ISBN:1581131941

DOI:10.1145/339331

Chairmen:
Alexandre Brandwajn
Univ. of California, Santa Cruz, Santa Cruz
,
Jim Kurose
Univ. of Massachusetts-Amherst, Amherst
,
Phillippe Nain
INRIA, Sophia Antipolis, France

ACM SIGMETRICS Performance Evaluation Review Volume 28, Issue 1
Special issue on proceedings of ACM SIGMETRICS 2000
June 2000
327 pages
ISSN:0163-5999
DOI:10.1145/345063
Chairmen:
Alexandre Brandwajn
Univ. of California, Santa Cruz, Santa Cruz
,
Jim Kurose
Univ. of Massachusetts-Amherst, Amherst
,
Phillippe Nain
INRIA Sophia Antipolis, France
Issue’s Table of Contents

Copyright © 2000 ACM.

Permission to make digital or hard copies of all or part 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, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMETRICS00

Sponsor:

SIGMETRICS

SIGMETRICS00: The International Conference on Measurement and Modeling of Computer Systems

June 18 - 21, 2000

California, Santa Clara, USA

Acceptance Rates

SIGMETRICS '00 Paper Acceptance Rate 28 of 165 submissions, 17%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
563
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)10

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Koller RVerma ARangaswami R(2011)Estimating Application Cache Requirement for Provisioning Caches in Virtualized SystemsProceedings of the 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2011.67(55-62)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1109/MASCOTS.2011.67
Zhang Jing Deng Lin Dou Yong (2010)Data locality characterization of OLTP applications and its effects on cache performance2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE)10.1109/ICACTE.2010.5579552(V3-580-V3-584)Online publication date: Aug-2010
https://doi.org/10.1109/ICACTE.2010.5579552
Koller RVerma ARangaswami R(2010)Generalized ERSS tree modelPerformance Evaluation10.1016/j.peva.2010.08.00467:11(1139-1154)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.peva.2010.08.004
Elnikety SDropsho SZwaenepoel W(2007)Tashkent+ACM SIGOPS Operating Systems Review10.1145/1272998.127303741:3(399-412)Online publication date: 21-Mar-2007
https://dl.acm.org/doi/10.1145/1272998.1273037
Elnikety SDropsho SZwaenepoel W(2007)Tashkent+Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 200710.1145/1272996.1273037(399-412)Online publication date: 21-Mar-2007
https://dl.acm.org/doi/10.1145/1272996.1273037
Tay YZou M(2006)A page fault equation for modeling the effect of memory sizePerformance Evaluation10.1016/j.peva.2005.01.00763:2(99-130)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.peva.2005.01.007
Murphy RRodrigues AKogge PUnderwood KArvind Rudolph L(2005)The implications of working set analysis on supercomputing memory hierarchy designProceedings of the 19th annual international conference on Supercomputing10.1145/1088149.1088193(332-340)Online publication date: 20-Jun-2005
https://dl.acm.org/doi/10.1145/1088149.1088193
Jin RAgrawal G(2005)A methodology for detailed performance modeling of reduction computations on SMP machinesPerformance Evaluation10.1016/j.peva.2004.10.01760:1-4(73-105)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.peva.2004.10.017
Zhou PPandey VSundaresan JRaghuraman AZhou YKumar S(2004)Dynamic tracking of page miss ratio curve for memory managementACM SIGOPS Operating Systems Review10.1145/1037949.102441538:5(177-188)Online publication date: 7-Oct-2004
https://dl.acm.org/doi/10.1145/1037949.1024415
Zhou PPandey VSundaresan JRaghuraman AZhou YKumar S(2004)Dynamic tracking of page miss ratio curve for memory managementACM SIGARCH Computer Architecture News10.1145/1037947.102441532:5(177-188)Online publication date: 7-Oct-2004
https://dl.acm.org/doi/10.1145/1037947.1024415
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents