On Saying “Enough Already!” in SQL
Michael J. Carey
Donald Kossmann
IBM Almaden Research Center
San Jose, CA 95120
carey@almaden.ibm.com, kossmann@db.fmi.uni-passau.de
Abstract
In this paper, we study a simple SQL extension that enables query
writers to explicitly limit the cardinality of a query result. We
examine its impact on the query optimization and run-time execution
components of a relational DBMS, presenting two approaches—aConservative approach and an Aggressive approach—to exploiting
cardinality limits in relational query plans. Results obtained froman empirical study conducted using DB2 demonstrate the benefitsof the SQL extension and illustrate the tradeoffs between our two
approaches to implementing it.

1 Introduction
The SQL-92 query language includes support for a wide rangeof relational query operations, including selection, projection,
many flavors of joins, unions, sorting, aggregation, grouping,and subqueries [MS93]. In addition, SQL continues to evolve,
with extensions such as the object features of SQL3 andthe control constructs of SQL/PSM. Surprisingly, despite its
impressive query power, SQL provides no way to specify alimit on a query’s result cardinality—so there is no declarative
way for a SQL query writer to say “enough already!” As aresult, application programs that wish to pose a query and thenprocess at most some number (N) of its result tuples must doso, using a cursor, by submitting the entire query and thenfetching only its first N results.
There are two relational database system trends that, in
our view, will soon produce a strong need for declarative
support for query cardinality limits. One trend is their current
evolution into object-relational database systems [Sto96]
and their use for managing multimedia data types suchas text and images. Multimedia predicates often involve
approximate matching (i.e., matching with a goodness-ofmatch measure), as in “show me the ten images in the
database that look the most like this example” [Fag96, CG96].
This is a clear case where ranked results and cardinality
limits are needed. Another trend is the increasing use of
relational databases in decision-support and data warehousing
environments. Ranking and cardinality limits are commonly
needed by business analysts [KS95], as in “show me lastCurrent address: University of Passau, 94030 Passau, Germany

week’s gross rental income from the ten most popular videos.”In this paper, we extend SQL with explicit support forlimiting the cardinality of a query result to a user-specified
number of tuples. While a cursor-based approach is sufficient
to limit the result size at the application level, in most cases
it fails to limit the work done by the database engine—
leading to potentially long response times, large amounts ofwasted work, and a corresponding reduction in the amountof processing capacity that the database engine can makeavailable for other, concurrent queries. After suggesting
this simple SQL extension, we show how to incorporate theknowledge it provides into the query optimizer and runtime
query execution subsystem of a typical relational DBMS. In
addition, we present experiments using an actual relational
DBMS (DB2) that quantify the potential performance gains.
The remainder of this paper is organized as follows: Section
2 presents the SQL extension and provides several examples
to illustrate its usefulness. Section 3 discusses the query processing implications of the extension, proposing two implementation strategies—a conservative strategy and an aggressive strategy—for exploiting query cardinality specifications.
Section 4 outlines our approach to evaluating the performanceof the different strategies, which involves running benchmark
queries against a synthetic database, and Section 5 applies thisapproach to DB2. Section 6 discusses related work, including
the “optimize for early results” features found in current commercial query optimizers. Section 7 presents our conclusions
and plans for future work.
2 Extending SQL
The specification of a cardinality limit for a query canbe supported by extending the syntax of SQL’s SELECT
statement [C 95, CG96]. In this paper, we will do so byadding a STOP AFTER clause as an optional suffix, i.e.:
SELECT ... FROM ... WHERE ...
GROUP BY ...
HAVING ...

ORDER BY sort
specification list STOP AFTER value expression 

An SQL <value expression> is any expression that
evaluates to an atomic value; it may be a constant, acomputation of some sort, or even a subquery [MS93]. In
a STOP AFTER clause, the expression must evaluate to an
integer value that specifies the maximum number of result
tuples desired. In addition, the <value expression>must be uncorrelated with the remainder of the query in orderto ensure that the query’s semantics are well-defined.

1

The semantics of a STOP AFTER query are straightforward to explain operationally: after doing everything else
specified by the query, retain only the first N result tuples(where N is the integer that <value expression> evaluates to). In cases where the result of the query is totally ordered by the inclusion of an ORDER BY clause, only the firstN tuples in this ordering are returned to the query’s user or application program. In cases where the particular N-tuple result
set is not completely defined, due to duplicate values for the
ORDER BY attribute(s), the choice of which of the candidatesets of N tuples will be returned is left unspecified. If there isa STOP AFTER clause but no ORDER BY clause, then any
N tuples that satisfy the rest of the query is considered to bea valid result. Finally, if there are fewer than N tuples in the
result, then the STOP AFTER clause has no effect. These
STOP AFTER semantics yield the same results as the cursorbased approach used by applications today.
In addition, we propose to eliminate some of SQL’s
restrictions concerning ORDER BY clauses. First, we suggest
eliminating SQL’s restriction of requiring a query’s ORDER
BY column(s) to also appear in its SELECT list.  Second, wesuggest allowing ORDER BY clauses to appear in subqueries,
as they become meaningful in subqueries that also have a
STOP AFTER clause. Both of these extensions are trivial,
and their usefulness for STOP AFTER queries should beapparent from the following examples.
2.1 Example SELECT Queries
To illustrate the usefulness of having the STOP AFTER
clause, as well as illustrating its generality, let us consider afew example queries that it enables.
Example 1: Spatial Data Consider an object-relational
travel database. Suppose the locations of various travelrelated objects are kept track of using location attributes,
which are of a user-defined Point data type, and supposethat the Point type has a distance function that returns the
distance between two points. We can then find the five hotels
closest to the O’Hare airport as follows:
SELECT h.name, h.address, h.phone
FROM Hotels h, Airports a
WHERE a.name = "O’Hare"
ORDER BY distance(h.location, a.location)
STOP AFTER 5;

Example 2: Decision-Support Data Now consider a business database containing product sales data. We can find the
top 10% of the software products in terms of gross sales revenues as follows:

SELECT p.name, s.gross
FROM Products p, Sales s
WHERE p.type = "Software"
AND p.prod num = s.prod num
ORDER BY s.gross DESC
STOP AFTER (SELECT count(*) / 10
FROM Products p
WHERE p.type = "Software")
In fact, some commercial systems already support this extension.

2.2 What About Updates?
Extending the SQL SELECT statement with a STOP AFTER
clause also makes it possible, without modifying SQL’s
INSERT, UPDATE, or DELETE statements, to express avariety of interesting updates as well. This is shown by thefollowing example involving a database of information about
baseball players.
Example 3: An Update We can give a 50% pay cut to thethree worst batters as follows:
UPDATE Players
SET salary = 0.5 * salary
WHERE id IN (SELECT p.id
FROM Players p
ORDER BY p.batting avg
STOP AFTER 3)

