Query serving infrastructure

• US 20070198484A1
• Filed: 02/22/2006
• Published: 08/23/2007
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Walters, Chad, Ahmed, Nawaaz, Travis, Robert
• Granted Patent: US 7,827,523 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models

Abstract

A system and method for dynamically composing a class is provided. A query is parsed and a compiler object tree is generated that corresponds to the operators in the query. A set of feature requests and responses are initiated and a set of feature objects are generated that are executed at runtime. The language of the query may be extended by registering a new operator, and optionally a new feature for a query language, with a search engine without modifying the source code of the search engine. The new operator may be specified in a plug-in and provided to the search engine via the plug-in. An application converts an end user query into an application query that conforms to the query language supported by the search engine and includes the new operator. The application query may also include references to traditional programming constructs and search engine primitives.

Claims

1. A method comprising performing a machine-executed operation involving instructions for dynamic class composition, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

receiving, at a compiler, a statement that conforms to syntax rules of a language supported by the compiler;

wherein the statement includes one or more constructs, including a particular construct; and

compiling the statement, wherein the step of compiling the statement includes the compiler performing the steps of;

dynamically loading a plug-in;

obtaining, from the plug-in, code for use in compiling statements that include paid particular construct; and

using said code to generate executable code for said statement.

2. The method of claim 1 wherein the step of obtaining code includes obtaining an execution object that includes code which, when executed, performs a function associated with said particular construct.

3. The method of claim 1 wherein:

the particular construct is a construct for which support was not provided by the designer of the compiler; and

the plug-in is provided by a party other than the designer of the compiler.

4. The method of claim 1 wherein:

the step of compiling the statement includes;

creating a parse tree by parsing the statement based on the syntax rules of the language;

generating, based on the parse tree, a compiler object tree that comprises a plurality of compiler objects, wherein each compiler object corresponds to a construct in said statement; and

obtaining the compiler object for said particular construct from the plug-in.

5. The method of claim 4 wherein:

the language supported by the compiler is a query language;

the statement is a query for providing one or more features;

the particular construct is a particular operator contained in the query; and

the each compiler object in the compiler object tree corresponds to an operator in said query.

6. The method of claim 5 wherein the step of compiling the statement includes generating a feature object which, when executed, returns a feature based on the query.

7. The method of claim 6 wherein the step of generating a feature object includes:

sending feature requests to one or more compiler objects in said compiler object tree; and

wherein each compiler object contains logic for determining how to respond to feature requests, wherein the logic reflects the semantics of the operator to which the compiler object corresponds.

8. The method of claim 6 at least one of the one or more compiler objects responding to the feature requests by providing an execution object used to construct a feature value for an applicable document.

9. The method of claim 7 wherein:

said particular operator is a polymorphic operator; and

said compiler object for said particular operator is designed to respond to multiple types of feature requests.

10. The method of claim 9 wherein the compiler object for the particular operator includes logic for:

providing a first feature object in response to a request for a first type of feature; and

providing a second feature object in response to a request for a second type of feature;

wherein the logic of the first feature object is different than the logic of the second feature object.

11. The method of claim 6 wherein the step of generating a feature object includes obtaining one or more additional feature objects used to construct the feature object by traversing the feature request down a relative portion of the compiler object tree, beginning with a current compiler object of the compiler object tree.

12. The method of claim 11 wherein the step of traversing includes each compiler object that receives a feature request for a particular feature determining whether to:

pass the feature request to compiler objects that reside below the compiler object in the compiler object tree;

ignore the feature request without passing the request to compiler objects that reside below the compiler object in the compiler object tree; and

provide a feature object for use in constructing said particular feature, wherein the feature object that encapsulates how the operator represented by the compiler object generates the particular feature identified in said feature request.

13. The method of claim 12 wherein the step of traversing includes:

sending feature requests to compiler objects that reside below a particular compiler object when the operator represented by the particular compiler object requires features from the operators represented by the compiler objects that reside below the particular compiler object.

14. The method of claim 12 wherein the step of determining is based, at least in part, on attributes, specified in the query, for the operator associated with the compiler object.

15. The method of claim 7, wherein:

the query includes a participate attribute associated with the particular operator; and

