International Business Machines Corporation

Marcel Kutsch

Knut Stolze

Deborah Yu

Nimrod Megiddo

Volker Gerhard Markl

Tam Minh Dai Tran

Xiao Li

Peter Haas

Serge Bourbonnais

Fatma Ozcan

Andrey Balmin

Vuk Ercegovac

Jonathan W Wierenga

Jesse E Jackson

Konstantinos Karanasos

Chunyang Xia

A method and associated system for selectively constructing a search result for a data requested by a search request specifying path information of a data node comprising the data. A template tree represents a hierarchy of the search result with expandable nodes which initially do not have actual data. A node of the template tree is dynamically expanded by a callback function to have a respective data for the node when the node is traversed for the first time during traversing the template tree according to the path information. The search result is created by expanding all nodes of the template tree that are specified in the path information. The data node in the search result is communicated to an entity that had originated the search request.

Expansion of a tree hierarchy

In one embodiment, a computer-implemented method includes selecting one or more sub-expressions of a query during compile time. One or more pilot runs are performed by one or more computer processors. The one or more pilot runs include a pilot run associated with each of one or more of the selected sub-expressions, and each pilot run includes at least partial execution of the associated selected sub-expression. The pilot runs are performed during execution time. Statistics are collected on the one or more pilot runs during performance of the one or more pilot runs. The query is optimized based at least in part on the statistics collected during the one or more pilot runs, where the optimization includes basing cardinality and cost estimates on the statistics collected during the pilot runs.

Dynamic query optimization with pilot runs

Techniques are disclosed for comparing database tables. In one embodiment, the database tables are partitioned. Queries are generated for retrieving each partition. For each generated query, a stored procedure is invoked, using the respective generated query as an input parameter to the stored procedure. The stored procedure is configured to generate a checksum based on the partition retrieved from executing the respective query. The application compares the generated checksums to determine if the partitions and/or tables are consistent.

Database table comparison

A method and system for expanding a template tree. A received search request includes (i) a search query and (ii) path information specifying at least one path of data nodes of the template tree. The template tree is a hierarchically organized data structure of data nodes. Each specified path in the path information includes a sequence of data nodes of the template tree. The data nodes in each sequence in each specified path are traversed. Each traversed data node that does not have a child node in the template tree is expanded to form in the template tree one or more child nodes corresponding to each expanded data node. Any other data node of the template tree is not expanded. Each formed one or more child nodes is instantiated with data values by retrieving the data values, in accordance with the search query, from at least one data source.

Selective expansion of a tree hierarchy

A system and associated method for selectively constructing a search result for a data requested by a search request specifying path information of a data node comprising the data. A template tree represents a hierarchy of the search result with expandable nodes which initially do not have actual data. A node of the template tree is dynamically expanded by a callback function to have a respective data for the node when the node is traversed for the first time during traversing the template tree according to the path information. The search result is created by expanding all nodes of the template tree that are specified in the path information. The data node in the search result is communicated to an entity that had originated the search request.

Selective construction of data search result per search request specifying path information

A method for consistent selectivity estimation based on the principle of maximum entropy (ME) is provided. The method efficiently exploits all available information and avoids the bias problem. In the absence of detailed knowledge, the ME approach reduces to standard uniformity and independence assumptions. The disclosed method, based on the principle of ME, is used to improve the optimizer's cardinality estimates by orders of magnitude, resulting in better plan quality and significantly reduced query execution times.

Selectivity estimation for conjunctive predicates in the presence of partial knowledge about multivariate data distributions

The present invention provides a method of selectivity estimation in which preprocessing steps improve the feasibility and efficiency of the estimation. The preprocessing steps are partitioning (to make iterative scaling estimation terminate in a reasonable time for even large sets of predicates), forced partitioning (to enable partitioning in case there are no 'natural' partitions, by finding the subsets of predicates to create partitions that least impact the overall solution); inconsistency resolution (in order to ensure that there always is a correct and feasible solution), and implied zero elimination (to ensure convergence of the iterative scaling computation under all circumstances). All of these preprocessing steps make a maximum entropy method of selectivity estimation produce a correct cardinality model, for any kind of query with conjuncts of predicates. In addition, the preprocessing steps can also be used in conjunction with prior art methods for building a cardinality model.

Growing community of inventors

Stuttgart, Germany

Marcel Kutsch