How slow is DISTINCT?

Question

I have the option of writing two different formats for a database structure:

Article
-------
ArticleID int FK

Article_Tags
------------
ArticleTagID int FK
ArticleID int FK
TagText varchar(50)

or

Article
-------
ArticleID int PK

Article_Tags
------------
ArticleTagID int PK
ArticleID int FK
TagText varchar(50) FK

Tag
---
TagText varchar(50) PK

If I want a list of all tags in the database, I could use:

select distinct tagtext from article_tags

or:

select tagtext from tag

The first situation is pretty easy. Maybe it would speed up if i indexed it properly. The second is a little harder because I have to constantly delete tags with no joins. Imagine a pretty large system, which would be better.

Answer 1

Option 2 with some modifications. Assuming you're limiting input to the values contained in the tag table you're then able to perform two different queries for different purposes.

The first query will give you a unique list of all currently USED tags.

The second query will give you all possible tags that can be used, including those that have not yet been used.

You would be better to use a tag ID and set up a relationship between the tag and article_tags tables. This would make option two more efficient as the index would simply be an integer rather than a string.

Answer 2

I would go with whichever solution will result in the best/cleanest design for your application. If you need to attach data directly to a tag then a separate table (i.e. a more normalised solution) would be the correct one.

I would warn against worrying too much about the performance difference in the 2 proposed solutions, if indexed, the difference is likely to be insignificant (both are fairly common use cases and can be easily optimised using standard db techniques). Making a decision between the 2 presented options on the basis of performance sounds like a premature optimisation.

Answer 3

I would go with

Article
-------
ArticleID int PK

Article_Tags
------------
ArticleTagID int PK
ArticleID int FK
TagId int FK

Tag
---
TagId int identity(1,1) PK
TagText varchar(50)

There really is no reason to denormalize this from get go. (your first and second versions are not normalized)

Having tags in a separate table is fine, and getting the unique tags is cleaner without that distinct statement.

Performance wise if any of the 3 options are going to perform pretty much the same provided the correct indexing is applied.

Answer 4

To answer the basic question from the title: a DISTINCT usually means sorting the data. Depending on indices, the structure of the query and the amount of data returned this might be gratis (proper index on tagtext, ORDER BY tagtext, small return set) or not (missing index, order irrelevant, massive return set).

Answer 5

The overhead of maintaining two tables would be very unlikely to be a reasonable tradeoff for messing up a simple design.

It would be simple enough to test it both ways if you're really worried about it, but from my extensive experience there's no question this is true.