Return to Answer

ALTER TABLE message
  DROP CONSTRAINT message_name_key  -- actual constraint name here!
, ADD  CONSTRAINT message_name_name_id_key UNIQUE (name) INCLUDE (name_id)
;

With these 3 indexes in place, and if your tables are vacuumed enough, both queries can make do with index-only scans exclusively. Then we are talking a few ms even for huge tables, or even below 1 ms execution time.

ALTER TABLE message
  DROP CONSTRAINT message_name_key  -- actual constraint name here!
, ADD  CONSTRAINT message_name_id_key UNIQUE (name) INCLUDE (id)
;

With these 3 indexes in place, and if your tables are vacuumed enough, both queries can make do with index-only scans exclusively. Then it takes a few ms at most, even for huge tables, or even below 1 ms execution time.

--

For the given specifications, it won't get faster than this::

PREPARE q1(text[]) AS
SELECT p.package_id
FROM   message m
JOIN   package_to_message p ON p.message_id = m.id
WHERE  m.name = ANY($1)
GROUP  BY 1
HAVING count(*) = cardinality($1)
AND    NOT EXISTS (  -- no other!
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p.package_id
   AND    p0.message_id <> ALL($1)
   );

For the given specifications, it won't get faster than this:

PREPARE q1(text[]) AS
WITH m AS (                              -- translate names to IDs
   SELECT id AS message_id 
   FROM   message
   WHERE  name = ANY($1)
   )
SELECT p.package_id
FROM   m
JOIN   package_to_message p USING (message_id)
GROUP  BY 1
HAVING count(*) = cardinality($1)        -- length of array
AND    NOT EXISTS (                      -- no other message
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p.package_id
   AND    p0.message_id <> ALL(TABLE m)  -- m holds IDs
   );

My queries assume that you pass distinct message names (no duplicates). Plus, message.name is defined UNIQUE.

Note how ANY and ALL accept an array or a set. See:

• How to use ANY instead of IN in a WHERE clause?

About the short syntax TABLE m:

• Is there a shortcut for SELECT * FROM?

Indexes & performance

Index 1

The UNIQUE constraint on table message covers the lookup nicely.
If performance is crucial (and you meet preconditions for index-only scans) a covering index would be slightly better:

ALTER TABLE message
  DROP CONSTRAINT message_name_key  -- actual constraint name here!
, ADD  CONSTRAINT message_name_name_id_key UNIQUE (name) INCLUDE (name_id)
;

See:

• Does a query with a primary key and foreign keys run faster than a query with just primary keys?
• Any pitfalls/benefits of creating PK with include(..) in PostgreSQL?

Index 2

The PRIMARY KEY on package_to_message(message_id, package_id) provides the perfect index for the next step.

Index 3

Ideally, you add another index on package_to_message(package_id, message_id) for the final step. See:

• Is a composite index also good for queries on the first field?

With these 3 indexes in place, and if your tables are vacuumed enough, both queries can make do with index-only scans exclusively. Then we are talking a few ms even for huge tables, or even below 1 ms execution time.

The key word here is "relational division".

For the given specifications, it won't get faster than this::

SELECT package_id
FROM   package_to_message p1
JOIN   package_to_message p2 USING (package_id)
JOIN   package_to_message p3 USING (package_id)
WHERE  p1.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_1')
AND    p2.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_2')
AND    p3.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_3')
AND    NOT EXISTS (  -- no other!
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p1.package_id
   AND    p0.message_id NOT IN (p1.message_id, p2.message_id, p3.message_id)
   );

But maybe you need a more generic/dynamic query ...

PREPARE q1(text[]) AS
SELECT p.package_id
FROM   message m
JOIN   package_to_message p ON p.message_id = m.id
WHERE  m.name = ANY($1)
GROUP  BY 1
HAVING count(*) = cardinality($1);

Call:

EXECUTE q1('{message_name_1, message_name_2, message_name_3}');

Related:

• How to filter SQL results in a has-many-through relation
• Using same column multiple times in WHERE clause
• Arbitrary queries on n:m relationship, including "all" and "any"

The key word here is "relational division".

For the given specifications, it won't get faster than this::

SELECT package_id
FROM   package_to_message p1
JOIN   package_to_message p2 USING (package_id)
JOIN   package_to_message p3 USING (package_id)
WHERE  p1.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_1')
AND    p2.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_2')
AND    p3.message_id = (SELECT m.id FROM message m WHERE m.name = 'message_name_3')
AND    NOT EXISTS (  -- no other!
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p1.package_id
   AND    p0.message_id NOT IN (p1.message_id, p2.message_id, p3.message_id)
   );

But maybe you need a more generic/dynamic query ...

PREPARE q1(text[]) AS
SELECT p.package_id
FROM   message m
JOIN   package_to_message p ON p.message_id = m.id
WHERE  m.name = ANY($1)
GROUP  BY 1
HAVING count(*) = cardinality($1)
AND    NOT EXISTS (  -- no other!
   SELECT FROM package_to_message p0
   WHERE  p0.package_id = p.package_id
   AND    p0.message_id <> ALL($1)
   );

Call:

EXECUTE q1('{message_name_1, message_name_2, message_name_3}');

Related:

• How to filter SQL results in a has-many-through relation
• Using same column multiple times in WHERE clause
• Arbitrary queries on n:m relationship, including "all" and "any"