Systems and methods for implementing and maintaining sampled tables in a database system

• US 9,953,054 B2
• Filed: 04/21/2014
• Issued: 04/24/2018
• Est. Priority Date: 04/22/2013
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Collins, Jesse Yarbro
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US14/257,901
• Publication Number:
  US 20140317087A1
• Time in Patent Office: 1,464 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

In accordance with disclosed embodiments, there are provided systems and methods for implementing and maintaining sampled tables in a database system. According to a particular embodiment such a system includes a processor and a memory to execute instructions at the system; a database to store database records; a query interface to submit queries to the database and receive results from the database; triggers to initiate a hash function on database insert transactions, the hash function to hash a primary key of each database record to be inserted into the database to determine whether a first hash value of the primary key of the database record to be inserted satisfies a sampling condition; a sample table to store a sample record corresponding to any database record to be inserted into the database which satisfies the sampling condition based on the hash function; a primary key index providing a first index of the primary keys of the sample records stored in the sample table; and an ordered hash index providing a second index on a second hash value corresponding to a second hash of the primary key of the sample records stored in the sample table ordered numerically by the second hash value. Other related embodiments are disclosed.

Claims

1. A system to execute within a host organization, wherein the system comprises:

a processor and a memory to execute instructions at the system;

a query optimizer to optimize database queries;

a database system having a plurality of database tables, each of the plurality of database tables to store database records, wherein each of the plurality of database tables embodies a trigger component, stored within the respective database table;

wherein the trigger component embodied within each respective database table is to initiate a hash function of the primary key for the respective database table upon a database insert transaction of a new database record being inserted into the respective database table;

a sample table within the query optimizer and maintained by the query optimizer separate from the plurality of database tables of the database system, wherein the sample table is to store a sample record corresponding to any database record being inserted into the respective database table of the database system which satisfies the sampling condition based on the hash function pursuant to the trigger component;

wherein the trigger component of each respective database table continuously maintains sampled records in the sample table upon any insert, change, or deletion to records within the respective database table satisfying the sampling condition based on the hash function;

wherein the hash function trigger is further configured to initiate the hash function upon any database record delete transaction for the table within which the respective hash function trigger resides and, responsive to a database record delete transaction, the hash function performs a hash of the primary key for a database record being deleted pursuant to the database record delete transaction to determine whether the database record being deleted satisfies the sampling condition indicating a sample record within the sample table must also be deleted or marked for deletion;

a primary key index providing an index of the primary keys of the sample records stored in the sample table;

a query interface to receive a query for the database system, wherein the queries to the database system are processed through the query interface and wherein the trigger component to initiate the hash function on database insert transactions resides within the query interface;

wherein the query optimizer is to optimize the received query by applying a plurality of filters to the sample table and selecting one of the plurality of filters based on which one of the plurality of filters corresponds to a greatest reduction in a number of records returned from the sample table, and wherein the query interface is to pass the trigger component to the query optimizer to perform the hash function for each database record being inserted into the database system to determine whether the database record being inserted satisfies a sampling condition; and

the query interface to execute the optimized query against the database system, wherein the optimized query applies the selected one of the plurality of filters to the database system in fulfillment of executing the received query.

2. The system of claim 1, further comprising:

wherein executing the optimized query against the database system comprises

executing the optimized query against at least one of the plurality of tables of the database system having the database records stored therein corresponding to the fewest number of records returned from the sample table during the optimizing of the received query.

3. The system of claim 2, wherein a hash function trigger resides within every table of the database system, the hash function trigger operable in conjunction with the query interface to initiate the hash function upon any database insert transaction to the table within which the respective hash function trigger resides.

4. The system of claim 1, wherein the hash function to determine whether the database record being inserted satisfies the sampling condition comprises logic of the hash function to:

generate the first hash value of the primary key of the database record being inserted;

receive the first hash value as a numeric value output from the hash function;

determine whether the numeric value output by the hash function falls within a specified sampling range of all possible values for the numeric value output by the hash function; and

insert the primary key in its un-hashed form into the primary key index of the sample table and additionally insert the second hash value corresponding to the second hash of the primary key in its hashed form into the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall within the specified sampling range or alternatively to discard the hash of the primary key without insertion into either the primary key index or the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall outside of the specified sampling range.

5. The system of claim 1, wherein each sample record stored within the sample table comprises at least:

the primary key of the sample records stored in the sample table in its un-hashed form; and

the second hash value corresponding to the hash of the primary key of the sample records stored in the sample table in its hashed form and ordered numerically by the value of the hash of the primary key; and

