← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to contrib/tsearch/README.tsearch

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/tsearch/README.tsearch
 
1
==========================================================================
 
2
This module is deprecated in 7.4 version of PostgreSQL and will be
 
3
obsoleted in 8.0. Please, use new tsearch2 contrib module.
 
4
==========================================================================
 
5
 
 
6
Tsearch contrib module contains implementation of new data type txtidx - 
 
7
a searchable data type (textual) with indexed access.
 
8
 
 
9
All work was done by Teodor Sigaev (teodor@stack.net) and Oleg Bartunov
 
10
(oleg@sai.msu.su).
 
11
 
 
12
CHANGES:
 
13
 
 
14
August 29, 2002
 
15
        Space usage and using CLUSTER command documented
 
16
August 22, 2002
 
17
        Fix works with 'bad' queries
 
18
August 13, 2002
 
19
        Use parser of OpenFTS v0.33.
 
20
 
 
21
IMPORTANT NOTICE:
 
22
 
 
23
This is a first step of our work on integration of OpenFTS
 
24
full text search engine (http://openfts.sourceforge.net/) into 
 
25
PostgreSQL. It's based on our recent development of GiST 
 
26
(Generalized Search Tree) for PostgreSQL 7.2 (see our GiST page
 
27
at http://www.sai.msu.su/~megera/postgres/gist/ for info about GiST)
 
28
and will works only for PostgreSQL version 7.2 and later.
 
29
 
 
30
We didn't try to implement a full-featured search engine with 
 
31
stable interfaces but rather experiment with various approaches.
 
32
There are many issues remains (most of them just not documented or
 
33
implemented) but we'd like to present a working prototype
 
34
of full text search engine fully integrated into PostgreSQL to 
 
35
collect user's feedback and recommendations. 
 
36
 
 
37
INSTALLATION:
 
38
 
 
39
   cd contrib/tsearch
 
40
   gmake
 
41
   gmake install
 
42
 
 
43
REGRESSION TEST:
 
44
 
 
45
   gmake installcheck
 
46
 
 
47
USAGE:
 
48
 
 
49
 psql DATABASE < tsearch.sql (from contrib/tsearch)
 
50
  
 
51
 
 
52
INTRODUCTION:
 
53
 
 
54
This module provides an implementation of a new data type 'txtidx' which is
 
55
a string of a space separated "words". "Words" with spaces 
 
56
should be enclosed in apostrophes and apostrophes inside a "word" should be 
 
57
escaped by backslash.
 
58
 
 
59
This is quite different from OpenFTS approach which uses array
 
60
of integers (ID of lexems) and requires storing of lexem-id pairs in database. 
 
61
One of the prominent benefit of this new approach is that  it's possible now
 
62
to perform full text search in a 'natural' way. 
 
63
 
 
64
Some examples:
 
65
 
 
66
  create table foo (
 
67
        titleidx  txtidx
 
68
  );
 
69
 
 
70
 2 regular words:
 
71
   insert into foo values ( 'the are' );
 
72
 Word with space:
 
73
   insert into foo values ( 'the\\ are' );
 
74
 Words with apostrophe:
 
75
   insert into foo values ( 'value\'s this' );
 
76
 Complex word with apostrophe:
 
77
   insert into foo values ( 'value\'s this we \'PostgreSQL site\'' );
 
78
 
 
79
   select * from foo where titleidx @@ '\'PostgreSQL site\' | this';
 
80
   select * from foo where titleidx @@ 'value\'s | this';
 
81
   select * from foo where titleidx @@ '(the|this)&!we';
 
82
 
 
83
test=# select 'two words'::txtidx;
 
84
    txtidx     
 
85
---------------
 
86
 'two' 'words'
 
87
(1 row)
 
88
 
 
89
test=# select 'single\\ word'::txtidx;
 
90
    txtidx     
 
91
---------------
 
92
 'single word'
 
93
(1 row)
 
94
 
 
95
 
 
96
FULL TEXT SEARCH:
 
97
 
 
98
The basic idea of this data type is to use it for full text search inside
 
99
database. If you have a 'text' column title and corresponding column 
 
100
titleidx of type 'txtidx', which contains the same information from 
 
101
text column, then search on title could be replaced by
 
102
searching on titleidx which would be fast because of indexed access.
 
103
 
 
104
As a real life example consider database with table 'titles' containing
 
105
titles of mailing list postings in column 'title':
 
106
 
 
107
  create table titles (
 
108
        title  text
 
109
 
 
110
 );
 
111
 
 
112
Suppose, you already have a lot of titles and want to do full text search
 
113
on them.
 
114
 
 
115
First, you need to install contrib/tsearch module (see INSTALLATION and USAGE).
 
116
Add column 'titleidx' of type txtidx, containing space separated words from 
 
117
title. It's possible to use function txt2txtidx(title) to fill 'titleidx' 
 
118
column (see notice 1):
 
119
  
 
120
  -- add titleidx column of type txtidx 
 
121
  alter table titles add titleidx txtidx;
 
122
  update titles set titleidx=txt2txtidx(title);
 
123
 
 
124
Create index on titleidx:
 
125
  create index t_idx on titles using gist(titleidx);
 
126
 
 
127
and now you can search all titles with words 'patch' and 'gist':
 
128
  select title from titles where titleidx ## 'patch&gist';
 
129
 
 
130
Here, ## is a new operation defined for type 'txtidx' which could use index 
 
131
(if exists) built on titleidx. This operator uses morphology to
 
132
expand query, i.e. 
 
133
  ## 'patches&gist' will find titles with 'patch' and 'gist' also.
 
134
If you want to provide query as is, use operator @@ instead:
 
135
  select title from titles where titleidx @@ 'patch&gist';
 
136
but remember, that function txt2txtidx does uses morphology, so you need
 
137
to fill column 'titleidx' using some another way. We hope in future releases
 
138
provide more consistent and convenient interfaces.
 
139
 
 
140
Query could contains boolean operators &,|,!,() with their usual meaning,
 
141
for example: 'patch&gist&!cvs', 'patch|cvs'.
 
142
Each operation ( ##, @@ ) requires appropriate query type - 
 
143
 txtidx ## mquery_txt
 
144
 txtidx @@ query_txt
 
145
 
 
146
To see what query actually will be used :
 
147
 
 
148
test=# select 'patches&gist'::mquery_txt;
 
149
    mquery_txt    
 
150
------------------
 
151
 'patch' & 'gist'
 
152
(1 row)
 
153
 
 
154
test=# select 'patches&gist'::query_txt;
 
155
     query_txt      
 
156
--------------------
 
157
 'patches' & 'gist'
 
158
(1 row)
 
159
 
 
160
Notice the difference !
 
161
 
 
162
You could use trigger to be sure column 'titleidx' is consistent
 
163
with any changes in column 'title':
 
164
 
 
165
  create trigger txtidxupdate before update or insert on titles
 
166
  for each row execute procedure tsearch(titleidx, title);
 
167
 
 
168
This trigger uses the same parser, dictionaries as function
 
169
txt2txtidx (see notice 1).
 
170
Current syntax allows creating trigger for several columns
 
171
you want to be searchable:
 
172
 
 
173
  create trigger txtidxupdate before update or insert on titles
 
174
  for each row execute procedure tsearch(titleidx, title1, title2,... );
 
175
 
 
176
Use function txtidxsize(titleidx) to get the number of "words" in column
 
177
titleidx. To get total number of words in table titles:
 
178
 
 
179
test=# select sum(txtidxsize(titleidx)) from titles;
 
180
   sum   
 
181
---------
 
182
 1917182
 
183
(1 row)
 
184
 
 
185
NOTICES:
 
186
 
 
187
1.
 
188
function txt2txtidx and trigger use parser, dictionaries coming with 
 
189
this contrib module on default. Parser is mostly the same as in OpenFTS and 
 
190
dictionaries are simple stemmers (sort of Lovin's stemmer which uses a 
 
191
longest match algorithm.) for english and russian languages. There is a perl
 
192
script makedict/makedict.pl, which could be used to create specific
 
193
dictionaries from files with endings and stop-words. 
 
194
Example files for english and russian languages are available 
 
195
from http://www.sai.msu.su/~megera/postgres/gist/tsearch/.
 
196
Run script without parameters to see information about arguments and options. 
 
197
 
 
198
Example:
 
199
cd makedict
 
200
./makedict.pl -l LOCALNAME -e FILEENDINGS -s FILESTOPWORD \
 
201
              -o ../dict/YOURDICT.dct
 
202
 
 
203
Another options of makedict.pl:
 
204
-f do not execute tolower for any char
 
205
-a function of checking stopword will be work after lemmatize, 
 
206
   default is before
 
207
 
 
208
You need to edit dict.h to use your dictionary and, probably, 
 
209
morph.c to change mapdict array.
 
210
 
 
211
Don't forget to do 
 
212
  make clean; make; make install
 
213
 
 
214
2.
 
215
txtidx doesn't preserve words ordering (this is not critical for searching)
 
216
for performance reason, for example:
 
217
 
 
218
test=# select 'page two'::txtidx;
 
219
    txtidx    
 
220
--------------
 
221
 'two' 'page'
 
222
(1 row)
 
223
 
 
224
3. 
 
225
Indexed access provided by txtidx data type isn't always good
 
226
because of internal data structure we use (RD-Tree). Particularly,
 
227
queries like '!gist' will be  slower than just a sequential scan,
 
228
because for such queries RD-Tree doesn't provides selectivity on internal 
 
229
nodes and all checks should be processed at leaf nodes, i.t. scan of
 
230
full index. You may play with function query_tree to see how effective
 
231
will be index usage:
 
232
 
 
233
test=# select querytree( 'patch&gist'::query_txt );
 
234
    querytree     
 
235
------------------
 
236
 'patch' & 'gist'
 
237
(1 row)
 
238
 
 
239
This is an example of "good" query - index will effective for both words.
 
240
 
 
241
test=# select querytree( 'patch&!gist'::query_txt );
 
242
 querytree 
 
243
-----------
 
244
 'patch'
 
245
(1 row)
 
246
 
 
247
This means that index is effective only to search word 'patch' and resulted
 
248
rows will be checked against '!gist'.
 
249
 
 
250
test=# select querytree( 'patch|!gist'::query_txt );
 
251
 querytree 
 
252
-----------
 
253
 T
 
254
(1 row)
 
255
 
 
256
test=# select querytree( '!gist'::query_txt );
 
257
 querytree 
 
258
-----------
 
259
 T
 
260
(1 row)
 
261
 
 
262
These two queries will be processed by scanning of full index !
 
263
Very slow !
 
264
 
 
265
4.
 
266
Following selects produce the same result
 
267
 
 
268
  select title from titles where titleidx @@ 'patch&gist';
 
269
  select title from titles where titleidx @@ 'patch' and titleidx @@ 'gist';
 
270
 
 
271
but the former will be more effective, because of internal optimization
 
272
of query executor.
 
273
 
 
274
 
 
275
TODO:
 
276
 
 
277
Better configurability (as in OpenFTS)
 
278
User's interfaces to parser, dictionaries ...
 
279
Write documentation
 
280
 
 
281
 
 
282
BENCHMARKS:
 
283
 
 
284
We use test collection in our experiments which contains 377905
 
285
titles from various mailing lists stored in our mailware
 
286
project. 
 
287
 
 
288
All runs were performed on IBM ThinkPad T21 notebook with 
 
289
PIII 733 Mhz, 256 RAM, 20 Gb HDD, Linux 2.2.19, postgresql 7.2.dev
 
290
We didn't do extensive benchmarking and all
 
291
numbers provide for illustration. Actual performance
 
292
is strongly depends on many factors (query, collection, dictionaries 
 
293
and hardware).
 
294
 
 
295
Collection is available for download from
 
296
http://www.sai.msu.su/~megera/postgres/gist/tsearch/mw_titles.gz 
 
297
(377905 titles from postgresql mailing lists, about 3Mb).
 
298
 
 
299
0. install contrib/tsearch module
 
300
1. createdb test
 
301
2. psql test < tsearch.sql (from contrib/tsearch)
 
302
3. zcat mw_titles.gz | psql test 
 
303
   (it will creates table, copy test data and creates index)
 
304
 
 
305
Database contains one table:
 
306
 
 
307
test=# \d titles
 
308
                Table "titles"
 
309
  Column  |          Type          | Modifiers 
 
310
----------+------------------------+-----------
 
311
 title    | character varying(256) | 
 
312
 titleidx | txtidx                 | 
 
313
Indexes: t_idx
 
314
 
 
315
Index was created as:
 
316
   create index t_idx on titles using gist(titleidx);
 
317
   (notice: this operation takes about 14 minutes on my notebook)
 
318
 
 
319
Typical select looks like:
 
320
   select title from titles where titleidx @@ 'patch&gist';
 
321
 
 
322
Total number of lexems in collection : 1917182
 
323
 
 
324
1. We trust index  - we consider index is exact and no
 
325
   checking against tuples is necessary.
 
326
 
 
327
   update pg_amop set amopreqcheck = false where amopclaid = 
 
328
   (select oid from pg_opclass where opcname = 'gist_txtidx_ops');
 
329
 
 
330
using gist indices
 
331
1: titleidx @@ 'patch&gist' 0.000u 0.000s 0m0.054s 0.00%
 
332
2: titleidx @@ 'patch&gist' 0.020u 0.000s 0m0.045s 44.82%
 
333
3: titleidx @@ 'patch&gist' 0.000u 0.000s 0m0.044s 0.00%
 
334
using gist indices (morph)
 
335
1: titleidx ## 'patch&gist' 0.000u 0.010s 0m0.046s 21.62%
 
336
2: titleidx ## 'patch&gist' 0.010u 0.010s 0m0.046s 43.47%
 
337
3: titleidx ## 'patch&gist' 0.000u 0.000s 0m0.046s 0.00%
 
338
disable gist index
 
339
1: titleidx @@ 'patch&gist' 0.000u 0.010s 0m1.601s 0.62%
 
340
2: titleidx @@ 'patch&gist' 0.000u 0.000s 0m1.607s 0.00%
 
341
3: titleidx @@ 'patch&gist' 0.010u 0.000s 0m1.607s 0.62%
 
342
traditional like
 
343
1: title ~* 'gist' and title ~* 'patch'  0.010u 0.000s 0m9.206s 0.10%
 
344
2: title ~* 'gist' and title ~* 'patch'  0.000u 0.010s 0m9.205s 0.10%
 
345
3: title ~* 'gist' and title ~* 'patch'  0.010u 0.000s 0m9.208s 0.10%
 
346
 
 
347
2. Need to check results against tuples to avoid possible hash collision.
 
348
 
 
349
   update pg_amop set amopreqcheck = true where amopclaid = 
 
350
   (select oid from pg_opclass where opcname = 'gist_txtidx_ops');
 
351
 
 
352
using gist indices
 
353
1: titleidx @@ 'patch&gist' 0.010u 0.000s 0m0.052s 19.26%
 
354
2: titleidx @@ 'patch&gist' 0.000u 0.000s 0m0.045s 0.00%
 
355
3: titleidx @@ 'patch&gist' 0.010u 0.000s 0m0.045s 22.39%
 
356
using gist indices (morph)
 
357
1: titleidx ## 'patch&gist' 0.000u 0.000s 0m0.046s 0.00%
 
358
2: titleidx ## 'patch&gist' 0.000u 0.010s 0m0.046s 21.75%
 
359
3: titleidx ## 'patch&gist' 0.020u 0.000s 0m0.047s 42.13%
 
360
 
 
361
There are no visible difference between these 2 cases but your
 
362
mileage may vary.
 
363
 
 
364
 
 
365
NOTES:
 
366
 
 
367
1. The size of txtidx column should be lesser than size of corresponding column.
 
368
   Below some real numbers from test database (link above).
 
369
 
 
370
   a) After loading data
 
371
   
 
372
-rw-------    1 postgres users    23191552 Aug 29 14:08 53016937
 
373
-rw-------    1 postgres users    81059840 Aug 29 14:08 52639027
 
374
 
 
375
Table titles (52639027) occupies 80Mb, index on txtidx column (53016937)
 
376
occupies 22Mb. Use contrib/oid2name to get mappings from oid to names.
 
377
After doing
 
378
 
 
379
test=# select title  into titles_tmp from titles;
 
380
SELECT
 
381
 
 
382
I got size of table 'titles' without txtidx field
 
383
 
 
384
-rw-------    1 postgres users    30105600 Aug 29 14:14 53016938
 
385
 
 
386
So, txtidx column itself occupies about 50Mb. 
 
387
 
 
388
     b) after running 'vacuum full analyze' I got:
 
389
 
 
390
-rw-------    1 postgres users    30105600 Aug 29 14:26 53016938
 
391
-rw-------    1 postgres users    36880384 Aug 29 14:26 53016937
 
392
-rw-------    1 postgres users    51494912 Aug 29 14:26 52639027
 
393
 
 
394
53016938 = titles_tmp
 
395
 
 
396
So, actual size of 'txtidx' field is 20 Mb !  "quod erat demonstrandum"
 
397
 
 
398
2. CLUSTER command is highly recommended if you need fast searching.
 
399
   For example:
 
400
 
 
401
  test=# cluster t_idx on titles;
 
402
 
 
403
  BUT ! In 7.2 CLUSTER command forgets about other indices and permissions,
 
404
  so you need be carefull and rebuild these indices and restore permissions
 
405
  after clustering. Also, clustering isn't dynamic, so you'd need to 
 
406
  use CLUSTER from time to time. In 7.3 CLUSTER command should works
 
407
  fine.
 
408
 
 
409
  after clustering:
 
410
 
 
411
-rw-------    1 postgres users    23404544 Aug 29 14:59 53394850
 
412
-rw-------    1 postgres users    30105600 Aug 29 14:26 53016938
 
413
-rw-------    1 postgres users    50995200 Aug 29 14:45 53394845
 
414
pg@zen:/usr/local/pgsql/data/base/52638986$ oid2name -d test                 
 
415
All tables from database "test":
 
416
---------------------------------
 
417
53394850 = t_idx
 
418
53394845 = titles
 
419
53016938 = titles_tmp
 
420