Ncr Corporation

Teradata US, Inc.

Future Wei Technologies, Inc.

Kuorong Chiang

Paul Laurence Sinclair

Donald Raymond Pederson

Grace Kwan-On Au

Bhashyam Ramesh

John Mark Morris

Sanjay Nair

Grace K Au

Mark Sirek

Arthur Vargas Lopes

Hong Gui

Bibhu Ranjan Priyadarshi

Pradeep Sathyanarayan

Jerry Lynn Klindt

Yi Xia

Chuchu Wu

Lawrence H Higa

Anantha B Subramanian

Wei Tang

A data store system includes an array of persistent storage devices configured to store a plurality of data store tables. The data store system includes a processor in communication with the storage device. The processor may receive a query comprising an aggregate function and identify structure of an argument of the aggregate function. The subset of data store tables may be associated with the argument. The processor may partially-execute the aggregate function on each data store table in the subset involved in the argument of the aggregate function to create partially-executed results for each data store table of the subset of data store tables. The processor may join the partially-executed results based on join conditions contained in the aggregate function. The processor may complete execution of the aggregate function on the partially-executed results to generate a final result of the aggregate function. A method and computer-readable medium are also disclosed.

Multi-table aggregation through partial-group-by processing

Search spaces for obtaining query execution plans for a query are identified. The search spaces are subdivided into sub-search spaces. Searches are initiated within the sub search spaces and plan costs for competing query execution plans are noted along with search costs associated with continuing to search the sub-search spaces. A decision is made based on the plan costs and search costs for utilizing search resources as to when to terminate the searching and to select the then-existing lowest cost query execution plan as an optimal query execution plan for executing the query.

Query plan searching and optimization

A server applied to a database management system and a method are provided. By calculating a data skew for a column based on an entropy for the column in a database, storing the data skew to a catalogue in the database, estimating a selectivity for the column by multiplying a first selectivity with the data skew, cardinality estimation in the database management system is improved. By calculating a degree of correlation for two columns in a database, storing the degree of correlation to a catalogue in the database, estimating a selectivity taking into account the degree of correlation, cardinality estimation in the database management system is improved. The improved cardinality estimates in turn improve the query plan generated by the optimizer which leads to better query performance.

Cardinality estimation in databases

Query conditions are received in a cache from a query optimizer of a Database Management System (DBMS). Dynamic statistics for the query conditions are maintained in the cache. Actual statistics are received in the cache after the query conditions are executed in the DBMS. Entropy-based estimated selectivity values for executing the query conditions are provided to the query optimizer to develop a query plan for executing queries having the query conditions. The entropy-based estimated selectivity values based, at least in part, on the dynamic statistics and the actual statistics.

Caching methods and a system for entropy-based cardinality estimation

A system and method of rewriting a database query where the query contains an aggregate includes the following. If one or more aggregate materialized views are considered, rewriting the query using an aggregate materialized view. If one or more non-aggregate multi-table materialized views are considered, the query is rewritten using a multi-table materialized view. A join cost is determined for each such non-aggregate multi-table materialized view. If one or more non-aggregate single table materialized views are considered, the query is rewritten using the single table materialized view. A join cost is determined for each such non-aggregate single table materialized view. Finally, a current total cost is determined for use of various materialized views as a function of join cost, aggregation cost and spool cost to select a rewritten query.

Cost-based query rewrite using materialized views

A method, computer program, and database system are disclosed for querying tables stored on multiple processing modules. The method includes specifying module group characteristics. A plurality of modules corresponding to the module group characteristics are then identified. The identified modules are sampled for statistics concerning at least one table specified in a query. An execution plan for the query is optimized based at least in part on the sampled statistics.

Method and system for querying tables stored on multiple processing modules

