2

Consider a many-to-many relationship between sources and tags, modeled in the conventional relational manner:

CREATE TABLE sources    (ix INTEGER PRIMARY KEY);
CREATE TABLE tags       (ix INTEGER PRIMARY KEY);
CREATE TABLE sourceTags (source INTEGER REFERENCES sources(ix),
                         tag    INTEGER REFERENCES tags(ix));

If I want to get all sources that have one or more tags, quite a few people (1, 2, 3, 4, 5) are suggesting to instead use an array of foreign keys with an inverse index. Indeed, if we create a materialized view on our data with the corresponding index:

CREATE MATERIALIZED VIEW tagArray AS
SELECT    sources.ix AS source, array_agg(sourcetags.tag) AS tags
FROM      sources
JOIN      sourcetags ON sources.ix = sourcetags.source
GROUP BY  sources.ix;

CREATE INDEX tagArray_tags ON tagArray USING GIN (tags);

then looking for sources with certain tags is blazingly fast;

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM tagArray
WHERE '{1}' <@ tags;

yields

 Aggregate  (cost=9709.89..9709.90 rows=1 width=0) (actual time=63.876..63.876 rows=1 loops=1)
   ->  Bitmap Heap Scan on tagarray  (cost=853.99..9479.57 rows=92127 width=0) (actual time=16.702..51.074 rows=90905 loops=1)
         Recheck Cond: ('{1}'::integer[] <@ tags)
         Heap Blocks: exact=7474
         ->  Bitmap Index Scan on tagarray_tags  (cost=0.00..830.95 rows=92127 width=0) (actual time=15.361..15.361 rows=90905 loops=1)
               Index Cond: ('{1}'::integer[] <@ tags)
 Planning time: 0.121 ms
 Execution time: 63.922 ms

(The timings here are based on a test DB populated with 1M rows and 100 tags, relatively evenly distributed, most sources only one tag, and some two or three.)

Now here is my question: is it possible to get the same performance without changing the DB schema? Some non-options:

  • The materialized view is not really an option because it would need to be refreshed often, which is expensive.
  • We cannot create an index on a non-materialized view.
  • I thought perhaps we create a function to find all sources with a certain tag as an array and then create a function index on that, but of course such a function would not be IMMUTABLE and hence that idea doesn't work either.

The best one I could come up with is also kind of the most obvious (maybe):

CREATE INDEX sourceTags_source_tag ON sourceTags (source, tag); 

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM sources
WHERE EXISTS (SELECT 1 
              FROM sourceTags 
              WHERE sourceTags.source = sources.ix AND sourceTags.tag = 1)

which in my tests (after SET enable_seqscan = OFF; yields)

 Aggregate  (cost=58088.97..58088.98 rows=1 width=0) (actual time=519.252..519.252 rows=1 loops=1)
   ->  Merge Semi Join  (cost=2.56..57860.78 rows=91276 width=0) (actual time=0.085..505.943 rows=90905 loops=1)
         Merge Cond: (sources.ix = sourcetags.source)
         ->  Index Only Scan using sources_pkey on sources  (cost=0.42..30408.42 rows=1000000 width=4) (actual time=0.039..271.176 rows=1000001 loops=1)
               Heap Fetches: 1000001
         ->  Index Only Scan using sourcetags_source_tag on sourcetags  (cost=0.43..23814.24 rows=91276 width=4) (actual time=0.032..50.263 rows=90905 loops=1)
               Index Cond: (tag = 1)
               Heap Fetches: 0
 Planning time: 0.878 ms
 Execution time: 519.332 ms

which isn't terrible but still almost an order of magnitude slower than the array approach.

The other advantage of the array approach is that I can easily write stuff like

SELECT * FROM tagArray WHERE '{2,3}' <@ tags;

instead of

SELECT COUNT(*)
FROM sources
WHERE
    EXISTS (SELECT 1 FROM sourceTags WHERE sourceTags.source = sources.ix AND sourceTags.tag = 2)
AND EXISTS (SELECT 1 FROM sourceTags WHERE sourceTags.source = sources.ix AND sourceTags.tag = 3)

which is not only a lot uglier but also a lot slower.

Arrays aren't typically considered part of a relational database, but I don't think in principle that an array of foreign keys is a bad thing. In practice, however, although there have been some proposals in the past, there is not currently any support for declaring arrays of foreign keys in PostgreSQL, so we would lose all integrity constraints, cascades, etc. On the other hand, the kind of query I am doing would seem to be relatively common -- so what am I missing?

  • Yes, that's one of the blog posts I cite which recommend using an array instead. – edsko Oct 22 '16 at 6:53
  • You can create a foreign key (trigger) for arrays. But I am not sure if that would work in all corner cases or how fast it would be – a_horse_with_no_name Oct 22 '16 at 7:45
  • Related question: How to filter SQL results in a has-many-through relation What indexes are there on the table when you tried the EXISTS and the other queries? – ypercubeᵀᴹ Oct 22 '16 at 9:02
  • I should probably have mentioned that. Apart from the indices created for the primary keys, also used a UNIQUE index on sourceTags (source, tag). – edsko Oct 23 '16 at 4:30
  • Index with arguments in the opposite order (tag, source) yields same performance and query plan. – edsko Oct 23 '16 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.