a customer organization identifier (OrgID) identifying which customer organization amongst a plurality of customer organizations have ownership and authority for the sample record stored in the sample table and the corresponding database record stored in the database system.

6. The system of claim 1, wherein each sample record stored in the sample table comprises one of:

a copy of the corresponding database record in the database system, including the primary key;

or

the primary key of the corresponding database record in the database system but not any remaining columns of the corresponding database record, wherein a join is performed via the primary key to bring the sample record stored in the sample table back together with the remaining columns of the corresponding database record in the database system.

7. The system of claim 1, further comprising:

a query optimizer to execute a query against the sample table;

wherein sample table is accessed via an index only access and scanned for a subset or a portion of the index corresponding to a specified customer organization based on an OrgID prefix maintained within an OrgID column and indexed within the sample table.

8. The system of claim 1, further comprising:

a query optimizer to execute a query against the sample table to identify a plurality of range markers for a processing job having multiple database transactions specified therein which is being broken down into a plurality of chunks, each corresponding to a non-overlapping sub-set of the processing job according to the plurality of range markers; and

wherein the query optimizer is to identify the plurality of range markers by issuing a query against the primary key index having therein the primary keys in their un-hashed form;

wherein the primary key index is scanned to identify a plurality of the primary keys to function as the range markers based on a specified interval quantity of rows; and

wherein scanning the primary key index negates having to scan all of the primary keys of the processing job being broken down into the plurality of chunks.

9. The system of claim 1, further comprising:

a query optimizer to optimize a database query having a leading wild card in a WHERE statement of an SQL query by scanning a subset of the ordered hash index and selecting a filter corresponding to a result set from the sample table having a smallest quantity of records returned; and

wherein the selected filter is then used as part of the database query being optimized when executed against a full dataset of the database system.

10. The system of claim 1, further comprising:

a query optimizer to issue a query for and return report preview results for a Graphical User Interface (GUI) by executing the query against the ordered hash index of the sample table using a filter specified by the GUI with a row number limit which restricts a maximum quantity of records returnable with the report preview results and which further terminates processing of the query when the row number limit is reached.

11. The system of claim 1:

wherein the database system of the host organization comprises a multi-tenant database system implemented by the host organization and storing customer data on behalf of a plurality of separate and distinct customer organizations; and

wherein the sample table comprises a relational database operated within the host organization to store the sample records without being directly accessible to any of the plurality of separate and distinct customer organizations which utilize the multi-tenant database system; and

wherein the sample table is indirectly accessible to the customer organizations through the query interface and a query optimizer of the system which performs query optimization on queries for execution against the multi-tenant database system.

12. The system of claim 11, wherein each of the plurality of separate and distinct customer organizations which utilize the multi-tenant database system is an entity selected from the group consisting of:

a separate and distinct remote organization, an organizational group within the host organization, a business partner of the host organization, or a customer organization that subscribes to cloud computing services provided by the host organization.

13. A method to execute within a host organization having at least a processor and a memory therein, wherein the method comprises:

storing records in a database system of the host organization, the database system having a plurality of database tables, each of the plurality of database tables to store database records, wherein each of the plurality of database tables embodies a trigger component, stored within the respective database table;

embodying a trigger component within each respective database table, wherein the trigger component is to initiate a hash function of the primary key for the respective database table upon a database insert transaction of a new database record being inserted into the respective database table and upon any change or delete transaction for any of the database records within the respective database table;

receiving database transactions at a query interface, the query interface to submit the database transactions to the database system;

triggering, via the trigger component, a hash function for each one of the database transactions;

wherein the hash function hashes a primary key of each database record being inserted at the database system at pursuant to the database transactions to determine whether a first hash value of the primary key of the database record being inserted satisfies a sampling condition;

maintaining a sample table within a query optimizer, wherein the sample table is maintained by the query optimizer separate from the plurality of database tables of the database system, wherein the sample table is to store a sample record corresponding to any database record being inserted into the respective database table of the database system which satisfies the sampling condition based on the hash function pursuant to the trigger component and further wherein the sample table is to update or delete any database record being changed or deleted within the respective database table which satisfies the sampling condition based on the hash function pursuant to the trigger component;

storing within the sample table, a sample record corresponding to any database record being inserted into the database which satisfies the sampling condition based on the hash function and updating within the sample table;

continuously maintaining, via the trigger component embodied within the database tables, sampled records in the sample table upon any insert, change, or deletion to records within the respective database table satisfying the sampling condition based on the hash function;

