Query Analysis in a Database

1 . A method of analyzing an expression to infer output data properties, comprising:

storing, in a storage device, a root node “e” in R, in which “e” is an expression and R is a root node of an abstract syntax tree (AST) of the expression “e”;

storing a number of child nodes of R into C 1 , . . . C n ;

with a processor coupled to the storage device, calling analyze(C i );

storing output properties of expression C into P i i; and

determining if any of the child nodes C i in {C 1 . . . C n } has not been analyzed;

in which if the last child node has been analyzed:

with the processor, calling compute-output-properties(R, P 1 , . . . P n );

storing, in the storage device, the result in P output : and

returning P output as the output properties of the expression “e.”

2 . The method of claim 1 , in which if the last child node has not been analyzed:

with the processor, calling analyze(C i ) in connection with the next child node to be analyzed;

storing, in a storage device, output properties of expression C into P i ; and

determining if any of the child nodes C i in {C 1 . . . C n } has not been analyzed.

3 . The method of claim 2 , in which with a processor, calling analyze(C i ), storing, in a storage device, output properties of expression C into P i , and determining if any of the child nodes C i in {C 1 . . . C n } has not been analyzed is performed any number of times.

4 . The method of claim 2 , in which with a processor, calling analyze(C i ), storing, in a storage device, output properties of expression C into P i , and determining if any of the child nodes C i in {C 1 . . . C n } has not been analyzed is performed until C n has been analyzed.

5 . The method of claim 1 , in which calling compute-output-properties(R, P 1 , . . . P n ) comprises:

with the processor, determining if any of the Min i values are unbounded;

with the processor, determining if any of the Max i values are unbounded;

with the processor, determining if all the Sort i values are non-decreasing, non-increasing, or constant;

with the processor, determining if all of the NullPresent i values are false; and

returning (Min out , Max out , Sort out , NullPresent out ) as the output properties P output .

6 . The method of claim 5 , in which, if any of the Min i values are unbounded, then setting Min out =unbounded, and if Min i values are not unbounded, then setting Min out =Min 1 + . . . +Min n .

7 . The method of claim 5 , in which, if any of the Max i values are unbounded, then setting Max out =unbounded, and if the Max i values are not unbounded, then setting Max out =Max 1 + . . . +Max n .

8 . The method of claim 5 , in which:

if all the Sort, values are sorted non-decreasing, then setting Sort out =non-decreasing;

if all the Sort i values are sorted non-increasing, then setting Sort out =non-increasing;

if all the Sort i values are sorted constant, then setting Sort out =constant; and

if all the Sort i values are not sorted non-decreasing, non-increasing, or constant, then setting Sort out =unordered.

9 . The method of claim 5 , in which:

if all of the NullPresent i values are false, then setting NullPresent out =false; and

if any of the NullPresent i values are true, then setting NullPresent out =true.

10 . A data processing system comprising:

a database to store data;

a processor communicatively coupled to the database to issue a query to the database in which, upon receipt of the query from the processor, the database analyzes a number of child nodes to determine a number of properties of the an expression associated with the child nodes; and

an output device to output the properties to a user.

11 . The data processing system of claim 10 , in which the database is a programmable processor, a computer, a system on a chip, an analytic database, a relational database, a non-relational database, a structured database, a stream processing system, an in-memory database, a key-value database, or combinations thereof.

12 . A method for performing an evaluation for a query comprising:

with a database, associating with a portion of a table column in a query a respective value range that represents minimum and maximum possible values of the portion of the table column;

associating a respective value range that represents minimum and maximum possible output values resulting from evaluation of an operator based on associated value ranges of a number of inputs to the operator; and

identifying a number of the operators that would evaluate to false based on associated value ranges of their inputs.

13 . The method of claim 12 , in which identifying a number of the operators that would evaluate to false based on associated value ranges of their inputs further comprises not analyzing records for which the operators would evaluate to false.

14 . The method of claim 12 , further comprising:

identifying a number of the operators that evaluate to true based on associated value ranges of their inputs; and

outputting records corresponding to a number of operators that evaluate to true to an output device.

15 . The method of claim 12 , further comprising:

identifying a number of the operators that evaluate to unbounded based on associated value ranges of their inputs, the unbounded operators comprising a portion of the table column;

with a database, associating with the portion of the table column a respective value range that represents minimum and maximum possible values of the portion of the table column;

associating a respective value range that represents minimum and maximum possible output values resulting from evaluation of an operator based on associated value ranges of a number of inputs to the operator; and

identifying a number of the operators that would evaluate to false based on associated value ranges of their inputs.

16 . The method of claim 15 , in which the method of claim 4 is performed any number of iterations until the operators evaluate to true.

17 . The method of claim 12 , in which a minimum or maximum value for a respective value range of an operator is unknown.

18 . The method of claim 12 , in which the table column is partitioned, and in which the value range associated with the table column comprises a value range for each partition.

19 . The method of claim 12 , in which the table column is partitioned into a plurality of partitions, and in which each partition's values are stored in a sorted order.