Systems and methods for searching multiple related tables
Methods and systems for performing a query over joined tables in the context of inexact matching provide efficient search engine functionality. The systems and methods are used to perform an efficient query on a parent table and joined child tables. Search grams are determined based on the query and parent records and child records are scanned for the search grams. Gram scores are computed based on a degree of matching between the parent and child records and the search grams.
1. A method for performing an efficient query on a parent table and one or more joined child tables, the method comprising:
determining one or more search grams based on the query, each of the one or more search grams being at least a portion of the query, wherein determining the one or more search grams comprises determining gram vectors for each search gram of the one or more search grams;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams, wherein gram vectors associated with a child table from the one or more joined child tables are sorted by a foreign key;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores;
repeating the identifying one or more child table partitions, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions;
generating a mapping structure having parent and child table partitions association information and parent and child records association information;
referencing the mapping structure to determine associations between parent and child table partitions and between parent and child records;
determining a new child record for inserting into a child table partition associated with a parent table partition having a parent record associated with the new child record;
in response to determining an available row exists in the child table partition, inserting the new child record into the available row;
in response to determining an available row does not exist in the child table partition, generating a new child table partition, associating the new child table partition with the parent table partition, and inserting the new child record into the new child table partition.
2. The method of claim 1 , further comprising computing the parent gram scores for the scanned parent records and the child gram scores for the scanned child records.
3. The method of claim 1 , wherein a portion of a first search gram of the one or more search grams overlaps with a portion of a second search gram of the one or more search grams.
4. The method of claim 1 , further comprising:
adding parent records and child records based on aggregate scores to an output heap.
5. The method of claim 1 , further comprising:
receiving the query from a user.
6. The method of claim 5 , further comprising:
providing query results to the user based on the aggregate scores.
7. The method of claim 1 , wherein the foreign key comprises a key associated with the parent table.
8. The method of claim 1 , wherein the parent table is joined with multiple child tables.
9. The method of claim 1 , wherein the parent table is joined with a chain of child tables.
10. The method of claim 1 , wherein child records are associated with parent records via a foreign key field.
11. The method of claim 1 , wherein child records are associated with parent records via common unique values.
12. A system for performing an efficient query on a parent table and one or more joined child tables, the system comprising:
a processor;
a memory element; and
a communications device, wherein the processor and memory element are in communication via the communications device, and wherein the processor is operable for:
determining one or more search grams based on the query, each of the one or more search grams being at least a portion of the query, wherein determining the one or more search grams comprises determining gram vectors for each search gram of the one or more search grams;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams, wherein gram vectors associated with a child table from the one or more joined child tables are sorted by a foreign key;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores;
repeating the identifying one or more child table partitions, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions
generating a mapping structure having parent and child table partitions association information and parent and child records association information;
referencing the mapping structure to determine associations between parent and child table partitions and between parent and child records;
determining a new child record for inserting into a child table partition associated with a parent table partition having a parent record associated with the new child record;
in response to determining an available row exists in the child table partition, inserting the new child record into the available row;
in response to determining an available row does not exist in the child table partition, generating a new child table partition, associating the new child table partition with the parent table partition, and inserting the new child record into the new child table partition.
13. The system of claim 12 , wherein the mapping structure is stored in the memory element.
14. The system of claim 12 , wherein the processor is further operable to add parent records and child records based on aggregate scores to an output heap.
15. The system of claim 12 , further comprising an input element for receiving the query from a user.
16. The system of claim 12 , further comprising a display element for displaying search results to a user.
17. A non-transitory computer readable medium including instructions that, when executed by a processor, cause the processor to perform a process comprising:
determining one or more search grams based on the query, each of the one or more search grams being at least a portion of the query, wherein determining the one or more search grams comprises determining gram vectors for each search gram of the one or more search grams;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams, wherein gram vectors associated with a child table from the one or more joined child tables are sorted by a foreign key;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores;
repeating the identifying one or more child table partitions, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions;
generating a mapping structure having parent and child table partitions association information and parent and child records association information;
referencing the mapping structure to determine associations between parent and child table partitions and between parent and child records;
determining a new child record for inserting into a child table partition associated with a parent table partition having a parent record associated with the new child record;
in response to determining an available row exists in the child table partition, inserting the new child record into the available row;
in response to determining an available row does not exist in the child table partition, generating a new child table partition, associating the new child table partition with the parent table partition, and inserting the new child record into the new child table partition.
18. The method of claim 1 , wherein the one or more search grams scanned for during the scanning of the parent records are different from the one or more search grams scanned for during the scanning of the child records.
19. The method of claim 12 , wherein the one or more search grams scanned for during the scanning of the parent records are different from the one or more search grams scanned for during the scanning of the child records.
20. The method of claim 17 , wherein the one or more search grams scanned for during the scanning of the parent records are different from the one or more search grams scanned for during the scanning of the child records.
21. The method of claim 1 , wherein the one or more child table partitions comprise at least two child table partitions.
22. The method of claim 1 , wherein determining the one or more search grams further comprises determining a weight of each search gram of the one or more search grams, and wherein computing the aggregate scores comprises incrementing a score array by a weight of at least one search gram of the one or more search grams.
23. The method of claim 1 , wherein a special partition associated with the parent table is used for an outer join not associated with a parent record.
24. The method of claim 23 , wherein the outer join comprises a child record.