wherein triggering the hash function includes initiating the hash function upon any database record delete transaction for the table within which the respective hash function trigger resides and, responsive to a database record delete transaction, performing a hash of the primary key for a database record being deleted pursuant to the database record delete transaction to determine whether the database record being deleted satisfies the sampling condition indicating a sample record within the sample table must also be deleted or marked for deletion;

providing a primary key index having therein an index of the primary keys of the sample records stored in the sample table;

receiving a query at the query interface of the database system, wherein the queries to the database system are processed through the query interface and wherein the trigger component to initiate the hash function on database insert transactions resides within the query interface;

optimizing the received query at the query optimizer of the host organization by applying a plurality of filters to the sample table and selecting one of the plurality of filters causing the fewest number of records to be returned from the sample table, and wherein the query interface is to pass the trigger component to the query optimizer to perform the hash function for each database record being inserted into the database system to determine whether the database record being inserted satisfies a sampling condition; and

executing the optimized query against the database system, wherein the optimized query applies the selected one of the plurality of filters to the database system in fulfillment of executing the received query.

14. The method of claim 13, wherein the hash function determines whether the database record being inserted satisfies the sampling condition by performing the following operations:

generating the first hash value of the primary key of the database record being inserted;

receiving the first hash value as a numeric value output from the hash function;

determining whether the numeric value output by the hash function falls within a specified sampling range of all possible values for the numeric value output by the hash function; and

the primary key in its un-hashed form into the primary key index of the sample table and additionally insert the second hash value corresponding to the second hash of the primary key in its hashed form into the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall within the specified sampling range or alternatively to discard the hash of the primary key without insertion into either the primary key index or the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall outside of the specified sampling range.

15. Non-transitory computer readable storage media having instructions stored thereon that, when executed by a processor of a system, the instructions cause the system to perform operations comprising:

storing records in a database system of the host organization, the database system having a plurality of database tables, each of the plurality of database tables to store database records, wherein each of the plurality of database tables embodies a trigger component, stored within the respective database table;

embodying a trigger component within each respective database table, wherein the trigger component is to initiate a hash function of the primary key for the respective database table upon a database insert transaction of a new database record being inserted into the respective database table;

receiving database transactions at a query interface, the query interface to submit the database transactions to the database system;

triggering, via the trigger component, a hash function for each one of the database transactions;

maintaining a sample table within a query optimizer, wherein the sample table is maintained by the query optimizer separate from the plurality of database tables of the database system, wherein the sample table is to store a sample record corresponding to any database record being inserted into the respective database table of the database system which satisfies the sampling condition based on the hash function pursuant to the trigger component;

storing within the sample table, a sample record corresponding to any database record being inserted into the database which satisfies the sampling condition based on the hash function and updating within the sample table;

continuously maintaining, via the trigger component embodied within the database tables, sampled records in the sample table upon any insert, change, or deletion to records within the respective database table satisfying the sampling condition based on the hash function;

wherein triggering the hash function includes initiating the hash function upon any database record delete transaction for the table within which the respective hash function trigger resides and, responsive to a database record delete transaction, performing a hash of the primary key for a database record being deleted pursuant to the database record delete transaction to determine whether the database record being deleted satisfies the sampling condition indicating a sample record within the sample table must also be deleted or marked for deletion;

providing a primary key index having therein an index of the primary keys of the sample records stored in the sample table;

receiving a query at the query interface of the database system, wherein the queries to the database system are processed through the query interface and wherein the trigger component to initiate the hash function on database insert transactions resides within the query interface;

optimizing the received query at the query optimizer of the host organization by applying a plurality of filters to the sample table and selecting one of the plurality of filters causing the fewest number of records to be returned from the sample table, and wherein the query interface is to pass the trigger component to the query optimizer to perform the hash function for each database record being inserted into the database system to determine whether the database record being inserted satisfies a sampling condition; and

executing the optimized query against the database system, wherein the optimized query applies the selected one of the plurality of filters to the database system in fulfillment of executing the received query.

16. The non-transitory computer readable storage media of claim 15, wherein the hash function determines whether the database record being inserted satisfies the sampling condition by performing the following operations:

generating the first hash value of the primary key of the database record being inserted;

receiving the first hash value as a numeric value output from the hash function;

determining whether the numeric value output by the hash function falls within a specified sampling range of all possible values for the numeric value output by the hash function; and

the primary key in its un-hashed form into the primary key index of the sample table and additionally insert the second hash value corresponding to the second hash of the primary key in its hashed form into the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall within the specified sampling range or alternatively to discard the hash of the primary key without insertion into either the primary key index or the ordered hash index of the sample table when the numeric value output by the hash function is determined to fall outside of the specified sampling range.