News Column

Patent Issued for Query Optimization in a Multi-Tenant Database System

June 3, 2014

By a News Reporter-Staff News Editor at Information Technology Newsweekly --, inc. (San Francisco, CA) has been issued patent number 8732157, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventors are Weissman, Craig (San Francisco, CA); Moellenhoff, Dave (Orinda, CA); Wong, Simon (Redwood City, CA); Nakada, Paul (San Francisco, CA).

This patent was filed on March 31, 2010 and was published online on May 20, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "The present invention relates generally to database systems and more particularly to query optimization systems and methods for use in multi-tenant database systems, wherein a centralized computer or set of computing devices serve and store applications and data for use by multiple tenants.

"Multi-tenant database systems allow for users to access applications and/or data from a network source that, to the user, appears to be centralized (but might be distributed for backup, redundancy and/or performance reasons). An example of a multi-tenant system is a computing system that is accessible to multiple independent parties to provide those parties with application execution and/or data storage. Where there is an appearance of centralization, and network access, each subscribing party (e.g., a 'tenant') can access the system to perform application functions, including manipulating that tenant's data.

"With a multi-tenant system, the tenants have the advantage that they need not install software, maintain backups, move data to laptops to provide portability, etc. Rather, each tenant user need only be able to access the multi-tenant system to operate the applications and access that tenant's data. One such system usable for customer relationship management is the multi-tenant system accessible to subscribers. With such systems, a user need only have access to a user system with network connectivity, such as a desktop computer with Internet access and a browser or other HTTP client, or other suitable Internet client.

"In database systems, to access, retrieve and process stored data, a query is generated, automatically or manually, in accordance with the application program interface protocol for the database. In the case of a relational database, the standard protocol is the structured query language (SQL). SQL statements are used both for interactive queries for data from the database and for gathering data and statistics. The efficiency of the query method underlying the actual query is dependent in part on the size and complexity of the data structure scheme of the database and in part on the query logic used.

"Previous database query methods have been inefficient for multi-tenant databases because such methods do not understand, and fail to account for, the unique characteristics of each tenant's data. For example, while one tenant's data may include numerous short records having only one or two indexable fields, another tenant's data may include fewer, longer records having numerous indexable fields.

"In addition to these structural (schema) differences, the distribution of data among different tenants may be quite different, even when their schemas are similar. Modern relational databases rely on statistics-based query optimizers that make decisions about the best manner to answer a query given accurate table-level and column-level statistics that are gathered periodically. Importantly, however, because existing relational databases are not multi-tenant aware, these statistics cut across all tenants in the database. That is, the statistics that are gathered are not specific to any one tenant, but are in fact an aggregate or average of all tenants. This approach can lead to incorrect assumptions and query plans about any one tenant.

"As a specific example, Oracle provides a query optimizer that can be used on an Oracle database. This query optimizer works generally as follows: for each table, column, or index, aggregate statistics are gathered (typically periodically or on demand by a database administrator ('DBA')). The gathered statistics typically include the total number of rows, average size of rows, total number of distinct values in a column or index (an index can span multiple columns), histograms of column values (which place a range of values into buckets), etc. The optimizer then uses these statistics to decide among a possible set of data access paths.

"In general, one goal of a query optimizer is to minimize the amount of data that must be read from disk (e.g., because disk access may be a slow operation). The optimizer therefore typically chooses tables or columns that are most 'selective'--that is, will yield the fewest rows when the query condition is evaluated. For instance, if a single query filters on two columns of a single table, and both columns are indexed, then the optimizer will use the index that has the highest number of distinct values because statistically for any given filter value a smaller number of rows are expected to be returned. If the optimizer knows that a certain column has a very high cardinality (number of distinct values) then the optimizer will choose to use an index on that column versus a similar index on a lower cardinality column. The optimizer assumes relatively even distribution of data and therefore reaches the conclusion that the high-cardinality column is likely to yield a smaller number of satisfying-rows for a given equality filter.

"Now consider in a multi-tenant system a physical column (shared by many tenants) that has a large number of distinct values for most tenants, but a small number of distinct values for a specific tenant. For this latter tenant the query optimizer will use this overall-high-cardinality column in error--because the optimizer is unaware that for this specific tenant the column is not selective.

"In the case of table joins, the optimizer's decisions may be even more important--deciding which table to retrieve first can have a profound impact on overall query performance. Here again, by using system-wide aggregate statistics the optimizer might choose a query plan that is incorrect or inefficient for a single tenant that does not conform to the 'normal' average of the entire database as determined from the gathered statistics.

"Accordingly, it is desirable to provide systems and methods for optimizing database queries, and for dynamically tuning a query optimizer, in a multi-tenant database system which overcome the above and other problems."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventors' summary information for this patent: "The present invention provides methods and systems for optimizing database queries in a multi-tenant database system. In certain aspects, for example, the present invention provides methods for dynamically tuning a query optimizer based on particular data characteristics of the tenant whose data is being searched and the particular query being executed. The systems and methods of the present invention advantageously harness greater semantic knowledge about the use of data tables by the underlying relational database. By tracking tenant-level statistics on top of the typical system-gathered statistics (e.g., Oracle gathered statistics), the present invention is advantageously able to optimize queries and/or make recommendations to the underlying query optimizer to improve its knowledge of the data, and therefore increase system performance, particularly for individual tenants. According to the present invention, a multi-tenant database stores data from multiple tenants. While the overall database structure or schema is fixed, each tenant may have a tenant-specific virtual schema that describes the logical structure of that tenant's data. In certain aspects, each tenant's virtual schema includes a variety of customizable fields, some or all of which may be designated as indexable. According to an aspect of the present invention, a method is provided for optimizing a query in a multi-tenant database having one or more data tables, each table having one or more logical columns defining data categories and one or more logical rows associated with one or more tenants, wherein a plurality of tenants have data stored in the data tables. The method typically includes generating tenant-level statistics for each of said plurality of tenants for each of the data tables, receiving a SQL query, and optimizing the SQL query based on the tenant-level statistics. In certain aspects, the method also includes generating user-level statistics for each user of each tenant and optimizing the SQL query based on the user-level statistics. According to another aspect of the present invention, a multi-tenant database system is provided. The multi-tenant database system typically includes a database having one or more data tables, each table having one or more columns defining data categories and one or more rows associated with one or more tenants, wherein a plurality of tenants have data stored in the data tables. The database system also typically includes a statistics generating module configured to generate tenant-level statistics for each tenant for each of the data tables, and a query optimization module, configured to optimize a database query based on the tenant-level statistics. In certain aspects, the statistics generation engine is configured to generate user-level statistics for each user of each tenant, and the query optimization module is configured to optimize a database query based on the user-level statistics. Reference to the remaining portions of the specification, including the drawings and claims, will realize other features and advantages of the present invention. Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with respect to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements."

For the URL and additional information on this patent, see: Weissman, Craig; Moellenhoff, Dave; Wong, Simon; Nakada, Paul. Query Optimization in a Multi-Tenant Database System. U.S. Patent Number 8732157, filed March 31, 2010, and published online on May 20, 2014. Patent URL:

Keywords for this news article include: inc., inc, Information Technology, Information and Data Tabulation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Information Technology Newsweekly

Story Tools Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters