Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have two tables that represent a list of urls and their related word indexes. Here are the table definitions for reference.

desc urllist;
+-------+---------------------+------+-----+---------+----------------+
| Field | Type                | Null | Key | Default | Extra          |
+-------+---------------------+------+-----+---------+----------------+
| id    | bigint(20) unsigned | NO   | PRI | NULL    | auto_increment |
| url   | text                | NO   |     | NULL    |                |
+-------+---------------------+------+-----+---------+----------------+

and

desc wordlocation;
+----------+---------------------+------+-----+---------+-------+
| Field    | Type                | Null | Key | Default | Extra |
+----------+---------------------+------+-----+---------+-------+
| urlid    | bigint(20) unsigned | NO   |     | NULL    |       |
| wordid   | bigint(20) unsigned | NO   |     | NULL    |       |
| location | int(10) unsigned    | NO   |     | NULL    |       |
+----------+---------------------+------+-----+---------+-------+

The software app is a web spider. It crawls a list of urls, extracts those urls, and inserts these into the urllist table. Then, an indexer checks to see what urls have not yet been indexed, and then proceeds to index said urls.

Here is the query I am using to find items in the left table (urllist) that have not yet been indexed in the right table (wordlocation). This query is as suggested on the mysql.com website:

select * from urllist ul 
left join wordlocation wl on ul.id = wl.urlid 
where wl.urlid IS NULL;

As of this writing my test database has only 600 indexed urls, and the wordlocation table has 1.3 million rows. However, my CPU is at 100%, and the longest I've waited to see if the query would complete is a half hour (which, it never did by the way).

To be thorough, here is the explanation of the query:

explain select * from urllist ul left join wordlocation wl on ul.id = wl.urlid where wl.urlid IS NULL;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra                   |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------+
|  1 | SIMPLE      | ul    | ALL  | NULL          | NULL | NULL    | NULL |   50364 |                         |
|  1 | SIMPLE      | wl    | ALL  | NULL          | NULL | NULL    | NULL | 1351371 | Using where; Not exists |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------------------+

I need this query to finish in seconds, not minutes. Also, I'm worried about scalability. I have 40,000 unique urls that are waiting to be added to the index, so how do I take that into consideration with my table and query design? 400,000 urls?

Just a couple notes about my decisions on the current table structure.

I have no intention of stopping at 400,000 urls, but perhaps bigint(20) is a bit overzealous?

Url as text is for more practical reasons. I index a lot of Asian and other foreign language domains which do not appear as their equivalent Kanji or other characters in the database and frequently take more than 255 characters.

I'm using MySQL. I'm definitely open to suggestions as to better table and query design. Please let me know if I can provide more information.

share|improve this question
2  
No index at wordlocation? At all? –  ypercube Jul 3 '13 at 20:29
    
Just as @ypercube suggested you should have an index on wordlocation, but further more, is that query ok? You want to left join on ul.id = wl.urlid but you also want wl.urlid to be null? –  user16484 Jul 3 '13 at 20:44
1  
@user16484: The query is okay. It is one of the established implementations of an anti-join. The left join would return both matching and non-matching rows. The WHERE clause would then filter the join's results down to the non-matching rows only. –  Andriy M Jul 3 '13 at 20:47
    
no, and I'm not quite sure how and when to index. Mysql suggests not being over anxious and creating indexes on all columns. But in one query or another throughout this application, each one of those columns in wordlocation is heavily used in where clauses. For now though, how would I add an index and on which column? I'm sure that can at least get me started and I can provide some better feedback –  user658182 Jul 3 '13 at 20:48
3  
@user16484: To address the NULL vs NULL bit specifically, if ul.id did contain NULLs, those would indeed be returned accompanied with the right side's wl.urlids also NULLs. But that would still indicate a no-match, because NULL is not equal to NULL (more exactly, NULL = NULL evaluates to UNKNOWN, which in this context would be treated same as FALSE). However, ul.id could not possibly have NULLs since it is defined as a non-nullable column. (And you'd think it would, since the name of the column suggests it's the primary key of the table and NULL in a PK column doesn't make sense.) –  Andriy M Jul 3 '13 at 23:36
show 3 more comments

2 Answers

up vote 1 down vote accepted

To help with your immediate problem, adding an index on wordlocation.urlid will help your query a lot.

For scalability, it sounds like your best route might be to add a field to urllist that can be easily referenced to see which urls have been indexed. For example a tinyint column called indexed with a default of zero (so new entries are always zero). Then when you index a url, update this column to a one.

share|improve this answer
add comment

First, your query is correct. You don't need the wordlocation columns though (they are going to be all NULL anyway) so I'd change select * to select ul.*:

SELECT ul.* FROM urllist AS ul 
LEFT JOIN wordlocation AS wl ON ul.id = wl.urlid 
WHERE wl.urlid IS NULL;

There are two more ways this kind of (anti-join or anti-semijoin) queries are usually written. Using NOT IN which is not recommended if the 2 joining columns are not both not nullable. Your urlid columns are not nullable indeed so this would work as well:

SELECT ul.* FROM urllist AS ul 
WHERE ul.id NOT IN 
      ( SELECT wl.urlid
        FROM wordlocation AS wl 
      ) ;

Or using NOT EXISTS:

SELECT ul.* FROM urllist AS ul 
WHERE NOT EXISTS
      ( SELECT 1
        FROM wordlocation AS wl
        WHERE ul.id = wl.urlid 
      ) ;

All three queries result in very similar execution plans and efficiency in MySQL. So, you should test with your data distribution (and table sizes) and the version of MySQL you are using, to decide which query to use.

The query is of course slow now because of the obvious missing index on wordlocation (urlid). The efficiency will improve (dramatically) when you add this index but that's not all is missing from this table.

You have no Primary Key defined. Check and think about your modelling and find which columns uniquely identify rows in this table. My guess is that you are processing web pages, extracting words from them and storing all (or some of the) words and their locations in the webpages. If that's correct, you could use the (urlid, location) as the primary key:

ALTER TABLE wordlocation
  ADD PRIMARY KEY (urlid, location) ;

And if you do that, you won't need a separate index on (urlid). You will probably be having other queries though, that search for words (I guess you also have a wordlist table), so you will need an index on (wordid) as well - or on (wordid, location) or some other combinations. What indexes you'll need depends on what queries you plan to run against these tables.

For the urllist.url datatype, I'd prefer to use VARCHAR(x) instead of TEXT. What is the longest url you could have? The length x can be as long as 65535 and if you want to index it, the index can be for up to the first 255 characters. (I assume that you are storing the URLs there and not the actual web pages. If you do store web pages, disregard this paragraph.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.