Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Let's say that I have a table called words with very many records.
Columns are id and name.

In the words table I have for example:

 'systematic', 'سلام','gear','synthesis','mysterious', etc.  

NB: we have utf8 words, too.
How to query efficiently to see which words include letters 's', 'm' and 'e' (all of them)?

The output would be:

systematic,mysterious

I have no idea how to do such a thing. It should be efficient because our server would suffer otherwise.

share|improve this question
    
Does each row contain a single word? –  Colin 't Hart Dec 17 '13 at 9:29
    
YES. Each row contains one single word. –  john.locke Dec 17 '13 at 9:45
    
this might help: it all depends on how often you write to that table though :) –  Jack Douglas Dec 17 '13 at 13:43
    
And you are always looking for single letters? Do you take accents (diacritic signs) into account? For instance, do you want to find é or è when looking for e? –  Erwin Brandstetter Dec 17 '13 at 19:40
    
@Erwin either way some sort of trigram indexing could help, right? –  Jack Douglas Dec 17 '13 at 20:28

3 Answers 3

up vote 4 down vote accepted

An easy approach would be to consider the array of letters corresponding to each word, and search inside that with the @> (contains) array operator. This works independantly of the letters positions as shown in the example from the manual, i.e. ARRAY[1,4,3] @> ARRAY[3,1] is true.

This array can be easily obtained with regexp_split_to_array(name, '').
[EDIT: per @Erwin's answer, string_to_array(name, NULL) is faster so better use that. It's a drop-in replacement in the rest of the answer]

Here's a demo that first materializes the array as a column in a test table containing a mix of english and french words (~511000 rows, average length=13 characters), and then a second test table without adding the array as a column.

=> CREATE TABLE tstword AS
    SELECT word_id as id,
    wordtext as name,
    regexp_split_to_array(wordtext, '') as arr FROM words;

To find a relatively large number of words:

=> select count(*) from tstword where arr @> array['s','m','e'];
 count 
-------
 42268
(1 row)

Time: 268.809 ms

This does a sequential scan as shown by EXPLAIN ANALYZE:

 explain analyze select name from tstword where arr @> array['s','m','e'];
                                                   QUERY PLAN                                                   
----------------------------------------------------------------------------------------------------------------
 Seq Scan on tstword  (cost=0.00..17554.46 rows=21256 width=14) (actual time=0.020..268.525 rows=42268 loops=1)
   Filter: (arr @> '{s,m,e}'::text[])
   Rows Removed by Filter: 468729
 Total runtime: 269.927 ms
(4 rows)

Time: 270.414 ms

But we can index the array with a GIN index:

CREATE INDEX idx_tst on tstword using gin(arr);

And then it's quite faster:

explain analyze select name from tstword where arr @> array['s','m','e'];
                                                         QUERY PLAN                                                         
----------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on tstword  (cost=252.74..11815.73 rows=21256 width=14) (actual time=46.378..60.203 rows=42268 loops=1)
   Recheck Cond: (arr @> '{s,m,e}'::text[])
   ->  Bitmap Index Scan on idx_tst  (cost=0.00..247.42 rows=21256 width=0) (actual time=45.202..45.202 rows=42268 loops=1)
         Index Cond: (arr @> '{s,m,e}'::text[])
 Total runtime: 61.677 ms
(5 rows)

Time: 70.185 ms

We might even avoid materializing the array as a column by directly indexing the expression, since postgres supports functional indexes.

create table tstword2 as select word_id as id,wordtext as name from words;
create index idx_tst2 on tstword2  using gin(regexp_split_to_array(name, ''));

Then the search has to be made with the exact same expression, and the index gets used:

 explain analyze select name from tstword2 where regexp_split_to_array(name, '') @> array['s','m','e'];
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on tstword2  (cost=40.00..44.02 rows=1 width=14) (actual time=39.390..48.435 rows=42268 loops=1)
   Recheck Cond: (regexp_split_to_array((name)::text, ''::text) @> '{s,m,e}'::text[])
   ->  Bitmap Index Scan on idx_tst2  (cost=0.00..40.00 rows=1 width=0) (actual time=39.053..39.053 rows=42268 loops=1)
         Index Cond: (regexp_split_to_array((name)::text, ''::text) @> '{s,m,e}'::text[])
 Total runtime: 49.748 ms
(5 rows)

Time: 50.193 ms

See GiST and GIN Index Types in the manual for caveats on these types of indexes.

share|improve this answer
    
+1 This approach is the first that bears fruit. I see more potential here ... –  Erwin Brandstetter Dec 18 '13 at 4:28

Test case

I built a halfway realistic test case:

CREATE TABLE word(word_id int, word text);
INSERT INTO word (word_id, word)
SELECT g%(2500000/25) -- max length 25
      ,left(string_agg(chr(97 + (random()^2 * 31)::int), ''), 3 + (random()^2 * 25)::int)
