Estimations d'erreur de la méthode de barrière logarithmique pour les problèmes de contrôle optimal stochastique linéaire quadratique

Résumé : Nous considérons un problèmes de contrôle optimal stochastique linéaire quadratique avec contrainte de positivité de la commande. Cette dernière est pénalisée avec la barrière logarithmique classique. Utilisant un argument de dualité et le principe du minimum stochastique, nous obtenons des estimations d'erreur pour la solution du problème pénalisé qui apparaît comme une extension naturelle de celle, bien connue, du cas déterministe.

Mots-clés : Commande stochastique, problèmes linéaire quadratique, contrainte de non-négativité, barrière logarithmique, principe du minimum stochastique

Introduction

The study of stochastic linear quadratic (LQ) optimal control problems is an area of active research. In fact, many problems arising in engineering design and mathematical finance can be modeled as stochastil LQ problems. Let us cite, for example, the portfolio selection problem ( [START_REF] Zhou | Continuous-time mean-variance portfolio selection: A stochastic LQ framework[END_REF][START_REF] Lim | Mean-variance portfolio selection with random parameters in a complete market[END_REF]) and the contingent claim problem ( [START_REF] Kohlmann | Relationship between backward stochastic differential equations and stochastic control[END_REF]). The stochastic LQ problem, in a finite time horizon [0, T ] and without constraints, can be stated as follows:

Minimize E T 0 u(t) R(t)u(t) + y(t) C(t)y(t) dt + y(T ) M y(T ) s.t. dy(t) = [A 0 (t)y(t) + B 0 (t)u(t)] dt + [A 1 (t)y(t) + B 1 (t)u(t)] dW (t), y(0) = x 0
Assuming that R(t) is positive definite, the problem above was extensively investigated in the 1960s and 1970s (see e.g. [START_REF] Wonham | On a matrix Riccati equation of stochastic control[END_REF][START_REF] Mclane | Optimal stochastic control of linear systems with state-and control-dependent disturbances[END_REF][START_REF] Bismut | Théorie probabiliste du contrôle des diffusions[END_REF][START_REF] Bismut | On optimal control of linear stochastic equations with a linear-quadratic criterion[END_REF][START_REF] Davis | Linear Estimation and Stochastic Control[END_REF], the surveys in [START_REF] Athens | Special issues on linear-quadratic-gaussian problem[END_REF] and references therein). In the mid-1990s, using an approach based on a stochastic Riccati equation, Chen-Li-Zhou [START_REF] Chen | Stochastic linear quadratic regulators with indefinite control weight costs[END_REF] treated the stochastic LQ problem even when R(t) can be indefinite. See also [START_REF] Chen | Stochastic linear quadratic optimal control problems[END_REF], where the relations between the stochastic LQ problem, the stochastic Pontryagin minimum principle (SPMP) and linear forward-backward stochastic differential equations, are studied. Even if the unconstrained case is well studied, when control constraints are present the only reference that we know is [START_REF] Hu | Constrained stochastic LQ control with random coefficients, and application to mean-variance portfolio selection[END_REF]. In fact, the authors consider a stochastic LQ problem where the control is constrained in a cone. They obtain explicit solutions for the optimal control and the optimal cost via solutions of a system of extended stochastic Riccati equations.

In this work we study a convex stochastic LQ problem with non-negativity control constraints. We consider a family of logarithmic penalized problems, parameterized by ε > 0. This means that the cost function is modified by adding a logarithmic barrier function multiplied by ε, which implies that the solution of the new problem is strictly positive. Our aim is to study the convergence, as ε ↓ 0, of the solution of the penalized problem to the solution of the initial one. In fact, we will obtain error estimates for the cost, control, state and adjoint state in the appropriate spaces. This result extend the classical error estimates obtained by Weiser [START_REF] Weiser | Interior point methods in function space[END_REF] in the deterministic framework.

