# 18. Free Text Search

Chapter Contents | Prev | Next
Keyword Search:
www.openlinksw.com
docs.openlinksw.com
Book Home
Contents
Preface
Free Text Search
Basic Concepts
Creating Free Text Indexes
The CREATE TEXT INDEX statement Choosing An Application Specific Document ID The composite Data Type Free Text Index Examples Pre-processing and Extending the Content Being Indexed Hit Scores Word Ranges Using Offband Data for Faster Filtering Order of Hits Noise Words
Querying Free Text Indexes
Text Triggers
Generated Tables and Internals
Removing A Text Index
Removing A Text Trigger
Internationalization & Unicode
Performance
Free Text Functions

## 18.2. Creating Free Text Indexes

### 18.2.1. The CREATE TEXT INDEX statement

Define and optionally initialize a text index on a column.

    create_freetext_index
    	: CREATE TEXT [XML] INDEX ON q_table_name '(' column ')'
    	[WITH KEY column]
    	[NOT INSERT]
    	[CLUSTERED WITH '(' column_commalist ')' ]
    	[USING FUNCTION]
    	[LANGUAGE STRING]
      [ENCODING STRING]
    	;

XML - The XML keyword specifies that the data is to be indexed as XML, hence element names and attributes will be processed separately for use with the XCONTAINS predicate.

The q_table_name is a qualified table name on which the index is created. The generated procedures and auxiliary tables will be with the owner and qualifier of this table.

The column must be a column of the above table, of the VARCHAR, NVARCHAR, LONG VARCHAR, LONG NVARCHAR, LONG XML or XMLTYPE data type. The column may additionally have the IDENTIFIED BY option if the content is XML. This will be used to provide a base URI for traversing relative references. The XML option for the index has to be specified if the content is LONG XML or XMLTYPE.

WITH KEY column - This allows optionally specifying a uniquely identifying column which will be used as a foreign key for referencing the table from the text index. If this is not specified and there is a single part integer primary key, this primary key is used as the key. If there is no suitable primary key and the option is not present, an integer column is added and a sequence object is used to supply distinct values.

When specified, the column must be non-NULL and its run time value must either be an integer or a composite (See composite data type). The length of the values of this column is crucially important since it is repeated for each distinct word of each row. This column is called the free text document id column in the rest of this documentation.

NOT INSERT - If present, specifies that the index is not filled when created. The VT_INDEX_<table> function is still created but not run. You can run this manually or scheduled at an appropriate time. If batching is enabled then the index will be filled up at that time.

CLUSTERED WITH - The column list must consist of columns of the table. Their values are stored in the text index so that the values can be more efficiently located for filtering than if they had to be retrieved from the table itself. The combined length of the columns should be relatively small, not much over 200 bytes for this to be effective. There is no hard upper limit but long blobs are not advisable.

USING FUNCTION - This allows specifying a hook function for indexing an unindexing a document. The index hook is called before processing the words of the column to be indexed. This can be used to index extra text in addition to the column value or to modify the text before indexing. If the hook function returns 1 the column is not additionally processed. If hook returns 0 the column is processed normally, in addition to the words the hook may have inserted. See the section on hook functions. The hook functions are always named <table>_<column>_INDEX_HOOK and <table>_<column>_UNINDEX_HOOK, in the owner and qualifier of the table, where <table> is the unqualified name of the table.

LANGUAGE - The string literal following this keyword may be a language name. See Internationalization for details.

ENCODING - The string literal following this keyword may be an encoding name.

Creating the text index may take a long time. All this time is in 'atomic' mode, so no other database activity is allowed during it and no log is generated. If there is an error, e.g. out of disk the created index is dropped and the error is reported. A checkpoint should be made after the index is complete. If the index should be created under a different qualifier or the generated tables altered after the index is created the NOT INSERT option should be used to delay filling the index.

The CREATE TEXT INDEX statement will automatically make a unique index based on the free text document id, if this is not the PK of the table. If one wishes to modify this index, it can be found and dropped with DROP INDEX and reconstructed, but make sure that the reference in SYS_VT_INDEX matches and that the new index has the same name as the previous version.

