The Advancing Art of Indexing - High-Performance Web Databases: Design, Development, and Deployment - page 645

Inverted indexing can provide greater functionality with just five indexes
defined. Multidimensional data bases attempt to address multiple column,
high-performance querying, but they have met maximum dimension con-
straints (up to 10 dimensions) and require additional maintenance (both
design and star-schema management).

Inverted indexing allows the indexing of columns
from more than one table or file to be combined into a single index. This
“prejoining” of the indexes yields fast, optimized cross-table joins for
searches that span more than one table.

Prejoined Indexes.

For example, users could search for all the customers in a particular city
and state (from CUSTOMERS table) who ordered a particular product
(from PRODUCT table) within a date range (from ORDERS table). The inter-
section is performed at the index level, rather than incurring the overhead
of large table joins and excessive data I/O.

Because each index in an RDBMS is separate and cannot be prejoined,
cross-table joins are notoriously slow, especially on large tables. The best
the user can do is key the desired columns in both tables and the common
column. Even then, the data is intersected by doing a keyed read on one ta-
ble, joining to the second table, reading all the related rows, and selecting
the rows that meet the second criteria. The alternative is to do a parallel
sort and merge. The method the optimizer chooses, however, may not be
the most efficient.

Some relational data bases try to make retrievals faster by allowing clus-
tered indexes or data clusters, which refers to the physical placement of re-
lated rows contiguously on disk. This approach reduces the amount of I/O
to read the rows, but the fact remains that more rows are read than meet
all the selection criteria. Inverted index retrievals remain the more efficient
and flexible option.

With inverted file indexing, users can com-
bine various operations to define their search criteria. These operations in-
clude relational logic (equal to, less than, greater than), Boolean logic
(AND, NOT, OR), and ranges (TO). In addition, a “sounds-like” feature (also
known as Soundex) allows phonetic searches on data. Commonly used for
name searches, a phonetic search allows users to find, for example,
“SMITH” even when spelled “SMYTHE.”

Various Search Operations.

Users can easily carry these operations across keyword indexes, in one
or more tables, to access data across the enterprise without concern of
data navigation or performance constraints.

RDBMSs support most of these operations, except a sounds-like func-
tionality. Still, the more complex the users' criteria, the greater the expo-
sure to poor performance.