Optimizing search query logic to speed retrieval

• US 8,661,023 B1
• Filed: 08/17/2012
• Issued: 02/25/2014
• Est. Priority Date: 08/01/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chun, Won S., Derby, Herb, Rohde, Douglas Lee Taylor, Zhuang, Xiaotong, Singh, Hermanpreet
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US13/588,545
• Time in Patent Office: 557 Days
• Field of Search: 707/2, 707/3, 707/714, 707/718, 709204-206
• US Class Current: 707/718
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Systems and methods are provided for processing a query at a computer system. The method includes building a query tree based on the query and grouping at least some nodes of the query tree into a group of nodes. Grouping is based on an operator node that is a parent of the at least some nodes. The group of nodes retains the functionality of the operator node but the operator node is eliminated by replacing the operator node with the group of nodes in the query tree. The method also includes traversing the query tree to obtain a result list from a search index that is responsive to the query.

Claims

1. A method of processing a query at a computer system comprising one or more processors and a memory storing one or more programs for execution of the method by the one or more processors, the method comprising:

building a query tree based on the query;

grouping at least some nodes of the query tree into a group of nodes based on an operator node that is a parent of the at least some nodes, the group of nodes retaining the functionality of the operator node;

eliminating the operator node by replacing the operator node with the group of nodes in the tree; and

traversing the tree to obtain a result list from a search index responsive to the query.

2. The method of claim 1, wherein as part of traversing the tree each call to a child node returns a plurality of matches.

3. The method of claim 1, wherein the query is a document search query, the at least some nodes are leaf nodes representing one or more query terms and the result list indicates documents responsive to the query.

4. The method of claim 3, wherein as part of traversing the tree each call to a child node includes a first document identifier, and wherein the leaf nodes use the first document identifier as a starting identifier.

5. The method of claim 4, wherein the child node returns a second document identifier, the second document identifier being a next matching document.

6. The method of claim 5, wherein the child node returns an error code if a next matching document does not exist.

7. The method of claim 1, wherein the operator node is an OR operator and traversing the tree includes skipping remaining members of the group once a matching result has been identified from a member of the group.

8. The method of claim 1, wherein the operator node is an AND operator and traversing the tree includes skipping remaining members of the group once a member of the group fails to find a matching result.

9. The method of claim 1, wherein replacing the operator node includes modifying a parent node of the operator node to recognize the group of nodes.

10. The method of claim 9, wherein modifying the parent node includes creating a jump-table, the jump-table enabling a particular node to branch directly to another node.

11. The method of claim 10, wherein as part of traversing the tree, the method further includes cutting a branch of the query tree by modifying the jump-table when the another node exhausts its possible matches.

12. The method of claim 9, wherein modifying the parent node includes:

generating logic for the parent node using control flow analysis; and

using the logic to search the index.

13. The method of claim 1, further comprising:

determining whether the operator node is a specific type of operator; and

performing the replacing when it is determined that the operator node is the specific type of operator.

14. The method of claim 1, further comprising

collecting statistics on frequency of use of group configurations;

and

determining whether the statistics indicate flattening is appropriate,

wherein the replacing is not performed when it is determined that the statistics do not indicate flattening is appropriate.

15. A tangible computer-readable storage medium having recorded and embodied thereon instructions that, when executed by the one or more processors of the computer system, cause the computer system to perform the method of claim 1.

16. The method of claim 1, the group of nodes including at least one leaf node and at least one operator node.

17. A system comprising:

one or more processors; and

one or more memories storing an index and instructions that, when executed by the one or more processors, cause the processors to perform the operations of;

receiving a query to process against a search index;

building a query tree based on the query;

grouping at least some nodes of the query tree into a group of nodes based on an operator node that is a parent of the at least some nodes, the group of nodes retaining the functionality of the operator node;

eliminating the operator node by replacing the operator node with the group of nodes in the tree; and

traversing the tree to obtain a result list from the search index responsive to the query.

18. The system of claim 17, wherein replacing the operator node includes modifying a parent node of the operator node to recognize the group of nodes.

19. The system of claim 18, wherein modifying the parent node includes creating a jump-table, the jump-table enabling a particular node to branch directly to another node.

20. The system of claim 19, wherein as part of traversing the tree, the operations further include cutting a branch of the query tree by modifying the jump-table when the another node exhausts its possible matches.

21. The system of claim 18, wherein modifying the parent node includes:

generating logic for the parent node using control flow analysis; and

using the logic to search the index.

22. The system of claim 17, the operations further comprising:

determining whether the operator node is a specific type of operator; and

performing the replacing when it is determined that the operator node is the specific type of operator.

23. A method of flattening a search query at a computer system comprising one or more processors and a memory storing one or more programs for execution of the method by the one or more processors, the method comprising:

building a query tree based on the query;

identifying a portion of the tree for flattening, the portion including at least one operator node and children of the operator node;

eliminating the at least one operator node by generating a jump-table for the portion of the tree, the jump-table including a row for the children of the operator node, each row including an indication of a next node to invoke based on a result of a match operation performed by the node associated with the row; and

traversing the tree using the jump-table and a search index to obtain a result list that is responsive to the query.

24. The method of claim 23, wherein as part of traversing the tree, the method further includes:

identifying an end-of-list condition for a match operation on a particular node; and

in response to identifying the end-of-list condition, modifying the jump-table to skip the row associated with the particular node.

25. The method of claim 23, the match operation returning a first identifier, the first identifier being equal to or greater than a second identifier that is given to the match operation.

26. The method of claim 25, the jump-table including an indication of a first next node if the second identifier matches the first identifier and including an indication of a second next node if the first identifier is greater than the second identifier.

27. A tangible computer-readable storage medium having recorded and embodied thereon instructions that, when executed by the one or more processors of the computer system, cause the computer system to perform the method of claim 23.