The article is organized as follows: In section 2 we fix the standard notation and the initial and penalized problems are stated. Using the stochastic Pontryaguin minimum principle (SPMP) (see [START_REF] Bensoussan | Lectures on stochastic control[END_REF][START_REF] Bensoussan | Stochastic maximum principle for distributed parameter system[END_REF][START_REF] Bismut | Analyse convexe et probabilités[END_REF][START_REF] Bismut | Théorie probabiliste du contrôle des diffusions[END_REF][START_REF] Bismut | An introductory approach to duality in optimal stochastic control[END_REF][START_REF] Peng | A general stochastic maximum principle for optimal control problems[END_REF][START_REF] Cadenillas | The stochastic maximum principle for linear convex optimal control with random coefficients[END_REF]), first order necessary and sufficient conditions are derived. Our main result is provided in section 3, in which we derive the error estimates. The proof use a simple duality argument and an application of the SPMP.

Problem Statement and Optimality Conditions

Let us first fix some notations. The space R m (m ∈ N * ) is endowed with its standard Euclidean norm denoted by | • |. The ith coordinate of a vector x is denoted by

x i . We set R m + := {x ∈ R m : x i ≥ 0}, and R m ++ := {x ∈ R m : x i > 0}.
Let T > 0 and consider a filtered probability space (Ω, F, F, P), on which a d-dimensional (d ∈ N * ) Brownian motion W (•) is defined with F = {F t } 0≤t≤T being its natural filtration, augmented by all P-null sets in F.

For ∈ N * let us define L 2 F [0, T ]; R := v : [0, T ] × Ω → R / v is F -adapted and ||v|| 2 < ∞ , L 2,∞ F [0, T ]; R := v : [0, T ] × Ω → R / v is F -adapted and ||v|| 2,∞ < ∞ ,
where we assume that all the mappings are B([0, T ]) × F T -measurable and ||v||

2 := E T 0 |v(t)| 2 dt 1 2 , ||v|| 2,∞ := E sup t∈[0,T ] |v(t)| 2 1 2
.

It is well known that L 2 F [0, T ]; R , •, • 2 is a Hilbert space, where u, v 2 := i=1 E T 0 u i (t)v i (t)dt . (1)
Let x 0 : Ω → R n be F 0 measurable and such that E(|x 0 | 2 ) < ∞. Consider the following affine stochastic differential equation (SDE)

dy(t) = f (t, ω, y(t), u(t))dt + d i=1 σ i (t, ω, y(t), u(t))dW (t), y(0) = x 0 ∈ R. (2)
In the notation above y(t) ∈ R n denotes the state function, which is controlled by u(t) ∈ R m , and

f : [0, T ] × Ω × R n × R m → R n , σ i : [0, T ] × Ω × R n × R m → R n×d are defined by f (t, ω, y, u) := A 0 (t, ω)y + B 0 (t, ω)u + D 0 (t, ω), σ i (t, ω, y, u) := A i (t, ω)y + B i (t, ω)u + D i (t, ω),
where, for i = 0, ..., d,

A i : [0, T ] × Ω → R n×n , B i : [0, T ] × Ω → R n×m and D i : [0, T ] × Ω → R n .
We assume that: (H1) The random matrices A i , B i , D i are progressively measurable with respect to F and bounded uniformly in (t, ω) ∈ [0, T ] by a constant D > 0.

We take as state and control space, respectively,

Y := L 2,∞ F ([0, T ]; R m ), U := L 2 F ([0, T ]; R m ). (3)
It is well known that for every u ∈ U, equation (2) has a unique solution y u ∈ Y and the following estimate hold:

||y|| 2 2,∞ ≤ L 1 E(y 2 0 ) + ||u|| 2 2 + d i=0 ||D i || 2 2 , (4)
for some positive constant L 1 . Denote respectively by S m + and S m ++ the sets of symmetric positive semidefinite and symmetric positive definite matrices of order m. Now, let us consider the set

U + := {u ∈ U / u(t, ω) ≥ 0 for a.a. (t, ω) ∈ [0, T ] × Ω} , (5)
and the random matrices R :

[0, T ] × Ω → S m ++ , C : [0, T ] × Ω → S n + , M : Ω → S n + .
We assume: (H2) The matrices R, C, M are bounded uniformly in (t, ω) ∈ [0, T ] by a constant C. In addition, we assume that R is uniformly positive definite, i.e. there exists α > 0 such that for a.a. (t, ω)

