doc/src/sgml/pgtrgm.sgml

   1 <!-- $PostgreSQL$ -->
   2
   3 <sect1 id="pgtrgm">
   4  <title>pg_trgm</title>
   5
   6  <indexterm zone="pgtrgm">
   7   <primary>pg_trgm</primary>
   8  </indexterm>
   9
  10  <para>
  11   The <filename>pg_trgm</filename> module provides functions and operators
  12   for determining the similarity of text based on trigram matching, as
  13   well as index operator classes that support fast searching for similar
  14   strings.
  15  </para>
  16
  17  <sect2>
  18   <title>Trigram (or Trigraph) Concepts</title>
  19
  20   <para>
  21    A trigram is a group of three consecutive characters taken
  22    from a string.  We can measure the similarity of two strings by
  23    counting the number of trigrams they share.  This simple idea
  24    turns out to be very effective for measuring the similarity of
  25    words in many natural languages.
  26   </para>
  27
  28   <note>
  29    <para>
  30     A string is considered to have two spaces
  31     prefixed and one space suffixed when determining the set
  32     of trigrams contained in the string.
  33     For example, the set of trigrams in the string
  34     <quote><literal>cat</literal></quote> is
  35     <quote><literal>  c</literal></quote>,
  36     <quote><literal> ca</literal></quote>,
  37     <quote><literal>cat</literal></quote>, and
  38     <quote><literal>at </literal></quote>.
  39    </para>
  40   </note>
  41  </sect2>
  42
  43  <sect2>
  44   <title>Functions and Operators</title>
  45
  46   <table id="pgtrgm-func-table">
  47    <title><filename>pg_trgm</filename> functions</title>
  48    <tgroup cols="3">
  49     <thead>
  50      <row>
  51       <entry>Function</entry>
  52       <entry>Returns</entry>
  53       <entry>Description</entry>
  54      </row>
  55     </thead>
  56
  57     <tbody>
  58      <row>
  59       <entry><function>similarity(text, text)</function></entry>
  60       <entry><type>real</type></entry>
  61       <entry>
  62        Returns a number that indicates how similar the two arguments are.
  63        The range of the result is zero (indicating that the two strings are
  64        completely dissimilar) to one (indicating that the two strings are
  65        identical).
  66       </entry>
  67      </row>
  68      <row>
  69       <entry><function>show_trgm(text)</function></entry>
  70       <entry><type>text[]</type></entry>
  71       <entry>
  72        Returns an array of all the trigrams in the given string.
  73        (In practice this is seldom useful except for debugging.)
  74       </entry>
  75      </row>
  76      <row>
  77       <entry><function>show_limit()</function></entry>
  78       <entry><type>real</type></entry>
  79       <entry>
  80        Returns the current similarity threshold used by the <literal>%</>
  81        operator.  This sets the minimum similarity between
  82        two words for them to be considered similar enough to
  83        be misspellings of each other, for example.
  84       </entry>
  85      </row>
  86      <row>
  87       <entry><function>set_limit(real)</function></entry>
  88       <entry><type>real</type></entry>
  89       <entry>
  90        Sets the current similarity threshold that is used by the <literal>%</>
  91        operator.  The threshold must be between 0 and 1 (default is 0.3).
  92        Returns the same value passed in.
  93       </entry>
  94      </row>
  95     </tbody>
  96    </tgroup>
  97   </table>
  98
  99   <table id="pgtrgm-op-table">
 100    <title><filename>pg_trgm</filename> operators</title>
 101    <tgroup cols="3">
 102     <thead>
 103      <row>
 104       <entry>Operator</entry>
 105       <entry>Returns</entry>
 106       <entry>Description</entry>
 107      </row>
 108     </thead>
 109
 110     <tbody>
 111      <row>
 112       <entry><type>text</> <literal>%</literal> <type>text</></entry>
 113       <entry><type>boolean</type></entry>
 114       <entry>
 115        Returns <literal>true</> if its arguments have a similarity that is
 116        greater than the current similarity threshold set by
 117        <function>set_limit</>.
 118       </entry>
 119      </row>
 120     </tbody>
 121    </tgroup>
 122   </table>
 123  </sect2>
 124
 125  <sect2>
 126   <title>Index Support</title>
 127
 128   <para>
 129    The <filename>pg_trgm</filename> module provides GiST and GIN index
 130    operator classes that allow you to create an index over a text column for
 131    the purpose of very fast similarity searches.  These index types support
 132    the <literal>%</> similarity operator (and no other operators, so you may
 133    want a regular btree index too).
 134   </para>
 135
 136   <para>
 137    Example:
 138
 139   <programlisting>
 140 CREATE TABLE test_trgm (t text);
 141 CREATE INDEX trgm_idx ON test_trgm USING gist (t gist_trgm_ops);
 142   </programlisting>
 143 or
 144   <programlisting>
 145 CREATE INDEX trgm_idx ON test_trgm USING gin (t gin_trgm_ops);
 146   </programlisting>
 147   </para>
 148
 149   <para>
 150    At this point, you will have an index on the <structfield>t</> column that
 151    you can use for similarity searching.  A typical query is
 152   </para>
 153   <programlisting>
 154 SELECT t, similarity(t, '<replaceable>word</>') AS sml
 155   FROM test_trgm
 156   WHERE t % '<replaceable>word</>'
 157   ORDER BY sml DESC, t;
 158   </programlisting>
 159   <para>
 160    This will return all values in the text column that are sufficiently
 161    similar to <replaceable>word</>, sorted from best match to worst.  The
 162    index will be used to make this a fast operation even over very large data
 163    sets.
 164   </para>
 165
 166   <para>
 167    The choice between GiST and GIN indexing depends on the relative
 168    performance characteristics of GiST and GIN, which are discussed elsewhere.
 169    As a rule of thumb, a GIN index is faster to search than a GiST index, but
 170    slower to build or update; so GIN is better suited for static data and GiST
 171    for often-updated data.
 172   </para>
 173  </sect2>
 174
 175  <sect2>
 176   <title>Text Search Integration</title>
 177
 178   <para>
 179    Trigram matching is a very useful tool when used in conjunction
 180    with a full text index.  In particular it can help to recognize
 181    misspelled input words that will not be matched directly by the
 182    full text search mechanism.
 183   </para>
 184
 185   <para>
 186    The first step is to generate an auxiliary table containing all
 187    the unique words in the documents:
 188   </para>
 189
 190   <programlisting>
 191 CREATE TABLE words AS SELECT word FROM
 192         ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');
 193   </programlisting>
 194
 195   <para>
 196    where <structname>documents</> is a table that has a text field
 197    <structfield>bodytext</> that we wish to search.  The reason for using
 198    the <literal>simple</> configuration with the <function>to_tsvector</>
 199    function, instead of using a language-specific configuration,
 200    is that we want a list of the original (unstemmed) words.
 201   </para>
 202
 203   <para>
 204    Next, create a trigram index on the word column:
 205   </para>
 206
 207   <programlisting>
 208 CREATE INDEX words_idx ON words USING gin(word gin_trgm_ops);
 209   </programlisting>
 210
 211   <para>
 212    Now, a <command>SELECT</command> query similar to the previous example can
 213    be used to suggest spellings for misspelled words in user search terms.
 214    A useful extra test is to require that the selected words are also of
 215    similar length to the misspelled word.
 216   </para>
 217
 218   <note>
 219    <para>
 220     Since the <structname>words</> table has been generated as a separate,
 221     static table, it will need to be periodically regenerated so that
 222     it remains reasonably up-to-date with the document collection.
 223     Keeping it exactly current is usually unnecessary.
 224    </para>
 225   </note>
 226  </sect2>
 227
 228  <sect2>
 229   <title>References</title>
 230
 231   <para>
 232    GiST Development Site
 233    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/"></ulink>
 234   </para>
 235   <para>
 236    Tsearch2 Development Site
 237    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/"></ulink>
 238   </para>
 239  </sect2>
 240
 241  <sect2>
 242   <title>Authors</title>
 243
 244   <para>
 245    Oleg Bartunov <email>oleg@sai.msu.su</email>, Moscow, Moscow University, Russia
 246   </para>
 247   <para>
 248    Teodor Sigaev <email>teodor@sigaev.ru</email>, Moscow, Delta-Soft Ltd.,Russia
 249   </para>
 250   <para>
 251    Documentation: Christopher Kings-Lynne
 252   </para>
 253   <para>
 254    This module is sponsored by Delta-Soft Ltd., Moscow, Russia.
 255   </para>
 256  </sect2>
 257
 258 </sect1>