2.3 Implications
Clearly, it is not hard to extend SQL to allow users to specify alimit on the result size of a query, and a number of interestingqueries and updates become expressible. The advantage ofextending SQL is that it provides information that the DBMS
can exploit during query optimization and execution. The
challenge, addressed in the next section, is to find ways to
exploit this information—ways that are effective, yet requireas few optimizer and runtime system changes as possible.
3 Processing STOP AFTER Queries
One approach to handling applications where a STOP AFTER
clause is needed is to do so with little or no change to the
database engine. This can be done externally, as is generally
done today, or it can be done by adding a very thin additional
query processing layer to the engine. This layer could strip
off the STOP AFTER clause and execute it (if necessary) tocompute the desired stopping cardinality; it could then submit
the remainder of the query to the engine, fetch results using
the system’s cursor interface until the desired number of tuples have been returned to the user, and then close the cursor.
As we will see later, however, both the “external” and “thinlayer” approaches miss opportunities for major performance
improvements that can be obtained by making use of the desired cardinality limits in the database engine.
In this section, we present a better alternative—extending
the relational database engine to understand and process
STOP AFTER queries. We will first describe a new query
operator, called Stop; this operator encapsulates the STOPAFTER functionality so that other operators, such as Sort and
Join, need not be changed and can be used in STOP AFTER
queries just as in other SQL queries. Then, we will describe
two extreme heuristics to place Stop operators in query plans:Conservative and Aggressive. At the end of the section, we
will describe how Stop operators and these two heuristics canbe integrated into an existing dynamic-programming based
optimizer. Throughout the section, we will focus on STOPAFTER query processing in the presence of an ORDER BY
clause because we expect this to be the most common case2

in practice; STOP AFTER queries without an ORDER BY
clause can be processed in a very similar way. Furthermore,
we will focus on STOP AFTER queries with only one queryblock; we will explore techniques to process queries withmore than one query block (e.g., queries against views or
queries with subqueries) in future work.
3.1 The Stop Operator
The Stop operator is a new logical query operator; it produces,in order, the top or bottom tuples of its input stream. The
Stop operator requires three parameters to be provided atquery initialization time. The first is N, the desired numberof result tuples. The second is a Sort Directive, which will be
one of three values: desc, asc, or none. If the sort directive
is desc (asc), the Stop operator sorts its input stream andtuples in descending (ascending)returns the top (bottom)
order. If the sort directive is none, the Stop operator simply
returns the first tuples from its input stream; the none option
is chosen by the optimizer when the Stop operator’s input
stream is known to already be appropriately sorted. The thirdparameter to Stop is a Sort Expression. If the sort directive
is desc or asc, the Stop operator sorts its input according tothis sort expression, which is usually identical to the ordering
expression from the ORDER BY clause of the query.
Like other logical operators (e.g., Join), the Stop operator
can have more than one physical operator that is capable of
implementing it in a query plan. Clearly, the implementationof the Stop operator should at least be dependent on its sort
directive. Accordingly, we define two different physical Stop
operators here: Scan-Stop, for when the sort directive is none,
and Sort-Stop, for when the sort directive is desc or asc. We
now discuss a possible implementation and a cost model (forthe optimizer’s use) for each one.
3.1.1 Scan-Stop
The Scan-Stop operator is extremely simple. Scan-Stop is apipelined operator that simply requests and then passes eachof the firsttuples of its input stream on to its consumer(i.e., to the operator above it in the query plan), after which
it closes down its input stream and returns an end-of-stream
indicator to its consumer. As a result, the cost of the ScanStop operator itself is negligible, and the total cost of a query
subplan rooted at a Scan-Stop operator is dominated by thecost required to produce the first tuples of its input stream.
In a state-of-the-art relational DBMS, the query optimizer’s
cost model provides estimates for the total cardinality of aplan’s output (ALL), the cost to produce the first tuple of aplan’s output (cost  ), and the cost to produce ALL output
tuples (cost ALL)). Given estimates for these quantities forthe subplan that generates the input stream for the Scan-Stopoperator, the optimizer can estimate the cost, cost  , for thewhole plan rooted at the Scan-Stop( ) operator as follows:
cost 

cost  cost ALL  cost 

ALL

(1)

This estimate assumes that the tuples after the first one are
generated smoothly by the subplan that feeds into the ScanStop operator, i.e., that cost "!#$ cost %!  is more or lessconstant for '&(!) ALL. Also, it assumes that *& ALL(since for ,+ ALL, cost  cost  ALL  ).
The nature of Equation 1 implies that the optimizer is likely
to favor pipelined query plans (e.g., query plans with nestedloop join operators) for STOP AFTER queries, particularlyis small. This is because
when the cardinality limit
pipelined execution plans quickly produce their first row (i.e.,
cost .-0/ ); therefore, the relative cost of the STOPAFTER query will be proportional to its cardinality limit. In contrast, if the Scan-Stop operator’s input stream is
produced by a pipeline-breaking subplan (e.g., one with a sortmerge join in it), then the cost to produce
tuples will bealmost the same as the cost to produce ALL tuples.
3.1.2 Sort-Stop
If the input of a (logical) Stop operator is not already sorted,
then the Stop operator must consume and sort its whole
input to produce the top or bottom
output tuples. For
relatively small (which we expect to be the most commoncase), the sorting can be carried out in main memory usinga priority heap [Knu73]. The firsttuples consumed by
the Sort-Stop operator can be inserted into a priority heap,
and the remaining tuples can then be tested with the heap’s
membership bound to determine whether or not the newtuple’s value warrants its insertion into the heap. The cost of
producing results with this implementation of the Sort-Stopoperator has the following three components: (1) the cost ofgenerating the whole input stream for the Sort-Stop operator(cost (ALL)), (2) the cost of testing ALL 1 tuples against
the heap’s membership bounds ( ALL 243 , where 3
is the cost of a comparison), and (3) the cost of inserting 5
qualifying tuples into a heap with at most elements (where
5 is estimated below). In all, the resulting plan cost can be
estimated as shown in Equation 2; again, we assume 6&
ALL, as for ,+ ALL, cost "7 cost 8 ALL).
cost  7 cost ALL9: ALL ;<=3$>5? @BADC" (2)Assuming randomly ordered data, 5 can be estimated as:

5=E:

.F



GIH

KJLJLJM

ALL

N HALL  HOPQR?

(3)(Here, H S denotes the k-th harmonic number [Knu73].)
Again, this cost estimate assumes thatis small andthat a heap oftuples will fit in memory. For larger ,external sorting is required. Although Sort-Stop’s specificrequirements invite the design of a specialized external SortStop algorithm, we will not discuss such an algorithm here.
Instead, we will assume a Sort-Stop implementation that uses
an ordinary external Sort operator in conjunction with the
Scan-Stop operator when is large.

3

