Method and system for partitioning search indexes

• US 8,930,332 B2
• Filed: 09/30/2010
• Issued: 01/06/2015
• Est. Priority Date: 03/12/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Burstein, Paul
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Waldron, Scott A
• Application Number:
  US12/894,938
• Publication Number:
  US 20110225165A1
• Time in Patent Office: 1,559 Days
• Field of Search: 707/756, 707/696
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

Methods and systems for partitioning search indexes are described. In one embodiment, such a method includes identifying, via a partition manager, a search index to be partitioned, where the search index includes a plurality of entity types, and wherein each of the plurality of entity types associates records stored in a data store with the respective entity type within the search index. The method further includes partitioning, via the partition manager, the search index into a first partitioned search index and a second partitioned search index, correlating, via a partitioning scheme, a first subset of the plurality of entity types with the first partitioned search index, and correlating, via the partitioning scheme, a second subset of the plurality of entity types with the second partitioned search index.

Claims

1. A method in a host organization having at least a processor and a memory therein, wherein the method comprises:

identifying a shared search index to be partitioned based on the shared search index having grown in size to exceed a threshold, wherein the shared search index provides indexing for a plurality of entity types, each of the plurality of entity types associating records stored in a data store of the host organization with the respective entity type of the shared search index;

partitioning, via the partition manager, the search index into a first partitioned search index and a second partitioned search index;

correlating, via a partitioning scheme, a first subset of the plurality of entity types with the first partitioned search index;

correlating, via the partitioning scheme, a second subset of the plurality of entity types with the second partitioned search index, wherein each of the first and second subsets are non-overlapping and wherein a sum of all entity types within the first and the second subsets constitute all of the entity types previously associated with the shared search index prior to its being partitioned;

determining the first partitioned search index correlates to only one single entity type based on the partitioning scheme, subsequent to the partitioning; and

promoting the first partitioned search index to a dedicated search index associated with the only one single entity type based on the partitioning scheme.

2. The method of claim 1, further comprising:

associating each of the plurality of entity types with a primary key uniquely identifying the respective entity type among the first partitioned search index and the second partitioned search index; and

storing the primary key for each of the plurality of entity types within the partitioning scheme.

3. The method of claim 2:

wherein the primary key for each of the plurality of entity types comprises one of;

a numeric primary key, an alphanumeric primary key, or a binary primary key; and

wherein the method further comprises;

receiving a search request specifying an entity type to search;

selecting either the first partitioned search index or the second partitioned search index based on the specified entity type to search and based further on the partitioning scheme correlating each of the plurality of entity types with the respective first or second partitioned search index; and

searching either the first partitioned search index or the second partitioned search index based on the selection.

4. The method of claim 3:

wherein the partitioning scheme comprises a listing of a plurality of partitioned search indexes, including at least the first partitioned search index and the second partitioned search index;

wherein the partitioning scheme associates each of the plurality of partitioned search indexes listed with one or more of the plurality of entity types in non-overlapping subsets of entity types;

wherein any one of the plurality of entity types is associated with no more than one of the plurality of partitioned search indexes listed; and

wherein all of the plurality of entity types are associated with one of the plurality of the plurality of partitioned search indexes listed.

5. The method of claim 3:

wherein the first partitioned search index comprises a shared partitioned search index, the shared partitioned search index associated, via the partitioning scheme, with two or more of the plurality of entity types.

6. The method of claim 1:

wherein the first partitioned search index comprises a dedicated search index, the dedicated search index associated, via the partitioning scheme, with no more than one of the plurality of entity types.

7. The method of claim 6, further comprising:

allocating a primary key to the one entity type associated with the dedicated search index, the primary key uniquely identifying the one entity type among the first partitioned search index and the second partitioned search index.

8. The method of claim 7, wherein allocating the primary key comprises:

executing a hash function against a string label identifying the one entity type associated with the dedicated search index to generate a binary string;

allocating the binary string as the primary key for the one entity type associated with the dedicated search index.

9. The method of claim 7, wherein the dedicated search index is locatable within a hierarchical directory structure of a file system based upon its primary key, the primary key corresponding to a named sub-directory within the hierarchical directory structure, and wherein the dedicated search index resides upon the file system within the named sub-directory.

10. The method of claim 9, further comprising:

