Reorganizing Queries with Grouping
Rui Okura

Yukiyoshi Kameyama

University of Tsukuba
Tsukuba, Japan
rui@logic.cs.tsukuba.ac.jp

University of Tsukuba
Tsukuba, Japan
kameyama@acm.org

Abstract1

Language-integrated query has attracted much attention
from researchers and engineers. It enables one to write a
database query with high-level abstractions, which makes it
possible to compose, iterate, and reuse queries. An important
issue in language-integrated query is the N+1 query problem,
and Cheney et al. proposed a program-transformation approach to solve it for a core language of Microsoft’s LINQ. In
our previous work, we extended their language to grouping(GROUP BY in SQL) and aggregate functions, and showedthat any term can be transformed to a single SQL query.
It still has a problem in that the resulting queries may beunnecessarily large and inefficient.
This paper solves the problem. Our key idea is re-organizationof queries with nested control structures. While our previous
work decomposes grouping into finer primitives before transformation, the new algorithm fuses nested control structures
after transformation, while keeping the absence of nested
data structures. Our algorithm also eliminates correlated subqueries as much as possible, to obtain better performance. We
have conducted performance measurements, which showsthat our new algorithm reduces the size of generated queries
and improves the performance for several examples.

Language-integrated query provides high-level abstractions
to the database queries, and has been attracting much attention from researchers and engineers. Studies based on
typed functional languages provide type safety for languageintegrated query, such Ohori et al’s SML# [9], Grust et al’s
Ferry [5], and Cooper et al’s Links [4]. Among all, one of themost popular system is Microsoft’s LINQ1 , which integrates
SQL with a high-level programming language F# [8].
Research on language-integrated query has been carriedout by a number of studies. Earlier approaches were conservative in the sense that they put syntactic restrictions on its
query sublanguage so that only SQL-equivalent queries canbe written in the language, which leads to poor composability and reusability [6]. More ambitious approaches including
Cooper [3] and Cheney et al. [1] allow arbitrary composition of program fragments, thus allowing component-based
construction of large complicated queries. By composing
queries, we naturally get a query with nested control structures (such as SELECT in SQL), and nested data structures(such as record of records, record of list of records), which are
not directly implementable by most dialects of SQL. Cheney
et al. introduced a quotation mechanism for queries, and program transformation over quoted terms to eliminate nested
data/control structures. They succeeded in transforming any
query into a single SQL query, but their target SQL does
not contain grouping (GROUP BY) and aggregate functions(such as MAX and SUM), which are particularly importantin realistic applications.
In our previous work [10] we proposed an algorithm tocover grouping and aggregate functions under the assumption that the target SQL allows subqueries (nested queries). 2

CCS Concepts: • Theory of computation → Database
query processing and optimization (theory); • Softwareand its engineering → Functional languages.
Keywords: database, language-integrated query, grouping,aggregation, normalization, type safety
ACM Reference Format:
Rui Okura and Yukiyoshi Kameyama. 2020. Reorganizing Queries
with Grouping. In Proceedings of the 19th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE ’20), November 16–17, 2020, Virtual, USA. ACM, New
York, NY, USA, 13 pages. https://doi.org/10.1145/3425898.3426960

Introduction