A method, system and apparatus for performing an inclusion hash join and an exclusion hash join using a hash join are provided. The inner and outer tables are transposed to left and right tables, respectively. A hash table is created from the left table, the right table is scanned, and the hash table is probed. If the right table hash value matches a hash table value, the actual values are compared. If they match, the current outer table row is included in the result. If an exclusion condition is present, the hash table is probed with the right-table-row's hash value. If no hash values match, the outer table row is added to the result and the next row is addressed. If one or more hash values match, the actual values are compared.

Method and system for inclusion hash joins and exclusion hash joins in relational databases

A method, database system, and computer program are disclosed for optimized costing. The method includes identifying a join that identifies a first table and a second table. The method further includes determining an optimized cost of reading the first table. If the number of unique first table values is greater than the number of unique second table values, the number of instances where a unique first table value matches a unique second table value is returned. Otherwise, the number of unique first table values is returned. The method further includes determining an optimized cost of reading the second table. The optimized cost of reading the second table includes the number of unique second table values. The method also includes summing the optimized cost of reading the first table and the optimized cost of reading the second table.

Efficient costing for inclusion merge join

A method for performing a join of a first table and a second table is disclosed. In one instance, each of the plurality of first table rows is grouped into one of a plurality of first table partitions. It is determined that a partitioning column of the first table is specified in an equality condition of the join. One of the plurality of second table rows is selected, and a partition number is generated for the selected one of the plurality of second table rows. For a second table row for which a partition number was generated, a first table partition with a partition number that matches the generated partition number is identified, and a product join is used to join the one or more first table rows in the matching partition with the selected one of the second table rows.

Partition join in a partitioned database system

A method for reorganizing rows from a partitioned database table is disclosed. The partitioned database table includes a plurality of populated partitions. Rows are organized in each of the populated partitions in accordance with a first value associated with each row. A file context is created for each partition of a subset of the populated partitions, each file context stores at least location data for a row in the partition and the first value associated with the row. Rows and merged from the subset of partitions into a single first-merge partition in order of the first value associated with each row. The creation of file contexts and merging of rows in the corresponding partitions is repeated until the subsets have included all populated partitions.

Reorganization of database records using partition merging

A method of performing a join includes identifying a join that identifies a first table and a second table. The first table includes a plurality of first table rows. Each of the plurality of first table rows are grouped into one of a plurality of first table partitions. The second table includes one or more second table rows. Each of the plurality of second table rows are grouped into one or more second table partitions. A determination is made as to whether the first table and the second table are joined on equality constraints. The one or more first table rows are joined with the one or more second table rows using a rowkey merge join where equality exists.

Performing a join in a partitioned database system

A method, computer system, and computer program are claimed for selecting rows from first and second tables each having rows containing values in columns. In at least the first table, the rows are divided into partitions at least one of which is populated by one or more rows. The method, computer system, and computer program include (a) defining a subset of the populated partitions of the first table that excludes at least one populated partition of the first table, (b) creating a file context, which stores at least location data for a row and a first value associated with the row, for each populated partition in the subset of the populated partitions of the first table, (c) determining the lowest first value stored by the file contexts for the first table, (d) identifying rows with a particular first value by at least reading the file contexts of the first table, and (e) repeating a through d until the subsets of the populated partitions of the first table have included all the populated partitions of the first table.

Reduced memory row hash match scan join for a partitioned database system

A method, apparatus, and article of manufacture for generating statistics for use by a relational database management system. A global aggregate spool is generated for each of a plurality of partitions of a subject table that are spread across a plurality of processing units of a computer system. Each of the global aggregate spools is scanned to generate summary records. The summary records are then merged to generate interval records for a compressed histogram of the subject table, wherein the compressed histogram includes both equal-height intervals and high-biased intervals. The compressed histogram can then be analyzed to estimate the cardinality associated with one or more search conditions of a user query or other SQL statement. Compared to a strictly equal-height histogram, the compressed histogram allows the relational database management system to more accurately estimate the cardinality associated with various search conditions. As a result, the relational database management system can better optimize the execution of the user query.

Growing community of inventors

Cerritos, CA, United States of America

Kuorong Chiang