Efficiently finding unique values in a database table

Question

I've got a database table with a very large amount of rows. This table represents messages that are logged by a system. Each message has a message type and this is stored it it's own field in the table. I'm writing a website for querying this message log. If I want to search by message type then ideally I would want to have a drop down box listing the message types that have come up in the database. Message types may change over time so I can't hard code the types into the drop down. I'll have to do some sort of lookup. Iterating over the entire table contents to find unique message values is obviously very stupid however being stupid in the database field I'm here asking for a better way. Perhaps a separate lookup table which the database occasionally updates listing just the unique message types that I can populate my drop down from would be a better idea.

Any suggestions would be much appreciated.

The platform I'm using is ASP.NET MVC and SQL Server 2005

Answer 1

A separate lookup table with the id of the message type stored in your log. This will reduce the size and increase the efficiency of the log. Also it would Normalize your data.

Answer 2

SELECT  DISTINCT message_type
FROM    message_log

is the most straightforward but not very efficient way.

If you have a list of types that can possibly appear in the log, use this:

SELECT  message_type
FROM    message_types mt
WHERE   message_type IN
        (
        SELECT  message_type
        FROM    message_log
        )

This will be more efficient if message_log.message_type is indexed.

If you don't have this table but want to create one, and message_log.message_type is indexed, use a recursive CTE to emulate loose index scan:

WITH    rows (message_type) AS
        (
        SELECT  MIN(message_type) AS mm
        FROM    message_log
        UNION ALL
        SELECT  message_type
        FROM    (
                SELECT  mn.message_type, ROW_NUMBER() OVER (ORDER BY mn.message_type) AS rn
                FROM    rows r
                JOIN    message_type mn
                ON      mn.message_type > r.message_type
                WHERE   r.message_type IS NOT NULL
                ) q
        WHERE   rn = 1
        )
SELECT  message_type
FROM    rows r
OPTION (MAXRECURSION 0)

Answer 3

Yep, I would definitely go with the separate lookup table. You can then populate it using something like:

INSERT TypeLookup (Type)
SELECT DISTINCT Type
FROM BigMassiveTable

You could then run a top-up job periodically to pull in new types from your main table that don't already exist in the lookup table.

Answer 4

Have you considered an indexed view? Its result set is materialized and persists in storage so that the overhead of the lookup is separated from the rest of whatever you're trying to do.

SQL Server takes care of automagically updating the view when there is a data change which in its opinion would change the contents of the view, so in this respect it's less flexible than Oracle materialized.

Answer 5

The MessageType should be a Foreign Key in the main table to a definition table containing the message type codes and descriptions. This will greatly increase your lookup performance.

Something like

DECLARE @MessageTypes TABLE(
        MessageTypeCode VARCHAR(10),
        MessageTypeDesciption VARCHAR(100)
)

DECLARE @Messages TABLE(
        MessageTypeCode VARCHAR(10),
        MessageValue VARCHAR(MAX),
        MessageLogDate DATETIME,
        AdditionalNotes VARCHAR(MAX)
)

From this design, your lookup should only query MessageTypes

Answer 6

I just wanted to state the obvious: normalize the data.

message_types
message_type | message_type_name

messages
message_id | message_type | message_type_name

Then you can just do without any cached DISTINCT:

For your dropdown

SELECT * FROM message_types

For your retrieval

SELECT * FROM messages WHERE message_type = ? 

SELECT m.*, mt.message_type_name FROM messages AS m
JOIN message_types AS mt
ON ( m.message_type = mt.message_type)

I'm not sure why you would want a cached DISTINCT which you'll have to update, when you can slightly tweak the schema and have one with RI.

Answer 7

Create an index on the message type:

CREATE INDEX IX_Messages_MessageType ON Messages (MessageType)

Then to get a list of unique Message Types, you run:

SELECT DISTINCT MessageType
FROM Messages
ORDER BY MessageType

Because the index is physically sorted in order of MessageType SQL Server can very quickly, and efficiently, scan through the index, picking up a list of unique message types.

It is not bad performing - it's what SQL Server is good at.

---

Admittedly, you can save some space by having a "message types" table. And if you only display a few messages at a time: then the bookmark lookup, as it joins back to the MessageTypes table, won't be a problem. But if you start displaying hundreds or thousands of messages at a time, then the join back to MessageTypes can get pretty expensive, and needless, and it will be faster to have the MessageType stored with the message.

But i would have no problem with creating an index on the MessageType column, and selecting distinct. SQL Server loves that sort of thing. But if you're finding it to be a real load on your server, once you're getting dozens of hits a second, then follow the other suggestion and cache them in memory.

My personal solution would be:

• create the index
• select distinct

and if i still had problems

• cache in memory that expires after 30 seconds

---

As for the normalized/denormalized issue. Normalizing saves space, at the cost of CPU when joins are constantly performed. But the logical point of denoralization is to avoid duplicate data, which can lead to inconsistent data.

Are you planning on changing the text of a message type, which if you stored with the messages you would have to update all rows?

Or is there something to be said for the fact that at the time of the message the message type was "Client response requested"?

Answer 8

As others have said, create a separate table of message types. When you add a record to the message table, check if the message type already exists in the table. If not, add it. In either case, then post the identifier from the message type table into the message table. This should give you normalized data. Yes, it's a little extra time when you add a record, but should be more efficient on retrieval.

If there are a lot more adds then reads and if the "message type" is short, an entirely different approach would be to still create the separate message type table, but don't reference it when doing adds, and only update it lazily, on demand.

Namely, (a) Include a time-stamp in each message record. (b) Keep a list of the message types found as of the last time you checked. (c) Each time you check, search for any new message types added since the last time, as in:

create table temp_new_types as
    (select distinct message_type
    from message
    where timestamp>last_type_check
);

insert into message_type_list (message_type)
select message_type
from temp_new_types
where message_type not in (select message_type from message_type_list);

drop table temp_new_types;

Then store the timestamp of this check somewhere so you can use it the next time around.

Answer 9

The answer is to use 'DISTINCT' and each best solution is different for different sizes of table. Thousands of rows, millions, billions ? more ? This are very different best solutions.