Exploring caching for efficient collection operations

Many useful programs operate on collection types. Extensive libraries are available in many programming languages, such as the C++ Standard Template Library, which make programming with collections convenient. Extending programming languages to provide collection queries as first class constructs in...

Full description

Saved in:
Bibliographic Details
Main Authors: Surapaneni, Swetha, Nerella, Venkata Krishna Suhas, Madria, Sanjay K., Weigert, Thomas
Format: Conference Proceeding
Language:English
Subjects:
Cache Policy
Conferences
Frequency estimation
Histograms
Join caching
Maintenance engineering
Programming
Query processing
Run-time
Selectivity
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many useful programs operate on collection types. Extensive libraries are available in many programming languages, such as the C++ Standard Template Library, which make programming with collections convenient. Extending programming languages to provide collection queries as first class constructs in the language would not only allow programmers to write queries explicitly in their programs but it would also allow compilers to leverage the wealth of experience available from the database domain to optimize such queries. This paper describes an approach to reducing the run time of programs involving explicit collection queries by leveraging a cache to store previously computed results. We propose caching the results of join (sub)queries which allows queries that miss the cache entirely to be answered partially from the cache thereby improving the query execution time. We also describe an effective cache policy to determine which join (sub)queries to cache. The cache is maintained incrementally, when the underlying collections change, and use of the cache space is optimized by a cache replacement policy.
ISSN:1938-4300
2643-1572
DOI:10.1109/ASE.2011.6100101