∈ [0, T ] × Ω v R(t, ω)v ≥ α|v| 2 for all v ∈ R m . (6)

The initial problem

Let ȳ ∈ Y be a reference state function and define

g 0 : [0, T ] × Ω × R n × R m → R as g 0 (t, ω, y, u) := 1 2 u R(t, ω)u + [y -ȳ(t, ω)] C(t, ω)[y -ȳ(t, ω)]. (7)
The cost function J 0 : U → R is defined as

J 0 (u) := E 1 2 T 0 g 0 (t, y(t), u(t))dt + 1 2 y u (T ) M y u (T ) . (8)
We consider the following stochastic optimal control problem:

Min J 0 (u) subject to u ∈ U + . (CP) 0
Assumptions (H1), (H2) imply that J 0 is a strongly convex continuous function. Since U + is closed and convex, we have that (CP) 0 has a unique solution u 0 . We denote y 0 := y u0 its associated state.

As usual in optimal control theory, optimality conditions can be expressed in terms of a Hamiltonian and an adjoint state. In fact, let

H 0 : [0, T ] × Ω × R n × R n × R n×d × R m → R
be the Hamiltonian of problem (CP) 0 , defined as

H 0 (t, ω, y, p, q, u) := g 0 (t, ω, y, u) + p • f (t, ω, y, u) + d i=1 q i • σ i (t, ω, y, u),
where q i denotes the ith column of q. For u

∈ U let (p u , q u ) ∈ L 2,∞ F ([0, T ]×R n )× L 2
F ([0, T ]×R n×d ), called the adjoint state associated to u, be the unique solution of the following linear backward stochastic differential equation (BSDE)(see [START_REF] Bismut | Analyse convexe et probabilités[END_REF]) : dp(t) = -D y H 0 (t, y u (t), p(t), q(t), u(t))dt + q(t)dW (t),

p(T ) = M y u (T ). ( 9
)
It is well known (see e.g. [START_REF] Mou | A variational formula for stochastic controls and some applications[END_REF]Proposition 3.1]) that there exists

L 2 > 0, such that ||p u || 2 2,∞ + ||q u || 2 2 ≤ L 2 E(y u (T ) 2 ) + ||u|| 2 2 . ( 10
)
Let us set p 0 := p u0 and q 0 := q u0 . Since g 0 (t, ω, y, •) is strictly convex, the stochastic Pontryagin minimum principle (SPMP) for linear convex optimal control with random coefficients [10, Theorem 3.2], yields that u 0 is a solution of (CP) 0 if and only if for a.a. (t, ω)

∈ [0, T ] × Ω, u 0 (t, ω) = argmin w∈R m + H 0 (t, ω, y 0 (t, ω), p 0 (t, ω), q 0 (t, ω), w). (11)
A straightforward computation (see [1, Section 2.1 ]) yields that

u 0 (t, ω) = π 0 (R(t, ω), z 0 (t, ω)) for a.a. (t, ω) ∈ [0, T ] × Ω, ( 12
)
where

z 0 (t, ω) := -R(t, ω) -1 B 0 (t, ω) p 0 (t, ω) + d i=1 B i (t, ω) q i 0 (t, ω)
and for (R, z) ∈ S m ++ × R m the map π 0 (R, z) is defined as the unique solution of Min

1 2 (x -z) R(x -z), s.t. x ∈ R m + .

The penalized problem

For ε > 0 define the function

J ε : U + → R ∪ {+∞} by J ε (u) := E 1 2 T 0 g 0 (t, y u (t), u(t)) + ε L(u(t)) dt + y u (T ) 1 2 M y u (T ) , (13) where
L : R m + → R ∪ {+∞} is defined as L(u) := - m i=1 log u i . Let us consider the penalized problem Min J ε (u) subject to u ∈ U + . (CP) ε
Using the arguments of [1, Lemma 1], we have that

u ∈ U + → E T 0 L(u(t))dt ∈ R ∪ {+∞}
is convex lower-semicontinuous (l.s.c), hence J ε is a strongly convex l.s.c. function. Therefore, (CP) ε has a unique solution u ε with associated state y ε := y uε . The Hamiltonian for (CP) ε

