Filter out rows where any value is not unique

Question

I am self joining on a table and get the following result:

+----+----+----+----+----+----+----+----+----+
| id | s1 | s2 | s3 | s4 | s5 | s6 | s7 | s8 |
+----+----+----+----+----+----+----+----+----+
|  1 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
|  2 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  7 |
|  3 | 10 | 11 | 12 | 11 | 13 | 11 |  8 |  1 |
|  4 |  4 |  2 |  3 |  1 | 10 | 11 | 17 | 13 |
|  5 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |
+----+----+----+----+----+----+----+----+----+

How do I filter out the rows where numbers in s1 to s8 are not unique, such as rows 2, 3, and 5?

Basic filter would be:

SELECT t1.id, t1.col as s1, t2.col as s2, t3.col as s3, t4.col as s4, t5.col as s5, t6.col as s6, t7.col as s7, t8.col as s8
FROM [...]
WHERE s1 NOT IN (s2, s3, s4, s5, s6, s7, s8),
AND s2 NOT IN (s3, s4, s5, s6, s7, s8),
AND s3 NOT IN (s4, s5, s6, s7, s8),
AND s4 NOT IN (s5, s6, s7, s8),
AND s5 NOT IN (s6, s7, s8),
AND s6 NOT IN (s7, s8),
AND s7 <> s8

where I check if every column is different from the others which for these 8 columns require 28 conditions (simplified using NOT IN), what is way too much.
Can I do that in an efficient way?

More details

CREATE TABLE superobject__object (
    superobject_id integer NOT NULL,
    path smallint NOT NULL,
    set smallint NOT NULL,
    object_id integer NOT NULL,
    color_id integer NOT NULL,
    CONSTRAINT superobject_object__pk PRIMARY KEY (superobject_id,path,object_id,color_id)
);
ALTER TABLE superobject__object ADD CONSTRAINT superobject_object__superobject_id_fk FOREIGN KEY (superobject_id) REFERENCES superobject (id);

ALTER TABLE superobject__object ADD CONSTRAINT superobject_object__object_id_fk FOREIGN KEY (object_id) REFERENCES object (id);

ALTER TABLE superobject__object ADD CONSTRAINT superobject_object__color_id_fk FOREIGN KEY (color_id) REFERENCES color (id);

It's combinatorial data. It's quite complicated to make it simple.
Basically, a superobject is made of objects which 1/ can have dependencies 2/ can be grouped together as set of options.
Think of a car you can buy green, yellow or red (set of options). If you buy the red paint, you can choose bonus hubcaps for a price.
Now, if you search for cars with green paint and hubcaps, you can't find that superobject because hubcaps have a dependency which is the red paint.
I solved this problem with the aforementioned table.
The dependencies (hierarchy) being not deep at all, I can afford to cut the superobjects into "paths".
For my car example, I have:

superobject_1 path_1 object_green_paint
superobject_1 path_1 object_yellow_paint
superobject_1 path_1 object_common_object
superobject_1 path_2 object_red_paint
superobject_1 path_2 object_hubcaps
superobject_1 path_2 object_common_object

As for the set of options, I give every object of a path a different integer and group the options together with the same integer:

superobject_1 path_1 set_1 object_green_paint
superobject_1 path_1 set_1 object_yellow_paint
superobject_1 path_1 set_2 object_common_object
superobject_1 path_2 set_1 object_red_paint
superobject_1 path_2 set_2 object_hubcaps
superobject_1 path_2 set_3 object_common_object

Why am I doing that instead of giving every combination its own path? Because the combinations grow exponentially for every set of options added.

Then, I search with:

SELECT s1.superobject_id as id, s1.set, s2.set, s3.set, s4.set, s5.set, s6.set, s7.set, s8.set FROM superobject__object s1
JOIN superobject__object s2 ON (s1.superobject_id, s1.path) = (s2.superobject_id, s2.path)
JOIN superobject__object s3 ON (s1.superobject_id, s1.path) = (s3.superobject_id, s3.path)
...
JOIN superobject__object s8 ON (s1.superobject_id, s1.path) = (s8.superobject_id, s8.path)
WHERE s1.object_id IN (SELECT id FROM object WHERE <filter_1>)
AND s2.object_id IN (SELECT id FROM object WHERE <filter_2>)
AND s3.object_id IN (SELECT id FROM object WHERE <filter_3>)
...
AND s8.object_id IN (SELECT id FROM object WHERE <filter_8>)

