Performance Improvement for Collection Operations Using Join Query Optimization

Programming languages with explicit support for queries over collections allow programmers to express operations on collections more abstractly than relying on their realization in loops or through provided libraries. Join optimization techniques from the field of database technology support efficient realizations of such language constructs. We describe an algorithm that performs run-time query optimization and is effective for single runs of a program. The proposed approach relies on histograms built from the data at run time to estimate the selectivity of joins and predicates in order to construct query plans. Information from earlier executions of the same query during run time can be leveraged during the construction of the query plans, even when the data has changed between these executions. Experimental results demonstrate improvement over earlier approaches, such as JQL.