H ε : [0, T ] × Ω × R n × R n × R n×d × R m + → R ∪ {+∞} is defined as H ε (t, ω, y, p, q, u) := H 0 (t, ω, y, p, q, u) + ε L(u).
We set (p ε , q ε ) := (p uε , q uε ) for the unique solution of the following BSDE:

dp(t) = -D y H ε (t, y ε (t), p(t), q(t), u ε (t))dt + q(t)dW (t), p(T ) = M y ε (T ). ( 14
)
As for the initial problem, the SPMP implies that u ε is the solution of (CP) ε if and only if for a.a. (t, ω)

∈ [0, T ] × Ω u ε (t, ω) = argmin w∈R m + H ε (t, ω, y ε (t, ω), p ε (t, ω), q ε (t, ω), w), (15)
Since H ε (t, ω, •) is convex and differentiable in u, condition [START_REF] Kohlmann | Relationship between backward stochastic differential equations and stochastic control[END_REF] is satisfied if and only if for a.a. (t, ω) ∈ [0, T ] × Ω,

D u H 0 (t, ω, y ε (t, ω), p ε (t, ω), q ε (t, ω), u ε (t, ω)) -ε 1 u ε (t, ω) = 0, (16)
where 1/u ε (t, ω) ∈ R m denotes the vector whose ith component is 1/u i ε (t, ω). Equation [START_REF] Lim | Mean-variance portfolio selection with random parameters in a complete market[END_REF] implies that (see [1, Section 2.2])

u ε (t, ω) = π ε (R(t, ω), z ε (t, ω)) for a.a. (t, ω) ∈ [0, T ] × Ω, (17)
where

z ε (t, ω) := -R(t, ω) -1 B 0 (t, ω) p ε (t) + d i=1 B i (t, ω) q i ε (t)
and for (R, z) ∈ S m ++ × R m the map π ε (R, z) is defined as the unique solution of

Min 1 2 (x -z) R(x -z) + ε L(x), s.t. x ∈ R m + .

Main Result

In this section we provide error estimates for the cost, control, state and adjoint state of the penalized problem. We denote by 1/u ε : [0, T ] × Ω → R m the mapping (1/u ε (t, ω)) i := 1/u i ε (t, ω).

Lemma 1. For every ε > 0 we have that 1/u ε ∈ U + .

Proof. The proof is based on [START_REF] Kohlmann | Relationship between backward stochastic differential equations and stochastic control[END_REF]. For notational convenience we assume that n = m = d = 1. The proof for the general case can be easily adapted. First, note that integrability problem comes when u ε (t, ω) is small. Thus, fix K 0 > 0 and set

Ω K0 := {(t, ω) ∈ [0, T ] × Ω / u ε (t, ω) ≤ K 0 } . Now, let η ∈ (0, K 0 ) and set Ĥε (t, ω, w) := H ε (t, ω, y ε (t, ω), p ε (t, ω), q ε (t, ω), w). If u ε (t, ω) ≤ η/2 we have for a.a. (t, ω) ∈ Ω K0 , omitting the (t, ω) argument, Ĥε (η) -Ĥε (u ε ) = 1 2 R(η + u ε )(η -u ε ) + [B 0 p ε + B 1 q ε ] (η -u ε ) +ε [log(u ε ) -log(η)]
On the other hand, using that log(•) is concave,

log(u ε ) -log(η) ≤ 1 η (u ε -η) ≤ 1 η -η 2 = -1 2 .
Therefore, by optimality of u ε ,

0 ≤ Ĥε (η) -Ĥε (u ε ) ≤ CK 0 η + D(|p ε | + |q ε |)η - ε 2 ≤ ηK 1 (1 + |p ε | + |q ε |) -1 2 ε,
where K 1 := max CK 0 , D . Thus, we conclude that

u ε ≤ 1 2 η ⇒ η ≥ ε 2K 1 (1 + |p ε | + |q ε |) .
Henceforth, for a.a. (t, ω) ∈ Ω K0 ,

