13

We have the following database structure

CREATE TABLE objects (
    id       int   PRIMARY KEY,
    name     text,
    address  text
);

CREATE TABLE tasks (
    id int           PRIMARY KEY,
    object_id int    NOT NULL,
    actor_id int     NOT NULL,
    description text
);

CREATE TABLE actors (
    id   int  PRIMARY KEY,
    name text
);

The user enters a whitespace-separated list of words (search terms, basically) and we have to search for tasks, that satisfy the following: the task is a "match" if each search term occurs at least once in concatenation of task's description, the name and address of its associated object and the name of its associated actor.

Now, if we are not concerned about performance, we can just do something like this (given query "foo bar"):

SELECT t.id, t.description
FROM tasks AS t
INNER JOIN actors AS a ON t.actor_id = a.id
INNER JOIN objects AS o ON t.object_id = o.id
WHERE to_tsvector(concat_ws(' ', t.description, o.name, o.address, a.name)) @@
    plainto_tsquery('foo bar');

Unfortunately, we are concerned about performance. The dataset will, probably, be as follows (and it is expected to grow):

  • about 10000 objects
  • about 1000 actors
  • about 100000 tasks evenly distributed between objects

What I've considered:

Make a denormalized table like this:

CREATE TABLE task_documents (
    id int PRIMARY KEY,
    doc tsvector
)

The field "doc" will contain the concatenation of task's description, associated object's name and address and actor's name. We will have to create an index over this field and it will be used in full text search queries. This table will be updated in update / insert triggers on tasks, actors, objects.

Drawbacks: tons of duplicated data (this one I am not quite concerned about), and updates to the master tables will become unpredictable in terms of number of rows updated (say, you update a name of some object and now suddenly you must update thousands of rows in task_documents).

Honestly, I don't have any more (good) ideas. It is obviously impossible to create an index, spanning 3 tables, so that it will be used for the WHERE clause in the original query.

UPD

Here's a sqlfiddle with DB schema and some data. I had to make it up, because we have no real data at the moment.

2
  • WHERE to_tsvector(concat_ws(' ', t.name, o.address, o.description, a.name)) @@ plainto_tsquery('foo bar') Doesn't work. It'd also be great if you actually inserted some sample data. and showed us what you wanted. Feb 16, 2017 at 15:10
  • @EvanCarroll I've added a sqlfiddle with data and fixed the query in question body
    – shylent
    Feb 16, 2017 at 16:04

3 Answers 3

12

Optimization

You're going down the right track.

You either need to

  1. Denormalize
  2. Cache

Caching the results

What you probably want is a MATERIALIZED VIEW. This is easy and works reasonably well.

CREATE MATERIALIZED VIEW foo
AS
SELECT t.id, to_tsvector(concat_ws(' ',a.name, o.address, t.description, a.name)) AS tsv
FROM tasks AS t
INNER JOIN actors AS a ON t.actor_id = a.id
INNER JOIN objects AS o ON t.object_id = o.id 
;

Then just

SELECT * FROM foo WHERE tsv @@ plainto_tsquery('foo bar');

Denormalizing the table

This can take a lot of forms, you've got this right though..

Redesign

Searching everything in a fuzzy fashion like this is a losing game. Even this knock off of Dungeon and Dragons meets Yahoo Answers has rules.

enter image description here

It becomes a lot easier to generate a query when you introduce syntax likes [text] for tagging, and is:answer to search just answers, rather than rebuilding Google and normalized indexes.

5
  • 2
    I guess, the materialized view wouldn't differ much from the denormalized table (as shown in my question), since it is, essentially a table. And you can't even regenerate part of it, only in full (REFRESH MATERIALIZED VIEW). As for the special syntax, - that will not fly in our case, I am afraid.
    – shylent
    Feb 16, 2017 at 16:33
  • @shylent unfortunately, there is no easy way to do this, nor will there ever be. You just can't grep the database. What you have works. If you want it to work faster, you have to look at a different solution. Feb 16, 2017 at 17:56
  • That's, actually, exactly what I thought even before asking the question: there is no easy way to do what I want. But, since I am not an expert, I thought, I might've missed something!
    – shylent
    Feb 16, 2017 at 21:47
  • @shylent considering accepting this answer or clarifying what you're looking for as acceptable. Feb 16, 2017 at 21:53
  • @EvanCarroll you are dumb Jul 15 at 12:19
8

This looks like a fairly generic full-text search problem in a relational database.

Your prediction that updates in actors or objects would be troublesome in a denormalized structure looks spot-on. Better exhaust the possibilities with the normalized schema before thinking of denormalizing, especially since your tables are modest in size.

I'd suggest to FT-index all textual fields separately, and use a query engineered on the idea of querying all of them and combining results with the OR logical conjunction through an UNION.

