granicus.if.org Git - postgresql/blob - doc/src/sgml/pgtrgm.sgml

   1 <!-- doc/src/sgml/pgtrgm.sgml -->
   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      <row>
 121       <entry><type>text</> <literal>&lt;-&gt;</literal> <type>text</></entry>
 122       <entry><type>real</type></entry>
 123       <entry>
 124        Returns the <quote>distance</> between the arguments, that is
 125        one minus the <function>similarity()</> value.
 126       </entry>
 127      </row>
 128     </tbody>
 129    </tgroup>
 130   </table>
 131  </sect2>
 132
 133  <sect2>
 134   <title>Index Support</title>
 135
 136   <para>
 137    The <filename>pg_trgm</filename> module provides GiST and GIN index
 138    operator classes that allow you to create an index over a text column for
 139    the purpose of very fast similarity searches.  These index types support
 140    the above-described similarity operators, and additionally support
 141    trigram-based index searches for <literal>LIKE</> and <literal>ILIKE</>
 142    queries.  (These indexes do not support equality nor simple comparison
 143    operators, so you may need a regular B-tree index too.)
 144   </para>
 145
 146   <para>
 147    Example:
 148
 149 <programlisting>
 150 CREATE TABLE test_trgm (t text);
 151 CREATE INDEX trgm_idx ON test_trgm USING gist (t gist_trgm_ops);
 152 </programlisting>
 153 or
 154 <programlisting>
 155 CREATE INDEX trgm_idx ON test_trgm USING gin (t gin_trgm_ops);
 156 </programlisting>
 157   </para>
 158
 159   <para>
 160    At this point, you will have an index on the <structfield>t</> column that
 161    you can use for similarity searching.  A typical query is
 162 <programlisting>
 163 SELECT t, similarity(t, '<replaceable>word</>') AS sml
 164   FROM test_trgm
 165   WHERE t % '<replaceable>word</>'
 166   ORDER BY sml DESC, t;
 167 </programlisting>
 168    This will return all values in the text column that are sufficiently
 169    similar to <replaceable>word</>, sorted from best match to worst.  The
 170    index will be used to make this a fast operation even over very large data
 171    sets.
 172   </para>
 173
 174   <para>
 175    A variant of the above query is
 176 <programlisting>
 177 SELECT t, t &lt;-&gt; '<replaceable>word</>' AS dist
 178   FROM test_trgm
 179   ORDER BY dist LIMIT 10;
 180 </programlisting>
 181    This can be implemented quite efficiently by GiST indexes, but not
 182    by GIN indexes.  It will usually beat the first formulation when only
 183    a small number of the closest matches is wanted.
 184   </para>
 185
 186   <para>
 187    Beginning in <productname>PostgreSQL</> 9.1, these index types also support
 188    index searches for <literal>LIKE</> and <literal>ILIKE</>, for example
 189 <programlisting>
 190 SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';
 191 </programlisting>
 192    The index search works by extracting trigrams from the search string
 193    and then looking these up in the index.  The more trigrams in the search
 194    string, the more effective the index search is.  Unlike B-tree based
 195    searches, the search string need not be left-anchored.
 196   </para>
 197
 198   <para>
 199    The choice between GiST and GIN indexing depends on the relative
 200    performance characteristics of GiST and GIN, which are discussed elsewhere.
 201    As a rule of thumb, a GIN index is faster to search than a GiST index, but
 202    slower to build or update; so GIN is better suited for static data and GiST
 203    for often-updated data.
 204   </para>
 205  </sect2>
 206
 207  <sect2>
 208   <title>Text Search Integration</title>
 209
 210   <para>
 211    Trigram matching is a very useful tool when used in conjunction
 212    with a full text index.  In particular it can help to recognize
 213    misspelled input words that will not be matched directly by the
 214    full text search mechanism.
 215   </para>
 216
 217   <para>
 218    The first step is to generate an auxiliary table containing all
 219    the unique words in the documents:
 220
 221 <programlisting>
 222 CREATE TABLE words AS SELECT word FROM
 223         ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');
 224 </programlisting>
 225
 226    where <structname>documents</> is a table that has a text field
 227    <structfield>bodytext</> that we wish to search.  The reason for using
 228    the <literal>simple</> configuration with the <function>to_tsvector</>
 229    function, instead of using a language-specific configuration,
 230    is that we want a list of the original (unstemmed) words.
 231   </para>
 232
 233   <para>
 234    Next, create a trigram index on the word column:
 235
 236 <programlisting>
 237 CREATE INDEX words_idx ON words USING gin(word gin_trgm_ops);
 238 </programlisting>
 239
 240    Now, a <command>SELECT</command> query similar to the previous example can
 241    be used to suggest spellings for misspelled words in user search terms.
 242    A useful extra test is to require that the selected words are also of
 243    similar length to the misspelled word.
 244   </para>
 245
 246   <note>
 247    <para>
 248     Since the <structname>words</> table has been generated as a separate,
 249     static table, it will need to be periodically regenerated so that
 250     it remains reasonably up-to-date with the document collection.
 251     Keeping it exactly current is usually unnecessary.
 252    </para>
 253   </note>
 254  </sect2>
 255
 256  <sect2>
 257   <title>References</title>
 258
 259   <para>
 260    GiST Development Site
 261    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/"></ulink>
 262   </para>
 263   <para>
 264    Tsearch2 Development Site
 265    <ulink url="http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/"></ulink>
 266   </para>
 267  </sect2>
 268
 269  <sect2>
 270   <title>Authors</title>
 271
 272   <para>
 273    Oleg Bartunov <email>oleg@sai.msu.su</email>, Moscow, Moscow University, Russia
 274   </para>
 275   <para>
 276    Teodor Sigaev <email>teodor@sigaev.ru</email>, Moscow, Delta-Soft Ltd.,Russia
 277   </para>
 278   <para>
 279    Documentation: Christopher Kings-Lynne
 280   </para>
 281   <para>
 282    This module is sponsored by Delta-Soft Ltd., Moscow, Russia.
 283   </para>
 284  </sect2>
 285
 286 </sect1>