the participate attribute determines whether the compiler object associated with the particular operator responds to a feature request.

16. The method of claim 7, wherein:

the query includes a transparency attribute associated with the particular operator; and

the transparency attribute determines whether the compiler object associated with the particular operator forwards a feature request to a different compiler object in the compiler object tree.

17. A method comprising performing a machine-executed operation involving instructions for dynamic class composition, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions are instructions which, when executed by one or more processors,

cause the one or more processors to perform the steps of;

receiving, at a compiler, a statement that conforms to syntax rules of a language supported by the compiler;

wherein the statement includes one or more constructs, including a particular construct; and

compiling the statement, wherein the step of compiling the statement includes the compiler performing the steps of;

creating a parse tree by parsing the statement based on the syntax rules of the language;

generating, based on the parse tree, a compiler object tree that comprises a plurality of compiler objects, wherein each compiler object corresponds to a construct in said statement; and

generating executable code for said statement based on feature objects obtained by issuing requests to compiler objects in the compiler object tree.

18. The method of claim 17 wherein:

the language supported by the compiler is a query language;

the statement is a query for providing one or more features;

the particular construct is a particular operator contained in the query; and

the each compiler object in the compiler object tree corresponds to an operator in said query.

19. The method of claim 18 wherein the step of generating executable code includes generating a feature object which, when executed, returns a feature based on the query.

20. The method of claim 19 wherein the step of generating a feature object includes:

sending feature requests to one or more compiler objects in said compiler object tree; and

wherein each compiler object contains logic for determining how to respond to feature requests, wherein the logic reflects the semantics of the operator to which the compiler object corresponds.

21. The method of claim 19 wherein at least one of the one or more compiler objects responds to the feature requests by providing an execution object used to construct a feature value for an applicable document.

22. The method of claim 20 wherein:

said query includes a particular operator that is a polymorphic operator; and

said compiler object for said particular operator is designed to respond to multiple types of feature requests.

23. The method of claim 22 wherein the compiler object for the particular operator includes logic for:

providing a first feature object in response to a request for a first type of feature; and

providing a second feature object in response to a request for a second type of feature;

wherein the logic of the first feature object is different than the logic of the second executor object.

24. The method of claim 19 wherein the step of generating a feature object includes obtaining one or more additional feature objects used to construct the feature object by traversing the feature request down a relevant portion of the compiler object tree, beginning with a current compiler object of the compiler object tree.

25. The method of claim 24 wherein the step of traversing includes each compiler object that receives a feature request for a particular feature determining whether to:

pass the feature request to compiler objects that reside below the compiler object in the compiler object tree;

ignore the feature request without passing the request to compiler objects that reside below the compiler object in the compiler object tree; and

provide a feature object for use in constructing said particular feature, wherein the feature object that encapsulates how the operator represented by the compiler object generates the particular feature identified in said feature request.

26. The method of claim 25 wherein the step of traversing includes:

sending feature requests to compiler objects that reside below a particular compiler object when the operator represented by the particular compiler object requires features from the operators represented by the compiler objects that reside below the particular compiler object.

27. The method of claim 25 wherein the step of determining is based, at least in part, on attributes, specified in the query, for the operator associated with the compiler object.

28. The method of claim 20, wherein:

the query includes a participate attribute associated with the particular operator; and

the participate attribute determines whether the compiler object associated with the particular operator responds to a feature request.

29. The method of claim 20, wherein:

the query includes a transparency attribute associated with the particular operator; and

the transparency attribute determines whether the compiler object for the particular operator forwards a feature request to a different compiler object in the compiler object tree.

30. A method comprising performing a machine-executed operation involving instructions for extending a query language, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions are instructions which, when executed by one or more processors,

cause the one or more processors to perform the steps of;

registering a new operator with a compiler;

wherein the step of registering includes identifying a plug-in that includes a first code that encapsulates logic of the new operator;

receiving a query that includes the new operator; and

using the first code that encapsulates logic of the new operator, from the plug-in, to compile the query to produce executable code that includes a second code for performing an operation associated with the new operator.

31. The method of claim 30, wherein:

the step of compiling is performed by a compiler associated with a search engine; and

the instructions further include instructions for executing the executable code using an execution engine associated with the search engine.

