An Efficient Method for Performing Record Deletions
and Updates Using Index Scans
C. Mohan
IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120, USA
http ://www. al mad en. ibm.
We present a method for efficiently performing
deletions and updates of records when the records
to be deleted or updated are chosen by a range
scan on an index. The traditional method involves
numerous unnecessary lock calls and traversals of
the index from root to leaves, especially when the
qualifying records' keys span more than one leaf
page of the index. Customers have suffered
performance losses from these inefficiencies and
have complained about them. Our goal was to
minimize the number of interactions with the lock
manager, and the number of page fixes,
comparison operations and, possibly, I/Os. Some
of our improvements come from increased synergy
between the query planning and data manager
components of a DBMS. Our patented method has
been implemented in DB2 V7 to address specific
customer requirements. It has also been done to
improve performance on the TPC-H benchmark.
1. Introduction
Relational database management systems
utilize B+-tree indexes [BaMc72] very otlen to efficiently
identify a set of records with certain characteristics. The
CPU cost of performing a root-to-leaf traversal in an
index tends to be very high since a binary search is done
at every level of the tree. We would like to avoid
traversals as much as possible by performing range scans
Permission to copy without fee all or part of this material
is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and its
date appear, and notice is given that copying is by
permission of the Very Large Data Base Endowment. To
copy otherwise, or to republish, requires a fee and~or
special permission from the Endowment
Proceedings of the
28 th
VLDB Conference,
Hong Kong, China, 2002
at the leaf level. Here, we illustrate how traditionally
RDBMSs have not been that efficient during certain types
of index accesses. We present a method to improve that
The query processing (optimization and execution)
research community is yet to recognize the need for the
query processing component (let us call it
data system), following the System R terminology) to be
conscious of concurrency control implications of its
actions. In [Moha92], we argued in favor of increased
synergy between the RDS and data manager (DM)
components by giving specific examples where both
correctness of query executions and/or performance were
impacted. This paper, in the process of describing an
efficient method to perform record deletions and updates
via index scans, provides another illustration of the
benefits of such increased synergy.
The rest of the paper is organized as follows. Before
discussing, in section 2, the problem that we are solving,
in the rest of this section, we give a brief introduction to
the relevant aspects of query processing and index
locking. In section 3, we describe our method for
efficiently performing record deletions via an index scan.
In section 4, we discuss extensions of our method to
handling record updates. We conclude with section 5.
Query Processing
RDBMSs implement the concept of a cursor. A
a construct (an iterator) used to scan and process a set of
data (records/keys/tuples satisfying certain conditions),
one at a time. RDBMSs implement two types of cursors:
user cursors and system cursors. A
user cursor
corresponds to a cursor defined in a user application using
an SQL DCL CURSOR statement.
System cursors
are the
ones that the RDBMS defines and uses internally to
access the tables whose data is needed to satisfy, users'
queries. One or more system cursors might be used to
produce the output corresponding to a single user cursor.
An example of a situation when a single user cursor might
be implemented using multiple system cursors is one

Get Proceedings 2002 VLDB Conference now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.