Hybrid evaluation of expressions in DBMS
First Claim
Patent Images
1. A method of evaluating an expression in a database management system, comprising:
- (a) determining whether said expression is strictly needed, wherein said determining step comprises determining if one or more arguments of said expression must be evaluated before said expression itself can be evaluated;
(b) determining a number of parents of said expression;
(c) evaluating said expression at an execution location using every argument in said expression, when it is determined that said expression has multiple parents, when said expression is strictly needed; and
(d) evaluating said expression at most once at an execution location using a subset of arguments in said expression, regardless of whether an evaluation of said expression is needed more than once at said execution location, when it is determined that said expression has a single parent.
1 Assignment
0 Petitions
Accused Products
Abstract
A hybrid approach for evaluating expressions in database management systems is described herein. For each expression in an execution location (XL), an execution strategy is selected. The strategies considered are lazy, lazy with memoization, eager, and eager with memoization. The execution strategies are assigned in a way that minimizes the estimated cost of evaluation.
61 Citations
16 Claims
-
1. A method of evaluating an expression in a database management system, comprising:
-
(a) determining whether said expression is strictly needed, wherein said determining step comprises determining if one or more arguments of said expression must be evaluated before said expression itself can be evaluated; (b) determining a number of parents of said expression; (c) evaluating said expression at an execution location using every argument in said expression, when it is determined that said expression has multiple parents, when said expression is strictly needed; and (d) evaluating said expression at most once at an execution location using a subset of arguments in said expression, regardless of whether an evaluation of said expression is needed more than once at said execution location, when it is determined that said expression has a single parent. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An article of manufacture including a computer-readable medium having instructions stored thereon that, when executed by a processing device, cause the processing device to perform operations comprising:
-
determining whether said expression is strictly needed wherein said determining step comprises determining if one or more arguments of said expression must be evaluated before said expression itself can be evaluated; determining a number of parents of said expression; evaluating said expression at an execution location using every argument in said expression, when it is determined that said expression has multiple parents, and said expression is strictly needed; and evaluating said expression at most once at an execution location using a subset of arguments in said expression, regardless of whether an evaluation of said expression is needed more than once at said execution location, when it is determined that said expression has a single parent. - View Dependent Claims (8, 9, 10, 11)
-
-
12. A compiler that evaluates an expression in a database management system, comprising:
-
a first module configured to determine whether said expression is strictly needed, and configured to determine if one or more arguments of said expression must be evaluated before said expression itself can be evaluated; a second module configured to determine a number of parents of said expression a third module configured to evaluate said expression at an execution location using every argument in said expression, when it is determined that said expression has multiple parents, and said expression is strictly needed; and a fourth module configured to evaluate said expression at most once at an execution location using a subset of arguments in said expression, regardless of whether an evaluation of said expression is needed more than once at said execution location, when it is determined that said expression has a single parent. - View Dependent Claims (13, 14, 15, 16)
-
Specification