Optimizing relational algebra operations using generic equivalence discriminators and lazy products
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Optimizing relational algebra operations using generic equivalence discriminators and lazy products. / Henglein, Fritz.
Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. Association for Computing Machinery, 2010. p. 73-82.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Optimizing relational algebra operations using generic equivalence discriminators and lazy products
AU - Henglein, Fritz
PY - 2010
Y1 - 2010
N2 - We show how to efficiently evaluate generic map-filter-product queries, generalizations of select-project-join (SPJ) queries in re- lational algebra, based on a combination of two novel techniques: generic discrimination-based joins and lazy (formal) products.Discrimination-based joins are based on the notion of (equiv- alence) discriminator. A discriminator partitions a list of values according to a user-specified equivalence relation on keys the val- ues are associated with. Equivalence relations can be specified in an expressive embedded language for denoting equivalence rela- tions. We show that discriminators can be constructed generically (by structural recursion on equivalence expressions), purely func- tionally, and efficiently (worst-case linear time). The array-based basic multiset discrimination algorithm of Cai and Paige (1995) provides a base discriminator that is both asymptotically and prac- tically efficient. In contrast to hashing, discrimination is fully ab- stract (only depends on which equivalences hold on its inputs), and in contrast to comparison-based sorting, it does not require an or- dering relation on its inputs. In particular, it is applicable to ref- erences (pointers). Furthermore, it has better asymptotic computa- tional complexity than both sorting and hashing.We represent cross-products and unions lazily (symbolically) as formal products of the argument sets (relations). This allows the selection operation to recognize on the fly whenever it is applied to a cross-product and invoke an efficient equijoin implementation. In particular, queries can still be formulated naively, using filter, map and product without an explicit join operation, yet garner the advantages of efficient join-algorithms during evaluation.The techniques subsume many of the optimization techniques based on relational algebra equalities, without need for a query preprocessing phase. They require no indexes and behave purely functionally. They can be considered a form of symbolic execution of set expressions that automate and encapsulate dynamic program transformation of such expressions and lead to asymptotic perfor- mance improvements over naive execution in many cases.
AB - We show how to efficiently evaluate generic map-filter-product queries, generalizations of select-project-join (SPJ) queries in re- lational algebra, based on a combination of two novel techniques: generic discrimination-based joins and lazy (formal) products.Discrimination-based joins are based on the notion of (equiv- alence) discriminator. A discriminator partitions a list of values according to a user-specified equivalence relation on keys the val- ues are associated with. Equivalence relations can be specified in an expressive embedded language for denoting equivalence rela- tions. We show that discriminators can be constructed generically (by structural recursion on equivalence expressions), purely func- tionally, and efficiently (worst-case linear time). The array-based basic multiset discrimination algorithm of Cai and Paige (1995) provides a base discriminator that is both asymptotically and prac- tically efficient. In contrast to hashing, discrimination is fully ab- stract (only depends on which equivalences hold on its inputs), and in contrast to comparison-based sorting, it does not require an or- dering relation on its inputs. In particular, it is applicable to ref- erences (pointers). Furthermore, it has better asymptotic computa- tional complexity than both sorting and hashing.We represent cross-products and unions lazily (symbolically) as formal products of the argument sets (relations). This allows the selection operation to recognize on the fly whenever it is applied to a cross-product and invoke an efficient equijoin implementation. In particular, queries can still be formulated naively, using filter, map and product without an explicit join operation, yet garner the advantages of efficient join-algorithms during evaluation.The techniques subsume many of the optimization techniques based on relational algebra equalities, without need for a query preprocessing phase. They require no indexes and behave purely functionally. They can be considered a form of symbolic execution of set expressions that automate and encapsulate dynamic program transformation of such expressions and lead to asymptotic perfor- mance improvements over naive execution in many cases.
U2 - 10.1145/1706356.1706372
DO - 10.1145/1706356.1706372
M3 - Article in proceedings
SN - 978-1-60558-727-1
SP - 73
EP - 82
BT - Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation
PB - Association for Computing Machinery
Y2 - 18 January 2010 through 19 January 2010
ER -
ID: 168290345