A freshly created text index is in synchronous mode. This means that that changes to the table are immediately reflected on the index as they occur. This is done through a set of automatically generated triggers. If large changes to data will be performed, the batch mode is far more efficient.

See Also:

Although it is recommended to use the methods described above, the vt_create_text_index function can also be used

### 18.2.2. Choosing An Application Specific Document ID

The free text index conceptually works by making an index entry for each distinct word of each indexed column value which references back to the row containing the data being indexed. Therefore the table must have a unique ID that will be stored in conjunction with each distinct word in the indexed column in the text index. For space efficiency this should be as short as possible. If nothing else is specified the CREATE TEXT INDEX statement makes such a unique column and fills it automatically from a sequence producing unique numbers. If a single part integer primary key exists then this key is used as the free text index document ID. Note However that the values <= 0 are prohibited. This is however not always optimal, hence the application may specify what column is used to identify the row for text indexing. Such a unique column is referred to as the Free Text Document ID.

Suppose that a table contains news articles that should most frequently be retrieved latest first, in descending order of a datetime field. This can be achieved by just selecting the matching articles and sorting them with a SQL ORDER BY clause but this can be very inefficient. The reason for this is that all hits will first have to be found, then sorted and only then can the first hit be returned to the user. Further, the sort key will have to be retrieved from the table, causing a random access for each text hit. The sorting can be totally avoided if the document ID that is used to refer to the table from the index is itself ordered by date. This has several advantages:

- To retrieve the n latest, one just takes the n first hits produced by the contains search, no sorting required.
- To get the next n hits, one repeats the search but now specifying that the start ID is the ID of the last row of the previous set. No sorting and no scrollable cursors are required and the first hits can be returned before generating all hits. This is specially useful if the search criteria match many articles.

This has a disadvantage in that a longer document ID will have to be stored for each distinct word of each distinct article. This may result in a 60% increase in the index size but largely offsets the penalties of sorting. One should however exercise the utmost care in making this ID as short as possible. The maximum length of the ID is 30 bytes, but with this length the storage is extremely wasteful, so an ID with fields adding up to some 10 bytes is much better.

We will note that the document ID can be an aggregate of several scalars. In the news article example, it could be a datetime, ID number pair. This is so because the datetime typically would not be unique and the ID is required itself to be unique.

However, rather than storing the datetime and an integer article number, it is advisable to compress the datetime into a number, e.g. a count of minutes after a given date. This maintains the temporal order to within a minute and takes less than half the space taken by the datetime with all its fractions, time zones etc.

For handling multi-part ID's like scalars there is a special data type, composite. Thus, if an application specific document ID is not an integer, it must be a composite totalling less than 30 bytes of content divided among its members.

### 18.2.3. The composite Data Type

A composite is like a heterogeneous array, except that it is limited in length, may be stored as a column value for a column declared as ANY, and may be a key part in a SQL index. Thus, comparison is defined for composites as follows:

- Composites are equal if all parts are equal.
- A composite is less than another if the first part of it which is not equal to the corresponding part of the other composite is less than that part.
- If a composite has less parts than another and all of its parts are equal to the corresponding parts of the longer composite, then the shorter is considered less.

The collation of composites is just like that of strings, except that in the place of characters, arbitrary run time typed scalars are compared.

When strings are compared inside composites, they are compared as binary, without any specific collation. Normal numeric coercion applies to comparison of composites. Narrow and wide strings are compared with binary collation. If two elements are of different types, e.g. a number and a string and are compared, the data type will decide the outcome. For example any integer is always less than any string.

The composite SQL function makes a composite. It takes a variable number of arguments and returns a composite. The composite_ref function takes a composite and a zero based index and returns the value. The serialized length of a composite is limited to 255 characters. If a composite is used in a free text index it is limited to 30 characters.

- composite()
- composite_ref()

See Also:

See the Data Types section for the storage requirement of each data type.

### 18.2.4. Free Text Index Examples

    composite (1, 2) = composite (1, 2)  is true
    composite (1, 2) < composite (1, 3) is true.
    composite (1, 0) > composite (1) is true.

    composite_ref (composite (1, 2), 1) = 2