д2◦ f0 ◦
д1z }| {z }| {{ f 4 ◦ G2 ◦ f 3 ◦ f 0 ◦ f 2 ◦ G1 ◦ f 1 (decomposition)|{z}{ f 4 ◦ G2
◦ f5 ◦
G1 ◦ f 1 (normalization)

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
GPCE ’20, November 16–17, 2020, Virtual, USA© 2020 Association for Computing Machinery.
ACM ISBN 978-1-4503-8174-1/20/11. . . $15.00
https://doi.org/10.1145/3425898.3426960

Figure 1. Overview of the Previous Work
1 https://docs.microsoft.com/en-us/dotnet/csharp/linq/
2 Subqueries are those queries whose input, output, or guard conditions

contain another query. PostgreSQL and several dialects of SQL allows
subqueries.

50

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi KameyamaG ◦ fi is fused to a single function and converted to a SELECT clause with grouping (written select_g in the figure).
We also found a rule for eliminating correlated subqueries,
which, if applicable, drastically improves the performanceof generated queries.
We have conducted performance measurements for various queries in language-integrated query with nested data
structures and nested control structures. Combined with thealgorithm in our previous work, the new algorithm works
surprisingly well; the performance of SQL queries generated
by our algorithm is the same or better than the performanceof those in our previous work for all examples, and it isalways better than those by Microsoft’s LINQ.
The contribution of this paper is summarized as follows:• We show that the algorithm in our previous worksometimes generates large queries for some cases, andtheir performance is rather poor if they contain correlated subqueries.
• We introduce new transformation rules which fusenested control structures in the generated queries.
• We conduct performance measurements on various
examples which use grouping and aggregation. The
results are in favor of our research compared with
Microsoft’s LINQ and our previous work.
The rest of this paper is organized as follows. Section 2 informally explains the problem in our previous work and theoverview of the results in this paper using examples. Section
3 gives the source language, its type system, and programtransformations in the previous work. Section 4 presents
our re-organization algorithm for queries with grouping andaggregate functions, and Section 5 gives the final transformation to SQL. Section 6 explains several involved examples. The performance measurements for our language is
explained in Section 7. Section 8 gives conclusion.

Fig. 1 illustrates how the algorithm works. The goal ofthis algorithm is to eliminate nested data structures from aquery with grouping and aggregate functions.
Terms such as fi and дi denote lambda terms λx .Q (aquery which takes an input table x and computes the valueof Q), and ◦ denotes function composition. Suppose we havea query д2 ◦ f 0 ◦ д1 where дi are queries with grouping andf 0 is a query without grouping. Functions in our language
may pass nested data structures such as a multi-set (bag) ofmulti-sets of records3 as intermediate data, hence the outputof д1 (the input of f 0 ) may be nested data, and similarly forthe output of f 0 .
In our previous work, we found that, by decomposing aquery with grouping (д1 and д2 ) into composition of smaller
operations such as a new grouping primitive G and existing
primitives in Cheney et al.’s language, we can apply Cheney
et al.’s normalization rules to eliminated nested data. The
primitive G is the ‘minimum’ grouping operator, namely,
it cannot destruct its input, nor compose output, and only
does grouping by specified keys and applying aggregate
functions to several fields of data. In the above figure, д1 isdecomposed to f 2 ◦ G1 ◦ f 1 where G1 is an instance of G andfi are instances of existing primitives. Then, we can apply
normalization rules by Cheney et al. to fi ◦ f j . We proved that,even with the G operator, we can eliminate all nested data
structures, and the resulting term can always be transformed
to a single query in SQL which allows subqueries.
Unfortunately, there is a problem in our previous work,
which we address in this paper. The final term f 4 ◦ G2 ◦ f 5 ◦G1 ◦ f 1 is converted to a query which has nested subqueries ofdepth five (five times nesting of SELECT statements), each ofwhich corresponds to one of fi and Gi . This is unnecessarily
redundant compared with the term before the decomposition,
whose depth is only three.

2

д2◦ f0 ◦
д1{ f 4 ◦ G2 ◦ f 3 ◦ f 0 ◦ f 2 ◦ G1 ◦ f 1{ f 4 ◦ G2
◦ f5 ◦
G1 ◦ f 1|{z}| {z }{

select_g◦

ExamplesThis section informally explains the outline of our work using several examples. We use the database consisting of two
tables in Fig. 3. The products table has the fields4 for productselect_g

Figure 2. Overview of This Work
pid
1
2
3
4

Fig. 2 gives our solution for the above problem. The idea issimple; while the decomposed form is needed to apply normalization, it is not needed after all nested data structures
are eliminated. Hence, we re-organize the resulting query byfusing function composition as much as possible, reducing
the size of the query. For this purpose, we present several fusion rules, which introduce no new nested data. For instance,

products
name catshirt
110
T-shirt 110
pants 111
suit
210

price
100
200
500
1000

ordersdatepid2020-01-01
1
2020-01-01
1
2020-01-01
2
2020-01-02
1
2020-01-02
4
2020-01-02
4

qty
3
10
2
5
15
20

Figure 3. Sample database tables

3 A simple (non-nested) data of table type is a multi-set of records which
4 We call each element of a record a field, which means a column for aconsist of basic data such a strings and numbers. Most SQL dialects canmanipulate such data only.

database table.

51

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

ID (pid), name (name), category (cat), and price (price), andthe orders table has the fields for the date of order (date),
product ID (pid), and quantity (qty).
2.1

FROM ( SELECT o .*FROM orders AS o
WHERE o. date = " 2020 -01 -01 " ) AS x
GROUP BY x. pidFirst Example

We see a problem in our previous work here. Initially we
had a simple query without nesting, but after transformation
we got a larger SQL query with nested SELECT statements. In
general, the query generated by our previous transformation
can be up to three times as large as the query before transformation, which is unacceptable. Even worse, the large sizeof queries sometimes causes a serious performance problem
of generated queries. This paper fixes these problems.

The following SQL query computes, for each order ID, thesum of quantities ordered on 2020-01-01.
SELECT o . pid AS pid ,SUM (o. qty ) AS qty_sum
FROM orders AS o
WHERE o . date = " 2020 -01 -01 "GROUP BY o . pid

Here, the SELECT statement is used with GROUP BY, andclassifies the given data by the value of the key o.pid. SUM isan aggregate function which computes the sum of all data ineach group. A query with grouping and aggregate functions
is frequently used in practical applications of database, yet,it has been an open problem [2] to cover GROUP BY in
language-integrated query before our previous study.
In our previous work, we proposed a solution for thisproblem when the target SQL allows subqueries. Our idea
is decomposition of queries, and the above query can be expressed in the following decomposed form:

2.2

Second Example

The second example is an instance of a nested query д2 ◦ f 1 ◦д1illustrated in the previous section.
Let д1 be the following function.
д1 (t 1 , t 2 ) = for(x ← G({date,pid},α 1 ) (t 1 ))yield {pid = x .pid,
sales = for(p ← t 2 )where (x .pid = p.pid)
yield {category = p.cat,sale = p.price ∗ x .qty_sum}}Q(simple) = G(pid,α ) (for(o ← table(“orders”))

where α 1 = {(qty, SUM, qty_sum)}

where (o.date = “2020-01-01”)

We can obtain a concrete query by applying д1 to two tables,for instance, д1 (table(”orders”), table(”products”)). д1 first
executes G({date,pid},α 1 ) (t 1 ) which computes a bag of the sumof quantity in each group classified by the value of the datefield and the pid field in the table t 1 . Then it computes anested data consisting of a bag of records with the fields pid
and sales, and the sales field is a bag of records.
The next function f extracts the sales field of an input
t, which is assumed to be a bag of records, and does somecomputation for each record.

yield o)where α = {(qty, SUM, qty_sum)}
Here, for(x ← T ) where B yield M corresponds to SELECTM FROM T AS x WHERE B in SQL. The G-operator is our new
operator for grouping and aggregate functions. It takes two
parameters (pid and α in the above example) and an argument (the term starting from for). Its first parameter is thefield(s) to be used as grouping key(s), and the second one
specifies (1) the field to which an aggregate function is applied, (2) an aggregate function, and (3) the field name which
stores the result of aggregation. The term G(pid,α ) (N ) classifies the input table N by the value of pid, computes the sumof the field qty in each group, and returns a bag (multi-set) of
the records consisting of the value of pid and the sum (in thefield qty_sum), hence, Q(simple) does the same computation
as the above SQL query.
The G-operator is a rather simplified operator than thegrouping feature in SQL. For instance, we cannot compute
SUM(qty * qty), nor SUM(qty)/2 by G alone. However, we
can express any SELECT statement with GROUP BY using
our G-operator and existing primitives; see Section 3.
Since the query Q(simple) uses no nested data as intermediate data, we can immediately convert it a SQL query as
follows.

f (t) = for(y ← t)for(z ← y.sales)
yield {category = z.category,sale = z.sale ∗ 0.8}
The third function in this series is д2 , which computes thesum of sales grouped by category, and extracts summationof sales (sales_sum) and multiplies it by 100.
д2 (t) = for(v ← G(category,α 2 ) (t))
yield {result = v.sale_sum ∗ 100}
where α 2 = {(sale, SUM, sale_sum)}
We can compose the three functions and apply the result
to concrete tables to obtain a concrete query. By executing(д2 ◦ f ◦ д1 )(table(”orders”), table(”products”)), we get:

SELECT x . pid AS pid ,SUM (x. qty ) AS qty_sum[{result = 176000}; {result = 2800000}].

52

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi Kameyama

Although the input and the output of this query are nonnested data (a bag of records which consists of fields withbasic values), nested data structures (a bag of records of bags)
are passed around between adjacent functions, hence theabove query is not directly expressible in SQL.
The transformation in our previous work can eliminate
the nested data structures in this query, and generate thefollowing SQL query (which we call Q 0 ).

In the next section we formally introduce the language
and our new transformation rules.

3

The Language with Grouping

This section presents the language Quelg, its type system,and program transformation rules in our previous work [10].
The new transformation in this paper will be given in thenext section.

SELECT v . sale_sum * 100 AS result
FROM ( SELECT z. category AS category ,SUM (z. sale ) AS sale_sum
FROM ( SELECT p. cat AS category ,p. price * x. qty_sum *0.8 AS sale
FROM ( SELECT y. date AS date ,y. pid AS pid ,SUM (y. qty ) AS qty_sum
FROM ( SELECT o .*FROM orders AS o)
AS y
GROUP BY y. date ,y. pid ) AS x ,products AS p
WHERE x. pid = p. pid ) AS z
GROUP BY z. category ) AS v

3.1

Language

We define the language Quelg for language-integrated query.
It is based on Cooper’s source language [3] without effects(which is nearly the same as Nested Relational Calculus[13]), and Cheney et al.’s T-LINQ [1] restricted to the codelevel terms. We added the grouping operator and aggregate
functions to their language.
Fig. 4 defines the syntax of terms in Quelg.
Terms M, N

Spec

α

::= x | c | λx . M | M N | ⊕(M)
| M ⊎ N | for(x ← M) N
| where M N | yield M| [ ] | table(t)| {l = M } | M.l | G(κ,α ) (M)::= {(l, ⊚, l ′)}Figure 4. Syntax of Terms in Quelg

The result is a single SQL, and can be executed in SQL processors which allow subqueries. However, it contains four-times
nested subqueries, which is unnecessarily large. In general,the decomposition may triple the depth of subqueries ofqueries, which is not acceptable. It also affects the performance of generated queries. It is true that a SQL optimizer
sometimes improves the performance of nested queries, but
it is not always the case. We found several examples whose
performance is rather poor compared with a hand-written,
equivalent SQL query.
The present paper solves this problem by transforming thegenerated queries further. The above example is transformedby our new transformation to the following one.

Terms are either a variable (x), constant (c), λ-abstraction,function application, primitive function call (where ⊕ denotes a primitive function), multiset union (M ⊎ N ), comprehension (for(x ← M) N ), conditional (where M N ), singleton (yield M), empty bag ([ ]), table expression (table(t)),
record construction ({l = M }), selection (M.l), or grouping(G(κ,α ) (L)).
An overlined expression denotes a sequence, for instance,l = M is an abbreviation for l 1 = M 1 , · · · , ln = Mn where
the length n is implicit. The metavariable t denotes a tablename (given by a string), l is a field name in the record, andκ is a finite set of field names used as grouping keys. The
specification α is a finite set of triples consisting of a fieldname (l) for the target of aggregation, an aggregate function(⊚), and a field name (l ′) for the result of aggregation.
Let us briefly explain the semantics of important constructs. First, most expressions compute a bag as its value,
where a bag is a multiset (an unordered list), and we write
it using list notation such as [a, a, b, c]. A table is a bag ofrecords such as {aдe = 25, name = “Tom”}. Whereas in thestandard database, each field of a record in a table should
hold a basic value such as integers or strings, Quelg allows
an arbitrarily data as the value of a field, hence nested data
structures such as a bag of records of records are legitimate(typable) in Quelg.

SELECT SUM ( z . sale ) * 100 AS result
FROM ( SELECT p. cat AS category ,p. price * SUM (o. qty ) * 0.8
AS saleFROM orders AS o , products AS p
WHERE o. pid = p. pid
GROUP BY o. date , o. pid , p. pid ,p. name , p. cat ,p. price ) AS z
GROUP BY z . category

The depth of subqueries in this query is smaller than thatof the query before transformation. By executing it, we get
the same result as the latter.

53

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

The term for(x ← M) N is bag-comprehension; for eachelement of the value of M (which should be a bag), it computes the term N which should return a bag, and returns themultiset-union of the bags. The term where L M returns thevalue of M if L returns true, and returns the empty bag [ ]otherwise. The term yield M returns a singleton multiset
consisting of the value of M.
The term G(κ,α ) (M) expresses the minimum functionalityof grouping and aggregation. It gets as input the value of M
(which should be a bag), and classifies the records based on
the values of grouping keys specified by κ, aggregates thevalues in the same group, and finally returns a bag of records
consisting of grouping keys and aggregated values.5 For
instance, by computing the query G(cat,α ) (table(“products”))
where α = {(price, MAX, max_price)} for the products table
in Section 2, we get [{cat = 210, max_price = 1000}] as its
result. We use typical aggregate functions such as SUM, AVG,
MAX, MIN and COUNT in the examples, but as long as ourtransformation is concerned, any aggregate functions areallowed if its input and output are basic types. See the typing
rule for grouping.
We have the standard notion of variable binding; the variable x is bound in the subterm M of λx . M and for(x ← L) M.
We identify α-equivalent terms, and substitution used in program transformation should be the capture-avoiding one.
Although our grouping operator has limited functionality,
we can express the SELECT statement with the GROUP BY
clause in SQL by combining our primitives with others. For
instance, the following SQL querycombination of G and existing primitives. By this decomposition, the term will have more opportunity to be transformed,
which is the key to our previous work.
3.2

Type System

The language Quelg is a statically typed language, and alltransformation rules must preserve typing of terms. Since it
has been argued in existing works in depth, we give a brief
overview of the type system.
Fig. 5 defines types and typing environments.
Base types
O
Types
A, B
Env
Γ

::= Int | Bool | String::= O | A →− B | Bag A | {l : A}::= · | Γ, x : A

Figure 5. Types of Quelg
A type is a basic type, a function type, a bag type Bag A
for multisets, or a record type {l : A}, which is abbreviationof {l 1 : A1 , · · · , lk : Ak }. Throughout this paper, we assume
that all field names l 1 , · · · , lk are mutually distinct.
For basic types O i , the type Bag {l : O } is called a table
type. Standard SQL can manipulate the values of table typeonly, and other nested data such as a bag of bags of records
must be translated away before generating an executable
SQL. A typing context Γ is standard where · denotes theempty environment.
Fig. 6 shows typing rules for important constructs.

SELECT p . cat as cat ,SUM ( p . price * o. qty ) as sales
FROM
products AS p , orders AS o
WHERE p . pid = o. pid
GROUP BY p . cat
HAVING SUM ( p . price * o. qty ) > 2000

FOR

Γ ⊢ M : Bag A Γ, x : A ⊢ N : Bag B
Γ ⊢ for(x ← M) N : Bag B

WHEREΓ ⊢ L : Bool Γ ⊢ M : Bag AΓ ⊢ where L M : Bag A

can be expressed as a term in Quelg as follows:for(r ← G(cat,α ) (for(p ← table(”products”))

SINGLETONΓ⊢M :AΓ ⊢ yield M : Bag A

GROUPING

Γ ⊢ L : Bag {κ : O ′′, m : O } l ⊆ m
α = {(l, ⊚, l ′)} ⊚i : O j →− O j′ (for all li and m j s.t. li = m j )for(o ← table(”orders”))
where (p.pid = o.pid)Γ ⊢ G(κ,α ) (L) : Bag {κ : O ′′, l ′ : O ′ }yield {cat = p.cat, sales = p.price ∗ o.qty}))where (r .s > 2000)

Figure 6. Type System of Quelg

yield {cat = r .cat, sales = r .s}
where α = {(sales, SUM, s)}

The last typing rule is the one for the grouping termG(κ,α ) (L). The first condition in its hypothesis says L musthave a table type. l ⊆ m means that the former set is a subset of the latter, in other words, for any li , there exists an
m j such that li = m j . The last condition in the hypothesis
says that the i-th aggregate function ⊚i must have the typeOj →− O j′ . Then G(κ,α ) (L) returns a bag of records which has

Note that our operator G does grouping and aggregation
only, and all other works are done by existing primitives.
We can thus decompose a primitive for grouping into the
5 For simplicity, we assume that all grouping keys are contained in the

results. See the typing rule.

54

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi Kameyama

the values of all the grouping keys, and the results of applying aggregate functions to the specified field in α with the
new field name l ′.
Note that our operator G does grouping and aggregation
only, and all other works are done by existing primitives in
Cheney et al.’s language. We can thus decompose SQL’s big
primitive for grouping into the combination of G and existing
primitives. Since for and other existing primitives can betransformed by Cheney et al.’s transformation rules, the termin the above form has more opportunity to be transformed,
which is the key to our previous work.
3.3(Stage 1)(λx .N ) M ⇝ N [x := M]{l = M }.li ⇝ Mi
for(x ← yield M) N ⇝ N [x := M]for(x ← for(y ← L) M) N ⇝for(y ← L) (for(x ← M) N ) (if y < FV (N ))for(x ← where L M) N ⇝where L (for(x ← M) N )for(x ← []) N ⇝ []for(x ← M 1 ⊎ M 2 ) N ⇝(for(x ← M 1 ) N ) ⊎ (for(x ← M 2 ) N )where true M ⇝ M
where false M ⇝ []Normalization

The query avalanche problem, or the N + 1-query problem inlanguage-integrated query means that, to execute a nested
for-term using the SQL processor which does not allow subqueries, one would need to generate many SQL queries andinteract with SQL processor many times, which degrades
the performance. Cooper solved the problem by programtransformation [3], and Cheney et al. formalized his idea ina program-generation framework; they introduced a typed
two-level language, and proved that any closed terms oftable types can be transformed to normal form which is directly translated to SQL. Our previous work extended it toa language with grouping and aggregate functions. Surprisingly, no new transformation rules are needed other thandecomposition of a big grouping primitive. By applying theirtransformation to our language, we have solved the N + 1query problem for our language.
Fig. 7 shows the normalization rules by Cheney et al.
The rules are classified into two stages, where Stage 1
rules should be applied before Stage 2 rules. 6 The former
consists of structural reductions for various types, while thelatter consists of ad hoc simplification rules. More detailed
explanation can be found in the literature [1].
It is proved that these rules are normalizing [10], and thesyntax of normal form is given in Fig. 8.
U is the top-level category, namely, a closed term of table
type in Quelg is normalized to U . Compared with the normal form in Cheney et al.’s work, our normal form allows
G(κ,α ) (U ) to appear in H , hence a term with nested control
structures such as for(x ← G(κ,α ) (U )) F is in normal form.
Nevertheless, we can prove that, no nested data types (otherthan the table types) appear in the types of any subterms ofnormal form, hence we can convert normal form in Fig. 8 toa SQL query if subqueries are allowed. See Okura et al. [10]for details. The query Q 0 in Section 2 has been obtained inthis way.

(Stage 2)
for(x ← M) (N 1 ⊎ N 2 ) ,→(for(x ← M) N 1 ) ⊎ (for(x ← M) N 2 )for(x ← M) [] ,→ []where L (M ⊎ N ) ,→(where L M) ⊎ (where L N )where L (where M N ) ,→where (L ∧ M) N
where L (for(x ← M) N ) ,→for(x ← M) where L N
Figure 7. Normalization rules

QueryU
Comprehension FH
BodyZ
RecordR
PrimitiveOp.
B
α
Key
κ

::= U1 ⊎ U2 | [ ] | F::= for(x ← H ) F | Z::= table(t) | G(κ,α ) (U )::= where B Z | yield R | H::= {l = B} | x::= ⊕(B) | x .l | c::= {(l, ⊚, l ′)}::= lFigure 8. Normal form of Quelg

4

Reorganizing QueriesThis section introduces novel transformations to optimize
normal form in the previous section, to reduce the size ofqueries and get better performance.
As we explained in Section 2, SQL queries obtained by ourprevious work is often unnecessarily large, and sometimes
very inefficient. This is contrasting with the normal formby Cheney et al.’s work which always generates compact
and efficient SQL queries. The difficulty in our language
lies in the fact that the grouping operator itself allows notransformations at all, therefore our normal form ought tocontain arbitrarily many nested control structures. Even

6 The order of applying rules in each stage does not matter, as the rules are(semantically) confluent and strongly normalizing.

55

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

worse, no further transformation seems to be applicable tonormal form within Quelg.
However, the normal forms are not arbitrarily complicated.
We only have to consider the combination of д ◦ f or f ◦ д,
where f is a for-term and д is an instance of the grouping
operator. Although fusing them within Quelg is not possible,
fusing them in SQL is possible, as SQL’s SELECT statementswith GROUP BY is very expressive. Put differently, in ourprevious work, we decomposed SQL’s grouping operation
before program transformation, and in this work, we do its inverse; we reorganize (re-compose) the function composition
such as д ◦ f into a single control structure, to obtain smaller
queries in SQL. We also consider a fusion transformation forother patterns to further optimize queries.
4.1

We introduce a language for intermediate representation (IR)which is useful to state our optimization for reorganization.

Table
Primitive
Input
OutputCondition
Key=

unionall(M[[U1 ]], M[[U2 ]])M[[[ ]]]=

select([ ], [ ] , false)

M[[G(κ,α ) (U )]] =gselect([(y ← table(t))], {l ′ = ⊚(y.l)},
if U = table(t)true, [y.κ], true)gselect([(y ← sub(M[[U ]]))], {l ′ = ⊚(y.l)},
true, [y.κ], true)
otherwise (where α = {(l, ⊚, l ′)})
M[[for(x ← H ) F ]] =select((x ← M aux [[H ]]) :: I, O, C)





if M[[F ]] = select(I, O, C)auxgselect((x ← M [[H ]]) :: I, O, C1 , [x .l] @ K, C2 )
if M[[F ]] = gselect(I, O, C1 , K, C2 )
M[[where B Z ]] =select(I, O, C ∧ M[[B]])





if M[[Z ]] = select(I, O, C)
gselect(I,O,
C∧
M[[B]], K, C2 )

1



if
M[[Z
]]
=
gselect(I, O, C1 , K, C2 )
M[[table(t)]] =select([(y ← table(t))], {l = y.l }, true)
M[[yield R]] = select([ ], M[[R]], true)

Intermediate Representation

Query

M[[U1 ⊎ U2 ]]::= select(I, O, C)| gselect(I, O, C, K, C)| unionall(Q, Q)
T ::= table(t) | sub(Q)B ::= c | x .l | ⊕(B)
I ::= [(x ← T )]O ::= {l = B}
C ::= B | C ∧ C
K ::= [B]Q

M[[{l = B}]]={l = M[[B]]}M[[⊕(B)]]=⊕(M[[B]])M[[e]]


Figure 9. Syntax of Intermediate Representation= e for e = x, c, x .l

M aux [[H ]] =table(t)sub(M[[G(κ,α ) (U )]])

if H = table(t)if H = G(κ,α ) (U )Figure 10. Translation from Quelg to IR

Fig. 9 gives the syntax of IR, which is a compact representation of SQL with small difference. The term select(I, O, C)
corresponds to a SELECT statement without grouping:
SELECT O FROM I WHERE C

two α-equivalent terms, and bound variables are renamed if
name clash occurs during program transformation.
Precise correspondence between IR and SQL will be given
later as a translation from the former to the latter.
Fig. 10 defines the translation from normal form in Fig. 8
to IR. Here t 1 :: t 2 is the cons operation for lists, and s 1 @ s 2
is concatenation for sequences. The variable y used in the
results of the translation should be a fresh variable.
Let us explain the translation, which converts any normal
form of bag type into a select-term or a gselect-term. This
allows us to treat IR terms uniformly.
Our intention of the translation is the ‘output-oriented’
resolution of nested control structures. For instance, for(x ←H ) for(x ′ ← H ′) Z is in normal form, but SQL’s SELECT
statement allows multiple tables as its input (implicit innerjoin), and so is our IR. We express it as a single select-term
which has (x ← H ) and (x ′ ← H ′) as its input. The above

Similarly, the term gselect(I, O, C1 , K, C2 ) corresponds to
one with grouping as follows:
SELECT O FROM I WHERE C1
GROUP BY K HAVING C2
I and O of these terms are called its input and output,
respectively. The term unionall corresponds to UNION ALL
in SQL. table(t) represents a table, and sub(Q) is a subquery.
The input I of a query is an ordered list of variable-binding
in the form (x i ← Ti ) which will be translated to Ti AS x i
in SQL. For brevity, we use the bag-notation [e 1 ; · · · , en ]for a list if it is used as an input term in IR. Variables in I
are bound by the select and gselect terms, but some care isneeded to understand their scopes since the order of the elements in I matters. To explain it using the term select([(x 1 ←T1 ); (x 2 ← T2 )], O, C), the variable x 1 is bound inT2 , O and C,
while x 2 is bound in O and C. Similarly to Quelg, we identify

56

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi Kameyamatranslation collects such H and H ′ by recursively traversing
the term (the first clause for for).
The term for(x ← H ) G(κ,α ) (U ) is similarly translated(the second clause for for), but it needs one more twist. This
term performs grouping for each x, namely, if H has N rows,
grouping takes place N times. To simulate the behavior by asingle grouping operation, we add all the fields of x to thegrouping keys ([x .l] @ K) so that the grouping operation
can distinguish records from different values of x. We can
optimize the translation; if the table for H has the field forprimary key, which means that each record in the table canbe distinguished by the value of the primary key, then we
only have to add the primary key to the grouping keys.
In this way, all (output-oriented) nesting of for is resolved
and we get a single select-term or gselect-term.
As an example, the term Q(simple) in Section 2 is translated to the following IR term:

It is easy to show that the above transformation preservetyping, and thus we do not lose the important property of
the absence of nested data structures.
The transformation reduces the depth of nested control
structures in queries, yet, it is limited to the case when the
input list of gselect is a singleton, and does not necessarily
improve the size and performance of queries, which is highly
dependent on the terms being transformed. See Section 7 forour experiments on these issues.
The above rule can be generalized in several ways. For
instance, we can generalize it to the rule where the input list
has multiple elements such that all the elements but the last
one are the pairs of a variable and a table expressions. For
this case, we only have to enumerate the table expressions
after the FROM clause in SQL to obtain the equivalent query.
More general cases are harder, which is left for future work.
The next rule transforms the pattern f ◦ д as follows:

gselect([(x ← sub(select([(o ← table(“orders”))],o.∗, o.date = “2020-01-01”)))],{pid = x .pid, qty_sum = SUM(x .qty)},true, [x .pid], true)

select([(y ← sub(gselect(I, O′, C1 , K, C2 )))], O, C)→ gselect(I, O [y := O′], C1 , K, C [y := O′] ∧ C2 )4.2This rule is very similar to the previous case. All the remarks after the first transformation applies to this rule, too.
As an example, the IR term for Q(simple) in Section 4.1 istransformed to the following term:

Reducing Query Size

We first transform the pattern д ◦ f where д is an operation
with grouping and f is an operation without grouping. This
combination is translated to the following IR term:gselect([(o ← table(“orders”))],{pid = o.pid, qty_sum = SUM(o.qty)},o.date = “2020-01-01”,[o.pid], true)

gselect([(y ← sub(select(I′, O′, C′)))], O, C1 , K, C2 )→ gselect(I′, O [y := O′], C1 [y := O′] ∧ C′,
K [y := O′], C2 [y := O′])As expected, the size of the query has been reduced.

The rule can be explained as follows. The query in the lefthand side of this rule first executes the subquery sub(· · · )to get a table as its value, then the outer query performs
grouping on the table. We can express the above combination
by a single statement in SQL. Note that the variable y in
the term before the transformation is bound in O, C1 , K,
and C2 , hence we need to substitute O ′ for y in the resultof transformation. Also the conditions C′ and C1 (whichcorresponds to the pre-condition for grouping) are mergedby conjunction.
Substitution for IR terms is in general dangerous, as thecorrespondence between the grouping operation and aggregate functions may be broken when a term that contains
aggregate functions is substituted for a variable which is in
the scope of a different grouping operator.7 The above transformation rule does not suffer from this problem since theterm O′ is a simple record and does not contain aggregate
functions. We need to consider this problem seriously, if ourlanguage allows subqueries to appear in expressions such as
the term exists(M), which is left for future work.

4.3

Eliminating Correlated Subquery

We consider the optimization for eliminating correlated subqueries. In our language, correlated subqueries are nested subqueries in which a variable bound by one subquery is dereferenced in the other subquery. It is well known that correlated
subqueries often show rather poor performance. Although
an experienced SQL writer would not write correlated subqueries unless it is absolutely necessary, our transformationbased approach may sometimes introduce correlated subqueries. Hence, we study this issue within our framework,and show that it is possible to eliminate correlated subqueries
to some extent, which leads to a great improvement on theperformance.
A query for(x ← table(t)) for(y ← G(κ,α ) (M)) N in
Quelg is transformed to the following IR term:
select([(x ← table(t));(y ← sub(gselect(I′, O′, C1 , K′, C2 )))]), O, C)
It is a correlated subquery if the variable x is used in thegselect-term. To optimize it while preserving the semantics,
we need to combine the input of select into one subquery.
This can be achieved by adding all the records in the table t
to the output (O′) and the grouping key (K′) of the subquery.

7 This is one of the reasons why introduced a G-operator which takes

aggregate functions as its parameter in Quelg. Since they are coupled byour operator, we do not have to worry about the problem.

57

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

The translation can be expressed as follows:(Stage 1)O1 [[gselect(I, O, C1 , K, C2 )]] =gselect(I′, O [y := O′],C1 [y := O′] ∧ C′, K [y := O′], C2 [y := O′])
(where I = [(y ← sub(select(I′, O′, C′)))])(Stage 2)O2 [[select(I, O, C)]] =gselect(I′, O [y := O′], C1 , K′, C [y := O′] ∧ C2 )(where I = [(y ← sub(gselect(I′, O′, C1 , K′, C2 )))])(Stage 3)O3 [[select(I, O, C)]] =O2 [[select(I′′, O [x .l := y.l ′], C [x .l := y.l ′])]]
where query = table(t) or sub(select or gselect)© where I = [(x ← query);ª­®
­(y ← sub(gselect(I′, O′, C1 , K′, C2 )))] ®®
­­ → I′′ = [(y ← sub(gselect((x ← query) :: I′,®
­®
{l ′ = x .l } @ O′, C1 , [x .l] @ K′, C2 )))] ¬«select([(x ← table(t));(y ← sub(gselect(I′, O′, C1 , K′, C2 )))], O, C)→ select([(y ← sub(gselect((x ← table(t)) :: I′,{l ′ = x .l } @ O′, C1 , [x .l] @ K′, C2 )))],O [x .l := y.l ′], C [x .l := y.l ′])This rule transforms a select-term which has two inputs:
the first one is a table term, and the second one is a grouping
term. The whole term is a correlated subquery if x occurs
in the rest of the query. The operator @ for records denotes
concatenation. We use filed names l ′ in several places but
for the moment let us ignore the difference between l ′ and l.
The rule adds the table (table(t)) to the input of the grouping term. The occurrences of x in O and C are substituted
for y, thus dependency on x is eliminated and the resulting query is no more a correlated subquery. We also add
all the fields in x to the key list of grouping to preserve thesemantics of the query. Put differently, the query after thetransformation takes the tagged (disjoint) union for each x,
and the grouping operation is applied to the resulting bag,rather than iterating grouping operations for each x.
One subtle issue remains in this transformation, namely,
the role of renaming field names from l to l ′. Its role is to
avoid the possible collision of field names between x and y.
Namely, the field x .l is added to y, but if y also has the fieldy.l, then we copy the value of x .l to y.l ′. For simplicity, we
rename all the fields in x regardless they have collision withy. By this trick, we can successfully translate a correlated
subquery to a non-correlated one while keeping semantics.
4.4

Figure 11. Optimizations(I, O, C), we map I to the FROM clause, O to SELECT, and C
to WHERE.
However the naive translation has a subtle problem as follows. As we explained in Section 4.1, if I = [(x 1 ← T1 ); (x 2 ←T2 )], then T2 may dereference x 1 , namely, the input tables
may have dependency. As the input tables (the expressions
after FROM) in SQL does not allow dependency, the naivetranslation fails. In fact, the following query in SQL raises
an error when executed.
SELECT *FROM products AS p ,( SELECT * FROM orders AS o
WHERE p. pid = o. pid ) AS x(* ERROR : invalid reference to FROM - clauseentry for table "p" *)Summary of Our Transformation

Fig. 11 summarizes the optimization rules other than thetranslation to IR.
Actually the third optimization for eliminating correlated
queries is generalized to the case where the first input is notnecessarily a table expression, but an arbitrary expression(select or gselect).
We take the left-most strategy when we apply these optimization rules to IR terms. As we will see later, by composing
the translations in Fig.10 with these optimizations we getsmaller, and sometimes better performant, queries than thoseobtained by our previous work.

5

We solve this problem using the LATERAL clause provided
by recent PostgreSQL,8 which makes it possible to allow
dependency among input tables. With the LATERAL clause,
the above query is written as follows.
SELECT *FROM products AS p ,LATERAL ( SELECT *FROM orders AS o
WHERE p. pid = o. pid ) AS x

Translation to SQL

As the final step of our translations, we translate IR to SQL.
For a technical reason explained below, we assume that the
back-end SQL is PostgreSQL (or other dialects which havean equivalent feature).
Our IR is designed to be a compact macro language for
SQL, so the translation between them should be identity
module the names of constructors: for an IR term selectExecuting this query has no problem.
Fig. 12 defines the translation from IR to SQL (PostgreSQL).
We assume that bound variables in IR terms are mutually
8 The feature has been supported by PostgreSQL since 9.3, and by MySQL

since 8.0.14.

58

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi Kameyama

Q(getSales) fetches the record with the same pid from theproducts table and orders table and calculates the sales. It
performs grouping based on pid as the key, and calculates theaverage of sales. It uses a nested data structure. The query istransformed to the following term.

unionall(S[[U1 ]], S[[U2 ]]) =S[[U1 ]] UNION ALL S[[U2 ]]S[[select(I, O, C)]] =SELECT S[[O]] FROM S[[I]] WHERE S[[C]]S[[gselect(I, O, C1 , K, C2 )]] =SELECT S[[O]] FROM S[[I]]
WHERE S[[C1 ]]GROUP BY S[[K]] HAVING S[[C2 ]]S[[table(t)]] = t
S[[sub(U )]]=for(o ← table(“orders”))
where (p.pid = o.pid)
yield {pid = o.pid,

LATERAL (S[[U ]])S[[c]]= c

S[[x .l]]= x .lS[[⊕(B)]]=⊕sql (S[[B]])S[[[(x ← T )]]]=

S[[T ]] AS x

S[[{l = B}]]=S[[B]] AS lS[[x]]Q(getSales) = G(pid,α ) (for(p ← table(“products”))

sales = p.price ∗ o.qty})
where α = {(sales, AVG, sales_avg)}
We can optimize Q(getSales) by using only the Stage 1
optimization, and get the following IR term.
gselect([(p ← table(“products”)); (o ← table(“orders”))],{pid = o.pid, sales_avg = AVG(p.price ∗ o.qty)},p.pid = o.pid, true, [o.pid], true)= x .∗

S[[C ∧ C ′]]=S[[C]] AND S[[C ′]]S[[[B]]]=

S[[B]]

By translating this IR term, we get the following compact
SQL query:

Figure 12. Translation from IR to SQL
distinct, and the same variable names can be used in thecorresponding SQL.
The above translation works for all the terms in our IR,
which completes the task for transforming a language-integrated
query to a single executable SQL query.

6

6.2

Query with Correlated Subquery

The second query Q(getQty) uses a correlated subquery,shown below:

Involved Examples

In this section, we apply our transformations to several examples with grouping and aggregate functions. They use thetables in Fig.3 in Section 2. We assume that examples use
our grouping operator from the first place, hence we do notneed to decompose them.
6.1

SELECT o. pid AS pid ,AVG (p. price * o. qty ) AS sales_avg
FROM products AS p , orders AS o
WHERE p. pid = o. pid
GROUP BY o. pid
HAVING TRUE

Q(getQty) =for(p ← table(“products”))
for(y ← G({name,date},α ) (for(o ← table(“orders”))
where (p.pid = o.pid)

Query with Nested Data Structure

yield {name = p.name,

The first query Q(getSales) uses a nested data structure andgrouping, shown below.

date = o.date,qty = o.qty}))Q(getSales) =yield {name = p.name, date = y.date,G(pid,α ) (for(x ← for(p ← table(“products”))

qty_sum = y.qty_sum}

yield {order = for(o ← table(“orders”))

where α = {(qty, SUM, qty_sum)}

where (p.pid = o.pid)
yield {pid = o.pid,

The query Q(getQty) retrieves records with the same pidfrom the products and orders tables, then performs groupingby the name and dates fields as keys. It calculates the total
number of the products for each date. It is already in normal
form, and we translate it using all optimizations from Stages
1 through 3. The IR term obtained by applying the Stage 1sales = p.price ∗ o.qty}})for(y ← x .order)
yield y)where α = {(sales, AVG, sales_avg)}

59

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

Table 1. Results of Performance Measurement

optimization only is shown below:
select([(p ← table(“products”));(y ← sub(gselect([(o ← table(“orders”))],{name = p.name, date = o.date,qty_sum = SUM(o.qty)},p.pid = o.pid,[p.name; o.date], true)))],{name = p.name, date = y.date,qty_sum = y.qty_sum},
true)

Query
LINQ
Quelg
Quelg-opt Trans
Q(simple)
3.18
3.57
3.18
0.03
Q(д2 ◦ f ◦ д1 )
Av
6.26
6.99
0.05
Q(getSales)
Av
4.38
4.35
0.22
Q(getCount)
2.75
3.60
2.75
0.03
2.14
2.51
2.14
0.06
Q(abstraction)
Q(predicate)
NA
1.42
0.99
0.03
Q(getScore)
NA
29.56
25.61
0.36
Q(getQty)
NA
1855.55
15.91
0.06
Q(multiple)
NA 19275.64
16.10
0.04
Q(for-G)
NA
26.14
22.59
0.04
Q(compose)
NA
3.17
1.52
0.14
Time unit is millisecond.

The IR term obtained by applying the Stage 2 and 3 optimizations for this term is shown as follows:
gselect([(p ← table(“products”)); (o ← table(“orders”))],{name = p.name, date = o.date,qty_sum = SUM(o.qty)},p.pid = o.pid,[p.pid; p.name; p.cat; p.price; o.date], true)

The first group consists of relatively simple queries which
do not generate correlated subqueries even if we naively
generate SQL queries (hence we do not need the Stage 3 optimization for these queries). We have seven queries in thisgroup (the upper half of Table 1). Q(simple) and Q(getSales)
are the ones in Sections 2.1 and 6.1, respectively, and Q(д2 ◦f ◦ д1 ) is an instance of the pattern д2 ◦ f ◦ д1 in Section 2.2. Q(getCount) performs grouping twice by nested Goperators, Q(abstraction) combines lambda abstraction anda G-operator, Q(predicate) groups the data using the predicate given as the argument of the query, and Q(getScore)used nested data structures as intermediate data in the computation with grouping.
The second group consists of queries that handle correlated subqueries, which need all of Stage 1 through 3 optimizations to optimize. There are four queries in this group(the lower half of Table 1). Q(getQty) is the one in Section 6.1,
Q(multiple) is a query in which a table and the G-operator
are mixed in the input of each for-constructor, Q(for-G) has
the G-operator in the output of the for-constructor and istranslated to a SQL query with correlated subqueries, andQ(compose) combines two queries with grouping.
Table 1 shows the execution time of SQL queries for threecases: LINQ (the first column), Quelg without optimization(the second), and Quelg with optimization (the third). The lastcolumn (Trans) shows the time for transforming queries by
the method in the present paper. The time unit is millisecond.
In the table, NA (not available) means the query cannot be
executed, and Av (avalanche) means that the query caused
the query avalanche (N + 1-query) problem.
Note that the time for transforming queries is much shorter
than the execution time, and is negligible. This is as expected, as our transformation rules are relatively simple asprogram transformations. This is a preferable result, since we
may have to generate SQL queries dynamically in languageintegrated query (while executing our high-level code in F#

Finally, we translate it to SQL, obtaining the following
query.
SELECT p . name AS name , o. date AS date ,SUM ( o . qty ) AS qty_sum
FROM products AS p , orders AS o
WHERE p . pid = o. pid
GROUP BY p . pid , p. name , p. cat , p. price ,o . date
HAVING TRUE

Note that we have obtained a single query without subqueries. If we had not used the optimizations in this paper,
we would have got a SQL query with a correlated subquery,which would be rather inefficient.

7

Performance

We have implemented our transformations in OCaml basedon Suzuki et al.’s typed tagless-final implementation for theirlanguage-integrated query [12], and compared the performance by measuring the execution time of SQL queries generated by our previous work and by the present paper. We
also measured the execution time of SQL queries generatedby Microsoft’s LINQ in F#. The computing environment is
Mac OS 10.13.2 with Intel Core i5-7360 CPU with 8GB RAM,and we use OCaml 4.07.1, F# 4.7 using .NET Core 3.1, andPostgreSQL 11.5. All queries used in the experiment are available online.9
We have used the tables in Fig.3 where the number ofrows is increased to 5000 (products) and 10000 (orders), andalso used several other tables. We have measured the performance for eleven queries with grouping, including theone in Section 6. The queries used in this experiments areclassified into two groups.
9 http://logic.cs.tsukuba.ac.jp/~rui/quelg_opt/example.html

60

GPCE ’20, November 16–17, 2020, Virtual, USA

Rui Okura and Yukiyoshi Kameyama

or other programming languages), and the time for code
generation matters for such cases.
We compare Microsoft’s LINQ and our methods. LINQ successfully generated and executed three queries only. There
are two reasons for this. First, LINQ does not transform
queries with grouping, hence a query with grouping which
has nested control structures causes the N + 1-query problem. In this experiment, the sizes of input tables are 500
or 1000, hence approximately 500 or 1000 SQL queries are
generated and sent to SQL processors, which needs a hugeamount of time (results marked with Av). The second reason is that LINQ does not support the LATERAL clause, andqueries with correlated subqueries cannot be generated (results marked with NA).
On the other hand, simple queries such as Q(simple),Q(getCount), and Q(abstraction) run as fast as our optimized one, since they do not need normalization or the LATERAL clause. Our un-optimized result (the second column)
sometimes performs worse than LINQ, since we decomposeda single query, which increases the complexity of queries,
and if no normalization is needed, the decomposition (without optimization) has a bad effect on performance.
We then compare the performance of our method withand without optimizations. For the queries from Q(simple)
to Q(getScore) (simpler queries), our optimization does nothave a big impact on the execution time even though our optimization succeeded in reducing the size of generate queries.
This can be explained by the fact that the query optimizer in
PostgreSQL improves the performance of redundant queries
before our optimization.
For the queries Q(getQty) and Q(multiple), which use
grouping, nested control structures, and generate correlated
subqueries, our optimization has shown great improvementson performance with the ratio from 15% to 1097%. The ratio varies from one example to another, however, a similar
improvement has been observed as long as we have tested.
These results are in favor of our work.
Optimization for correlated subqueries is a big issue in
database studies, which is beyond the scope of this paper, but
we think that our program-transformation (and programgeneration) approach is beneficial to study the issue when
the target language contains grouping, as we can make useof the standard technique for program transformations.
Finally we mention the size of generated queries which is
not on the table. For all cases, the size of generated queries
was reduced by our optimization from 33% to 67%, where
we measured the size of queries by the number of SELECT
statements in the query. Query size does not matter for small
queries, but it sometimes matters since many database engines have the upper limit on the number of subqueries or ofquery size, and the program-transformation approach may
occasionally generate large queries. Hence, the smaller sizeof queries is preferable even if the performance remains thesame.

The experiments we have conducted use relatively small
queries, and thorough experiments using larger examples
from practical applications are left for future work.

8

Conclusion

Language-integrated query reduces the impedance mismatch
problem, and provides high-level abstractions to programmers when they write database queries. Cooper’s influential
paper has the title “The Script-Writer’s Dream: How to Write
Great SQL in Your Own Language, and Be Sure It Will Succeed” which suggests us that writing a SQL query in yourown, favorite programming language is a dream of scriptwriters. The “dream” does not come true without cost; despite
many researchers’ efforts, transforming a query with grouping and aggregation into an efficient SQL query has been an
open problem for years. In our previous work, we solved thisproblem when the target SQL allows nested control structures (subqueries), but their solution has another problem ofexcessively large queries and their poor performance.
This paper solves the problem by re-organizing the queryto obtain a smaller query with fewer control structures. The
result of our experiments is encouraging; SQL queries generated by our method are smaller and outperforms thosegenerated by Microsoft’s LINQ, and one by our previous
work.
Research on language-integrated query is still a hot topic.
For example, Kiselyov et al. has proposed a technique tocover the ORDER BY clause in language-integrated query [7].
Ricciotti et al. proved strong normalization for both homogeneous and heterogeneous queries [11].
Let us state future work other than those already mentioned in this paper.
The next step of the present work is to give an efficient implementation of the program transformation. If we generate
SQL queries only statically, the time for the transformation
does not matter, however, when we dynamically generate
SQL queries in language-integrated query the transformation time matters. Formal verification of our transformation
for suitable semantics is also an important remaining work.
From the practical point of view, extending the source
language Quelg to cover a larger subset of SQL than thepresent one is an interesting topic. In this work, we allow
subqueries to appear in the FROM or SELECT clause, but
subqueries must not appear in, for instance, the WHERE
clause in this study. Classic database theory investigatedsuch subqueries, and we hope to combine our results withthem as future work.
Acknowledgements. We would like to thank anonymous
reviewers for constructive comments. The second author
is supported in part by JSPS Grant-in-Aid for Scientific Research (B) No. 18H03218 and No. 17H01724A.

61

Reorganizing Queries with Grouping

GPCE ’20, November 16–17, 2020, Virtual, USA

References

Suzhou, China, November 27-29, 2017, Proceedings. 364–383. https://doi.org/10.1007/978-3-319-71237-6_18[8] Erik Meijer, Brian Beckman, and Gavin M. Bierman. 2006. LINQ:
reconciling object, relations and XML in the .NET framework. In
Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, USA, June 27-29, 2006. 706. https://doi.org/10.1145/1142473.1142552[9] Atsushi Ohori and Katsuhiro Ueno. 2011. Making Standard ML a
Practical Database Programming Language. In Proceedings of the 16th
ACM SIGPLAN International Conference on Functional Programming(Tokyo, Japan) (ICFP ’11). Association for Computing Machinery, New
York, NY, USA, 307–319. https://doi.org/10.1145/2034773.2034815[10] Rui Okura and Yukiyoshi Kameyama. 2020. Language-Integrated
Query with Nested Data Structures and Grouping. In Functional and
Logic Programming, Keisuke Nakano and Konstantinos Sagonas (Eds.).
Springer International Publishing, Cham, 139–158.
[11] Wilmer Ricciotti and James Cheney. 2020. Strongly Normalizing
Higher-Order Relational Queries. In 5th International Conference on
Formal Structures for Computation and Deduction (FSCD 2020) (Leibniz
International Proceedings in Informatics (LIPIcs), Vol. 167), Zena M. Ariola (Ed.). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl,
Germany, 28:1–28:22. https://doi.org/10.4230/LIPIcs.FSCD.2020.28[12] Kenichi Suzuki, Oleg Kiselyov, and Yukiyoshi Kameyama. 2016. Finally,safely-extensible and efficient language-integrated query. In Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and
Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20- 22, 2016. 37–48. https://doi.org/10.1145/2847538.2847542[13] Val Tannen, Peter Buneman, and Limsoon Wong. 1992. Naturally
Embedded Query Languages. In Database Theory - ICDT’92, 4th International Conference, Berlin, Germany, October 14-16, 1992, Proceedings.
140–154. https://doi.org/10.1007/3-540-56039-4_38[1] James Cheney, Sam Lindley, and Philip Wadler. 2013. A practicaltheory of language-integrated query. In ACM SIGPLAN International
Conference on Functional Programming, ICFP’13, Boston, MA, USA September 25 - 27, 2013. 403–416. https://doi.org/10.1145/2500365.
2500586[2] James Cheney, Sam Lindley, and Philip Wadler. 2014. Languageintegrated query using comprehension syntax: state of the art, open
problems, and work in progress. Technical Report. http://popl.mpisws.org/2014/dcp2014/cheney.pdf, (Accessed on Oct 2020).
[3] Ezra Cooper. 2009. The Script-Writer’s Dream: How to Write GreatSQL in Your Own Language, and Be Sure It Will Succeed. In Database
Programming Languages - DBPL 2009, 12th International Symposium,
Lyon, France, August 24, 2009. Proceedings. 36–51. https://doi.org/10.
1007/978-3-642-03793-1_3[4] Ezra Cooper, Sam Lindley, Philip Wadler, and Jeremy Yallop. 2007.
Links: Web Programming Without Tiers. In Formal Methods for Components and Objects, Frank S. de Boer, Marcello M. Bonsangue, SusanneGraf, and Willem-Paul de Roever (Eds.). Springer Berlin Heidelberg,
Berlin, Heidelberg, 266–296.
[5] Torsten Grust, Manuel Mayr, Jan Rittinger, and Tom Schreiber. 2009.
FERRY: Database-Supported Program Execution. In Proceedings ofthe 2009 ACM SIGMOD International Conference on Management of
Data (Providence, Rhode Island, USA) (SIGMOD ’09). Association for
Computing Machinery, New York, NY, USA, 1063–1066. https://doi.
org/10.1145/1559845.1559982[6] Torsten Grust, Jan Rittinger, and Tom Schreiber. 2010. Avalanche-Safe
LINQ Compilation. PVLDB 3, 1 (2010), 162–172. https://doi.org/10.
14778/1920841.1920866[7] Oleg Kiselyov and Tatsuya Katsushima. 2017. Sound and Efficient
Language-Integrated Query - Maintaining the ORDER. In Programming Languages and Systems - 15th Asian Symposium, APLAS 2017,62