32. The method of claim 30, wherein:

an end user query is received from a user over a network by an application; and

based on the end user query, the application;

converts the end user query into the application query that includes the new operator, and

submits the application query to the search engine.

33. The method of claim 32, wherein the instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

before execution of the application query, generating a tree of a plurality of compiler objects based on the application query, wherein each compiler object corresponds to at least one operator in the application query;

sending a feature request from a first compiler object in the tree to a second compiler object in the tree; and

in response to receiving the feature request, the second compiler object returning a feature object, wherein the feature object includes the second code that is executed during execution of the application query.

34. The method of claim 32, wherein the plug-in is provided to the compiler by a designer of the application who is not the designer of the compiler.

35. The method of claim 34, wherein the plug-in includes a definition for a new feature and the new operator is associated with the new feature.

36. The method of claim 30, wherein the compiler is moved from a first runtime environment that supports a particular programming interface to a second runtime environment that supports the particular programming interface.

37. The method of claim 30, wherein:

the new operator is a polymorphic operator; and

an object at compile time that corresponds to the new operator is capable of providing more than one output.

38. A method comprising performing a machine-executed operation involving instructions for compiling an application query received from a search application, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions are instructions which, when executed by one or more processors,

cause the one or more processors to perform the steps of;

a developer of the search application registering, with a compiler, code that references a search primitive of a search engine through an API exposed by the search engine;

designing the search application so that it submits a query that includes a particular operator that is associated with the registered code;

when the compiler receives the application query, the compiler generating, based on the operator associated with the registered code, executable code that incorporates the registered code; and

executing the executable code;

wherein the search primitive is from the group consisting of;

document stream feature,

position stream feature, and

a unit operator.

39. The method of claim 38, wherein the executable code is executed against an index of a collection of web pages, wherein the index was generated, at least in part, by crawling the Internet.

40. The method of claim 38, wherein:

the search primitive is a document stream feature; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to executing code associated with the document stream feature, the search engine determining a set of documents that contain a set of one or more characters that are included in the query.

41. The method of claim 38, wherein:

the search primitive is a position stream feature; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to executing code associated with the position stream feature, the search engine determining a set of positions in a selected document of a set of one or more characters that are included in the query.

42. The method of claim 38, wherein:

the search primitive is a unit operator; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to executing code associated with the unit operator, the search engine identifying at least one of a document with the input to the unit operator, a position in a particular document of the input, and a score of a particular document based on the input.

43. A method comprising performing a machine-executed operation involving instructions for executing an application query, wherein the machine-executed operation is at least one of:

A) sending the instructions over transmission media;

B) receiving the instructions over transmission media;

C) storing the instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein the instructions are instructions which, when executed by one or more processors,

cause the one or more processors to perform the steps of;

receiving, at a search engine, the application query, wherein;

the search engine indexes web-accessible content on the Internet obtained, at least in part, by crawling the Internet to discover web-accessible content made available thereon; and

the application query includes at least one programming construct from the following programming constructs;

a variable assignment statement,

a conditional execution statement,

a list comprehension,

a participate attribute, and

a transparent attribute;

compiling the application query to generate a compiled query; and

executing the compiled query.

44. The method of claim 43, wherein:

the application query includes the variable assignment statement; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to receiving the application query, the search engine assigning a value in the variable assignment statement to a variable in the variable assignment statement and using said variable in execution of the application query.

45. The method of claim 43, wherein:

the application query includes the conditional execution statement; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to receiving the application query, the search engine executing a particular statement in the conditional execution statement only if the conditional is true.

46. The method of claim 43, wherein:

the application query includes the list comprehension; and

the instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the step of, in response to receiving the application query, the search engine determines a set of values for a variable by evaluating one or more conditions identified in the list comprehension.

47. The method of claim 43, wherein:

the application query includes the participate attribute;

the participate attribute is associated with a particular operator; and

the participate attribute determines whether, during compilation of the application query, a compiler object associated with the particular operator responds to a feature request.

48. The method of claim 43, wherein:

the application query includes the transparency attribute;

the transparency attribute is associated with a particular operator; and

the transparency attribute determines whether, during compilation of the application query, a compiler object associated with the particular operator forwards a feature request to a different compiler object.