u ε ≥ ε 4K 1 (1 + |p ε | + |q ε |) and thus 1 u ε ≤ 4K 1 (1 + |p ε | + |q ε |) ε . (18)
The result follows from [START_REF] Cadenillas | The stochastic maximum principle for linear convex optimal control with random coefficients[END_REF] using that u ε ∈ U and that y ε ∈ Y is almost surely continuous.

Remark. Estimate (18) generalizes [9, Theorem 1] obtained in the deterministic framework. In the deterministic case we have that u ε is uniformly positive, whereas in our setting we can prove only [START_REF] Mou | A variational formula for stochastic controls and some applications[END_REF].

Consider the Lagrangian L : U × U → R, associated to problem (CP) 0 , defined by L(u, λ) := J 0 (u) -λ, u 2 ,

where we recall that •, • 2 is defined in [START_REF] Alvarez | Asymptotic expansions for interior penalty solutions of control constrained linear-quadratic problems[END_REF]. Define the dual function d : U + → R by d(λ) := inf u∈U L(u, λ). We have: Taking u = u ε -u 0 in (4) yields that

||y ε -y 0 || 2 2,∞ = O(ε).
Finally, using the estimates above and that y ε -y 0 is almost surely continuous, estimate [START_REF] Cadenillas | The stochastic maximum principle for linear convex optimal control with random coefficients[END_REF] implies that

||p ε -p 0 || 2 2,∞ + ||q ε -q 0 || 2 2 ≤ L 2 E (y ε (T ) -y 0 (T )) 2 + ||u ε -u 0 || 2 2 = O(ε).

Proof.

  By lemma 2, we haveJ 0 (u ε ) -εmT ≤ max λ∈U + min u∈U L(u, λ) ≤ min u∈U max λ∈U + L(u, λ) = min u∈U + J 0 (u) = J 0 (u 0 ),from which (23) follows. The strong convexity of J 0 (•) implies that||u ε -u 0 || 2 2 = O(ε).

RR n°7455

http://www.inria.fr ISSN 0249-6399

Lemma 2. For every ε > 0,

Proof. Consider the following auxiliary problem Min J 0 (u) -ε 1/u ε , u 2 subject to u ∈ U.

(CP) aux Lemma 1 implies that the above problem is well-defined. Since the cost function is strongly convex and continuous, problem (CP) aux admits a unique solution u aux , with associated state y aux := y uaux . The Hamiltonian H aux of problem (CP) aux is defined as

We let (p aux , q aux ) be the unique solution of the following BSDE:

The SPMP yields that u aux is a solution of (CP) aux if and only if

Using that Ĥaux (t, ω, •) is convex and differentiable, ( 21) is satisfied if and only if

Therefore, noting that (ommiting the (t, ω) argument)

D y H aux (t, ω, y aux , p aux , q aux , u aux ) = D y H ε (t, ω, y aux , p aux , q aux , u aux ), equations ( 14), [START_REF] Lim | Mean-variance portfolio selection with random parameters in a complete market[END_REF] imply that (y ε , p ε , q ε , u ε ) satisfies ( 20)- [START_REF] Zhou | Continuous-time mean-variance portfolio selection: A stochastic LQ framework[END_REF]. Therefore,

Now, we can prove our main result, which yields error bounds for (y ε , p ε , q ε , u ε ), usually referred as the central path. In particular, we obtain the convergence of (y ε , p ε , q ε , u ε ) to (y 0 , p 0 , q 0 , u 0 ) in the appropriate spaces. Theorem 3. Assume that (H1) and (H2) hold. Then for every ε > 0, the following estimates hold J 0 (u ε ) -J 0 (u 0 ) ≤ εmT (23)


Clément Genzmer

Volker Hudlet

Hyunjung Park

Daniel Schall

Pierre Senellart

The SIGMOD 2010 Programming Contest A Distributed Query Engine

We report on the second annual ACM SIGMOD programming contest, which consisted in building an efficient distributed query engine on top of an in-memory index.

CONTEXT

