Execution engine for generating reports for measuring effectiveness of advertising campaigns

• US 10,115,123 B2
• Filed: 09/17/2014
• Issued: 10/30/2018
• Est. Priority Date: 09/17/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: McHugh, Jason George, Snyder, Sean Michael
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US14/488,577
• Publication Number:
  US 20160078470A1
• Time in Patent Office: 1,504 Days
• Field of Search: 707603, 707714, 707754, 707999102
• CPC Class Codes: G06Q 30/0242 Determining effectiveness of advertisements

Abstract

A report execution engine processes reports for evaluating advertising campaigns. The report execution engine maintains a plurality of generators, each generator including instructions to generate execution plans for one or more columns of a report. The report execution engine uses different generators for generating sub-plans for processing columns of the report. A generator generates a sub-plan for processing a column of the report and invokes other generators for generating sub-plans for remaining columns of the report. The generator receives a sub-plan for the remaining columns of the report from another generator and generates a combined execution plan based on the sub-plans. An execution plan comprises a hierarchical structure of nodes, each node representing a portion of computation of the report. The report execution engine generates the report based on the execution plan and sends the results for presentation.

Claims

1. A computer-implemented method comprising:

storing a plurality of generators, each generator comprising computer-executable instructions for generating a sub-plan, wherein the sub-plan includes instructions to generate execution plans for one or more columns of reports;

receiving, by a report execution engine, a report definition specifying a plurality of columns that include one or more metrics based on user interactions with an online system;

identifying a set of generators from the plurality of generators, each of the set of generators configured to generate execution plan of at least one of the plurality of columns specified by the report definition, the set of generators comprising a first generator, and a second generator, wherein the plurality of generators are arranged as a series of generators, the identifying comprising, repeating until all columns of the report definition are assigned to at least a generator;

providing a set of columns of the report definition to generators from the series of generators until a particular generator responds with information indicating that the particular generator includes instructions to process at least a subset of columns from the set of columns;

assigning the subset of columns to the particular generator; and

providing the remaining columns of the set of columns to the remaining generators from the series of generators to assign the remaining columns to the plurality of generators;

generating a plurality of sub-plans for processing columns of the report definition, the generating comprising, for each generator assigned to at least a column of the report definition;

generating, by the generator, a sub-plan for processing the columns of the report definition assigned to the generator;

generating a combined execution plan by combining one or more pairs of sub-plans from the plurality of sub-plans, each pair of sub-plans comprising a first sub-plan and a second sub-plan, wherein the combined execution plan uses an operator to combine resulting data of the first sub-plan and resulting data of the second sub-plan;

executing, by the report execution engine, the combined execution plan to generate results based on the received report definition; and

sending, by the report execution engine, the generated results for presentation.

2. The computer-implemented method of claim 1, further comprising:

identifying the first generator, the identifying comprising, sending the report definition to each of a series of generators from the plurality of generators until a generator returns information indicating the generator includes instructions to generate execution plan for at least a column of the report definition; and

using the generator as the first generator.

3. The computer-implemented method of claim 2, further comprising:

providing information identifying the remaining columns of the report definition to one or more of the remaining generators from the plurality of generators for identifying the second generator.

4. The computer-implemented method of claim 1, wherein processing the remaining columns of the report definition by the second generator comprises:

generating, by the second generator, a sub-plan for a second column of the report definition; and

providing the remaining columns other than the first and the second column to a third generator for generating a third sub-plan.

5. The computer-implemented method of claim 4, further comprising:

receiving, from the third generator, a third sub-plan for processing the columns of the report definition other than the first column and the second column; and

generating the second sub-plan by combining the sub-plan for processing the second column with the third sub-plan.

6. The computer-implemented method of claim 1, wherein the operator for combining the first sub-plan and the second sub-plan is one of:

a concatenate operator, a join operator, a cross product operator, or a union operator.

7. The computer-implemented method of claim 1, further comprising:

selecting the operator for combining the first sub-plan with the second sub-plan based on the results returned by the first sub-plan and the second sub-plan, the results comprising a first result set generated by the first sub-plan and a second result set generated by the second sub-plan.

8. The computer-implemented method of claim 7, further comprising:

responsive to determining that the first result set is distinct from the second result set, selecting a concatenate operator for combining the first sub-plan and the second sub-plan.

9. The computer-implemented method of claim 7, further comprising:

responsive to determining that the first result set and the second result set comprise partial rows, selecting a join operator for combining the first sub-plan and the second sub-plan.

10. The computer-implemented method of claim 9, further comprising:

responsive to determining that the report requires empty values of columns from one of the result sets, selecting an outer join operator for combining the first sub-plan and the second sub-plan.

11. The computer-implemented method of claim 9, further comprising:

responsive to determining that the report requires full data for columns from both the result sets, selecting an inner join operator for combining the first sub-plan and the second sub-plan.

12. The computer-implemented method of claim 1, further comprising:

receiving a new report definition using a first metric defined by a new generator and a second metric defined by an existing generator; and

