Is there anything else I can do to optimize this MySQL query?

Question

I have two tables, Table A with 700,000 entries and Table B with 600,000 entries. The structure is as follows:

Table A:

+-----------+---------------------+------+-----+---------+----------------+
| Field     | Type                | Null | Key | Default | Extra          |
+-----------+---------------------+------+-----+---------+----------------+
| id        | bigint(20) unsigned | NO   | PRI | NULL    | auto_increment | 
| number    | bigint(20) unsigned | YES  |     | NULL    |                | 
+-----------+---------------------+------+-----+---------+----------------+

Table B:

+-------------+---------------------+------+-----+---------+----------------+
| Field       | Type                | Null | Key | Default | Extra          |
+-------------+---------------------+------+-----+---------+----------------+
| id          | bigint(20) unsigned | NO   | PRI | NULL    | auto_increment | 
| number_s    | bigint(20) unsigned | YES  | MUL | NULL    |                | 
| number_e    | bigint(20) unsigned | YES  | MUL | NULL    |                | 
| source      | varchar(50)         | YES  |     | NULL    |                |
+-------------+---------------------+------+-----+---------+----------------+

I am trying to find if any of the values in Table A are present in Table B using the following code:

$sql = "SELECT number from TableA";
$result = mysql_query($sql) or die(mysql_error());

while($row = mysql_fetch_assoc($result)) {
        $number = $row['number'];
        $sql = "SELECT source, count(source) FROM TableB WHERE number_s < $number AND number_e > $number GROUP BY source";
        $re = mysql_query($sql) or die(mysql_error);
        while($ro = mysql_fetch_array($re)) {
                echo $number."\t".$ro[0]."\t".$ro[1]."\n";
        }
}

I was hoping that the query would go fast but then for some reason, it isn't terrible fast. My explain on the select (with a particular value of "number") gives me the following:

mysql> explain SELECT source, count(source) FROM TableB WHERE number_s < 1812194440 AND number_e > 1812194440 GROUP BY source;
+----+-------------+------------+------+-------------------------+------+---------+------+--------+----------------------------------------------+
| id | select_type | table      | type | possible_keys           | key  | key_len | ref  | rows   | Extra                                        |
+----+-------------+------------+------+-------------------------+------+---------+------+--------+----------------------------------------------+
|  1 | SIMPLE      | TableB     | ALL  | number_s,number_e       | NULL | NULL    | NULL | 696325 | Using where; Using temporary; Using filesort | 
+----+-------------+------------+------+-------------------------+------+---------+------+--------+----------------------------------------------+
1 row in set (0.00 sec)

Is there any optimization that I can squeeze out of this?

I tried writing a stored procedure for the same task but it doesn't even seem to work in the first place... It doesn't give any syntax errors... I tried running it for a day and it was still running which felt odd.

CREATE PROCEDURE Filter() 
Begin 
  DECLARE number BIGINT UNSIGNED; 
  DECLARE x INT; 
  DECLARE done INT DEFAULT 0; 
  DECLARE cur1 CURSOR FOR SELECT number FROM TableA; 
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1; 
  CREATE TEMPORARY TABLE IF NOT EXISTS Flags(number bigint unsigned, count int(11)); 
  OPEN cur1; 
  hist_loop: LOOP 
    FETCH cur1 INTO number; 
    SELECT count(*) from TableB WHERE number_s < number AND number_e > number INTO x; 
    IF done = 1 THEN 
      LEAVE hist_loop; 
    END IF; 
    IF x IS NOT NULL AND x>0 THEN 
      INSERT INTO Flags(number, count) VALUES(number, x); 
    END IF; 
  END LOOP hist_loop; 
  CLOSE cur1;
END

Answer 1

It looks to me like you have separate indexes on the number_e and number_s columns, probably created with separate ADD INDEX(number_e) and ADD INDEX(number_s) columns.

You will likely get much better performance if you add an index that encompasses both those columns, as they are both being used in your query, and MySQL is clearly not choosing to use either of the single-column indexes, judging that a whole table scan would be faster (not uncommon if your query spans a large range of values).

ALTER TABLE tblB ADD INDEX(number_s,number_e);

You won't need the individual number_s index after that, as MySQL can use the one you just created for queries against number_s only, so you might as well drop that one.

Answer 2

You are trying to find intervals which contain a point. This is not so fast with a B-tree index (the default index type in most databases), however an R-tree index will work well for this sort of query. MySQL doesn't allow you to change the type of an index directly, but you can force MySQL to use an R-Tree by using the GEOMETRY column type.

Quassnoi covers this in his article on nested sets in MySQL. While it's not quite the same, it's very similar. A quote from the article:

There is also a certain class of tasks that require searching for all ranges containing a known value:

* Searching for an IP address in the IP range ban list
* Searching for a given date within a date range

and several others. These tasks can be improved by using R-Tree capabilities of MySQL

Answer 3

First, I assume the desired output is to group all 'source' where the input lies between number_e and number_s, and the count thereof.

I'm scratchy on the syntax, but you might consider using a 'BETWEEN' clause up there instead of an explicit comparison using less-than/greater-than operators

Edit: What Zombat says applies too; indexes will help too.