Using a Relational Database for an Inverted Text IndexN3Labs - Full-Text Search Technology Document Archive The document shown below has been authored by those indicated. [home] [doclist]
Document Body Page Navigation Panel
Page 1 2 Using a Relational Database for an Inverted Text Index Steve Putz Xerox Palo Alto Research Center
Copyright January 1991 Xerox Corporation. All rights reserved. System Sciences Laboratory Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304
[P91-00158] SSL-91-20 1 1 Page 2 3 2 2 Page 3 4 1 Using a Relational Database for an Inverted Text Index Steve Putz Xerox Palo Alto Research Center
Abstract Inverted indices for free-text search are commonly stored and updated using B-Trees. This paper shows how to efficiently maintain a dynamic inverted index for rapidly evolving text document sets using a suitable SQL-based relational database management system. Using a relational system pro-vides performance and reliability features such as efficient index access and maintenance, caching, multi-user transactions, access control, back-up and error recovery.
Table of Contents 1.0 Introduction.................................................................................................. 2 2.0 Inverted Index Storage Optimizations ......................................................... 2 3.0 Relational System Requirements ................................................................. 4 4.0 Structure of the Relational Database Tables ................................................ 4 4.1 Structure of the Postings Table ............................................................................. 5 4.2 Specifying the SQL Table and Index .................................................................... 7 4.3 Using Separate Word and Postings Tables............................................................ 7
5.0 Using the Inverted Index.............................................................................. 8 5.1 Retrieval of Postings............................................................................................. 9 5.2 Retrieval from Separate Word and Postings Tables.............................................. 9 5.3 Retrieval with a Limited Document Identifier Range......................................... 10
6.0 Insertion of Postings .................................................................................. 11 6.1 Update Optimizations ......................................................................................... 11 6.2 Appending to Existing Postings Lists................................................................. 11 6.3 Removal of Postings ........................................................................................... 11
7.0 Sybase Implementation Statistics .............................................................. 12 7.1 Space Used.......................................................................................................... 12 7.2 Indexing Speed ................................................................................................... 13 7.3 Search Speed....................................................................................................... 13
8.0 Conclusion ................................................................................................. 14 9.0 References.................................................................................................. 14 3 3 Page 4 5 2 Using a Relational Database for an Inverted Text Index 1.0 Introduction Efficient implementations of free-text search algorithms often require an inverted index. An inverted index is a data structure that maps a search key (e. g. a word) to a postings list enumerating documents containing the key. It is often useful for the postings list to also include the locations of each word occurrence within each document. An index of this type allows efficient implementation of boolean, extended boolean, proximity and relevance search algorithms [5].
Because it allows efficient insertion, lookup and deletion, the file-based B-Tree data structure is useful for implement-ing a large dynamically updated inverted index [1]. Cutting and Pedersen have developed several space and time op-timizations for efficiently maintaining an inverted index using a B-Tree and a heap file [2]. Unfortunately good B-Tree packages are not generally available for most computer languages and operating systems, and implementation of efficient and reliable B-Tree software is difficult. The algorithms for B-Tree insertion and deletion can be complex and difficult to debug, especially for B-Trees with variable length records. Adding the capability for multi-user trans-actions and error recovery is even more difficult.
A relational database management system is a kind of general purpose database system that represents data as the contents of one or more tables. Relational systems typically use B-Trees to maintain indices on the contents of the da-tabase tables. The tables can be searched in a wide variety of ways using a general purpose query language such as SQL [6]. Several relational systems are commercially available on a wide variety of computer hardware and operat-ing systems. Many relational systems have excellent performance and reliability, and they provide valuable features such as distributed database access, multi-user transactions, access control, back-up, and error recovery. Many have application programming interfaces that allow convenient integration of database access into computer programs.
Although relational systems can maintain indices on the contents of database tables, they are not directly suitable for free-text search of large document sets. Many relational systems cannot store large (or even small) text documents, and the relational systems that can store large documents do not provide for efficient searching of them. However a full-text information retrieval system can be built using the database tables in a suitable relational system as a B-Tree-like database structure, eliminating the need for separate B-Tree software and gaining the performance, robustness and additional features provided by the relational system.
The methods described in this paper will not turn a relational system by itself into a text retrieval system. Rather the relational system serves as an efficient and robust data storage and retrieval system upon which text indexing and re-trieval application programs can be built. In situations where a good B-Tree package is available, its use (with the op-timizations described in section 2.0) may be more appropriate than using a relational system. Most of the text indexing and search algorithms described in this paper can be applied to implementations using either a B-Tree pack-age or relational system.
2.0 Inverted Index Storage Optimizations Cutting and Pedersen have developed several space and time optimizations for maintaining an inverted text index us-ing a B-Tree and a heap file [2]. These optimizations can be adapted for implementation with a suitable relational sys-tem. Cutting and Pedersen use a B-Tree to store a short postings list for each indexed word as shown in Figure 1. When a postings list becomes too large for the B-Tree (e. g. more than 16 postings), portions of it are pulsed to a sep-arate heap file. The heap is a binary memory file with contiguous chunks allocated as necessary for the overflow post-ings lists. For very long postings lists (several hundred postings), heap chunks are linked together with pointers. Heap management software handles allocation and deallocation and keeps track of deallocated chunks for reuse. 4 4 Page 5 6 2.0 Inverted Index Storage Optimizations 3 Figure 1. An Inverted Index using a B-Tree and Heap
Cutting and Pedersen use several techniques to minimize the space required for storing postings lists. A word‘s post-ings list is encoded as a list of integer document identifier and word frequency pairs, followed by a list of integer word positions for each document as shown in Figure 2.
Figure 2. Postings List Encoding Example
Document identifiers (after the first) within a document list are delta encoded as a difference from the previous iden-tifier. For example, the sequence of document identifiers (515, 676, 786, 881) becomes (515, 161, 110, 95) when delta encoded. Word positions within a document are also delta encoded.
The integer values are each byte encoded using a variable-length format such that small values require less storage space than large values as shown in Table 1. The high bit of each encoded byte indicates whether additional bytes fol-low. The low seven bits of each byte encode a portion of the integer with least significant bytes first.
Table 1. Space Required to Store Integer Values min value max value bits encoded bytes required 0 127 7 1 128 16383 14 2 16384 2097151 21 3 2097152 268435455 28 4
Table 2 shows a sequence of document identifiers along with their delta encodings and variable length byte encod-ings. The byte values are shown in hexadecimal notation.
Heap file B-Tree word postings list word postings list postings list postings list
with delta encoding: with variable length
integer values:
byte encoding (hex):
document list positions list 12 515 1 D161 3 2 D17 D10 0C 83, 04 01 A1, 01 03 02 11 0A
doc A 12 doc A freq 515 1 doc B freq 676 3 doc B 2 doc B 19 doc B 29 doc A doc B id id pos pos pos pos 5 5 Page 6 7 4 Using a Relational Database for an Inverted Text Index Table 2. Byte and Delta Encoded Document Identifiers identifier encoding (hex) Did encoding (hex) doc A 515 83, 04 515 83, 04 doc B 676 A4, 05 161 A1, 01 doc C 786 92, 06 110 6E doc D 881 F1, 06 95 5F doc E 1150 FE, 08 269 8D, 02 doc F 1182 9E, 09 32 20
3.0 Relational System Requirements Cutting and Pedersen‘s encoding for postings lists can be adapted for use with relational systems that have an applica-tions programming interface and provide an efficient variable length binary data type capable of storing values up to approximately 250 bytes long. 1 The performance and space efficiency of the resulting text retrieval system depend on various properties of the relational system. For example, space efficiency will be very poor using a relational system that consumes a fixed amount of memory for every table value regardless of the value lengths. The methods described in this paper have been implemented and tested using the SQL Server database management system available from Sybase Incorporated using application programs written in the C programming language. 2
In order to use a relational system to implement an efficient inverted text index, several algorithms must be imple-mented in application programs. The application programs are necessary to encode, decode and manipulate the post-ings lists stored in the relational system. The Sybase DB Library is a set of programming language routines and macros that allow an application program to interact with the SQL Server [4].
The Sybase SQL Server supports Transact-SQL, an enhanced version of the SQL relational database language [3]. Transact-SQL provides a variable length character data type called "varchar" and a variable length binary data type called "varbinary." These data types can store values from 1 to 255 bytes long. For a large index it is important that the storage space used by these data types is the actual lengths of the stored values, not the maximum length.
The amount of storage space required to store an inverted text index in a relational system using these methods can vary widely depending on the relational system used and other factors such as the choice of non indexed "drop words." In experiments with the Sybase SQL Server and a list of 72 drop words, the index size tends to be between 30% and 50% of the size of the original documents for document sets between 10 and 64 million bytes.
4.0 Structure of the Relational Database Tables It is possible to store the postings lists of an inverted text index as rows in a relational database table rather than using a B-Tree and heap file as described in section 2.0. When an appropriate SQL index is created for the table, the SQL Server provides the same search and update capabilities as the B-Tree implementation (in fact the SQL Server creates a B-Tree to accomplish this).
1. A character data type can be used if character values are allowed to contain any of the 8-bit character codes from 0 through 255. Although many relational systems provide separate data types for storing long character or binary data strings, the methods described in this paper do not require them. Note that special long data types provided by some relational systems may be inefficient when used to store small or medium size data strings.
2. SYBASE, SQL Server, Transact-SQL, and DB-Library are trademarks of Sybase Inc. 6 6 Page 7 8 4.0 Structure of the Relational Database Tables 5 Rather than allowing postings lists of arbitrary length or linking postings lists together with pointers, long postings lists are split into pieces no longer than 255 bytes and stored in adjacent database table rows. Since most words in a full text inverted index occur relatively infrequently, most postings lists are short and a single table row per word is sufficient to contain the postings for most words. Depending on the document set size, about 5% of the words will re-quire two or more table rows to store all the postings. In a large document set, some words may require a hundred or more table rows for their postings.
4.1 Structure of the Postings Table An inverted text index can be efficiently stored using a single relational database table with the record structure shown in Table 3. The table‘s word column contains an indexed word or other key. When a word‘s postings do not fit in a single postings block, multiple rows will contain the same word, each with a block value containing a portion of the complete postings.
Table 3. Columns for Combined Word and Postings Table column name data type bytes description word varchar ?100 contains an indexed word firstdoc integer 4 contains the lowest document id referenced in the block flags tinyint 1 indicates the block type, length of doc list and/ or sequence number block varbinary ?255 contains encoded document and/ or position postings for the word
The firstdoc column contains the lowest document identifier for which postings are contained in the corresponding block value.
There are three types of block encodings which are distinguished by the value stored in the flags column: When 0 < flags < 128, the block value contains a the complete encoded postings list as described in section 2.0. The flags value contains the number of document/ frequency pairs in the document list. With this block type the positions list is never split; it is always contained entirely in the block. Figure 3 shows the column values for the example from section 2.0.
Figure 3. Postings Example Using a Single Table Row (0 < flags < 128)
When flags = 0, the block contains only a document list, encoded as described in section 2.0. The number of identifi-er/ frequency pairs in the document list can be inferred from the length of the block. Any row with flags = 0 must be immediately followed by a positions list row with the same word and firstdoc values and have a flags value = 128.
block apple
document list (hex) positions list (hex)
word firstdoc flags 515 2 doc A
0C
doc A 83, 04 01 doc B A1, 01 03 doc B 02 doc B 11 doc B 0A doc A doc B pos id freq Did freq pos Dpos Dpos
(515 encodes as 83, 04) 7 7 Page 8 9 6 Using a Relational Database for an Inverted Text Index Figure 4. Postings Example Using Two Table Rows (flags = 0 and flags = 128)
When flags 128, the block contains only a positions list, encoded as described in section 2.0. A row with flags 128 is always associated with the document list from a previous row with flags = 0. Figure 4 shows the relationship be-tween the document list encoded in one row and the positions list encoded in the following row.
When a document list becomes too long to encode within a single block, it is split and additional database rows are used. The corresponding positions list is also split. If they are small enough, the remaining portions of the document list and positions list can be combined into a new third row (with 0 < flags < 128). Otherwise two new rows are creat-ed, one with flags = 0 for the left over documents list and the other with flags = 128 for the corresponding positions list.
For example, assuming the maximum block size is 12 bytes (rather than 255), adding new postings to the example of Figure 4 would require the creation of a new row as shown in Figure 5. The rows shown in Figure 4 would remain un-changed.
Figure 5. Added Table Row after a Document List Overflow
When a positions list overflows, its block is split, but the corresponding document list block is not split. A document list may refer to postings in several consecutive table rows. These continuation rows are given a firstdoc value equal to the document identifier in effect where the split occurred in the positions list.
The flags value of a continuation row is set to 128 unless the firstdoc value is the same as that of the previous row, in which case the flags value is set to the previous row‘s flags value plus one. This is necessary to guarantee unambigu-ous ordering of the continuation blocks. An example of continuation rows is given in Figure 6.
block box doc C
6E
doc A 83, 04 01 doc B A1, 01 02 doc C 02 doc D 5F doc D 03 doc A doc B word firstdoc flags
515 0
document list (hex):
box doc C 07
doc A 1F B1, 02 doc B 6B 42 doc D 91, 01 doc D 32 doc D 0E doc B doc C 515 128
positions list (hex): Dpos pos pos Dpos pos pos Dpos Dpos
Did id freq Did freq freq Did freq (515 encodes as 83, 04)
block box word firstdoc flags 1150 2
(1150 encodes as FE, 08) document list (hex) positions list (hex)
doc E 55 doc E FE, 08 02 doc F 20 01 doc E 62 doc F 11 doc E doc F pos id freq Did freq Dpos pos 8 8 Page 9 10 4.0 Structure of the Relational Database Tables 7 Figure 6. Postings Example Using Continuation Rows
4.2 Specifying the SQL Table and Index In order to get efficient access to information in a large relational database table, the relational system must be in-structed to create an index. The following SQL commands create an empty postings table called "postings" and build an appropriate index for it.
CREATE TABLE postings (word varchar( 100) NOT NULL, firstdoc int NOT NULL, flags tinyint NOT NULL, block varchar( 255) NOT NULL) CREATE CLUSTERED INDEX clust_ index ON postings (word, firstdoc, flags)
It is essential that the index be on the word, firstdoc, and flags fields in that order. This causes most relational sys-tems to create a B-Tree index using these three fields as the key. When the table rows for a given word are retrieved using the index, they will be enumerated in ascending order of the firstdoc field. Rows with the same firstdoc field will be enumerated in ascending order of the flags field.
Making the index "CLUSTERED" tells the relational system to place the indexed fields directly into the B-Tree, sav-ing a level of indirection. Retrievals will be faster if the index is clustered.
4.3 Using Separate Word and Postings Tables As a variation, the words may be held in a separate table which is joined to the postings table for queries via an inte-ger wordnum key. The separate words table has the advantage of providing a place to store information about each word such as number of occurrences of each word as shown in Table 4.
block crate word firstdoc flags 515 0
document list (hex):
crate doc C D7, 02
doc A 82, 01 72 doc B 9E, 01 BC, 01 doc C 93, 01 doc B doc C 515 128
positions list (hex): Dpos pos pos Dpos pos Dpos
(515 encodes as 83, 04)
crate 786 128 positions list (hex):
crate 786 129 positions list (hex):
(doc C‘s id is 786) doc D 17 doc C DD, 01 5E doc C 6B 42 doc D 2F doc D 36 doc C doc D Dpos Dpos Dpos Dpos pos Dpos Dpos
doc C 89, 02 doc C E3, 02 86, 01 doc C F3, 03 4D doc C 8A, 02 doc C doc C Dpos Dpos Dpos Dpos Dpos Dpos
doc C 6E doc A 83, 04 01 doc B A1, 01 02 doc C 0C doc D 5F doc D 04 doc A doc B Did id freq Did freq freq Did freq 9 9 Page 10 11 8 Using a Relational Database for an Inverted Text Index Table 4. Columns for Separate Word Table column name type bytes description word varchar ?100 contains an indexed word wordnum integer 4 contains a unique word number doc_ count integer 4 optional field for number of documents containing the word word_ count integer 4 optional field for total number of occurrences of the word
The postings table is the same as described in section 4.1 except it has a wordnum column instead of a word column as shown in Table 5.
Table 5. Columns for Separate Postings Table column name type bytes description wordnum integer 4 contains the word number for an indexed word firstdoc integer 4 contain the lowest document id referenced in the block flags tinyint 1 indicates the block type, length of doc list and/ or sequence number block varbinary ?255 contains encoded document and/ or position postings for the word
The following SQL commands creates an empty words table called "wordlist" and postings table called "numpost-ings" and builds an appropriate index for each.
CREATE TABLE wordlist (word varchar( 100) NOT NULL, wordnum integer NOT NULL, doc_ count integer NOT NULL, word_ count integer NOT NULL)
CREATE CLUSTERED INDEX clust_ index ON RH_ word list (word, wordnum, doc_ count, word_ count) CREATE TABLE numpostings (wordnum integer NOT NULL, firstdoc int NOT NULL, flags tinyint NOT NULL, block varchar( 255) NOT NULL)
CREATE CLUSTERED INDEX clust_ index ON numpostings (wordnum, firstdoc, flags) In practice, additional database tables may be used to store other useful information such as document lengths, docu-ment creation dates, and access control information.
5.0 Using the Inverted Index In order to perform a text search operation, an application program must perform several steps. It must retrieve the ta-ble rows containing postings for one or more words and decode the posting blocks. The postings lists from each word are compared or combined as appropriate for the type of text search being performed.
For boolean searches, the document lists for each word are combined using set intersection and union operations. Proximity search algorithms use the word positions information to select just the documents in which the queried 10 10 Page 11 12 5.0 Using the Inverted Index 9 words occur in a particular relationship. In both kinds of searches, the resulting documents can be priority ranked ac-cording to the number of times the queried words occurred, possibly weighted by parameters such as the document lengths and importance of each query word.
5.1 Retrieval of Postings The postings for a given word are retrieved from the relational system using an appropriate SQL query expression. For example, the SQL query below retrieves the rows for the word "box" from the postings table named "postings":
SELECT word, firstdoc, flags, block FROM postings WHERE word = "box" ORDER BY firstdoc, flags
In practice, the "ORDER BY" clause is not required because the rows are already properly ordered in the clustered in-dex. With some relational systems, using "ORDER BY" may impose a performance penalty. The resulting rows are shown in Table 6. The first row contains a document list (flags = 0), the second contains the corresponding word po-sitions (flags ?128), and the third row contains combined document and positions list for the last two documents (flags = 2).
Table 6. Results of Search for Postings of the Word "box" word firstdoc flags block box 515 0 830401A101026E025F03 box 515 128 1FB1026B42079101320E box 1150 2 FE08022001556211
Many text search queries do not require word position information (e. g. simple boolean queries). For these queries, the SQL expression can be modified to retrieve only those rows that contain document lists (i. e. with flags < 128). Also it is not necessary to retrieve the word field, since it is known in advance. The rows retrieved by the following SQL query are shown in Table 7:
SELECT firstdoc, flags, block FROM postings WHERE word = "box" AND flags < 128
Table 7. Results of Search for Document Lists Only firstdoc flags block 515 0 830401A101026E025F03 1150 2 FE08022001556211
5.2 Retrieval from Separate Word and Postings Tables When separate word and postings tables are used as described in section 4.3, the two tables are joined as in the fol-lowing SQL query, which produces the same results as the previous example:
SELECT firstdoc, flags, block FROM wordlist, numpostings WHERE word = "box" AND wordlist. wordnum = numpostings. wordnum AND flags < 128 11 11 Page 12 13 10 Using a Relational Database for an Inverted Text Index 5.3 Retrieval with a Limited Document Identifier Range By specifying a constraint on the firstdoc column, it is possible to construct an SQL query to retrieve word postings that occur within a specified range of document identifiers. This is useful if document identifiers are assigned in a meaningful order, such as by creation or entry date. For example, the following SQL query retrieves only rows con-taining document identifiers between 1160 and 1170:
SELECT firstdoc, flags, block FROM postings WHERE word = "box" AND firstdoc >= (SELECT max (firstdoc) FROM postings WHERE word = "box" AND flags < 128 AND firstdoc <= 1160) AND firstdoc < 1170
Table 8 shows the results of this query. The requested document identifier range falls within the results (along with a few postings outside the range).
Table 8. Results of Search for "box" in Documents 1160 through 1170 firstdoc flags block 1150 2 FE08022001556211
When document identifiers are assigned in date order and the correspondence between identifiers and key dates is stored in another database table, the firstdoc column can be used to implement a date range constraint. For example, the document identifiers associated with key dates can be stored in a two-column table as in Table 9.
Table 9. Example of Date and Document Identifier Correspondence Table date firstdoc 1 Aug 1990 1 1 Sep 1990 480 1 Oct 1990 829 1 Nov 1990 1160 1 Dec 1990 1170 1 Jan 1991 1302
Given such a table named "docdates," the document identifier values "1160" and "1170" in the previous SQL query can be replaced with appropriate SQL sub-queries as shown below to find documents indexed during November 1990:
SELECT firstdoc, flags, block FROM postings WHERE word = "box" AND firstdoc >= (SELECT max (firstdoc) FROM postings WHERE word = "box" AND flags < 128 AND firstdoc <= (SELECT max (firstdoc) FROM docdates WHERE date <= "1 Nov 1990")) AND firstdoc < (SELECT min (firstdoc) FROM docdates WHERE date >= "1 Dec 1990") 12 12 Page 13 14 6.0 Insertion of Postings 11 6.0 Insertion of Postings The inverted index implementation described here is designed so postings from new documents can be efficiently added to the index at any time. A limitation of this implementation is that document identifiers must be added to the index in ascending order.
6.1 Update Optimizations Cutting and Pedersen have developed efficient algorithms for creating and updating an inverted index by buffering a large number of postings lists in main memory and periodically merging them into the externally stored index [2]. This merge update optimization dramatically reduces the number of secondary storage accesses required to index new documents. This optimization is equally important when storing the inverted index in a relational system.
At any given time, the final row( s) containing the document list and positions list for a large number of words should be kept in main memory. Whenever a row‘s block becomes filled (to its maximum of 255 bytes), it is stored into the database and a new empty row begun.
If the relational system‘s application programming interface provides efficient bulk data copy primitives, they should be used for inserting new rows into the database tables.
6.2 Appending to Existing Postings Lists In order to append new postings to those already stored for a word, the table rows containing the last document list and positions list for the word must first be retrieved into main memory. The new postings are appended to the re-trieved lists and the updated table rows eventually stored back to the database.
The following SQL expression retrieves just the rows containing the last document list and positions list for the word "box". The resulting row from the postings table is shown in Table 10.
SELECT firstdoc, flags, block FROM postings WHERE word = "box" AND firstdoc >= (SELECT max (firstdoc) FROM postings WHERE word = "box" AND flags < 128)
The result may either be a single row containing document and positions lists (with 0 ?flags < 128) or multiple rows, the first containing the document list (with flags = 0) and the rest containing the positions lists (with flags 128). Only the last row of positions needs to be kept in main memory.
Table 10. Results of SQL Query to Retrieve Last Document and Positions Lists for the Word "box" firstdoc flags block 1150 2 FE08022001556211
6.3 Removal of Postings The fact that the index is inverted according to individual words makes the removal of a single document inefficient. The technique described in section 5.3 can be used to reduce the number of rows which must be examined looking for the document‘s identifier, but single document removal is still inefficient. Note that removing a range of document identifiers from the index can be done for about the same cost as removing a single document. 13 13 Page 14 15 12 Using a Relational Database for an Inverted Text Index If document removal is infrequent, an auxiliary table can be used to hold the removed document identifiers. Often there is already a table containing an entry for each document. If so, this feature can be added for very little cost.
When it is known in advance what identifier ranges will be removed, the insertion algorithm can be modified to ar-range the database so the range boundaries always occur between rows. This will cause less efficient space utilization, but removing all documents between the range boundaries can then be done with a single SQL expression rather than an exhaustive search of individual word postings.
For example, if the indexing software started new table rows for 1991‘s documents (starting with document identifier 1302), the following SQL expression will remove all document postings from the year 1990 or earlier:
DELETE postings WHERE firstdoc < (SELECT min (firstdoc) FROM docdates WHERE date >= "1 Jan 1991")
7.0 Sybase Implementation Statistics The methods described in this paper have been implemented on a Sun Unix workstation using a Sybase SQL Server. Text indexing and search programs were implemented in the C programming language using the Sybase DB-Library package. The indexing program is 2000 lines long and the boolean text search program is 1200 lines long.
Two electronic encyclopedia databases were used to test the software: The Alphapedia section of the 1990 Random House Encyclopedia (18,000 articles, 126,000 words) and Grolier‘s Academic Encyclopedia (31,000 articles, 780,000 words). An inverted index was created for the words (except for a list of 72 drop words) occurring in each encyclopedia. A separate index was created for the article titles in each encyclopedia, as well as an index for the Ran-dom House article categories.
7.1 Space Used The amount of storage space used by a relational system to store an inverted index depends on the efficiency of its in-ternal data and index storage. For each of the two encyclopedias, Table 11 shows the original text size, the number of indexed words, the number of distinct words, and the number of table rows and space required to encode the inverted index.
Table 11. Size of Full Text Encoded Inverted Indices table name text size words vocabulary rows table size (% text) Sybase-1 Sybase-2 (% text) RH_ word 7856 KB 844753 59141 65334 3632 KB (46%) 6374 KB 4398 KB (56%) GR_ word 63256 KB 5035874 139870 191148 17816 KB (28%) 31142 KB 20908 KB (33%)
Three index sizes are given. The column labeled "table size" is the amount of storage space required using the encod-ings described in this paper, assuming no additional storage or indexing overhead. The column labeled "Sybase-1" is the actual database table size reported by the Sybase SQL Server after the table rows were added to the relational da-tabase by the document indexing program.
It was discovered that for the Sybase SQL Server, 30% less space is required for the same database tables when they are copied using the Sybase bulk database copy program, apparently because the data is then stored more compactly. The column labeled "Sybase-2" shows the reduced amount of space resulting from this technique. It may be possible 14 14 Page 15 16 7.0 Sybase Implementation Statistics 13 to achieve similar space savings in the incremental indexing program by using the available DB-Library bulk copy routines.
The encoding techniques presented here are most efficient for indexing the words of text documents, however the same database structure can also be used for a smaller inverted index of document titles, keywords, or category codes. Table 12 shows the space required to encode inverted indices for the encyclopedia article titles and category codes. Complete article titles were indexed separately from individual title words.
Table 12. Size of Title and Category Encoded Inverted Indices table name text size words vocabulary rows index size (% text) Sybase-1 Sybase-2 (% text) RH_ category 105 KB 17938 55 317 58 KB (55%) 112 KB 80 KB (76%) RH_ titleword 290 KB 34762 17006 17050 392 KB (135%) 766 KB 528 KB (182%) RH_ title 290 KB 17938 17632 17632 456 KB (157%) 892 KB 620 KB (214%) GR_ titleword 590 KB 73899 26170 26396 672 KB (114%) 1292 KB 908 KB (154%) GR_ title 590 KB 30762 30388 30388 880 KB (149%) 1658 KB 1164 KB (197%)
7.2 Indexing Speed Indexing speed depends almost entirely on the speed with which rows can be retrieved and stored into the relational system. Our indexing program was able to create an inverted index for the Random House Encyclopedia in 37 min-utes 1 . This is the equivalent of 380 words per second or about 14 megabytes of text per hour. Due to overhead associ-ated with writing out and later retrieving buffered postings when main memory becomes full, the larger Grolier‘s Encyclopedia was indexed at a rate of 140 words per second (6.4 megabytes of text per hour). Better buffering and the use of bulk copy routines would improve the indexing speed.
7.3 Search Speed Text search speed using the inverted index depends on the speed with which rows can be retrieved from the relational system and the postings lists decoded and combined by the search program. Our boolean text search program per-forms separate SQL queries for each word in the search query, decodes the results and combines the document identi-fier lists using union and intersection operations 2 . The resulting document list is sorted so the documents with the most word matches occur at the head of the list.
Table 13 lists several boolean text search queries performed using the Grolier‘s Encyclopedia index, and the amount of time taken to compute the matching document identifiers. The "%" at the end of a search query term is the SQL wildcard character used to match multiple words with the same prefix (e. g. "newt%" matches "newt," "newton," newtonian," etc.). The "&" character indicates boolean AND operator and the "|" character indicates the OR operator.
For each search, Table 13 lists the number of matching documents, the number of SQL queries required, the number of table rows retrieved, and the total number of document identifiers processed. The column labeled "1st time" indi-cates the number of seconds required for a query that has not been performed recently. Due to caching in the SQL server, immediately repeating the query results in a faster response as shown in the column labeled "2nd time."
The timings shown include the time to construct and perform the SQL queries, decode the results, and combine the document identifier lists from multiple rows, but do not include the time required to initialize the SQL server connec-tion and rank the document lists.
1. Running on a Sun 4/ 490 SPARC processor with 32 megabytes of main memory. 2. Multiple term queries could be made faster by retrieving the postings for all the terms using a single SQL query. 15 15 Page 16 14 Using a Relational Database for an Inverted Text Index Table 13. Boolean Text Search Speed text search query matches queries rows docs 1st time 2nd time xxxxx 0 1 0 0 0.09 0.02 newt 7 1 1 7 0.13 0.02 newt% 205 1 11 205 0.36 0.07 fight 197 1 2 197 0.18 0.06 battle 758 1 7 758 0.11 0.02 california 785 1 7 785 0.11 0.03 general 2235 1 18 2235 0.29 0.07 war 4170 1 34 4170 0.37 0.11 century 5471 1 44 5471 0.37 0.12 war & century 1257 2 78 9641 0.59 0.36 california & war & century 79 3 85 10426 0.89 0.38 fight & battle & california & general & war & century 4 6 112 13616 1.30 0.54 (fight | battle) & california & general & war & century 14 6 112 13616 1.14 0.56
8.0 Conclusion Information retrieval systems often provide full text search using B-Trees and heap files, but reliable high perfor-mance B-Tree software is not available for many computing environments and it is difficult to implement. It is possi-ble to implement an efficient inverted index using database tables in a relational database management system as a substitute for B-Trees and heap files. Using a relational system‘s application programming interface, it is possible to create text indexing and search programs with performance and space efficiency similar to that obtained using a B-Tree package. Available relational systems provide high performance along with valuable features not normally found in a B-Tree package, such as multi-user transactions, access control, reliable back-up, and automatic error re-covery.
9.0 References [1] R. Bayer and E. McCreight. "Organization and Maintenance of Large Ordered Indexes." Acta Informatica, 1: 173?189, 1972.
[2] D. Cutting and J. Pedersen. "Optimizations for Dynamic Inverted Index Maintenance." Proceedings of the 13th International Conference on Research and Development in Information Retrieval, pp. 405?411, September 1990.
[3] M. Darnovsky and J. Bowman. Transact-SQL User‘s Guide, SYBASE Release 4.0, Sybase Inc., May 1989. [4] S. Goodman and A. Cohen. Open Client DB-Library Reference Manual, SYBASE Release 4.0, Sybase Inc., May 1989
[5] G. Salton and M. McGill. Introduction to Modern Information Retrieval. McGraw Hill, 1983. [6] J. H. Trimble, Jr. and D. Chappell. A Visual Introduction to SQL. John Wiley & Sons, 1989. 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|