receiving a search request specifying an entity type to search;

determining the primary key allocated to the specified entity type from the partitioning scheme;

identifying the named sub-directory within the file system based on a comparison of the determined primary key against a plurality of named sub-directories within the file system, each of the plurality of named sub-directories having a partitioned search index stored therein; and

searching the dedicated search index within the identified named sub-directory based on the identification.

11. The method of claim 9, further comprising:

receiving a search request specifying an entity type to search;

executing a hash function against the specified entity type to search to generate a corresponding binary string for the specified entity type to search;

identifying the named sub-directory within the file system based on a comparison of the corresponding binary string against a plurality of named sub-directories within the file system, each of the plurality of named sub-directories having a partitioned search index stored therein, and wherein each of the plurality of named sub-directories are named with a binary string corresponding to an entity type associated with the partitioned search index stored within the named sub-directory; and

searching the dedicated search index within the identified named sub-directory based on the identification.

12. The method of claim 9:

wherein allocating the primary key to the one entity type associated with the dedicated search index comprises allocating one of a numeric primary key, an alphanumeric primary key, or a binary primary key to the one entity type; and

wherein the method further comprises;

creating a new named sub-directory for the dedicated search index;

naming the new named sub-directory to match the value of the allocated primary key; and

storing the dedicated search index within the new named sub-directory.

13. The method of claim 1, wherein the method further comprises:

identifying one of the first partitioned search index or the second partitioned search index to be a first dedicated search index and adding a new second dedicated search index that provides indexing for the same one entity type as the first dedicated search index resulting in each of the first dedicated search index and the second dedicated search index being associated with the one entity type based on the partitioning scheme when one of the first partitioned search index or the second partitioned search index is identified as the first dedicated search index; and

identifying one of the first partitioned search index or the second partitioned search index to be a first shared search index and portioning the first shared search index into first and second shared search indexes when one of the first partitioned search index or the second partitioned search index is identified as the first shared search index;

wherein identifying the search index to be partitioned comprises;

determining a size of the search index to be partitioned;

comparing the size against a size threshold;

determining the size exceeds the size threshold; and

initiating partitioning for the search index to be partitioned based on the determination that the search index exceeds the size threshold.

14. The method of claim 1, wherein partitioning the search index into the first partitioned search index and the second partitioned search index comprises:

allocating one or more of the plurality of entity types to the first partitioned search index;

allocating a remaining portion of the plurality of entity types which are not allocated to the first partitioned search index to the second partitioned search index; and

partitioning the search index into the first partitioned search index and the second partitioned search index in accordance with the allocations.

15. The method of claim 1, wherein partitioning the search index into the first partitioned search index and the second partitioned search index comprises:

cloning the search index in its entirety to create a first search index clone and a second search index clone;

deleting all entity types within the first subset of the plurality of entity types from the second search index clone;

deleting all entity types within the second subset of the plurality of entity types from the first search index clone;

designating the first search index clone as the first partitioned search index;

designating the second search index clone as the second partitioned search index; and

updating the partitioning scheme in accordance with the partitioning.

16. The method of claim 1, further comprising:

receiving a search request from an entity associated with an OrgID, the search request specifying data stored within the data store of the host organization indexed according to the partitioning scheme by the dedicated search index; and

sending the search request to one of a plurality of work thread processors or to a bank of work thread processors to implement the requested search.

17. The method of claim 1, further comprising:

determining the dedicated search index exceeds a size threshold;

adding a new second dedicated search index that provides indexing for the same one entity type as the first dedicated search index resulting in each of the first dedicated search index and the second dedicated search index being associated with the one entity type based on the partitioning scheme, and further wherein the one entity type is only associated with the first dedicated search index and the second dedicated search index based on the partitioning scheme.

18. The method of claim 1:

wherein correlating the first subset of the plurality of entity types with the first partitioned search index and correlating the second subset of the plurality of entity types with the second partitioned search index comprises modifying a tree within the partitioning scheme;

wherein the tree comprises a plurality of nodes organized according to binary strings associated with the nodes, each of the plurality of nodes having a binary string with one or more significant digits in binary form; and

wherein modifying the tree comprises;

replacing one of the plurality of nodes corresponding to the search index with two new nodes, a first new node corresponding to the first partitioned search index and a second new node corresponding to the second partitioned search index,

