I've a scheme of two main tables: problem and tag and a relation (which is a many to many connector) table: problem_tags which excerpt of them is like:

Problem table:

 id |                name                | rating 
  1 | Special Permutation                |   1600
  2 | Binary String Reconstruction       |   1500
  3 | Special Elements                   |   1500
  4 | Alice, Bob and Candies             |   1300
  5 | K-th Not Divisible by n            |   1200
  6 | Same Parity Summands               |   1200
  7 | Sum of Round Numbers               |    800
  8 | Skier                              |   1400
  9 | Square?                            |    900

Tag table:

 id |           name            
  1 | constructive algorithms
  2 | dfs and similar
  3 | math
  4 | brute force
  5 | implementation
  6 | two pointers
  7 | binary search
  8 | data structures

Problem tags table:

 problem_id | tag_id 
          1 |      1
          2 |      1
          2 |      2
          2 |      3
          3 |      4
          3 |      5
          3 |      6
          4 |      5
          5 |      3
          5 |      7

My question is how can I filter out problems based on multiple tags, i.e. all problems that are tagged math and binary search and brute force; or all problems that are tagged math but not constructive algorithms; or for a more complex one all problems that are only tagged with math and implementation and nothing else?

Currently I've come up with something like this:

  1. Find all problem's ids that are tagged math (joining tag and problem_tags table)
  2. Find all problem's ids that are tagged binary search
  3. Find all problem's ids that are tagged brute force
  4. Get intersection of all above ids
  5. Select problems where their ids is in the above intersection

But my solution lacks when it reaches the second example (only tagged with selected tags) and I think it's not the most optimal and SQL-ish way for doing it.


I had just asked that on a different forum. The best solution for a 3rd Normal Form schema design was to select all that is needed in the linking table and compare the Cardinality (count) of the matching results.

The other forum was for Oracle. The answer you seek is the PostgreSQL version of this post: https://community.oracle.com/message/15613817#15613817

-- copy paste from original post
-- Oracle version
select *     
from my_recipes rp    
where rp.recipe_id  in  
    select tg.recipe_id     
    from my_recipe_tags tg    
    where tg.tag_id in    (
                            -- expands string '1:2:3' into a table w/ 3 row    
                            select to_number(regexp_substr(:p_search_tags,'[^:]+', 1, level) )    
                            from  dual    
                            connect by regexp_substr(:p_search_tags, '[^:]+', 1, level) is not null    
    group by tg.recipe_id                         
                      -- counts cardinality of Tags in search
    having count(*) = regexp_count(:p_search_tags, '[^:]+')                               
) ;

Untested (needs to be fixed)

select *
where p.id in (
    select pt.problem_id
    from PROBLEM_TAGS pt
        join TAGS t on pt.tag_id = t.tag_id
    where t.name in ('math','binary search', 'brute force') -- should be from a CTE
    group by pt.problem_id
    having count(*) = 3 -- count(*) from CTE

For the 2nd version, add AND p.id NOT IN clause.

For the 3rd version add a filter that ensures pt.problem_id has the exact cardinality of the queried tags.

and p.id in (
    select pt.problem_id
    from PROBLEM_TAGS pt
    group by pt.problem_id
    having count(*) = 2 -- you have two tags for 3rd one
                        -- you should pull Cardinality from CTE also
| improve this answer | |
  • I'm not that much of an expert in SQL so I'll appreciate if you could map your solution to my asked schema. – Masked Man May 20 at 22:33
  • @MaskedMan - I need the CREATE TABLE and INSERT statements to test. If you can set the schema up on db fiddle, I can ensure the SQL statements actually work. Edit your original post and add the link, please. thanks. – Michael Kutz May 20 at 22:58
  • I think it's the solution that I'm looking for but 2 issues here, First: what is the purpose of having count(*) = 3 after the group by part, could you explain it a bit? cause when I changed it, the result set changed, I have some guesses but not sure. Second: in the second code snippet in join TAGS t on pt.tag_id = t.tag_id change the t.tag_id to t.id as Tag table has id and not tag_id ;). – Masked Man May 21 at 0:22
  • I'll appreciate if you answer my previous comment. – Masked Man May 21 at 23:46
  • @MaskedMan - 3 is the Cardinality of the Tags you are querying. It should be something like ( select count(*) from list_of_must_have_tags ). I don't know PostgreSQL syntax that well to demonstrate that concept. Having a link to DB Fiddle would be helpful. ;) – Michael Kutz May 22 at 12:57

Your Answer

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

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