Arbitrary queries on n:m relationship, including "all" and "any"
Is this query any efficient?


No, it is extremely inefficient for multiple reasons.

0. Test schema

Basing my answer on this simplified schema:

CREATE TABLE tag (
  tag_id serial PRIMARY KEY
, tag    text NOT NULL
);

CREATE TABLE task (
  task_id  serial PRIMARY KEY
, task     text NOT NULL
);

CREATE TABLE task_tag (
  task_id    int
, tag_id     int
, PRIMARY KEY (tag_id, task_id)  -- columns in this order
, FOREIGN KEY (task_id) REFERENCES task
, FOREIGN KEY (tag_id)  REFERENCES tag;
);


1. The query is very inefficient

Your original query, adapted to test schema:

SELECT DISTINCT ON (task.task_id) task.*  -- DISTINCT is dead freight
FROM   task, LATERAL (
   SELECT array_agg(tag.tag) AS tags  -- array_agg more expensive than array constructor
   FROM   task_tag 
   JOIN   tag ON task_tag.tag_id = tag.tag_id 
   WHERE  task_tag.task_id = task.task_id 
   GROUP  BY task_tag.task_id  -- redundant noise
   ) tt
WHERE  tt.tags @&gt; array['tag1'::text, 'tag3'::text];  -- or array literal.


What's wrong? For starters:


No reason to add DISTINCT ON. The lateral join only joins to a single row after the aggregation.
An array constructor is cheaper for this simple array aggregation.


Why is array_agg() slower than the non-aggregate ARRAY() constructor?

No need to add GROUP BY, after the WHERE clause already filters one task_id.
Depending on how you call the query, it may be more convenient to pass a single array literal instead of an array constructor.


Equivalent query 1:

SELECT ts.* 
FROM   task ts
JOIN   LATERAL (
   SELECT ARRAY (
      SELECT tg.tag
      FROM   task_tag tt
      JOIN   tag      tg USING (tag_id)
      WHERE  tt.task_id = ts.task_id
      ) AS tags 
   ) tt ON tt.tags @&gt; '{tag1, tag3}'::text[];


But that's still a waste. The LATERAL does more harm than good while all rows have to be aggregated anyway.

Equivalent query 2:

SELECT ts.* 
FROM   task ts
JOIN  (
   SELECT task_id
   FROM   task_tag
   GROUP  BY 1
   HAVING array_agg(tag_id) @&gt; '{1, 3}'::int[];
   ) AS tags USING (task_id);


As you can see, I am not building array of tags, just tag_id. Much more efficient. Resolve your input tags to IDs before you pass them to the query. 

Much faster than before but still extremely inefficient for tables of non-trivial size.

2. The whole approach is very inefficient

The above approach cannot use an index. The dynamically generated array does work with indexes. The predicate comes after the aggregation. 

2.1 MATERIALIZED VIEW for read-only (or mostly) tables

To make it work with an index you would have to add a MATERIALIZED VIEW with readily aggregated tag arrays (or IDs, preferably) per task_id. And a GIN index on the array column. Only good for read-only (or mostly) tables, since the MV is just a snapshot, quickly outdated with writes to the underlying tables.

Related:


Can PostgreSQL index array columns?


The MATERIALIZED VIEW:

CREATE MATERIALIZED VIEW task_tags_mv AS
SELECT task_id, array_agg(tag_id) AS tag_ids
FROM   task_tag
GROUP  BY 1;


Of course, we work with tag_id again, not raw tags. And for integer arrays there are much faster, specialized operator classes and indexes available from the additional module intarray. Related:


GIN index on smallint[] column not used or error “operator is not unique”


So we use this specialized index:

CREATE INDEX task_tags_mv_arr_idx ON task_tags_mv USING GIN(tag_ids gin__int_ops);


And this query:

SELECT ts.* 
FROM   task ts
JOIN   task_tags_mv mv USING (task_id)
WHERE  mv.tag_ids @&gt; '{1, 3}'::int[];  -- uses intarray operator


This is fast, now. And the same setup works for matching ANY tag, using the overlap operator &amp;&amp; instead of the contains operator:

...
WHERE  mv.tag_ids &amp;&amp; '{1, 3}'::int[];  -- uses intarray operator


2.2 Generic queries

Else you need completely different query techniques that can work with indexes. Yper* pointed to a related question on SO in his comment:


How to filter SQL results in a has-many-through relation


You specific requirement is to make is simple to provide a list of tags to a generic query.

A recursive CTE is one way without dynamic SQL. (There are many others.) Nested in an SQL function with VARIADIC parameter for convenience:

CREATE OR REPLACE FUNCTION f_tasks_with_tags(VARIADIC _tags text[])
  RETURNS SETOF task AS
$func$
   WITH RECURSIVE cte AS (
      SELECT task_id, 1 AS idx
      FROM   task_tag
      WHERE  tag_id = (SELECT tag_id FROM tag WHERE tag = _tags[1])

      UNION
      SELECT task_id, c.idx + 1
      FROM   cte c
      JOIN   task_tag tt USING (task_id)
      WHERE  tag_id = (SELECT tag_id FROM tag WHERE tag = _tags[c.idx + 1])
      )
   SELECT t.*
   FROM   cte  c
   JOIN   task t USING (task_id)
   WHERE  c.idx = array_length(_tags, 1)
$func$  LANGUAGE sql STABLE;


Call:

SELECT * FROM f_tasks_with_tags('tag1', 'tag3'); -- add any number of tags


About VARIADIC (follow links for more):


Passing multiple values in single parameter


Depending on value frequencies, it helps performance (a lot) to pass sparse tags first. It is cheaper to eliminate non-qualifying tasks early.

Another potentially even faster approach: dynamic SQL. Build and execute a query like:

SELECT t.*
FROM  (
   SELECT task_id
   FROM   task_tag t1
   JOIN   task_tag t2 USING (task_id)
-- JOIN   task_tag t3 USING (task_id)
-- more ...
   WHERE  t1.tag_id  = 1
   AND    t2.tag_id  = 3
-- AND    t3.tag_id  = 789
-- more ...
   ) tt
JOIN  task t USING (task_id);


In this query, Postgres can optimize the sequence of joins automatically to evaluate sparse tags first - up to a maximum of join_collapse_limit tables. See:


Postgres JOIN conditions vs WHERE conditions


There are many code examples for building queries dynamically in a plpgsql function on this site. Try a search.

SQL Fiddle (also has intarray module).

dbfiddle here