<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>

[{'answer_id': 48480, 'author': 'Slartibartfast', 'author_id': 4433, 'author_profile': 'https://Stackoverflow.com/users/4433', 'pm_score': 4, 'selected': False, 'text': '<p>I don\'t see a problem with a straightforward solution: Table for items, table for tags, crosstable for "tagging"</p>\n\n<p>Indices on cross table should be enough optimisation. Selecting appropriate items would be  </p>\n\n<pre><code>SELECT * FROM items WHERE id IN  \n    (SELECT DISTINCT item_id FROM item_tag WHERE  \n    tag_id = tag1 OR tag_id = tag2 OR ...)  \n</code></pre>\n\n<p>AND tagging would be  </p>\n\n<pre><code>SELECT * FROM items WHERE  \n    EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag1)  \n    AND EXISTS (SELECT 1 FROM item_tag WHERE id = item_id AND tag_id = tag2)  \n    AND ...\n</code></pre>\n\n<p>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.</p>\n'}, {'answer_id': 48481, 'author': 'Brad Bruce', 'author_id': 5008, 'author_profile': 'https://Stackoverflow.com/users/5008', 'pm_score': 3, 'selected': False, 'text': "<p>The easiest method is to create a <strong>tags</strong> table.<br>\n<code>Target_Type</code> -- in case you are tagging multiple tables<br>\n<code>Target</code> -- The key to the record being tagged<br>\n<code>Tag</code> -- The text of a tag </p>\n\n<p>Querying the data would be something like:</p>\n\n<pre><code>Select distinct target from tags   \nwhere tag in ([your list of tags to search for here])  \nand target_type = [the table you're searching]\n</code></pre>\n\n<p><strong>UPDATE</strong><br>\nBased on your requirement to AND the conditions, the query above would turn into something like this</p>\n\n<pre><code>select target\nfrom (\n  select target, count(*) cnt \n  from tags   \n  where tag in ([your list of tags to search for here])\n    and target_type = [the table you're searching]\n)\nwhere cnt = [number of tags being searched]\n</code></pre>\n"}, {'answer_id': 48485, 'author': 'FlySwat', 'author_id': 1965, 'author_profile': 'https://Stackoverflow.com/users/1965', 'pm_score': 0, 'selected': False, 'text': "<p>You won't be able to avoid joins and still be somewhat normalized.</p>\n\n<p>My approach is to have a Tag Table.</p>\n\n<pre><code> TagId (PK)| TagName (Indexed)\n</code></pre>\n\n<p>Then, you have a TagXREFID column in your items table.</p>\n\n<p>This TagXREFID column is a FK to a 3rd table, I'll call it TagXREF:</p>\n\n<pre><code> TagXrefID | ItemID | TagId\n</code></pre>\n\n<p>So, to get all tags for an item would be something like:</p>\n\n<pre><code>SELECT Tags.TagId,Tags.TagName \n     FROM Tags,TagXref \n     WHERE TagXref.TagId = Tags.TagId \n         AND TagXref.ItemID = @ItemID\n</code></pre>\n\n<p>And to get all items for a tag, I'd use something like this:</p>\n\n<pre><code>SELECT * FROM Items, TagXref\n     WHERE TagXref.TagId IN \n          ( SELECT Tags.TagId FROM Tags\n                WHERE Tags.TagName = @TagName; )\n     AND Items.ItemId = TagXref.ItemId;\n</code></pre>\n\n<p>To AND a bunch of tags together, You would to modify the above statement slightly to add AND Tags.TagName = @TagName1 AND Tags.TagName = @TagName2 etc...and dynamically build the query.</p>\n"}, {'answer_id': 48489, 'author': 'Zizzencs', 'author_id': 686, 'author_profile': 'https://Stackoverflow.com/users/686', 'pm_score': 3, 'selected': False, 'text': '<p>You might want to experiment with a not-strictly-database solution like a <a href="http://en.wikipedia.org/wiki/Content_repository_API_for_Java" rel="nofollow noreferrer">Java Content Repository</a> implementation (e.g. <a href="http://en.wikipedia.org/wiki/Apache_Jackrabbit" rel="nofollow noreferrer">Apache Jackrabbit</a>) and use a search engine built on top of that like <a href="http://en.wikipedia.org/wiki/Apache_Lucene" rel="nofollow noreferrer">Apache Lucene</a>.</p>\n\n<p>This solution with the appropriate caching mechanisms would possibly yield better performance than a home-grown solution.</p>\n\n<p>However, I don\'t really think that in a small or medium-sized application you would require a more sophisticated implementation than the normalized database mentioned in earlier posts.</p>\n\n<p>EDIT: with your clarification it seems more compelling to use a JCR-like solution with a search engine. That would greatly simplify your programs in the long run.</p>\n'}, {'answer_id': 48558, 'author': 'digiguru', 'author_id': 5055, 'author_profile': 'https://Stackoverflow.com/users/5055', 'pm_score': 0, 'selected': False, 'text': '<p>What I like to do is have a number of tables that represent the raw data, so in this case you\'d have</p>\n\n<pre><code>Items (ID pk, Name, &lt;properties&gt;)\nTags (ID pk, Name)\nTagItems (TagID fk, ItemID fk)\n</code></pre>\n\n<p>This works fast for the write times, and keeps everything normalized, but you may also note that for each tag, you\'ll need to join tables twice for every further tag you want to AND, so it\'s got slow read. </p>\n\n<p>A solution to improve read is to create a caching table on command by setting up a stored procedure that essentially creates  new table that represents the data in a flattened format...</p>\n\n<pre><code>CachedTagItems(ID, Name, &lt;properties&gt;, tag1, tag2, ... tagN)\n</code></pre>\n\n<p>Then you can consider how often the Tagged Item table needs to be kept up to date, if it\'s on every insert, then call the stored procedure in a cursor insert event. If it\'s an hourly task, then set up an hourly job to run it. </p>\n\n<p>Now to get really clever in data retrieval, you\'ll want to create a stored procedure to get data from the tags. Rather than using nested queries in a massive case statement, you want to pass in a single parameter containing a list of tags you want to select from the database, and return a record set of Items. This would be best in binary format, using bitwise operators.</p>\n\n<p>In binary format, it is easy to explain. Let\'s say there are four tags to be assigned to an item, in binary we could represent that </p>\n\n<pre><code>0000\n</code></pre>\n\n<p>If all four tags are assigned to an object, the object would look like this...</p>\n\n<pre><code>1111\n</code></pre>\n\n<p>If just the first two...</p>\n\n<pre><code>1100\n</code></pre>\n\n<p>Then it\'s just a case of finding the binary values with the 1s and zeros in the column you want. Using SQL Server\'s Bitwise operators, you can check that there is a 1 in the first of the columns using very simple queries.</p>\n\n<p>Check this link to find out <a href="http://cas.sdss.org/dr6/en/help/docs/sql_help.asp" rel="nofollow noreferrer">more</a>.</p>\n'}, {'answer_id': 48590, 'author': 'Portman', 'author_id': 1690, 'author_profile': 'https://Stackoverflow.com/users/1690', 'pm_score': 0, 'selected': False, 'text': '<p>To paraphrase what others have said: the trick isn\'t in the <strong>schema</strong>, it\'s in the <strong>query</strong>.</p>\n\n<p>The naive schema of Entities/Labels/Tags is the right way to go. But as you\'ve seen, it\'s not immediately clear how to perform an AND query with a lot of tags.</p>\n\n<p>The best way to optimize that query will be platform-dependent, so I would recommend re-tagging your question with your RDBS and changing the title to something like "Optimal way to perform AND query on a tagging database".</p>\n\n<p>I have a few suggestions for MS SQL, but will refrain in case that\'s not the platform you\'re using.</p>\n'}, {'answer_id': 48604, 'author': 'chakrit', 'author_id': 3055, 'author_profile': 'https://Stackoverflow.com/users/3055', 'pm_score': 1, 'selected': False, 'text': "<p>I'd second @Zizzencs suggestion that you might want something that's not totally (R)DB-centric</p>\n\n<p>Somehow, I believe that using plain nvarchar fields to store that tags with some proper caching/indexing might yield faster results. But that's just me.</p>\n\n<p>I've implemented tagging systems using 3 tables to represent a Many-to-Many relationship before (Item Tags ItemTags), but I suppose you will be dealing with tags in a lot of places, I can tell you that with 3 tables having to be manipulated/queried simultaneously all the time will definitely make your code more complex.</p>\n\n<p>You might want to consider if the added complexity is worth it.</p>\n"}, {'answer_id': 48652, 'author': 'Troels Arvin', 'author_id': 4462, 'author_profile': 'https://Stackoverflow.com/users/4462', 'pm_score': 6, 'selected': True, 'text': '<p>About ANDing: It sounds like you are looking for the "relational division" operation. <a href="http://www.dbazine.com/ofinterest/oi-articles/celko1" rel="noreferrer">This article</a> covers relational division in concise and yet comprehendible way.</p>\n\n<p>About performance: A bitmap-based approach intuitively sounds like it will suit the situation well. However, I\'m not convinced it\'s a good idea to implement bitmap indexing "manually", like digiguru suggests: It sounds like a complicated situation whenever new tags are added(?) But some DBMSes (including Oracle) offer bitmap indexes which may somehow be of use, because a built-in indexing system does away with the potential complexity of index maintenance; additionally, a DBMS offering bitmap indexes should be able to consider them in a proper when when performing the query plan.</p>\n'}, {'answer_id': 48692, 'author': 'Jeff Atwood', 'author_id': 1, 'author_profile': 'https://Stackoverflow.com/users/1', 'pm_score': 6, 'selected': False, 'text': '<p>Here\'s a good article on tagging Database schemas:</p>\n\n<p><a href="http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/" rel="noreferrer">http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/</a></p>\n\n<p>along with performance tests:</p>\n\n<p><a href="http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/" rel="noreferrer">http://howto.philippkeller.com/2005/06/19/Tagsystems-performance-tests/</a></p>\n\n<p>Note that the conclusions there are very specific to MySQL, which (at least in 2005 at the time that was written) had very poor full text indexing characteristics.</p>\n'}, {'answer_id': 264016, 'author': 'Winston Fassett', 'author_id': 31015, 'author_profile': 'https://Stackoverflow.com/users/31015', 'pm_score': 4, 'selected': False, 'text': '<p>I just wanted to highlight that the article that @Jeff Atwood links to (<a href="http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/" rel="noreferrer">http://howto.philippkeller.com/2005/04/24/Tags-Database-schemas/</a>) is very thorough (It discusses the merits of 3 different schema approaches) and has a good solution for the AND queries that will usually perform better than what has been mentioned here so far (i.e. it doesn\'t use a correlated subquery for each term).  Also lots of good stuff in the comments.</p>\n\n<p>ps - The approach that everyone is talking about here is referred to as the "Toxi" solution in the article.  </p>\n'}, {'answer_id': 4688196, 'author': 'nitinahuja', 'author_id': 575252, 'author_profile': 'https://Stackoverflow.com/users/575252', 'pm_score': 0, 'selected': False, 'text': '<p>A variation to the above answer is take the tag ids, sort them, combine as a ^ separated string and hash them. \nThen simply associate the hash to the item. Each combination of tags produces a new key. To do an AND search simply re-create the hash with the given tag ids and search.\nChanging tags on an item will cause the hash to be recreated. Items with the same set of tags share the same hash key.</p>\n'}]
['https://Stackoverflow.com/questions/48475', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/5035/']