For the second year in a row, a programming contest was organized in parallel with the ACM SIGMOD 2010 conference. Undergraduate and graduate student teams from over the world were invited to compete to develop an efficient distributed query engine over relational data. Students had several months to work on their implementation, which was judged for their overall performance on a variety of workloads. The teams responsible for the five best systems were invited to present their work during the SIGMOD 2010 conference, and the winning team (one-man team cardinality formed of Hyunjung Park, Stanford University), was awarded a prize of $5,000.

In addition to encouraging students to be active in the database research community, the aim is to build over the years, throughout a series of contests, an open source inmemory distributed database management system. Thus, the candidates of this year's contest relied on the inmemory index implementation produced as the outcome of last year's competition.

We first describe in more detail the task the contestants were involved in, as well as the workload their implementation was evaluated on. We then report on the outcome of the competition, before describing the key ideas of the systems ranked first and second.

TASK DESCRIPTION

As previously mentioned, the task was to program a simple distributed relational query engine. Contestants had to provide a binary library conforming to a specific interface, along with the corresponding source code. Each submission was evaluated on a dedicated cluster of eight machines, over a series of eight secret query loads. The input provided to the implementation for each workload was the description of which nodes of the cluster stored (parts of) which tables, possibly horizontally partitioned, as well as a set of queries, expressed in a simple subset of SQL. The goal was then to provide the correct output to these queries, as fast as possible. The final score of each submission was computed as a monotonous function of the total time used for running all workloads. Workloads where the submission crashed, did not return the correct output, or ran over the time limit of five to ten minutes (depending on the workload), were assigned penalties.

All queries were simple select-project-join queries, of the form: SELECT alias.attribute, ... FROM table AS alias, ... WHERE condition1 AND ... AND conditionN where a condition might be any of:

• alias.attribute = constant • alias.attribute > constant • alias1.attribute1 = alias2.attribute2
A parser for this subset of SQL was provided.

Attribute values were either character strings or integers, and tables were stored in text files on disk. All tables had at least one column indexed in memory, the implementation of the index being provided based on last year's contest. Before the actual starting of each workload, the contestants were given a predefined number of seconds to perform some preprocessing steps over the data. At this point, their implementation received a set of queries which was representative of the workload.

Among the eight benchmarks, five were of a reasonably small scale and were designed to test the workability of the binary provided by the contestants. The last three were designed to test the performance (up to 150,000 queries, and up to 1,000,000 tuples stored on a given node). Contestants were given a one-line description of each workload, though the actual structure of the input data was not disclosed. The benchmarking tool would initiate 50 parallel connections on a master node and then would start issuing the queries.

The full description of the task is available at http: //dbweb.enst.fr/events/sigmod10contest/.

THE COMPETITION

The initial description of the task was made available in December 2009 along with all necessary interfacing code, though some addition and fixes came over the following months as bugs or imprecisions were pointed out by contestants. Starting from February 2010, contestants had access to the evaluation cluster and could check the score of their submission and their ranking. Students had then up to April to work on their implementation. Then, a shortlist of five finalist teams, whose submission had the best performance, was selected and these teams could use the remaining time before the beginning of the conference, in June, to continue improving their implementation.

Setting up the evaluation cluster, eight dedicated PCs running a 64bit version of Linux on a single-core CPU, was not completely straightforward. First, it was critical to ensure the security of the machines and the nondisclosure of the contents of the benchmarks, whereas contestants were allowed to run arbitrary code on the cluster. The solution chosen was to run each submission as a new unprivileged Linux user without any write access to any part of the disk (except for a temporary directory that was emptied after each evaluation), and to set up a strict firewall that prevented any information leaking outside the cluster. Second, for scores to be meaningful, evaluation times had to be reproducible from one run to another. This led us to use dedicated servers rather than virtualization, to clear all system caches across runs, and to ensure, as much as possible, that no concurrent processes were active on the cluster nodes. Third, it turned out that contestants encountered problems (crashes, timeouts) while running their submissions on the evaluation workloads that they were not able to reproduce on their test benchmarks. To help them with debugging, we provided them with stack traces and other similar crash information, from the execution log of the evaluation. This, however, could not be automated, because of potential leaks of detailed information about the content of the benchmarks, and resulted in a time-consuming task for the organizers.

