<p>How would you design a database to support the following tagging features:</p>

<ul>
<li>items can have a large number of tags</li>
<li>searches for all items that are tagged with a given set of tags must be quick (the items must have ALL tags, so it's an AND-search, not an OR-search)</li>
<li>creating/writing items may be slower to enable quick lookup/reading</li>
</ul>

<p>Ideally, the lookup of all items that are tagged with (at least) a set of n given tags should be done using a single SQL statement. Since the number of tags to search for as well as the number of tags on any item are unknown and may be high, using JOINs is impractical.</p>

<p>Any ideas?</p>

<hr>

<p>Thanks for all the answers so far.</p>

<p>If I'm not mistaken, however, the given answers show how to do an OR-search on tags. (Select all items that have one or more of n tags). I am looking for an efficient AND-search. (Select all items that have ALL n tags - and possibly more.)</p>

I don't see a problem with a straightforward solution: Table for items, table for tags, crosstable for "tagging"
Indices on cross table should be enough optimisation. Selecting appropriate items would be
```
```
SELECT * FROM items WHERE id IN  
    (SELECT DISTINCT item_id FROM item_tag WHERE  
    tag_id = tag1 OR tag_id = tag2 OR ...)
```
```
AND tagging would be
```
```
SELECT * FROM items WHERE  
    EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag1)  
    AND EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag2)  
    AND ...
```
```
which is admittedly, not so efficient for large number of comparing tags. If you are to maintain tag count in memory, you could make query to start with tags that are not often, so AND sequence would be evaluated quicker. Depending on expected number of tags to be matched against and expectancy of matching any single of them this could be OK solution, if you are to match 20 tags, and expect that some random item will match 15 of them, then this would still be heavy on a database.