Example of a Composite Application Specific Document ID

The below code creates a table for news articles and defines a text index with a composite document id.

    create table article(author_name varchar(255),
    		     description long varchar,
    		     pub_date datetime,
    		     id integer,
    		     title varchar(255),
    		     dtid any not null,
    		     primary key(id));

    create text index on article (description)
    	with key dtid clustered with (pub_date, author_name);

Note:

The dtid must be unique, non null and must be a composite since it is used as a custom text index id.

Next we define a mapping between dates and integers. These will be minutes consecutive of 1990-1-1 0:00. With 525600 minutes per 365 day year we will not run out of values for a long time, the positive integer limit being 2**31.

    create procedure date2short (in dt datetime)
    {
      return (1440 * datediff ('day', {d'1990-1-1'}, dt)
    	+ hour (dt) * 60 + minute (dt));
    }

    create procedure short2date (in n integer)
    {
      return (dateadd ('minute', mod (n, 1440),
    	dateadd ('day', n / 1440, {d'1990-1-1'})));
    }

Now we can insert an article:

    insert into article (id, drtid, description, pub_date)
    	values (1, composite (date2short ({dt '2001-1-15 12:44'}), 1),
    		'sample news article', {dt '2001-1-15 12:44'});

Note:

The composite is the date2short of the datetime and the id. The dtid must be specified and cannot be generated by a trigger, since the free text index related triggers must have access to the value.

The text index will be in synchronous mode by default so we can now query the data:

    select id from article where contains (description, 'sample');
    select id from article where contains (description, 'sample', descending);

The first query will return the oldest hits first, the second the newest first. Note that inserting in ascending order of the document ID is incomparably more efficient than in descending order. There is no great speed difference between reading in ascending or descending order.

If no application specific ID were specified the order would reflect the insertion order. Note that in this example articles do not have to be received in publication order, although insertions will naturally tend to follow this.

Now since the ID has an application semantic, we can use it for filtering based on date:

Consider:

    select id from article where contains (description, 'sample', descending,
    	start_id, composite (date2short ({dt'2001-1-5'})));

Since the search goes in descending order of id and starts at an id beginning with the numeric value corresponding to 2001-1-5 0:00, we may only get hits where the id date component is less than this, newest first.

There is no time penalty for the start_id option. This is therefore incomparably faster than the query:

    select id from article where contains (description, 'sample', descending)
    and pub_date < {dt '2001-1-5'};

See Also:

The reference section for contains for a definition of these options.

### 18.2.5. Pre-processing and Extending the Content Being Indexed