A total of 29 teams took part in the competition, from 23 different institutions in 13 countries. An amazing collective effort was put in this contest, with some teams literally dedicating months of working time to the competition. As a result, leading implementations are impres-sively sophisticated and efficient.

The five finalist teams and their score, computed at the end of the competition, are listed in Table 1. Note that only the top two teams managed to pass all benchmarks in the allocated time. Both of these implementations are interesting: the winning one, cardinality's, is generally faster, but is actually slower than the second-ranked, namely dbis's, on the last workload, which is also the most difficult one.

More details about the results of the competition can be found at the following URL: http://dbweb.enst. fr/events/sigmod10contest/results/.

KEY IDEAS BEHIND LEADING IM-PLEMENTATIONS

We present in this section the general ideas behind the two systems we implemented. When not stated otherwise, the description applies to both.

Given the task, query planner and executor are two main components to build. Undoubtedly, both of them can make an enormous impact on the overall performance. Here we discuss key decisions on designing and implementing these components in more detail. We refer to a textbook on database management systems such as [START_REF] Ramakrishnan | Database Management Systems[END_REF] for precisions on some of the techniques used.

Query Planning

In order to determine the most efficient physical query plan, we implemented cost-based query optimization. Our objective is to minimize total resource consumption rather than response time because of the many concurrent queries running at the same time. The cost model focuses on network transfer as well as sequential and random disk reads. Incorporating CPU cost would be a natural next step, but we believe that its impact on the quality of the selected plan will be marginal given the performance of the main-memory index and the limited class of supported SQL queries. Also, calibrating parameters for complex models would have been more difficult due to restricted access to the evaluation cluster.

Finalist teams employed various plan search strategies. Team cardinality enumerates all possible physical query plans and estimates their costs. Because plans are built bottom-up, a dynamic programming technique is applied in order to avoid building and evaluating the same subplan multiple times. During plan enumeration, uninteresting subplans are pruned according to heuristics that favor index-based operators. These heuristics not only reduce the size of search space but also complements the rather simple cost model. Note that time and space consumption of this exhaustive search is bounded because the contest specifies that at most five tables are joined. On the other hand, team dbis first performs an exhaustive search for all possible join orders and then refines the plan with optimal join order using heuristics. Once the optimal join order is chosen, the query planner starts with a basic plan using table scans and block nested-loop joins. Subsequently, alternative plans are derived using as many index-based operators as possible. In this step, a block nested-loop join can be replaced by a merge join when two primary key columns are joined. Likewise, if one or both join columns are indexed, a hash join can be used by treating the given index as a hash-based access structure. A similar procedure applies for access operators; a table scan is substituted by an index scan followed by an optional table seek based on the offset retrieved from the index. Exploiting partitioning information during query planning turns out to be a crucial observation for passing all benchmarks. Clearly, certain queries can be answered by accessing only relevant partitions because all tables are range-partitioned based on the primary key column. For example, primary key joins do not cover all possible partition pairs, but are processed only between partition pairs whose ranges overlap. Similarly, conditions on the primary key column can eliminate out-of-range partitions. Because accessing multiple partitions usually involves network transfer, skipping one partition can decrease the running time significantly. If partitioning information indicates that a condition is unsatisfiable, we generate a query plan with a no-op operator that produces an empty result set.

Statistics of each partition are gathered during the preprocessing step. We obtain partition sizes and estimate the cardinality and average column sizes by sampling a few first pages in each partition. Also, we count the number of distinct values for indexed columns. Other than these basic statistics, we do not maintain detailed information about data distribution and rely on fixed selectivity factors depending on the type of predicates.

Query Execution: Single Node

Tables stored on disk are accessed through memorymapped I/O. This strategy has two main advantages. First, we can deploy a high performance buffer pool with little implementation effort because the page cache in the Linux kernel provides this function for us. Even though a naïve approach using an input file stream library also utilizes the page cache, we cannot read the page cache directly. Consequently, excessive memory copy between kernel and user spaces cannot be avoided. Second, we can access columns spanning multiple pages efficiently. Unlike most traditional databases, underlying data files are stored in the comma-separated values (CSV) format. Thus, addressing a column would be complicated unless there is a contiguous address space for an entire file. Note that despite these advantages, this strategy would not have been practical on 32-bit architectures where available address space is considerably smaller.