which gives me something like the first table. I then proceed to filter out the rows where you have objects from the same set (of options) as you can't find cars with green AND yellow paint at the same time as one option exclude the others.

Answer 1

Short and simple

If your columns are all integer (int4 !), NOT NULL, and you are free to install the additional module intarray (or already have it), there is a very simple solution:

WHERE uniq(sort(ARRAY[s1, s2, s3, s4, s5, s6, s7, s8]))
         = sort(ARRAY[s1, s2, s3, s4, s5, s6, s7, s8])

Or, while you know the number of columns, the simpler version you found yourself:

WHERE # uniq(sort(ARRAY[s1, s2, s3, s4, s5, s6, s7, s8])) = 8

Fast

The main challenge with this kind of query is that the many joins can produce an exorbitant number of rows (before filtering). It's typically more efficient to filter rows early. The simple predicate above filters after joining all relations. Chances are, there is a more efficient (albeit more verbose) query. Your original approach being a hot contender.

For all I know, after your question update, this might be the faster:

SELECT id, s1, s2, s3, s4, s5, s6, s7, s8
FROM  (
   SELECT superobject_id AS id, path, set AS s1
   FROM   superobject__object JOIN object o ON o.id = s.object_id AND <filter_1>)
   ) s1
JOIN  (
   SELECT superobject_id AS id, path, set AS s2
   FROM   superobject__object JOIN object o ON o.id = s.object_id AND <filter_2>)
   ) s2 USING (id, path)
...
JOIN  (
   SELECT superobject_id AS id, path, set AS s8
   FROM   superobject__object JOIN object o ON o.id = s.object_id AND <filter_8>)
   ) s8 USING (id, path)
WHERE  s2 <> s1
AND    s3 NOT IN (s1, s2)
...
AND    s8 NOT IN (s1, s2, s3, s4, s5, s6, s7);

Or still:

...
WHERE # uniq(sort(ARRAY[s1, s2, s3, s4, s5, s6, s7, s8])) = 8

The most substantial change versus your version is that I replaced all object_id IN (subquery) clauses with joins. The rationale being what I happened to post just yesterday:

• When using a CTE, why do I need to use SELECT twice in order to filter on values from an auxiliary statement?

With then 16 tables in the FROM clause we now surpass the default of 8 in join_collapse_limit from_collapse_limit . Past that limit Postgres stops trying to flatten all join items and evaluate every possible order of joins (because the number of combinations gets out of hand and planning becomes too expensive). So it becomes increasingly important to move the most selective filters to the top of the FROM clause. Read this chapter in the manual for details:

• "Controlling the Planner with Explicit JOIN Clauses"

Either selectivity is hard to predict for you and Postgres typically comes up with better estimates based on available statistics. That can't work perfectly, but still typically better than manual intervention.

Or you know better which filters are most selective. Then you'll want to define the order or joins manually to get the best plan and save on planning time.

I rearranged the FROM clause into 8 subqueries. Now you can play with the two mentioned settings to optimize query plans (and planning time). You'll want to set these locally, like:

BEGIN;
SET LOCAL from_collapse_limit = 1;
SET LOCAL join_collapse_limit = 1;

SELECT ...

ROLLBACK;  -- or COMMIT;

The USING clause mainly shortens the syntax. You may as well spell it out with ON.

Also important: I start with s2 <> s1 not s1 NOT IN (s2, s3, s4, s5, s6, s7, s8) to stay in sync with the order of joins. But that may constrain the order of FROM items. So while the best order of joins is unclear, the alternative short filter may still be better.

Depending on cardinalities and what exactly is in your filters, there may be room for more optimization. But we have well left the domain of simple questions in a public forum and entered into the territory of paid consulting work ...

Related:

• Complex view becomes slow when adding ORDER BY in outer query with small LIMIT
• Postgres JOIN conditions vs WHERE conditions