List:General Discussion« Previous MessageNext Message »
From:SGreen Date:June 8 2005 2:05pm
Subject:Re: What's the optimal db design choice for my 400 000 entries?
View as plain text  
"Tommy Svensson \(InfoGrafix\)" <tommy@stripped> wrote on 06/07/2005 
04:49:09 PM:

> Hi all you mysql gurus,

> I have 400 000 unique strings where each and every one of these strings 
are
> associated with 1 - 50 (appr.) integer values.

> Now, pretty simple for you guys I guess, but how will I design my
> database to make a search interface against this data as rapid as 
possible?

> My first guess for a table whould be

> TABLE list
> string     int
> =======    =====
> string1    234
> string1    6323
> string1    343
> string2    313
> string2    9055
> ...
> string434  5445
> string434  12
> ...

> 
> But I come to a grinding halt when I realize this table will be 400 000 
rows
> big, times the sum over the number of associated integers for each 
unique
> string... let's say each unique string always have 10 associated 
integers.
> Then we have a table of 400 000 x 10 = 4 000 000 rows. Is this really 
the
> best approach?

> A search would appropriately look like this

> Search: string434

> and produce the following output

> Result: 5445 12.

> I guess the sql could look like this:

> SELECT int FROM list WHERE string = 'string434'

> What would be the optimal select query if I would like to return ints 
for
> strings that begin with say 'str'?

> And what if I wanted to search for strings where I only know the mid 
part or
> the end of the string? How then would a performance stable sql command 
look?

> If the above design suggestion is the optimal one, then I guess the 
internal
> database workings do not contain duplicates of the string values as they 
do
> in the table...? I'm kinda hoping a binary tree is built or something
> similar. Though I read somewhere that in order for the db to optimize 
and
> create btrees and the like, some data must be indexed... but how? I 
can't
> very well make the string column 'primary' since it isn't...?

> Very, very, very interested in hearing what you pros have to say! Thx a 
lot
> for this forum!

> /Tommy


You are correct in your analysis that you would have four million strings 
in your table if you only created one table. The solution to your problem 
is the design technique called "normalization" which in its simplest 
explanation is the process of preventing data duplication.

Create a table for your strings. Since they are all unique, this table 
will top out at 400000 rows.

CREATE TABLE StringMaster (
        id int unsigned auto_increment primary key
        , stringvalue varchar(255)
        , UNIQUE (stringvalue)
);

And a second table to associate the string values with their 1-50 integer 
values

CREATE TABLE StringInteger (
        StringMaster_ID int unsigned not null
        , IntegerValue int not null
        , PRIMARY KEY(StringMaster_ID, IntegerValue)
        , KEY (IntegerValue, StringMaster_ID)
)

The primary key prevents the same integer value from being assigned to the 
same string more than once (in case you don't want that restriction just 
delete the word PRIMARY from the declaration). The second key is a 
"covering key" or "covering index" to do reverse lookups (tell me all of 
the strings associated with the integer 36). The other index will nearly 
double the storage requirements for this table. The payoff is that it will 
make your lookups VERY fast and it really won't take up that much room as 
integer values only use about 4 bytes per value. 

So let's estimate disk space:

StringMaster:
(255 chars + 4 bytes) * 400000 rows = (appx) 103600000 bytes (around 99 
MB) max size

StringIntegers:
8 bytes * 400000 string values * 10 integers per string = 32000000 bytes 
(about 30 MB) data
plus an additional 30 MB or so for the extra index

Even with another index on StringMaster you are looking at less that 250MB 
total. This is trivial for MySQL to handle (even on a P-II with almost no 
memory) and you should get great results.  There are working MySQL 
databases with BILLIONS of entries containing hundreds of gigabytes of 
data and with the right equipment and design, they are performing very 
nicely.

You asked about how to write a query that searches for only part of a 
string. For that I kindly refer you to the excellent manual. It can tell 
you so much more about the LIKE function and the RLIKE function and all of 
the other things MySQL can do with strings than I have time to go over. 
(It's pretty easy once you actually try it out and get a feel for it)

http://dev.mysql.com/doc/mysql/en/string-comparison-functions.html
http://dev.mysql.com/doc/mysql/en/regexp.html

Shawn Green
Database Administrator
Unimin Corporation - Spruce Pine



Thread
What's the optimal db design choice for my 400 000 entries?Tommy Svensson \(InfoGrafix\)8 Jun
  • Re: What's the optimal db design choice for my 400 000 entries?Jeremiah Gowdy8 Jun
  • Re: What's the optimal db design choice for my 400 000 entries?SGreen8 Jun