Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-24
2002-04-16
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06374232
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to efficiently retrieving information from databases.
BACKGROUND OF THE INVENTION
Relational databases store information in indexed tables that are organized into rows and columns. A user retrieves information from the tables by entering a request that is converted to queries by a database application, which then submits the queries to a database server. In response to the queries, the database server accesses the tables specified by the query to determine which information within the tables satisfies the queries. The information that satisfies the queries is then retrieved by the database server and transmitted to the database application and ultimately to the user.
FIG.
2
(
a
) illustrates a logical layout of an exemplary table T (
200
) within a relational database. Table
200
comprises three user columns, column A
204
, column B
206
, and column C
208
, and eleven rows
210
-
230
. Table
200
also contains an internal column or pseudocolumn
202
, referred to as a rowid. A table's rowid is retrievable by query and uniquely identifies a row in the table, but is not normally displayed when the structure of the table is listed. For example, a rowid of
221
uniquely identifies row
210
, which contains the values of 3 in column A
204
,
5
in column B
206
, and 2 in column C
208
. In this example, the values of the columns A
204
, B
206
, and C
208
are integers, but it is to be understood that columns of a database table can hold values of any of a variety of types including floating point numbers and variable length strings of characters.
For any given database application, the queries to retrieve information from a table must conform to the rules of a particular query language. Most query languages provide users with a variety of ways to specify the information to be retrieved. For example, in the Structured Query Language (SQL), the query, select A from T where A<5, requests the retrieval of the information contained in column A of specified rows of table T that satisfies a specified condition. The conditions in the where clause specify one or more predicates, in this example A<5, which must be satisfied by matching rows. In the example, rows
210
,
214
,
216
,
218
,
220
,
226
, and
230
of table T
200
satisfy this query because the corresponding values of column A
204
are
3
,
3
,
2
,
1
,
4
,
2
, and
4
, respectively. On the other hand, rows
212
,
222
,
224
, and
228
of table T
200
do not satisfy this query because the corresponding values of column A
204
are
6
,
5
,
7
, and
8
, respectively.
One approach to access the rows of a table in processing a query is called a “full table scan,” in which a database server fetches every row of the table and inspects every column named in the where clause. FIG.
2
(
b
) illustrates one possible physical layout
200
′ of table T wherein the corresponding row data
210
′-
230
′ is stored in one or more units (or “extents”) of contiguous blocks. A block is the smallest quantity of data that can be read from a persistent store such as a disk into dynamic memory. If a database system requires any information stored in a particular block, the database system must read the entire block into memory. To retrieve values for a particular column of a table, the database system must read all the blocks that have any data from that column of the table. Since values for the column may be present in all or almost all the blocks of a table, the entire base table or significant portion thereof must be read into memory in order to retrieve the column values. This retrieval can be very costly, as the column data itself may be a small percentage of the data stored in the table.
The sizes of the blocks in the examples and figures herein are simplified for purposes of illustration. Typically, however, the size of the blocks is generally from 512 (2
9
) bytes to 16,384 (2
14
) bytes, but the size of the extents are much larger and of any size, e.g. 30 megabytes. Storing row data in contiguous blocks enables the use of efficient multi-block input/output techniques, for example allowing overhead of reading from disk storage, such as seeking to a block, to be pipelined.
Over time, as rows are added and dropped, the physical order of the row data usually does not correspond to the logical order of the rows in the table, if there is a logical order. Accordingly, the order of the row data in the blocks may appear to be random. In the example of FIG.
2
(
b
), the first unit of contiguous blocks (extent
240
′) contains row data
218
′,
228
′,
224
′, and
216
′, and
222
′; the second unit of contiguous blocks (extent
242
′) contains row data
210
′,
212
′,
214
′,
220
′, and
230
′; and the third unit of contiguous blocks (extent
244
′) contain row data
226
′.
In order to process the exemplary query select A from T where A<5, a full table scan reads all of extent
240
′ containing row data
218
′,
228
′,
224
′, and
216
′, and
222
′, all of extent
242
′ containing row data
210
′,
212
′,
214
′,
220
′, and
230
′, and the used portion of extent
244
′ containing row data
226
′. Thus, the full table scan reads the data for all the columns in table T
200
, even though only the information from column A
204
was necessary to process the query. If the amount of the data for the columns not used in the query is very large, then the full table scan methodology becomes very inefficient because of the unnecessary amount of disk input/output.
Accordingly, many database systems provide indexes to increase the speed of the data retrieval process. A database index is conceptually similar to a normal index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied with the location of the information. Values in one or more columns of a table are stored in an index, which is maintained separately from the actual database table.
One implementation of a database index is a B-tree, whose logical layout is illustrated in FIG.
3
(
a
). A B-tree index is a hierarchical arrangement of two types of nodes: leaf nodes and branch nodes. Leaf nodes reside at the lowest level of the B-tree hierarchy and contain values from the actual column or columns upon which the index is built and the rowid of the corresponding rows. Leaf nodes may contain data for many rows, e.g. 100 rows, but, for purposes of example, leaf nodes are illustrated herein as containing a single row. For example, B-tree index
300
, being built upon column A
204
of table T
200
, has leaf nodes
310
-
330
collectively holding the values of column A
204
. Specifically, leaf node
310
holds the value
1
from column A
204
and the rowid
118
, which identifies row
218
of table T
200
. As another example, leaf node
330
contains an index value of 8 from column A
220
and a rowid of
123
, identifying row
228
of table T
200
. Each leaf node contains a pointer or other link to the subsequent leaf node. For example, leaf node
328
, which contains an index value of 7, points to leaf node
330
, which contains an index value of 8.
The non-leaf nodes of a B-tree index are branch nodes. Branch nodes contain information that indicate a range of values. In the illustrated B-tree index
300
, nodes
302
,
304
,
306
, and
308
are branch nodes and therefore each corresponds to a range of values. The range of values indicated by each branch node is such that all nodes that reside below a given branch node correspond to the values that full within the range of values for the given branch node. For example, node
306
is a branch node that corresponds to the numerical range from 4 to 6. Consequently, nodes
320
,
322
,
324
, and
326
, which all reside below node
306
in the hierarchy, correspond to values that fall wi
Dageville Benoit
Ho Alexander Channing
Ozbutin Cetin
Zait Mohammed
Ditthavong & Carlson P.C.
Homere Jean R.
Oracle Corp.
LandOfFree
Method and mechanism for retrieving values from a database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and mechanism for retrieving values from a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for retrieving values from a database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2916517