How can I better optimize my tables and a LEFT JOIN query to find items that don't yet exist in the right table?

Question

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.

Answer 1

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.

Answer 2

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