Let us consider the news application. Assume now a many to many relationship between articles and numbered news channels.

    create table article_channel (
    	a_id integer references article,
    	c_id integer,
    	primary key (a_id, c_id);

Assume further that free text search criteria be combined to channel membership tests.

This could be expressed as follows

    select * from article
    	where contains (description, 'sample')
    	and exists
    		(select 1 from article_channel
    		where a_id = id and c_id = ?);

We have a random access per each hit to a table with at least the population of the article table for each hit. The situation is yet worse if there is an OR of multiple channel id's to which the article may belong.

To optimize this, we may choose to add an extra word for each channel in which the article appears. Likewise, we may add the text of the title of the article to the text being index.

This can be done with the index hook feature.

    create text index on article (description)
    	with key dtid clustered with (pub_date, author_name)
    	using function ;

We then define the hook functions

    create procedure
    	article_description_index_hook (inout vtb any, inout d_id any)
    {
      for (select c_id from article_channel
    	where a_id = composite_ref (d_id, 0))
      do
        {
          vt_batch_feed (vtb, sprintf ('ch%d', c_id), 0);
        }
      vt_batch_feed (vtb, coalesce ((select title from article
    	where dtid = d_id), ''), 0);
      return 0;
    }

This function gets all channel id's where the article appears and adds the word ch<nnnn> where <nnnnn> is the channel id. Thus to look for 'xx' on channel 1 or 10 one can use the text expression xx and (ch1 or ch10). Additionally, the text of the title is added to the text being indexed. Note that the d_id supplied is the free text document id and that the second part of it is the article id.

To reverse the effect, the unindex function works as follows:

    create procedure
    	article_description_unindex_hook (inout vtb any, inout d_id any)
    {
      for (select c_id from article_channel
    	where a_id = composite_ref (d_id, 0))
      do
        {
          vt_batch_feed (vtb, sprintf ('ch%d', c_id), 1);
        }
      vt_batch_feed (vtb, coalesce ((select title
    	from article where dtid = d_id), ''), 1);
      return 0;
    }

These hooks accept 2 inout parameters, the so called vt batch and the free text document ID of the row at hand.

The function returns 1 to indicate that it has processed all words of the row to be indexed and 0 to indicate that it expects the default text to be processed by the caller as normally. Returning 1 is useful for example if extra word normalization is applied by the hook.

If the resulting index is used by xcontains() special predicate then hook functions should not alter the indexing of XML documents. xcontains() reads both free-text index and the actual document in order to locate particular fragments and it may miss search hits or get false hits if free-text index of a column does not match to the actual content of the column. It is still safe to call vt_batch_feed more than once during a single call of a hook function: first call for an unmodified XML document in the column plus calls for additional data.

If offband columns are declared then any call of a hook function should either return 0 or call vt_batch_feed_offband() before returning a non-zero value. If this condition is violated for a document then NULL is retured instead of correct offband value for the document without signalling any error.

The vt batch is an opaque data structure that accumulates words that will be added to the text index entry for a given row. The vt_batch_feed function adds words to the batch, the first argument is the vt batch, the second is the text and the third is a flag 0 for insert and 1 for delete. The text to be associated to the d_id in the index is the concatenation of all the text supplied by successive calls to vt_batch_feed. Word proximity is defined as if all text were a single string in the order of calling vt_batch_feed.

It is possible to partially alter the rtext associated with an existing document. This could be done when adding channels to an article which already exists. This could be done with the procedure:

    create procedure
    	ch_add_article (in cid integer, in aid integer)
    {
      declare vtb, _dtid, cname any;
      if (exists (select 1 from article_channel
    	where c_id = cid and a_id = aid))
        return;

      insert into article_channel (c_id, a_id) values (cid, aid);
      select dtid into _dtid from article where id = aid;

      vtb := vt_batch (1);
      vt_batch_d_id (vtb, _dtid);
      vt_batch_feed (vtb, sprintf ('ch%d', cid), 0);
      vt_batch_process_db_dba_article (vtb);
    }

This first checks if the article is already on the channel, and if not, it makes a vt batch, gets the free text document id of the article, associates it to the vt batch and then adds a single word, ch<nnnn>. The vt batch is applied by calling the generated procedure vt_batch_process_<table>_<column> with the vt batch as only argument.

If multiple documents should be processed in one batch, it is possible to call vt_batch_d_id multiple times to feed data about multiple documents. In this case the successive document ids must be given in ascending order. The batch can be processed (applied to the words table) by calling T_BATCH_PROCESS_<table>_<column>, generated by the index creation.

The sensitive columns of the UPDATE trigger generated are the free text document id, the CLUSTERED WITH columns and the main text column. If more columns are needed for hook functions etc., the triggers should be manually edited.

If an explicit integer document ID column is specified, its value may not be 0 or negative.

See Also

vt_batch, vt_batch_feed, vt_batch_feed_offband, vt_batch_d_id.

### 18.2.6. Hit Scores

When a document satisfies a text search expression a score is computed to reflect the closeness of the match. This is a positive integer, with a higher value meaning a closer match. The scores are only comparable between results of the same query against the same database. Moreover, the scoring rules are different for different versions of Virtuoso server, due to the progress in information retrieval theory. Thus the only really safe thing to do with scores is to sort the list of hits by descending score to produce more relevant hits first. In addition, the CONTAINS predicate allows specifying a lower limit to the score of produced hits so a smart application can reduce a number of retrieved documents by filtering out the less relevant documents.

While the real scoring rules of the server are too sophisticated to be listed here, the basic concept is simple: hits for restrictive terms are most important than hits for generic terms, frequent hits in same document are more important than occasional, hits that are probably concentrated in same sentence are more important than hits here and there in a long text:

- The score of a single word term is proportional to the frequency of the word in the document.
- The score of a phrase is proportional to both the frequency of the phrase in the document and the number of words in the phrase.
- The score of a proximity term 'A NEAR B' depends on the distance between A and B in words - greater distances result in smaller scores. E.g. the score is 100 for zero distance, 80 for 5 word distance, 50 for distance 10, 20 for distance 20; then it slowly decreases to 1 for distance 100. If the distance is 100 words or greater then the condition A NEAR B is considered not to be satisfied. If the A-B pair occurs several times throughout the document the scores of each pair are added. Virtuoso searches for shortest possible pairs, so if there is more than one word A around B then the nearest A is selected for scoring.
- Score of a term like A AND B AND C... AND Z is a minimum of scores of A, B,... Z plus some bonuses. Longer list of AND'ed terms get higher score. A special bonus for term A AND B is added if hits of subterm A are close to the hits of subterm B.
- Score of a term like A OR B OR C... OR Z is a maximum of scores of A, B,... Z, with some additional corrections. Longer list of OR'ed terms get lower score. A special bonus for term A OR B is added if hits of subterm A are close to the hits of subterm B.
- Score of a term like A AND NOT B is equal to the score of subterm A. The subterm B is used for filtering out redundand hits but it does not affect the scoring.

The xcCONTAINS predicate can also return scores. These scores are somewhat similar to scores made by CONTAINS but rules for them are too complicated to be explained here.

### 18.2.7. Word Ranges

This feature allows returning the positions of matches of a query inside the indexed text. This is done by creating a virtual column which gets as its value an array of arrays, one array for each top level term of the text query expression. The component arrays in turn contain word positions, expressed as the ordinal number of the first and last word of each match of the term in question. The ordinal numbers are counted from 0, skipping noise words.

Word Ranges

    select dbg_obj_print (r), * from ftt
    	where contains (dt, 'foo', ranges, r);

Prints the array

    (L(0 0 ) )

to the server standard output, indicating that the match starts and ends at the 0'th word, inclusive.

This feature can be used to show specific portions of matching documents in applications. This is internally used as part of the xcontains predicate for XML text. Also see the function search_excerpt ().

### 18.2.8. Using Offband Data for Faster Filtering

When evaluating a select where there is a contains predicate and filtering conditions on columns of the table on which the text index is defined it is useful to store the most frequently used columns in the free text index instead of the table itself.

The rationale is that in order to access the filtering data the engine will do a merge join with the text index table instead of a nested loop join with the actual table. Further note that if the columns to be accessed are not in the index that begins with the free text document id actually 2 random accesses will be needed: 1. to get the primary key based on the document id and 2. to get the filtering criterion based on the primary key. It is vastly more efficient to do a merge join in the text index to get frequently needed non-text filtering or sorting keys.

If the text index is maintained in background mode the offband data will also be maintained with a delay. This should not be a problem however since this is no more delayed than the text data itself.

If a select with a contains does not reference any columns from the indexed table besides the document id, then no access to the actual table will be generated in the compiled query. Likewise, if only columns found in the index used to link the document id to the table are referenced, only that index will be accessed. A special case of the latter situation is where the document id is the primary key itself. This will speed up retrieving the row for free text hits.

Let us consider a query for getting articles where the author name is at a specific value:

    select id from article where contains (description, 'sample')
    	and author_name = 'John Pumpkin';

This can be alternately written as

    select id from article
    	where contains (description, 'sample', offband, author_name)
    	and author_name = 'John Pumpkin';

In the latter case the author_name will be retrieved from the text index, saving 2 random accesses, one to the index on dtid and the other to the table itself per each free text hit.

The notation is different because the semantic is slightly different. The author_name in the latter case is the name at the time of indexing the article and in the latter case it is the name at the time of evaluating the query. There can be a difference if the index is maintained with a delay. For most applications this is however irrelevant. offband data should not be used for often changing, transactional data.

Now consider

    select * from (select top 10  dtid from article
    	where contains (description, 'sample', offband, author_name)
    	order by author_name) a, article b where a.dtid = b.dtid;

The derived table select the 10 first articles matching the text condition in order of author_name. This does not itself access the article table at all. The outer select will then select the full row for these 10 articles. This is possible since the inner select only references dtid, which is the free text index document id and author_name which is declared an offband column in the text index.

This does less disk access than

    select top 10 * from article
    	where contains (description, sample', offband, author_name)
    	order by author_name;

In this case, all matches are fetched, including the row in the article table and all are sorted and the top 10 are returned. This differs from the first by the fact that this accesses the article table for each of the text hits, not only the top 10. This can easily make a 3x speed difference when running in memory and much greater when IO is involved, not to mention the adverse impact of more IO on the working set.

### 18.2.9. Order of Hits

Rows from a select where there is a contains predicate and no exact match of the primary key of the table are produced in the order of the document id of the free text index if there is no ORDER BY. If there is an ORDER BY matching an index, the query is evaluated in the order of that index and each consecutive row in the order of the index is compared against the free text expression. This is practically never desirable.

If results are desired in the order of the free text document id, there MUST BE NO ORDER BY. The DESCENDING option of contains should be used to produce the reverse order, see contains reference section. If another sorting order is desired, an ORDER BY can be used but to avoid using an index the ordering columns should be expressions or ordinal numbers of result columns.

Therefore:

    select * from article where contains (description, 'sample')
      order by id;

Will have the effect of traversing the table in the order of id and checking each row for free text match. This is practically NEVER good.

To produce the results in order of id instead of dtid it is better to write

    select id, * from article where contains (description, 'sample')
      order by 1;

or

    select * from article where contains (description, 'sample')
      order by id + 0;

### 18.2.10. Noise Words

Noise words are often occurring words which can be skipped to save space in the indexing, such as 'the', 'of', and' etc. These are ignored when they occur in queries or documents to be indexed. The set of noise words is configurable and is read from the noise.txt file, in the server's working directory, at server start up. Words mentioned in that file will be ignored for both indexing and querying.

The file noise.txt consists of control lines and text lines. A text line is just a string of one or more words to be declared as noise. Please keep them shorter than 1000 characters.

Control lines are those starting with "Language:" or "Encoding:" (case is important) "Language: lang-id" tells the system to use rules for language "lang-id" for subsequent text lines, until either another "Language:" control line or end of file. Similarly, "Encoding: enc-id" tells the system to use rules for encoding "enc-id". Control lines are always in plain ASCII, no matter which encoding is active for text lines. By default, the server default language and "UTF-8" encoding will be used.

The simplest way of composing noise.txt is to place every word on a separate line and save the file in UTF-8 encoding; this will work fine for most European languages.

Example

    AND
    OF
    THIS
    THE

Noise words seem to be case-insensitive, but this is not so. If you enter a word on a text line, up to four noise words will be registered:

- the word exactly as it was entered;
- an uppercased form of this word, if it is defined for active language;
- an lowercased form of this word, if it is defined for active language;
- a capitalized form, with one (or more) first chars in upper case and the rest in lower case.

An error is signalled for a free text query consisting exclusively of noise words.

It is important to understand that changes in noise.txt may invalidate free text indexes that were filled with the previous version of noise.txt. For example, if a text contains a phrase 'A B C' and after indexing the word 'B' is added to the noise.txt then 'contains' predicate will properly search for words 'A' and 'C' but will fail to find the phrase 'A B C' or 'A C' due to differences in counting of word positions. The 'xcontains' predicate is even more sensitive to changes in word positions, because any change in word counting will corrupt the index for element names. In addition, "persistent XML" documents may contain pre-calculated word positions for all elements and these positions may become out of sync with positions in free text index, so it is best not to change noise.txt if the database contains any free text indexes on persistent XMLs.

Previous Basic Concepts | Chapter Contents | Next Querying Free Text Indexes