Systems and methods for searching multiple related tables
Methods, systems, and computer readable media are described herein for processing a query on a parent table and associated child tables to provide efficient search engine functionality. 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 querying a parent table and one or more child tables, the method comprising:
generating a mapping structure based on the parent table and the one or more child tables;
configuring a memory to store the mapping structure;
partitioning, using a processor caching architecture, the parent table into one or more parent table partitions, and the one or more child tables into one or more child table partitions;
determining one or more search grams based on a 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 at least one gram vector for each search gram of the one or more search grams;
identifying the parent table having the one or more parent table partitions including one or more parent records;
identifying the one or more child table partitions from the one or more child tables, the one or more child table partitions including one or more child records, wherein the one or more child table partitions are associated with at least one of the one or more parent table partitions;
scanning parent records in a parent table partition for the one or more search grams; and
scanning child records in one or more second child table partitions associated with the parent table partition for the one or more search grams,
wherein child records of gram vectors associated with a child table from the one or more child tables are sorted by a foreign key and a partition number.
2. The method of claim 1 , further comprising:
computing parent gram scores for the scanned parent records based on a degree of matching with the one or more search grams; and
computing child gram scores for the scanned child records based on a degree of matching with the one or more search grams.
3. The method of claim 2 , further comprising:
computing aggregate scores based on the parent and child gram scores; and
repeating the identifying the one or more child table partitions, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each parent table partition.
4. The method of claim 3 , further comprising:
adding, based on the aggregate scores, second parent records and second child records to an output heap; and
providing query results based on the aggregate scores.
5. The method of claim 3 , 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.
6. The method of claim 3 , wherein the mapping structure comprises association information associated with the one or more parent table partitions and the one or more child table partitions, and wherein the method further comprises;
referencing the mapping structure to determine associations among the one or more parent table partitions and the one or more child table partitions.
7. The method of claim 1 , wherein the mapping structure comprises association information associated with the one or more parent table partitions and the one or more child table partitions, and wherein the method further comprises;
referencing the mapping structure to determine associations among the one or more parent table partitions and the one or more child table partitions.
8. The method of claim 1 , further comprising:
determining a new child record for inserting into a child table partition associated with a second 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; and
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 second parent table partition, and inserting the new child record into the new child table partition.
9. 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.
10. The method of claim 1 , wherein the foreign key comprises a key associated with the parent table.
11. The method of claim 1 , wherein the parent table is joined with multiple child tables.
12. The method of claim 1 , wherein child records comprised in a child table partition are associated with parent records in a second parent table partition via a foreign key field or via common unique values.
13. 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.
14. The method of claim 1 , wherein a special partition, associated with the parent table, is associated with an outer join not associated with a parent record.
15. The method of claim 14 , wherein the outer join comprises a child record.
16. A system for querying a parent table and one or more child tables, the system comprising:
a processor;
a memory; and
a communications device, wherein the processor and the memory are in communication via the communications device, and wherein the processor is operable for:
generating a mapping structure based on the parent table and the one or more child tables;
configuring the memory to store the mapping structure;
determining one or more search grams based on a 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 at least one gram vector for each search gram of the one or more search grams;
identifying the parent table having one or more parent table partitions including one or more parent records;
identifying one or more child table partitions from the one or more child tables, the one or more child table partitions including one or more child records, wherein the one or more child table partitions are associated with at least one of the one or more parent table partitions;
scanning parent records in a parent table partition for the one or more search grams; and
scanning child records in one or more second child table partitions associated with the parent table partition for the one or more search grams,
wherein child records of gram vectors associated with a child table from the one or more child tables are sorted by a foreign key and a partition number.
17. The system of claim 16 , wherein the processor is further operable to add selected parent records associated with the parent table partition and selected child records associated with the one or more second child table partitions to an output heap.
18. The system of claim 16 , further comprising: an input element for receiving the query from a user, or a display element for displaying search results to the user.
19. The system of claim 16 , further comprising a processor caching architecture for partitioning the parent table into the one or more parent table partitions, and the one or more child tables into the one or more child table partitions.
20. A non-transitory computer readable medium including instructions that, when executed by a processor, cause the processor to perform a process for querying a parent table and one or more child tables, the process comprising:
generating a mapping structure based on the parent table and the one or more child tables;
configuring a memory to store the mapping structure;
determining one or more search grams based on a 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 at least one gram vector for each search gram of the one or more search grams;
identifying the parent table having one or more parent table partitions including one or more parent records;
identifying one or more child table partitions from the one or more child tables, the one or more child table partitions including one or more child records, wherein the one or more child table partitions are associated with at least one of the one or more parent table partitions;
scanning parent records in a parent table partition for the one or more search grams; and scanning child records in one or more second child table partitions associated with the parent table partition for the one or more search grams,
wherein child records of gram vectors associated with a child table from the one or more child tables are sorted by a foreign key and a partition number.