3.2 The Conservative Policy
We now turn to the question of where Stop operators shouldbe placed in a query plan. Stop operator placement involves
a fundamental tradeoff: On one hand, a deeply placed Stop
operator will cut down the size of intermediate results early,
thus reducing the cost of operators higher up in the plan. On
the other hand, it is possible for a deeply placed Stop operator
to eliminate too many tuples of an intermediate result; thissituation must then be trapped at run-time, and the executionof the query must be restarted to produce the remaining(missing) tuples of the query result.
An ideal optimizer would weigh the risk and cost of restarts
against the benefits of deep Stop operators placement. However, current optimizers have no notion of risk. We therefore
propose the use of a heuristic Stop operator placement policy to assist the optimizer in placing Stop operators in a plan.
In this subsection, we will present the Conservative policy,
which completely avoids restarts by restricting Stop operator
placement to “provably safe” locations in a plan. In the next
subsection, we will present the Aggressive policy, which does
permit the placement of Stop operators at unsafe places.
3.2.1 Conservative Stop Placement
The Conservative policy introduces Stop operations as earlyas possible in a plan, subject to the following principle whichmakes sure that under no circumstances restarts are required:Conservative Stop Placement Principle: Never insert
a Stop operator at a point in a plan where its presence
can cause tuples to be discarded that may be required
to compose the requested N tuples of the query result.
Intuitively, a Stop operator can be applied to a tuple stream ifevery tuple in that stream is guaranteed to generate at least one
tuple of the overall query result. During query optimization,
this condition can be tested for a tuple stream produced bya subplan by (i) inspecting the query predicates that remain
to be applied following the subplan (to complete the query),and (ii) examining the integrity constraints involving columns
that participate in these remaining predicates. The conditionis satisfied for the subplan’s output stream if each of theremaining predicates is non-reductive, defined as follows:
1. the predicate is of the form TU
V , where T is anexpression computable from the stream and V is anexpression involving one or more tables yet to be added
to the plan, and
2. it can be inferred from the database integrity constraints
that (i) T cannot be null, and (ii) for each T there must
exist at least one V such that T;WV holds.
For example, if T is a column with a NOT NULL constraint,
and the database has a referential integrity constraint declaringthat T is a foreign key that references a table yet to bejoined whose key is V , then these criteria are met—making
TNXV a non-reductive predicate. In the case of outer-join

predicates, the two conditions can be relaxed because a tuple
from the outer relation survives even if no matching tuple
from the inner relation exists. In the case of GROUP BY or
DISTINCT queries, if the grouping operation (or duplicate
elimination) remains to be done, a similar set of rules can bederived. In this case, the tuple stream must be functionallydependent on the GROUP BY (or DISTINCT) column(s), andany HAVING predicates must also satisfy the conditions above
so that all groups will survive. Naturally, the Conservative
Stop insertion conditions will always hold at the root of aplan for the whole query because no predicates remain to be
applied at that point. In all cases, the Stop operator inserted
will have a cardinality parameter of , where is the value
specified in the STOP AFTER clause.
3.2.2 Conservative Plan Examples
Consider the following database for managing a company’s
employees, departments, and employees’ travel expense accounts (TEAs):
Emp(empId, name, salary, works in, teaNo)
Dept(dno, name, budget, function, description)
TEA(accountNo, expenses, comments)
The underlined columns are the primary keys for the tables,
while the italicized columns (works in, teaNo) are foreign keys. In addition to key and referential integrity constraints, we assume that the database has an integrity constraint to enforce the fact that every employee must work in
a department; i.e., Emp.works in is NOT NULL. Finally,
we assume that not all employees travel, so the corresponding
specification for Emp.teaNo would say NULL ALLOWED.
Figure 1 shows three STOP AFTER queries, with corresponding query execution plans, to show how Conservative
Stop placement works. In Query 1, a Stop operator can beplaced beneath the join on the Emp side (i.e., just above a scanof the Emp table). This is permitted because e.works in= d.dno is a non-reductive predicate. In contrast, in Query2, the placement of a Stop operator will be forbidden at thatpoint in the plan, as two predicates remain: e.works in= d.dno and d.function = ’Research’. The latter
predicate is not non-reductive: If the Emp tuple stream werereduced to the 10 highest paid employees before the join, thequery could come up short, as joining those employees with
only research departments could eliminate many of them. Y Finally, in Query 3, which asks for the bottom 10 tuples by departmental budget rather than the top 10 by employee salary,the Stop operator must again be placed above, rather than below, the join. In this case, the join predicate itself is nonreductive, as our integrity constraints provide no guaranteethat every department has at least one employee.
To complete our discussion of the Conservative approach,
we need to raise one subtle point that we have glossed over
up to now. Even if a join predicate satisfies the criteria forbeing non-reductive, it is possible that the join may reduce theZ

Lou Gerstner, for example, is not an IBM researcher!

4

