STRUCTURAL EQUIVALENCE

摘要

The systems, methods, devices, and non-transitory media of the various embodiments enable query execution plan graphs to be compared to determine whether all or portions of two or more queries define data sets that are structurally equivalent. Two data sets may be structurally equivalent when each data set may be composed with a bijective relation that yields the other. In the various embodiments, when all or a portion of a first query that has been previously run defines a data set that is structurally equivalent to a data set defined by all or a portion of a second query that is to be run, the structure preserving transform may be applied to the corresponding portion of the second query to transform that portion of the second query into the corresponding portion of the first query, thereby allowing the results from previously running the first query to be reused.

主权项

1. A method for data reuse based on query structural equivalence, comprising:
receiving a first expression defining a first data set; identifying a first plurality of candidate expressions that match all or a portion of the first expression, wherein the first plurality of candidate expressions define a first plurality of data sets; determining whether a first candidate expression in the first plurality of candidate expressions defines a data set that is structurally equivalent to the first data set; and transforming all or a portion of the first expression into the first candidate expression in response to determining that the first candidate expression defines a data set that is structurally equivalent to the first data set.