generating an execution plan for the new report definition based on a sub-plan generated by the new generator and a sub-plan generated by the existing generator.

13. The computer-implemented method of claim 1, wherein the metrics associated with the advertising campaign comprise one or more of:

information describing impressions of advertisements shown to users and information describing conversions.

14. The computer-implemented method of claim 1, wherein the report definition specifies a column comprising information identifying advertising campaigns.

15. The computer-implemented method of claim 1, further comprising:

introducing in the first sub-plan and the second sub-plan, additional columns not specified by the report definition; and

using the additional columns to combine intermediate results generated by first sub-plan with intermediate results generated by the second sub-plan.

16. The computer-implemented method of claim 1, wherein the second generator determines the operator based on a type of data returned by the first sub-plan and the second sub-plan.

17. The computer-implemented method of claim 1, wherein the operator is at least one of:

a concatenate operator, an outer join operator, an inner join operator, or some combination thereof.

18. A non-transitory computer readable storage medium storing instructions for:

storing a plurality of generators, each generator comprising computer-executable instructions for generating a sub-plan, wherein the sub-plan includes instructions to generate execution plans for one or more columns of reports;

receiving, by a report execution engine, a report definition specifying a plurality of columns that include one or more metrics based on user interactions with an online system;

identifying a set of generators from the plurality of generators, each of the set of generators configured to generate execution plan of at least one of the plurality of columns specified by the report definition, the set of generators comprising a first generator, and a second generator, wherein the plurality of generators are arranged as a series of generators, the identifying comprising, repeating until all columns of the report definition are assigned to at least a generator;

providing a set of columns of the report definition to generators from the series of generators until a particular generator responds with information indicating that the particular generator includes instructions to process at least a subset of columns from the set of columns;

assigning the subset of columns to the particular generator; and

providing the remaining columns of the set of columns to the remaining generators from the series of generators to assign the remaining columns to the plurality of generators;

generating a plurality of sub-plans for processing columns of the report definition, the generating comprising, for each generator assigned to at least a column of the report definition;

generating, by the generator, a sub-plan for processing the columns of the report definition assigned to the generator;

generating a combined execution plan by combining one or more pairs of sub-plans from the plurality of sub-plans, each pair of sub-plans comprising a first sub-plan and a second sub-plan, wherein the combined execution plan uses an operator to combine resulting data of the first sub-plan and resulting data of the second sub-plan;

executing, by the report execution engine, the combined execution plan to generate results based on the received report definition; and

sending, by the report execution engine, the generated results for presentation.

19. The non-transitory computer readable storage medium of claim 18, further comprising:

identifying the first generator, the identifying comprising, sending the report definition to each of series of generators from the plurality of generators until a generator returns information indicating the generator includes instructions to generate execution plan for at least a column of the report definition; and

using the generator as the first generator.

20. The non-transitory computer readable storage medium of claim 18, further comprising, wherein processing the remaining columns of the report definition by the second generator comprises:

generating, by the second generator, a sub-plan for a second column of the report definition; and

providing the remaining columns of the report definition to a third generator for generating a third sub-plan for columns of the report definition other than the first column and the second column.

21. The non-transitory computer readable storage medium of claim 18, further comprising:

selecting the operator for combining the first sub-plan with the second sub-plan based on the results returned by the first sub-plan and the second sub-plan, the results comprising a first result set generated by the first sub-plan and a second result set generated by the second sub-plan.

22. A computer-implemented system comprising:

a computer processor; and

a non-transitory computer readable storage medium storing instructions for;

storing a plurality of generators, each generator comprising computer-executable instructions for generating a sub-plan, wherein the sub-plan includes instructions to generate execution plans for one or more columns of reports;

receiving, by a report execution engine, a report definition specifying a plurality of columns that include one or more metrics based on user interactions with an online system;

identifying a set of generators from the plurality of generators, each of the set of generators configured to generate execution plan of at least one of the plurality of columns specified by the report definition, the set of generators comprising a first generator, and a second generator, wherein the plurality of generators are arranged as a series of generators, the identifying comprising, repeating until all columns of the report definition are assigned to at least a generator;

providing a set of columns of the report definition to generators from the series of generators until a particular generator responds with information indicating that the particular generator includes instructions to process at least a subset of columns from the set of columns;

assigning the subset of columns to the particular generator; and

providing the remaining columns of the set of columns to the remaining generators from the series of generators to assign the remaining columns to the plurality of generators;

generating a plurality of sub-plans for processing columns of the report definition, the generating comprising, for each generator assigned to at least a column of the report definition;

generating, by the generator, a sub-plan for processing the columns of the report definition assigned to the generator;

generating a combined execution plan by combining one or more pairs of sub-plans from the plurality of sub-plans, each pair of sub-plans comprising a first sub-plan and a second sub-plan, wherein the combined execution plan uses an operator to combine resulting data of the first sub-plan and resulting data of the second sub-plan;

executing, by the report execution engine, the combined execution plan to generate results based on the received report definition; and

sending, by the report execution engine, the generated results for presentation.