Indexing (with the simple the text configuration for exact and language-agnostic matching, but use whatever is best in your case provided it's the same as in the query):

create index idx1 on objects using gin(to_tsvector('simple', name||' '||address));
create index idx2 on tasks using gin(to_tsvector('simple', description));
create index idx3 on actors using gin(to_tsvector('simple', name));

Searching for word1 or word2 anywhere in the indexed expressions :

WITH
 words(w) AS (VALUES ('word1'), ('word2')),
 matching_objects(id) as (select o.* from objects as o, words where to_tsquery('simple',w) @@ to_tsvector('simple', o.name||' '||o.address)),
 matching_tasks as (select t.* from tasks as t, words where to_tsquery('simple',w) @@ to_tsvector('simple', t.description)),
 matching_actors as (select a.* from actors as a, words where to_tsquery('simple',w) @@ to_tsvector('simple', a.name))
SELECT * FROM (
 SELECT t.id, t.description, a.name as actor_name, o.name as object_name
   FROM matching_tasks AS t JOIN actors AS a ON t.actor_id = a.id JOIN objects AS o ON t.object_id = o.id
UNION
  SELECT t.id, t.description, a.name as actor_name, o.name as object_name
    FROM tasks AS t JOIN matching_actors AS a ON t.actor_id = a.id JOIN objects AS o ON t.object_id = o.id
UNION
  SELECT t.id, t.description, a.name as actor_name, o.name as object_name
    FROM tasks AS t JOIN actors AS a ON t.actor_id = a.id JOIN matching_objects AS o ON t.object_id = o.id
) AS result;

Searching for word1 AND word2 in the same field would work by replacing

 words(w) AS (VALUES ('word1'), ('word2'))

with

 words(w) AS (VALUES ('word1 & word2'))

If word1 AND word2 must be present simultaneously in the same "task" (including joined tables) but not necessarily in the same field, it should be workable by adding a GROUP BY step on top of the above, filtering out the results that don't have exactly N hits when N words are searched for.

The query becomes:

WITH
 words(w) AS (VALUES ('word1'), ('word2')),
 matching_objects as (select w, o.* from objects as o, words where to_tsquery('simple',w) @@ to_tsvector('simple', o.name||' '||o.address)),
 matching_tasks as (select w,t .* from tasks as t, words where to_tsquery('simple',w) @@ to_tsvector('simple', t.description)),
 matching_actors as (select w, a.* from actors as a, words where to_tsquery('simple',w) @@ to_tsvector('simple', a.name))
SELECT id FROM (
 SELECT w, t.id
   FROM matching_tasks AS t JOIN actors AS a ON t.actor_id = a.id JOIN objects AS o ON t.object_id = o.id
UNION
  SELECT w, t.id
    FROM tasks AS t JOIN matching_actors AS a ON t.actor_id = a.id JOIN objects AS o ON t.object_id = o.id
UNION
  SELECT w, t.id
    FROM tasks AS t JOIN actors AS a ON t.actor_id = a.id JOIN matching_objects AS o ON t.object_id = o.id
) AS r GROUP BY id HAVING count(*)=(select count(*) FROM words);

The fact that UNION deduplicates the tuples takes care of filtering cases when the same word is found among different subqueries of the UNION construct.

This query produces only IDs of tasks. They'd need to be joined against actors and objects again to get back the columns that need to be displayed or returned.

7
  • 1
    Thanks for the ideas! However, I see a problem with your suggestion: if we index textual fields separately, it is easy to search for "any" of the search terms, but impossible to search for "all" of them (at least I don't see a way, that will utilize the created indices). Think of it like that: if the user enters "word1" and is not satisfied with results, he is going to enter "word2" (so that the search query becomes "word1 word2") to narrow the search, not to broaden it.
    – shylent
    Feb 16, 2017 at 21:42
  • Currently your question says: the task is a "match" if each search term occurs at least once.... Please expand it with all the search modes you're interested in. Feb 16, 2017 at 22:30
  • But.. "each term occurs at least once" means, that every term must participate in a match, or, in other words "we must match all terms". I guess, my question is just poorly worded. Sorry for that.
    – shylent
    Feb 16, 2017 at 22:33
  • @shylent: OK, I just edited the answer in that sense. Unless I'm missing something, I don't see this as significantly different in the solution. Feb 16, 2017 at 22:37
  • Doesn't really take into account stop words, if for example you search for 'I am an automobile', it will return nothing, because stop words will not have a match
    – xtrinch
    Jan 25, 2021 at 16:00
-5

Are you using the right technology? No, for example a Solr/Lucene index will do it much better. If you need, you could do that on the database side (user supplied index)

And you have not thought about query and data imperfections, for example return "house", "houe", "gouse" and similar misspellings, let alone synonyms or using hierarchies of search terms for queries. Soon your users will ask for faceted search...

Going down here is a dangerous and unsustainable route. If you can, you should avoid it.

2
  • Perhaps, you are right. Our plan was to, kind of, dip our toes into this feature (full text search), since we are not quite sure if it will work for users at all. So we wanted to avoid making drastic infrastructure changes (such as introducing solr / elasticsearch / whatever into the stack), hide the implementation behind the API and see how it works or if it works at all.
    – shylent
    Feb 16, 2017 at 16:12
  • 5
    1. Great, now he has to sync everything between PG and Solr. 2. you can use pg_trgm for misspellings. 3. PG handles multi-word synonyms far better than Solr does Feb 16, 2017 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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