FROM  (SELECT generate_series(1, 2500000) AS g) g
GROUP  BY 1
ORDER  BY 1;  --> 100k rows

Lower case words with 3 to 25 letters, some additional characters as stand-ins for non-ASCII letters. Shorter words are more common and some letters are more common than others. Using random()^2 to get a tilted data distribution.

Using this I ran a number of tests to compare @Daniel's approach with some alternatives.

word LIKE ALL(arr)

I found this query to be surprisingly effective, even without index:

SELECT * FROM word
WHERE  word LIKE ALL('{%l%,%w%,%x%,%y%,%z%,%~%}'::text[]);

To make it work, you would pad your letters with %. I.e.:a -> %a% and form an array like above.

About as fast with a sequential scan on 100k rows as other solutions based on a GIN index. I also tested with 10k and 40k rows and on Postgres 9.1. Similar results.

This is going to deteriorate with even bigger tables. But if your table holds 100k rows or fewer (and doesn't have other big columns) this simple query may be all you need.

Functional index

string_to_array()

First of all, use string_to_array(word, NULL)) instead of regexp_split_to_array(word, ''). I found it to be 5-6 times faster in Postgres 9.1 and 2-3 times faster in Postgres 9.3. Primarily affects index maintenance, but to a lesser degree query performance, too.

Either of these expression results in an unsorted array with possible duplicates.

CREATE INDEX word_arr_gin_idx ON word USING gin(string_to_array(word, NULL));

Ineffective variants

Removing duplicates from the array is ineffective, since the GIN algorithm does that by itself. Quoting the manual:

Each key value is stored only once, so a GIN index is very compact for cases where the same key appears many times.

I include this ineffective variant in the fiddle anyway to proof the point and also as proof of concept - how to use a user-defined IMMUTABLE function in an index:

CREATE OR REPLACE FUNCTION uniq_arr(text)
  RETURNS text[] AS
$func$
SELECT ARRAY(
   SELECT DISTINCT i
   FROM   unnest(string_to_array($1, NULL)) t(i))
$func$ LANGUAGE sql IMMUTABLE;

CREATE INDEX word_uniq_arr_gin_idx ON word USING gin(uniq_arr(word));

An index on a distinct, sorted arrays also shows the same search times, while being more expensive. I didn't include it.

-> SQLfiddle demo.

Fold letters

However, an IMMUTABLE function like demonstrated above can be used to fold letters. A typical use case would be with the unaccent module to remove accents (diacritic signs), i.e. to also find é, è etc. when looking for e.

This would be a very effective solution:

CREATE OR REPLACE FUNCTION unaccent_arr(text) RETURNS text[] AS
$func$
SELECT string_to_array(unaccent('unaccent', $1), NULL)
$func$ LANGUAGE sql IMMUTABLE SET search_path = public, pg_temp;

CREATE INDEX word_unaccent_arr_gin_idx ON word USING gin(unaccent_arr(word));

Detailed explanation in this related answer on SO (be sure to read it):
Does PostgreSQL support “accent insensitive” collations?

I tested locally on Postgres 9.1 and 9.3, but cannot include it in the fiddle, where I cannot install additional modules.

share|improve this answer
1  
+1, makes me think we should ask Jake to include some pg extensions in SQLFiddle –  Jack Douglas Dec 18 '13 at 9:37
    
@JackDouglas: That would be great! As far as I have seen, pg_trgm and hstore are already installed (at least on 9.3). But I have been wishing for unaccent, tablefunc and some others on several occasions. –  Erwin Brandstetter Dec 18 '13 at 9:44
    
can you give me a wish-list, and any opinion on any risk they might introduce? –  Jack Douglas Dec 18 '13 at 15:25
    
@JackDouglas: In addition to the already existing pg_trgm and hstore, my shortlist would be tablefunc, intarray, unaccent,` btree_gist. I have been using these a lot without problems so far and they make sense on sqlfiddle. Maybe also btree_gin, citext` and uuid-ossp. Potential risks? None that I know of. Of course, more functionality offer more possibilities for abuse in general. And people may be confused to find things working that do not in their installation. Should be made public in the FAQ or somewhere so that at least interested folks can find it ... –  Erwin Brandstetter Dec 18 '13 at 21:46

Postgresql has many indexing options. It also has some powerful components built on top of these indexing options.

One such feature is full text search. See http://www.postgresql.org/docs/9.3/static/textsearch.html

share|improve this answer
1  
Full text search is hardly useful since it is based on dictionaries and stemming. I won't help with finding single letters across the string. Maybe with a custom parser that defines single letters as tokens, which I haven't seen or tried yet ... –  Erwin Brandstetter Dec 18 '13 at 0:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.