assigning the binary string of the replaced node to the first new node,

adding a significant digit to the binary string of the first new node with a “

0”

binary value,

allocating the entity types of the first subset of entity types to the first new node,

assigning the binary string of the replaced node to the second new node,

adding a significant digit to the binary string of the second new node with a “

1”

binary value, and

allocating the entity types of the second subset of entity types to the second new node.

19. The method of claim 18, further comprising:

receiving a search request specifying an entity type to search;

executing a hash function against the specified entity type to search to generate a corresponding binary string for the specified entity type to search;

comparing the corresponding binary string for the specified entity type against the significant digits of the plurality of nodes in the tree until a single matching node is identified based on the binary string of the identified node; and

searching an index within the identified node.

20. The method of claim 1, wherein the data store comprises a multi-tenant database implementation having elements of hardware and software that are shared by a plurality of separate and distinct customer organizations.

21. The method of claim 20, wherein the multi-tenant database implementation stores a plurality of data elements comprising a first portion of the plurality of data elements residing within a non-relational data store of the multi-tenant database implementation and a second portion of the plurality of data elements residing within a relational data store of the multi-tenant database implementation.

22. A non-transitory computer readable storage medium having instructions stored thereon that, when executed by a processor of a host organization, the instructions cause the host organization to perform operations comprising:

identifying a shared search index to be partitioned based on the shared search index having grown in size to exceed a threshold, wherein the shared search index provides indexing for a plurality of entity types, each of the plurality of entity types associating records stored in a data store of the host organization with the respective entity type of the shared search index;

partitioning, via the partition manager, the search index into a first partitioned search index and a second partitioned search index;

correlating, via a partitioning scheme, a first subset of the plurality of entity types with the first partitioned search index;

correlating, via the partitioning scheme, a second subset of the plurality of entity types with the second partitioned search index, wherein each of the first and second subsets are non-overlapping and wherein a sum of all entity types within the first and the second subsets constitute all of the entity types previously associated with the shared search index prior to its being partitioned;

determining the first partitioned search index correlates to only one single entity type based on the partitioning scheme, subsequent to the partitioning; and

promoting the first partitioned search index to a dedicated search index associated with the only one single entity type based on the partitioning scheme.

23. The non-transitory computer readable storage medium of claim 22, wherein the instructions cause the host organization to perform further operations, comprising:

allocating a primary key to each of the plurality of entity types by executing a hash function against a string label identifying each respective entity type associated to generate the primary key in binary form;

storing the allocated primary keys for the plurality of entity types within the partitioning scheme;

receiving a search request specifying an entity type to search;

executing the hash function against the specified entity type to search to generate a corresponding binary string for the specified entity type to search;

identifying either the first partitioned search index or the second partitioned search index by comparing the corresponding binary string for the specified entity type to search against the allocated primary keys stored within the partitioning scheme; and

searching either the first partitioned search index or the second partitioned search index based on the identification.

24. A system comprising:

a processor and a memory;

a communications interface to a data store;

a partition manager to identify a shared search index to be partitioned based on the shared search index having grown in size to exceed a threshold, wherein the shared search index provides indexing for a plurality of entity types, each of the plurality of entity types associating records stored in a data store of the host organization with the respective entity type of the shared search index;

the partition manager to further partition search index into a first partitioned search index and a second partitioned search index;

a partitioning scheme to correlate a first subset of the plurality of entity types with the first partitioned search index;

the partitioning scheme to further correlate a second subset of the plurality of entity types with the second partitioned search index, wherein each of the first and second subsets are non-overlapping and wherein a sum of all entity types within the first and the second subsets constitute all of the entity types previously associated with the shared search index prior to its being partitioned;

the partition manager to further determine the first partitioned search index correlates to only one single entity type based on the partitioning scheme, subsequent to the partitioning; and

the partition manager to further promote the first partitioned search index to a dedicated search index associated with the only one single entity type based on the partitioning scheme.

25. The system of claim 24, further comprising:

a hashing module to perform consistent hashing against string identifiers for the plurality of entity types to generate binary strings as an output of the hashing module, wherein the binary strings generated by the hashing module are allocated to the plurality of entity types as primary keys, and wherein the binary strings generated by the hashing module are further used to locate corresponding search indexes.