Optimization of Object Queries on Collections Using Annotations for the String Valued Attributes

Object oriented programming languages raised the level of abstraction by supporting the explicit first class query constructs in the programming codes. The query constructs can be optimized by leveraging the techniques of query optimization from the domain of databases. The existing optimization approaches such as JQL, however, incur high run time overhead as optimizations are performed only at run time. Therefore, in this paper, we propose an approach that performs the query optimization at compile time utilizing the metadata annotations in the source code. The proposed approach first collects the data from the sample execution of the program and extracts the essential metadata for the string valued attributes. Then, the annotations consisting of the metadata values associated with string attributes are generated in the source code and the histograms are built using those annotations. The selectivity estimates of the predicates and the joins in the query are computed from the histograms. Next, the query plan is generated at compile time through the maximum selectivity heuristic. The query plan is modified at run time in cases of significant updates to the string data. The approach also incorporates the cache heuristics that determine whether to cache the query result or not. The cached query results are incrementally maintained up-to-date. Our experimental results demonstrate that our approach has reduced the run time of the program more than the earlier approaches such as JQL.