Query execution uses a simple pull-based, Volcanostyle, iterator model [START_REF] Graefe | Volcano -an extensible and parallel query evaluation system[END_REF] where each operator implements Open(), GetNext(), and Close() interfaces. A tuple passed by GetNext() is always represented as a vector of pointerlength pairs. Because we avoid memory copy as much as possible, these pointers usually reference either memorymapped files or communication buffers.

Query Execution: Multiple Nodes

Send and receive operators fulfill the communication among the master and slave nodes. A receive operator generates a request message by serializing the subplan rooted at its child and ships the message to its corresponding send operator. Upon receiving a request message, the send operator constructs the subplan, executes it, and sends its result back as a response message. Each send operator runs on its own worker thread for concurrent execution. Some finalist teams maintained a thread pool with a fixed number of worker threads. However, a naïve approach without a thread pool also performs well because only hundreds of threads are created and destroyed each second in this setting.

The send and receive operators exchange messages over TCP/IP connections, so efficient TCP communication is vital to the performance. The first challenge to minimize TCP overhead is to amortize TCP connection setup and tear-down cost across multiple requestresponse pairs. Finalist teams addressed this challenge in slightly different ways, but the main idea is to maintain established TCP connections for reuse. Some teams keep a single TCP connection between each pair of nodes, while the others initiate a new TCP connection whenever there is no reusable connection. In the contest setting, the latter works better because receive operators do not have to wait for the single TCP connection to be available. Another challenge is to reduce per-message TCP overhead in order to increase application throughput. To achieve this goal, we pack each message into fewer TCP segments by setting the TCP_CORK option on all TCP connections. The Linux kernel does not transmit partial TCP segments as long as the TCP_CORK option is set and a 200-millisecond timer does not expire. As a result, more network bandwidth is utilized by request and response messages rather than TCP/IP headers. These two techniques yield a substantial performance improvement; benchmark 6 runs more than four times faster.

Message compression is another natural way to save network bandwidth. For request messages, we adopted a variable-length integer code that serializes smaller integers into fewer bytes. This simple encoding is quite effective for request messages because serialized query plans contain many small integers such as node ids and column ids. An optimized variable-length encoding implementation decreases the running times of benchmarks 6 and 7 by more than 20%. For response messages, we experimented with a couple of lossless compression algorithms. Even though we observed good compression ratios and some performance improvements using our test dataset and queries, we failed to decrease any benchmark running time. This result is not surprising because the cost of message compression can be more expensive than the benefit depending on workload and hardware configuration. Clearly, we need a more sophisticated algorithm that determines which messages to compress in order for this technique to work well across various workloads.

CLOSING REMARKS

The SIGMOD 2009 and 2010 programming contests were a chance for many students (at both the undergraduate and graduate levels) to discover and design parts of the architecture of a distributed database management system. The contest was used in several universities as part of the curriculum or as an optional alternative to other assignments. This programming contest will run again next year, organized by Stavros Harizopoulos and Mehul Shah from HP Labs. It is our hope that this competition will help foster the next generation of database researchers and practitioners.

Table 1 :

 1 Final score, corresponding time, and proportion of the eight workloads processed

	Team	Institution	Country	Score	Time Workloads
	1. cardinality Stanford University	USA	88	3min 18s	8/8
	2. dbis	TU Kaiserslautern	Germany	98	5min 45s	8/8
	3. spbu	Saint-Petersburg University Russia	108 >12min 17s	7/8
	4. insa	INSA Lyon	France	119 >22min 20s	7/8
	5. bugboys	KAUST	Saudi Arabia	142 >30min 19s	5/8
	Naïve implementation		207 >45min 31s	2/8

ACKNOWLEDGMENTS

We are very grateful to the sponsors of the programming contest: NSF, Microsoft (platinum sponsors); Amazon, INRIA Saclay (gold sponsors); Exalead, Yahoo! (silver sponsors). We would also like to acknowledge our advisory board: Serge Abiteboul, Magdalena Balazinska, Samuel Madden, and Michael Stonebraker.