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