SELECT [FROM Emp e, Dept d
WHERE e.works in = d.dno
ORDER BY e.salary DESC
STOP AFTER 10;

SELECT [FROM Emp e, Dept d
WHERE e.works in = d.dno
AND d.function = ’Research’
ORDER BY e.salary DESC
STOP AFTER 10;

Join
Stop(10)Stop(10)Stop(10)

Join

Join

Dept

Emp

Query 1 & Plan 1

SELECT [FROM Emp e, Dept d
WHERE e.works in = d.dno
ORDER BY d.budget
STOP AFTER 10;

Emp

Dept

Dept

Query 2 & Plan 2

Emp

Query 3 & Plan 3

Figure 1: Example Queries and Conservative Plans
cardinality of the input stream in question—this can happen if,
and only if, the to-be-joined table is empty, in which case evena Cartesian product with this table will reduce the stream’s
cardinality (to zero). While true, this does not invalidate our
specification of the Conservative approach, as the query result
is itself empty in this case—so pruning the tuple stream will
not cause required tuples to be erroneously discarded.
3.3 The Aggressive Policy
The Conservative policy has several advantages: its Stop operators simply take their value of from the STOP AFTER
clause, and Conservative execution plans are a straightforward
extension of regular plans (with Stops added in strategic but
safe places). It also has a disadvantage, however: it only inserts Stop operations at points where all remaining predicatesare non-reductive, so in the absence of NOT NULL and referential integrity constraints, it cannot place Stop operators below joins in multi-way join plans. Given that joins are expensive operations that benefit significantly from input cardinality
reductions, it would be nice if we could relax this restriction.
That is the goal of the Aggressive policy.
3.3.1 Aggressive Stop Placement
The Aggressive policy seeks to introduce Stop operations as
early in query plans as possible, regardless of whether or nottheir insertion is provably safe. In other words, the Aggressive
policy operates according to the following principle:
Aggressive Stop Placement Principle: Insert Stop
operators in query plans wherever they can provide abeneficial cardinality reduction.
Thus, an optimizer that employs the Aggressive policy willconsider a Stop insertion at each point in a query plan tree
where the first (high order) column of the query’s ORDERBY clause can be computed, i.e., at each point where a setof top (or bottom) tuples can be identified with respect tothe requested result order. Several new issues arise when the
optimizer is able to generate plans with a Stop operator below
one or more reductive predicates. First of all, the optimizer
must now compute the stopping cardinality for such a Stop
operator; this can be done using a simple formula based on
the cardinality estimates utilized by a typical state-of-the-art
query optimizer. Let ALL\^]`_badc be the estimated number oftuples that would be produced by the query as a whole without
any Stops, and let ALLef]`gLhLi jlk be the estimated number oftuples produced by the subplan that feeds tuples into the Stop
denote the target
operator in question. As always, letcardinality of the query as a whole (the value specified in the
STOP AFTER clause). Given these quantities, the stopping
cardinality for the Stop operator in question should be set to:nm^op h 

ALLef]`gLh`i jlk
2ALL\^]`_badc(4)

In other words, the Stop should reduce the cardinality of thetuple stream at its point in the plan in proportion to the optimizer’s estimate of the overall cardinality reduction requestedby the user. In practice, it would be better to inflate the stopping cardinality by, say, 20% to accommodate estimation error; we will explore this issue further in Section 5.
Since setting the stopping cardinality in this way relies on
cardinality estimates, additional steps must be taken to ensurethat the right number of result tuples is ultimately produced
by an Aggressive query plan. To handle situations where
the Aggressive optimizer sets a Stop operator’s stopping
cardinality too high, another (final) Stop operator must beplaced at (or near) the root of the plan. To handle situations
where the stopping cardinality is set too low, the query plan
must be restarted to produce the missing tuples. We propose
to handle the required restart activity at runtime by having
a well-placed Restart operator in the Aggressive query plan.
We present this operator in the following subsection, showing
how it can be added to an Aggressive Stop plan as part of aplan refinement step that takes place after Aggressive query
optimization is completed.
3.3.2 Restarts and Plan Refinement
The job of a Restart operator is to make sure that, above
the point where it is placed in the query plan, at least
tuples will surely be generated. If the Restart operator’s input
stream is exhausted before tuples are received, then it must
“restart” the query subplan beneath it to generate the required,but missing, results. There are several possible strategies for
actually restarting a query subplan. Ideally, we would like tocompute the missing tuples without recomputing any of theresults that we have already gathered. However, this would insome situations be difficult (if not impossible) to accomplish

5without making all of the system’s operators restartable.
q handle restarts without changing existing runtime operTo
ators, we adopt a simple approach: the Restart operator will
simply close and then re-open the iterator associated with theoperator that feeds it tuples from the subplan immediately beneath it—causing the root operator of the subplan to recursively close and re-open its own input iterator(s), and so on
down the line. The Stop operator in the scope of the subplan will reconfigure itself when it is reopened by increasing
its stopping cardinality by a predetermined factor (e.g., a factor of 2) to let more data through the next time around. The
other operators in the subplan will simply start over from the
beginning, though their cost will be lower since much of therelevant data will still be in the buffer pool. To ensure that thecorrect number of results are ultimately produced, the Restart
operator will repeat this process (if necessary) until it has produced tuples or there are no more tuples to produce.
Restart operator insertion can be done by post-processing
the optimizer’s chosen query plan as follows: Find the nonConservative Stop operator in the plan and insert a Restart
operator at the first point above it where all remaining
predicates are non-reductive. If we produce
results there,
we are “safe”; no further cardinality shrinkage can occur. The
post-processor can simply walk up the plan tree from the nonConservative Stop operator in order to place the Restart as
deeply as possible (to minimize the cost of a restart).
For Aggressive query plans that are fully pipelined, or havepipelined sections, there is an additional plan refinement thatis possible and very useful: Scan-Stop pullup. This transformation pulls Scan-Stop operators residing in a pipelined
segment of a query plan up to the top of the pipeline. This
reduces the risk of restarts, as it re-positions the Scan-Stopabove reductive predicates in the pipeline (whose impact on
the tuple stream cardinality might be difficult to estimate).
In the extreme case, when all the remaining reductive predicates are applied in the pipeline, Scan-Stop pullup converts
an Aggressive Scan-Stop operator into a Conservative one—completely eliminating the risk of restarts; Scan-Stop pullup
must, therefore, be performed before Restart operator placement, and when the pullup transformation is performed, thecardinality parameter of the affected Scan-Stop operator must,of course, be recomputed based on its new position in thequery plan. Note that Scan-Stop pullup is never detrimental. Consider, for example, a Scan-Stop operator sitting immediately beneath a pipelined operator such as a nested loop
index join (NLIJ). In such a case, nothing is gained by having
the Scan-Stop operator sit beneath the NLIJ operator, because
the NLIJ produces output incrementally, on demand—i.e., its
cost is proportional to the amount of data that it is asked tomaterialize, not to the size of its inputs. We can thus pull the
Scan-Stop operator up above the NLIJ without increasing thecost of the plan. This pullup opportunity arises because thetwo NLIJ plans will have the same cost during plan enumeration, and the risk of restarts is not taken into account during
enumeration.

v Stop(10)s Stop(10)t JoinRestartt Joins Stop(20) r TEA
Emp

Dept

Restartw Joinv Stop(20)w Join

u TEA

Dept

Emp

Plan 1
Plan 2
Figure 2: Aggressive Stop Push-Down for a 3-Way Join
3.3.3 Aggressive Plan Examples
Figure 2 shows two examples of query plans that could be
produced by Aggressive Stop optimization followed by plan
refinement for the following query:
SELECT e.name, e.salary, d.name, t.expenses
FROM Emp e, Dept d, TEA t
WHERE e.works in = d.dno
AND e.teaNo = t.accountNo
ORDER BY e.salary DESC;
STOP AFTER N;

Recall that all employees work in some department, but not
every employee has a travel account. For illustration, supposethat half of the employees have a travel account (i.e., anassociated TEA tuple). In Plan 1 of Figure 3, where Emp is
joined with TEA first, the Aggressive approach is able to placea Stop operator just above the scan of Emp, at which point the
stopping cardinality is set to 20 (because xzy{yD|M}~ " NH andy{yD }bf*`/ ). Because this Stop operator is xznon-Conservative,a corresponding Restart operator is needed; it goes above
the first Join, where the Conservative approach would haveplaced a Stop(10) operator. If the join is non-pipelined (e.g.,a sort-merge or hash join), the Aggressive plan can provide asignificant join cost savings over its Conservative counterpart.
In Plan 2, the join with the TEA table comes last. Since its
join predicate is reductive, the Conservative plan for this joinorder would only be able to place a Stop(10) operator at theroot of the plan. In contrast, the Aggressive approach again
places a Stop(20) operator right above where Emp is accessed.
The potential cost savings in this case is obviously large—if
either join is non-pipelined, Plan 2 is quite a bit cheaper thanits Conservative (in this case “do nothing”) counterpart.
3.4 Extended Query Optimization
Stop operators impact the cost of other operations in a queryplan, thus affecting optimization decisions such as accesspath selection, join methods, and join orderings. We now
show how to extend a modern query
optimizer—one that usesdynamic programming a la [S 79]—to incorporate our Stop
placement policies.
3.4.1 Plan Enumeration
Modern query optimizers use rules to control the enumerationof alternative query plans [GD87, Loh88]. To enumerate all
possible plans with Stop operators, we propose modifying the
optimizer’s rule set to model the Stop operator as another6kind of access path for intermediate results. This willcause the query optimizer to consider adding a Stop operator
immediately after each of its usual ways of accessing eitherbase data or subplan data. Moreover, this change introduces
Stops with minimal impact on the optimizer as a whole, as
the rest of its rule set remains untouched. This is important toensure modularity, and therefore maintainability, of the Stopenhanced rule set. The insertion of a Stop operator must also
be considered at the root of each query plan to ensure thatthe right number of result tuples (as specified by the STOPAFTER clause) will be returned to the application. This can beaccomplished through another new rule that considers addinga Stop operator at this final point.
Once these additional Stop rules have been established,both the Conservative and Aggressive policies can easily
be integrated by defining conditions that control in whichsituations (i.e., for which subplans) a Stop rule can be applied;again, other rules of the optimizer are not affected. A vitalcondition for both policies is that a Stop operator may only begenerated at places in a plan where the top or bottom tuples
can be identified (i.e., where at least the first column of thequery’s ORDER BY expression is computable). To implement
the Conservative policy, the conditions of the Stop rules would
further be restricted to generate Stop operators only at safe
places (as defined in Section 3.2). Such a restriction would
not be considered for the Aggressive policy.
An important issue to make plan enumeration more efficient is to avoid the enumeration of plans with superfluous
Stop operators. To keep track of the places where a Stop
operator is useful, we introduce an additional plan property
called stopping cardinality. (The use of plan properties is
a common technique implemented in most query optimizers [GD87, Loh88, S 96].) For the Conservative policy, thestopping cardinality property can take one of two values: ENFORCED, indicating that the plan’s result stream already satisfies the STOP AFTER clause’s cardinality specification, or
NOT ENFORCED, indicating that this is not true. At leavesof plans (e.g., table scans), the stopping cardinality property
is set to NOT ENFORCED; it is set to ENFORCED when a(Conservative) Stop operator is added to the plan. This property is “destroyed” (reset to NOT ENFORCED) by operatorsthat potentially change the cardinality of their input streams(e.g., certain joins), and is transported by other operators. Using the Conservative policy, therefore, Stop operators can only
be added to NOT ENFORCED subplans, and again, this constraint can be implemented in the condition part of the rules.
In addition to ENFORCED and NOT ENFORCED, thestopping cardinality can be set to ASSISTED to support theAggressive policy. This is done by a non-Conservative Stop
operator whose stopping cardinality is based on cardinality
estimates, and it specifies that cardinality reduction has been
performed but that an additional Stop operator is neededat (or near) the root of the plan to guarantee ENFORCED
cardinality for the whole plan. An ASSISTED stopping
cardinality is transported by every operator; it is overwrittenby the final Conservative Stop operator, so only plans with at
most one non-Conservative Stop operator are enumerated.
3.4.2 Impact on Pruning
In the dynamic programming approach to query optimization,a (sub-) plan  is pruned in favor of a (sub-) plan  ifY
and only if  has both a higher cost and weaker propertiesthan  . In addition to the properties considered in aY
traditional optimizer, our STOP-AFTER-extended optimizer
must respect certain additional pruning conditions. If theoutput of  and  Y is ordered according to the query’s
ORDER BY expression, then  may only be pruned infavor of if 
has higher cost and weaker propertiesY(as in traditional optimizers) and cost(Scan-Stop(  L e op h ))
cost(Scan-Stop(   e op h  .  Otherwise, even if   hasYhigher cost than  for producing all results,   may be partYof the overall best plan to produce
results. As stated in
Section 3.1.1, this condition will force the optimizer to retainplans with (seemingly expensive) pipelined operators, such asscans of unclustered indexes.
If  and  Y are not ordered according to the query’s
ORDER BY expression, all of their tuples must be produced
to compute the overall ordered query result. In this case, ourStop-enhanced optimizer must still respect certain additional
pruning conditions to retain query plans with deep Stop
operators. To see why, consider the following query:
SELECT *FROM Emp e, Dept d
WHERE e.works in = d.dno
ORDER BY e.salary
STOP AFTER 100

Suppose that the database has 10,000 employees and 1,000
departments, and that a Sort-Stop operation on 10,000 tuples
costs 40,000 units, as compared to 200 units for either a SortStop or a plain Sort operation on 100 tuples. Also, assume thata sort-merge join costs 43,000 units to join 10,000 employeeswith 1,000 departments, versus 3,200 units for a sort-merge
join between 100 employees and 1,000 departments. (Forsimplicity, we use @BADC to approximate the cost of sorting tuples for a Sort-Stop or sort-merge join.)
During plan enumeration, the following two subplans will
be enumerated, among others:
P = SMJoin(Sort-Stop(Emp), Dept)P = SMJoin(Emp, Dept)YGiven our assumptions, the cost estimate for subplan P  is
43,200 units (40,000 + 3,200), while the cost of  will beYestimated as 43,000 units, which is slightly lower. To produce
the final query result in the requested order (e.salary), a
Sort operator costing 200 units can be attached to  , giving atotal cost of 43,400 units. For  , a Sort-Stop operator costingY
40,000 units is required, resulting in a total cost of 83,000
units. Thus, the winning plan is based on  rather than  —Yeven though  itself has higher cost than  . This is becauseY has stronger cardinality properties; i.e.,  produces 100

Scan-Stop cost as in Equation (1); 7d as in Equation (4.

7SELECTe.name, e.salary
FROM Emp e
ORDER BY e.salary DESC
STOP AFTER N;
Test Query 1

SELECT e.name, e.salary,d.nameFROM Emp e, Dept d
WHERE e.works in = d.dno
ORDER BY e.salary DESC
STOP AFTER N;

SELECT e.name, e.salary,d.name, t.expenses
FROM Emp e, Dept d, TEA t
WHERE e.works in = d.dno
AND e.teaNo = t.accountNo
ORDER BY e.salary DESC
STOP AFTER N;

Test Query 2
Figure 3: STOP AFTER Test Queries

tuples and has a stopping cardinality of ENFORCED, whereas Y produces 10,000 tuples and has a stopping cardinality of
NOT ENFORCED. In general, a plan has stronger cardinality
properties than another plan and may not be pruned if it has
a smaller estimated result cardinality or a stronger stopping
cardinality property obeying the total order: ENFORCED >ASSISTED > NOT ENFORCED.
Obviously, adding rules for Stop enumeration and restricting pruning increases the sizes of the query optimizer’s search
space and its set of candidate query plans. Studying this impact is beyond the scope of this paper, but given the efficiency
and pre-existing complexity of modern query optimizers, we
do not believe that our extensions will seriously impact theirperformance. In fact, related search space issues have beenstudied in the context of GROUP BY query optimization (e.g,[CS94]); those results are directly applicable here.
4 Evaluation Methodology
We have proposed two approaches to placing Stop operators
in execution plans for STOP AFTER queries. To comparethem to each other, and to the “do nothing” approach, wewill employ a synthetic database and several representative
STOP AFTER queries. Our approach will be to “cheat”—
using our knowledge of the attribute value distributions totranslate the STOP AFTER queries into regular SQL queries
with additional predicates that force the target DBMS do an
amount of work that is essentially the same as if its queryplans were Stop-enhanced.
4.1 Synthetic Database
For the test database, we used the tables and integrity
constraints presented in the examples of Section 3. We
controlled the attribute value distributions to facilitate our test
queries and built indexes on all the relevant attributes.
Our test database consists of the Emp, Dept, and TEA
tables introduced earlier. The integrity constraints specify
that every employee works in a department, but not every
employee has a travel account. Each table holds 100,000 rowsof 100 bytes each. (We also tried other table sizes, including amuch smaller Dept table, but will not show those results here;
we saw large performance benefits for our STOP AFTER
schemes, but since the Dept join itself was inexpensive, thebasic results were similar to our single-table query results.)
The tables’ attribute values were synthesized to control range
predicate selectivities and join selectivities. Emp.salaryvalues ranged from 0 to 99,999, and the key and foreign
key values were chosen so that each Emp row joins withexactly one Dept row and one TEA row. We created

Test Query 3clustered indexes on Dept.dno and TEA.accountNo to
support joins between each of these tables and the Emp table.
Our experiments varied the index created on Emp.salary,which was the field used in the ORDER BY clauses of our test
queries—we tried clustered, unclustered, and no index at all,using a descending order index in the cases where this field
was indexed.
4.2 Test Queries
Our test queries are shown in Figure 3. The queries range froma simple single-table query to more complex join queries. The
most highly paid employees.
first query simply finds theIts purpose is to investigate the impact of the STOP AFTER
clause on (1) row blocking (for sending the result set backto the client), (2) access path selection, and (3) costs to sortquery results. The second query finds themost highly
paid employees and their department names. Its purpose is
to show the impact of the STOP AFTER clause on the choiceof join method. The third query finds the most highly paid
employees, including both their department names and theirtravel expenses. Its purpose is to provide a more complex join
example to explore the tradeoffs between the Conservativeand Aggressive approaches. For each query, we varied therequested stopping cardinality from 1 to 100,000.
4.3 DB2 Simulation Approach
Given these queries, we wanted to know—before embarking
on an actual implementation, and for a real DBMS with sophisticated query optimization (including cardinality estimation) and an industrial-strength runtime system—how much
benefit could be obtained from our STOP AFTER optimizations as a function of the stopping cardinality and the physical database design. We chose to “simulate” the executionof Stop plans on IBM’s DB2 for Common Servers by replacing each query’s STOP AFTER clause with an appropriately
designed Emp.salary predicate.
For Queries 1 and 2, we can create regular DB2 queries
that require the same amount of work by dropping their
STOP AFTER clauses and adding a predicate of the form
e.salary >= 100,000-N. Rewriting the queries thisway simulates the effect of placing a Stop operator just above
the table or index scan of the table Emp, as it gives DB2 apredicate to apply at that point that has the same filtering effectas the Stop operator would have there.
For Query 3, we can simulate a Conservative version ofPlan 1 of Figure 2, where there is one Stop operator thatsits immediately above the join Emp  TEA (in place of
Figure 2’s Restart operator), via the following DB2 query:8

SELECT e.name, e.salary, d.name, t.expenses
FROM
Emp e, Dept d, TEA t
WHERE e.works in = d.dno
AND e.teaNo = t.accountNo
AND e.salary + t.zero  100,000-N
ORDER BY e.salary DESC;

as index scans for small values of ); obtaining accurate
times required running them several times and reporting(total elapsed time / no of runs).
5 Experiments and Results

The field TEA.zero is a special field of the TEA tablethat simply contains the value 0 in each row. Using thisfield, we have translated the STOP AFTER N clause in theoriginal version of Query 3 into the predicate e.salary+ t.zero >= 100,000-N; doing so provides the same
selectivity as the simpler predicate introduced for Queries 1
and 2, but forces DB2 to wait until after Emp and TEA havebeen joined before restricting the number of tuples (where theConservatively placed Stop operator would do it).
We can also simulate an Aggressive version of Query 3, one
where the Stop operator is pushed down to the Emp table, andwhere there is a Restart operator at the top of the query plan
to handle the case where an estimation error causes the plan
to prematurely run out of tuples. We can do so by runningthe following query, which has a pair of parameterized
predicates on Emp.salary, against DB2 from within a C++
application program that uses the parameters to simulate theeffects of estimation and restarts:
SELECT e.name, e.salary, d.name, t.expenses
FROM Emp e, Dept d, TEA t
WHERE e.works in = d.dno
AND e.teaNo = t.accountNo
AND ?  e.salary AND e.salary  ?
AND e.salary + t.zero  100,000-N
ORDER BY e.salary DESC;

Instantiation of the two query parameters (the “?”s) enables
the C++ program to simulate underestimation, precise estimation, and overestimation of the required cardinality for the
Stop operator; it also allows the program to simulate a restartof the query. In addition to this parameterized range predicate,
the DB2-translated aggressive query still includes the special
predicate involving TEA.zero to simulate the presence of a
Stop operator after Emp  TEA; this operator’s job is to cut
down the cardinality when the parameters of the range predicate lead to a range that is too large (simulating a case where
the required cardinality is overestimated).
4.4 Test Environment Details
Our tests were run on an IBM RS/6000 PowerStation 550 with
128MB of main memory running AIX 4.1.4. We used the
product version of IBM’s DB2 for Common Servers (Version
2.1.1). We used DB2’s default settings almost exclusively,
which gave us 4 MB of main-memory buffer space (desirable
so that we didn’t have to generate a huge database for our
tests), a 512 KB application heap for row blocking, and query
optimization level 5. All queries were run against a warm
database (though this was largely a non-issue because thedatabase size was much larger than the buffer pool). We
measured warm times because cold query execution times
were not accurately measurable for the shorter queries (suchNote: We could not simulate a Restart operator in the middle of a plan.

In this section, we use our synthetic database and test queries
to explore, using the DB2 “simulation” scheme outlined in
the previous section, (i) the performance benefits of our STOPAFTER optimization techniques and (ii) the tradeoffs between
Aggressive and Conservative query plans.
5.1 Traditional vs. STOP AFTER Query Optimization
We begin by examining the benefits of STOP AFTER query
optimization for single table queries; we then explore its
impact on join queries. Results are given for three approaches
in this section: (1) TRADITIONAL, which is the traditional,“do nothing” approach in which an application program
hands DB2 the original STOP AFTER query with the STOPAFTER N clause removed, opens a cursor over the results,
requests
rows (one at a time), and then closes the cursor.
(2) TRAD(NRB), which is the traditional approach, but withno row blocking. By default, the DB2 server process ships
answer sets to client processes in large blocks of rows (basedon the application heap size) to minimize communication
costs; the TRAD(NRB) results were obtained by turning thisfeature off, thereby making the server send results back one
row at a time. (3) STOP-AFTER which is the Conservative
STOP AFTER optimization approach; these results wereobtained by sending DB2 the “simulated” STOP AFTER
queries described in Section 4.3.
5.1.1 Single Table Queries (Query 1)
Figure 4 presents the performance results for Query 1 as afunction of , the query’s stopping cardinality, when there isa clustered index available on Emp.salary. Query 1 getsthe names and salaries of the most highly paid employees.
In all three approaches, DB2 utilizes the clustered index toprocess the query—to extract the results in the desired orderwithout sorting—so all of the performance differences seen
here are due to row blocking. TRADITIONAL has very
poor performance (note the logarithmic y-axis!) for small
because it groups query results into blocks of about 500
rows before sending them back to the client; this is clearlya waste when relatively few of the result rows are ultimately
consumed by the application. TRAD(NRB) performs well forsmall , but becomes relatively worse for large
becauseit requires a client/server interaction for each result row. At¡./D/  /D/¢/ , TRAD(NRB) ends up being 2.5 times slower
than TRADITIONAL. In contrast, STOP-AFTER does wellthroughout the entire range. In this case, DB2 sends resultrows back in chunks of min( , application heap), as the
STOP-AFTER plan limits the result size on the server side;
this is good for small
because it avoids wasted work, andgood for large because it involves low overhead when many
results are indeed desired by the application program.

9

100

10

10

£

1

0.1
TRADITIONAL
TRAD (NRB)
STOP-AFTER

0.01

0.001

£

1

0.1
TRADITIONAL
TRAD (NRB)
STOP-AFTER

0.01

0.001
1

10

100

1000

10000 100000

10

TRADITIONAL
TRAD (NRB)
STOP-AFTER

1
1

10

N

100

1000

10000 100000

N

1

10

100

1000

10000 100000

N

Figure 4: Resp. Time (log), Q1

Figure 5: Resp. Time (log), Q1

Figure 6: Resp. Time (log), Q1

Clustered Index on Emp.salary.

Unclustered Index on Emp.salary.

No Index on Emp.salary.

Figure 5 presents the results for Query 1 when there isan unclustered index on Emp.salary. The traditional approaches use a table-scan followed by a sort to obtain thequery result; they do not know that the application program
will only request of the results, and the table-scan/sort plan
is a cheaper plan for Query 1 in the absence of the STOPAFTER clause. In contrast, the STOP-AFTER approachchooses the unclustered index to obtain the results whenis small, as it has enough information to compare the costsof producing the requested
tuples each way. As a result,
STOP-AFTER performs much better than either of the traditional approaches for most of the range of values, entering
the ballpark of their performance only for ¤+¥¦/  /¢/D/ .
TRADITIONAL and TRAD(NRB) perform similarly until
this region, at which point the cost of client/server communication becomes significant enough to cause TRAD(NRB)
to perform worse than TRADITIONAL.
Lastly, Figure 6 presents the results for Query 1 when
there is no index on Emp.salary. In this case, all three
approaches sort to produce the query’s ordered result set.
STOP-AFTER has the lowest cost here (by about a factor ofthree at §¨ ) because it only sorts therows actuallyof interest to the application program. © In contrast, bothtraditional approaches sort 100,000 rows, making them quite a
bit more expensive. Again, TRAD(NRB) is somewhat slower
than TRADITIONAL due to the cost of shipping the query
result back to the application one row at a time. (In fact, fromthis point on we will stop showing TRAD(NRB) results, as it
consistently lost to TRADITIONAL in the remaining tests.)
5.1.2 Join Queries (Query 2)
Figures 7- 9 show the results for Query 2. This query asks
mostfor the name, salary, and department name of thehighly paid employees, so it is like Query 1 with the additionªResponse Time [s]100Response Time [s]Response Time [s]£100

The DB2 query plan for this simulated STOP AFTER version of Query 1
is a table scan, with the Emp.salary predicate being applied, followed by asort to order the query result; this sort is small, occurring in memory, for small
 . The actual STOP-AFTER query plan would be a table scan followed bya Sort-Stop operation; the Sort-Stop would be an in-memory operation forsmall  , and would require external sorting for larger  . It should be clearthat the overall cost for these two execution plans is essentially the same,
which is what makes this a reasonable simulation.

of a Dept join. Regardless of the availability or type of
Emp.salary index, STOP-AFTER performs much better
than TRADITIONAL. The reason for this is quite simple:
Since the STOP-AFTER plan is chosen based on the valueof , and the join predicate is non-reductive (given the test
database’s integrity constraints), only the firstrows ofEmp are joined with Dept in this plan. Moreover, whenis small, the STOP-AFTER query plan uses the nested-loop
index join method to perform the join, which is cheaper than
the sort-merge join method used in the TRADITIONAL ( insensitive) plan. Sort-merge is the superior strategy for a fullEmp  Dept join, but not for a restricted join; although theDept table can be accessed in dno order using its clusteredindex, the sort-merge query plan still involves sorting the Emp
table on the works in column as well as sorting the join’s
result to produce the results in salary order. The advantageof the STOP-AFTER approach is especially pronounced in
Figures 7 and 8. Here, the STOP-AFTER plan uses the
Emp.salary index to cheaply obtain the most highly paid
employees (by piping the results of an index scan into an
inexpensive Scan-Stop operator); moreover, for small ,where it uses the nested-loop index join method to probe theDept table, no further sorting is needed.
In addition to these results, we also ran tests with noindex on Dept.dno. We observed smaller differences inthose tests, but STOP-AFTER still significantly outperformed
TRADITIONAL. STOP-AFTER was better for small
because its ability to do Stop push-down led to cheaper joins
as well as cheaper sorts; for «/ , for example, STOPAFTER outperformed TRADITIONAL by a factor of two
when an index existed on Emp.salary, and it won by afactor of 1.5 without this index.
5.2 Aggressive Plans: Benefits and Risks
We have seen that STOP AFTER query plans can provide
a large cost savings with respect to traditional query plans
with cursors. But what about Aggressive plans—how muchadditional savings can they provide? And how costly are theestimation errors that may occur? These questions are thefocus of our next tests which are based on Query 3, the 3way join query that asks for the name, salary, department, and

10

100

100
100

1

£

0.1

TRADITIONAL
STOP-AFTER

0.01

0.001

Response Time [s]£10

Response Time [s]Response Time [s]

10

1

£

0.1

TRADITIONAL
STOP-AFTER

0.01

0.001
1

10

100

1000

10000 100000

TRADITIONAL
STOP-AFTER
1

1

10

N

100

1000

10000 100000

N

1

10

100

1000

10000 100000

N

Figure 7: Resp. Time (log), Q2

Figure 8: Resp. Time (log), Q2

Figure 9: Resp. Time (log), Q2

Clustered Index on Emp.salary.

Unclustered Index on Emp.salary.

No Index on Emp.salary.

Trad

Cons

128.3

63.9

preciseAg(1)
6.4

underestimate
Ag(1/5) Ag(1/10)
33.2
63.1

overestimate
Ag(5) Ag(10)
6.7
18.5

Table 1: Resp. Time [s], Q3; No Idx on Emp.salary; ¬­/D/travel expenses of the most highly paid employees.
In the previous tests, the STOP-AFTER results showwhat both the Conservative and Aggressive approach would
produce, as the join predicate used there was non-reductive.
We must distinguish the approaches here, however, as the TEA
join predicate is (potentially) reductive and is thus a barrier
to deep Stop push-down in the Conservative approach. As
shown in Table 1, which contains the cost of Traditional,
Conservative, and Aggressive plans for Query 3 with ®/D/ and no index on Emp.salary, the difference between
the Conservative and Aggressive approaches can be quite
large. If the optimizer’s cardinality estimates are precise(the Ag(1) column in Table 1), Aggressive outperforms
Conservative by a factor of 10 in this experiment. Here, theConservative plan involved a full sort-merge join for Emp 
TEA, followed by a Sort-Stop and a nested-loop index join
to find the matching Dept names. ¯ The Aggressive plan
has a Sort-Stop operator just above the Emp scan, and uses
the nested-loop index join method for both joins; it therefore
avoids sorting the whole Emp table. The Traditional plan issignificantly worse than both Stop-enhanced approaches; ituses two sort-merge joins and thus sorts the whole Emp table
three times (twice for the joins and once to produce the final
query result in the right order).
Table 1 also shows the cost of Aggressive plans if the
cardinality estimates are too low or too high. If the optimizer
underestimates the “precise” stopping cardinality by a factor
of T (the Ag(1/ T ) numbers), then T restarts are required to
produce the full query result. In this case, restarts are very
expensive, as each one requires re-scanning the Emp table.
As a result, the Ag(1/5) plan is about 5 times, and Ag(1/10)
about 10 times, as expensive as the Ag(1) plan. Both Ag(1/5)
and Ag(1/10) are still better than, or at least as good as, the°10

An alternative Conservative plan with slightly lower cost would completely sort the Emp table and then do two nested loop index joins; we could
not model this plan with our DB2 simulation approach.

Conservative and Traditional plans for ±²`/¢/ . However,for large (not shown in Table 1), when the potential benefitsof Aggressive Stop push-down decrease, the cost of Ag(1/5)
and Ag(1/10) can exceed those of Conservative and even
Traditional plans by up to a factor of two in the extreme case( ³N`/¢/  /¢/D/ ).
If the optimizer overestimates the “precise” stopping cardinality (the Ag( T ) numbers), an Aggressive plan carries more
Emp tuples than necessary until the final Stop; this requires
no restarts, but means that too much work is done in the
Join and Stop operators. In this experiment, the extra work
is fairly cheap, so the performance degradation is moderate
and the Ag(5) and Ag(10) plans outperform the Traditionaland Conservative plans. In general, even for large N, overestimated Aggressive plans never become worse than Conservative plans—they have, at worst, the same performance. This
does not make it wise to always overestimate the stopping cardinality of Aggressive Stops, however. We also conducted
experiments with Query 3 and an index on Emp.salary.
Restarts were cheap in this case (since the whole Emp tableneed not be re-scanned), while extra work was relatively expensive if the index was unclustered, so underestimation outperformed overestimation.
6 Related Work
Many commercial relational database systems allow applications to pass a hint to the optimizer to indicate that they would
like the first few tuples of the query result to be produced
quickly. For example, Oracle
7 has an optimization optioncalled FIRST ROWS [A 92], and IBM’s DB2 system offers an OPTIMIZE FOR N ROWS clause [IBM95]. The details of how (or how well) these features are implemented has
not been published, but according to their reference manuals,
they heuristically bias the query optimizer to more heavily favor pipelined execution plans. We experimented with DB2’s
OPTIMIZE FOR N ROWS construct. Its plans were as efficient as our Stop plans for single-table queries when an index
existed on the query’s ORDER BY column; when no such index existed (so no fully pipelined plan existed), or when thequery was complex (making fully pipelined plans inefficient),
our Stop plans performed much better.

11

Other SQL extensions related to our STOP AFTER clausehave recently been proposed for decision support and multimedia queries. [KS95] proposes specifying cardinality limitsby having “rank(. . . ) &´ ” predicates in the WHERE clauseof the query. Conceptually, the rank function and the corresponding query predicates are evaluated after all other predicates, joins, and aggregations have been computed; the paper
does not discuss how cardinality limits can be exploited earlier
to reduce join and sorting costs. [CG96] proposes an ORDER
BY [N] clause that is similar to (though less powerful than)our STOP AFTER clause. The paper does discuss the implications of the new clause on query processing, but focuses on
dealing with the limited query interfaces of multimedia data
sources (e.g., joins are not addressed) and their execution costfeatures (e.g., expensive predicates and ranking expressions);
as a result, their optimization framework and query processing
techniques are very different than ours.
Related work on relational query processing has concentrated on developing pipelined join methods or cost models
that can predict the cost to obtain the first row of a query’s
result set (see [G 92, WA91, BM96], among others). To ourknowledge, none has proposed a Stop operator or studied how
to achieve deep Stop pushdown for STOP AFTER queries.
7 Conclusions
We have examined the opportunities and query processing
issues raised by adding a STOP AFTER clause to SQL’s
SELECT statement. We discussed how STOP AFTER support can be added to an existing DBMS, encapsulating thedetails of STOP AFTER queries by adding Stop operators to
its query execution system. Doing so makes it unnecessary
to change the rest of the system’s query execution engine; its
existing operators for scan, join, and so on are unaffected. We
discussed how to implement the Stop operator physically, describing Scan-Stop and Sort-Stop realizations of this operator
and their costs. Finally, we proposed and empirically evaluated two policies for STOP AFTER plan generation, Conservative and Aggressive, and explained how they can be realized
in a rule-based query optimizer. The Conservative approach
only permits Stop operators to be positioned at plan points
where they are sure not to eliminate tuples that should ultimately participate in the query result; in contrast, the Aggressive approach is more adventurous, using required cardinality
estimation to aggressively limit intermediate result sizes.
We used a synthetic database and query translation scheme
to “simulate” our two approaches on DB2, comparing themto each other and to the traditional “just use a cursor” approach. We saw that, as anticipated, orders-of-magnitude
performance gains can be achieved. The benefits of specialized STOP AFTER handling were seen to be particularly pronounced when an index is available on the query’s ORDER
BY column(s). The Conservative approach always provided
superior performance with respect to the traditional approach;
the Aggressive approach was shown to offer further improvements at the price of introducing some sensitivity to cardinal-

ity estimation errors.
In terms of future work, we plan to implement STOPAFTER in the Garlic system [C 95] at IBM Almaden. On
the optimizer side, we also plan to explore techniques forhandling complex STOP AFTER clauses (with subqueries
that share common subexpressions with the query body) andfor pushing Stop operators down into queries with multiple
query blocks. On the runtime system side, we plan todesign a more efficient external Sort-Stop operator and to
explore join methods to handle STOP AFTER queries withmulti-table ORDER BY expressions (drawing on Fagin’s µ·¶
work [Fag96] in the join case).
Acknowledgments We would like to thank Eugene Shekita
for reading through the paper and making several very helpful
suggestions. Manish Arya helped with the DB2 installation.
References[A ¸ 92] E. Armstrong, et al. ORACLE7 server – application
developer’s guide, Oracle Corporation, 1992.
[BM96] R. Bayardo and D. Miranker. Processing queries for the
first few answers, Proc. 3rd CIKM Conf., Rockville, MD, 1996.
[C ¸ 95] M. Carey et al. Towards heterogeneous multimedia information systems, Proc. IEEE RIDE Workshop, Taipei, Taiwan,
1995.
[CG96] S. Chaudhuri and L. Gravano. Optimizing queries overmulitmedia repositories, Proc. ACM SIGMOD Conf., Montreal,
Canada, 1996.
[CS94] S. Chaudhuri and K. Shim. Including group-by in query
optimization, Proc. 20th VLDB Conf., Santiago, Chile, 1994.
[Fag96] R. Fagin. Combining fuzzy information from multiple
systems, Proc. ACM PODS Conf., Montreal, Canada, 1996.
[GD87] G. Graefe and D. J. DeWitt. The EXODUS optimizer
generator, Proc. ACM SIGMOD Conf., San Francisco, CA, 1987.
[G ¸ 92] S. Ganguly, et al. Query optimization for parallel execution,
Proc. ACM SIGMOD Conf., San Diego, CA, 1992.
[IBM95] IBM Corporation. DB2 application programming guidefor common servers (version 2), 1995.
[Knu73] D. E. Knuth. The Art of Computer Programming/Sorting
and Searching, volume 3, Addison-Wesley, 1973.
[KS95] R. Kimball and K. Strehlo. Why decision support fails andhow to fix it, SIGMOD Record, 24(3):92–97, 1995.
[Loh88] G. Lohman. Grammar-like functional rules for representing
query optimization alternatives, Proc. ACM SIGMOD Conf.,
Chicago, IL, 1988.
[MS93] J. Melton and A. Simon. Understanding the new SQL: acomplete Guide, Morgan-Kaufmann Publishers, Inc., 1993.
[S ¸ 79] P. Selinger, et al. Access path selection in a relational database management system, Proc. ACM SIGMOD Conf., Boston,MA, 1979.
[S ¸ 96] D. Simmen, et al. Fundamental techniques for order
optimization, Proc. ACM SIGMOD Conf., Montreal, Canada,
1996.
[Sto96] M. Stonebraker. Object-Relational DBMSs: The Next Great
Wave, Morgan Kaufmann Publishers, Inc., 1996.
[WA91] A. Wilshut and P. Apers. Dataflow query execution in aparallel main memory, Proc. 1st PDIS Conf., Miami, FL, 1991.

12