13

I have a table which will potentially store hundreds of thousands of integers

desc id_key_table;

+----------------+--------------+------+-----+---------+-------+
| Field          | Type         | Null | Key | Default | Extra |
+----------------+--------------+------+-----+---------+-------+
| id_key         | int(16)      | NO   | PRI | NULL    |       |
+----------------+--------------+------+-----+---------+-------+

From a program, I have a large set of integers. I'd like to see which of these integers are NOT in the above id_key column.

So far I've come up with the following approaches:

1) Iterate through each integer and perform a:

select count(*) count from id_key_table where id_key = :id_key

When count is 0 the id_key is missing from the table.

This seems like a horrible, horrible way to do it.


2) Create a temporary table, insert each of the values into the temporary table, and perform a JOIN on the two tables.

create temporary table id_key_table_temp (id_key int(16) primary key );

insert into id_key_table_temp values (1),(2),(3),...,(500),(501);

select temp.id_key
from id_key_table_temp temp left join id_key_table as main 
         on temp.id_key = main.id_key 
where main.killID is null;

drop table id_key_table_temp;

This seems like the best approach, however, I'm sure there is a far better approach I haven't thought of yet. I'd prefer to not have to create a temporary table and use one query to determine which integers are missing.

Is there a proper query for this type of search?

(MySQL)

4
  • 2
    I like how you asked your question (Welcome to DBA) however, it is probably far more appropriate on stackoverflow as it deals with interacting with a program of some sort (not dba per se) Commented May 11, 2011 at 16:31
  • Thank you for the welcome, I thought a place like this might have some more gurus than stackoverflow. I don't mind re-asking there though.
    – Clinton
    Commented May 11, 2011 at 16:46
  • 2
    As suggested, I reposted to StackOverflow: stackoverflow.com/questions/5967822/…
    – Clinton
    Commented May 11, 2011 at 16:50
  • Similar situation was treated for sql server in this question: Technique for sending lots of data into stored proc. You should find there that the problem is similar in other db environments. Anyway, I go for solution no. 2 - send list of ids, parse, put in table, join to your main table. That if you can't use other solutions, but here you have to dig :-).
    – Marian
    Commented May 11, 2011 at 21:01

5 Answers 5

7

Your second solution using the LEFT JOIN is by far the best approach. I would not use a temporary table, I'd use a regular table and populate it with new values any time you wanted run the query.

6

It sounds like the "large set of integers" is still considerably smaller than the table with "hundreds of thousands of integers". With that supposition and unless there is a way in MySQL to use an array of your integers as a table in your SQL statement, your second option is probably the best. It should do a full scan of the temp table and the index on the main table. The primary benefit being that it only has to scan the index containing hundreds of thousands of integers one time and only has to send the client the results. Your query could (but need not be) rewritten as the following:

SELECT * FROM id_key_table_temp 
WHERE id_key NOT IN (select id_key FROM id_key_table);
1
  • I am not endorsing a temporary table over a regular table as I have no knowledge of the differences on the MySQL platform. In Oracle a temporary table would probably be best, but then in Oracle you would just use an array as a table and join directly to it. Commented May 12, 2011 at 14:44
3

Instead of a temporary table and inserting with insert into id_key_table_temp values (1),(2),(3),...,(500),(501);, you could construct a subquery with all the values you are trying to check:

select id_key
from ( select @row := @row + 1 as id_key 
       from (select 0 union all select 1 union all select 3 union all select 4 union all select 5 union all select 6 union all select 6 union all select 7 union all select 8 union all select 9) s1,
            (select 0 union all select 1 union all select 3 union all select 4 union all select 5 union all select 6 union all select 6 union all select 7 union all select 8 union all select 9) s2,
            (select 0 union all select 1 union all select 3 union all select 4 union all select 5 union all select 6 union all select 6 union all select 7 union all select 8 union all select 9) s3,
            (select 0 union all select 1 union all select 3 union all select 4 union all select 5 union all select 6 union all select 6 union all select 7 union all select 8 union all select 9) s4,
            (select @row:=0) s5 ) s
where id_key in(1, 2, 3, 500, 501)
      and id_key not in (select id_key from main);
2

As noted in my comment, this is probably more suited to stackoverflow. However, I think that both of those solutions aren't the best:

Solution 1 requires multiple select calls, very inefficient

Solution 2 is better, but I'm not sure the cost of inserting that many values is the best solution.

A possible solution 3 would to be make one query:

SELECT DISTINCT id_key FROM id_key_table

and programmatically get the difference from your integer set and what's in the DB. At worst, (since it's a lot of integers) This route should be better than Solution 1. Solution 2 has the potential to ALSO return a lot of integers (if the table has a bunch that aren't in your dataset), so it depends™ !

2
  • I'm not a fan of this solution since the resultset would be very large.
    – Clinton
    Commented May 11, 2011 at 16:48
  • @Clinton true, but it could be very large in your second solution as well, if you don't provide enough integers to filter it out. Commented May 11, 2011 at 18:24
2

I pretty much addressed this in StackOverflow, but I would like to elaborate more on using the permanent temp (PermTemp) table. (permanent temp, isn't that an oxymoron ?)

In StackOverflow, I had the stored procedure test.CreateSampleTable and test.GetMissingIntegers make a sample table and then create a dynamic temp table to populate before doing the big JOIN to find differences.

This time, let's create the sample table along with the permanent table table.

Here is test.LoadSampleTables:

DELIMITER $$

DROP PROCEDURE IF EXISTS `LoadSampleTables` $$
CREATE DEFINER=`lwdba`@`127.0.0.1` PROCEDURE `LoadSampleTables`(maxinttoload INT)
BEGIN

  DECLARE X,OKTOUSE,MAXLOOP INT;

  DROP TABLE IF EXISTS test.id_key_table;
  DROP TABLE IF EXISTS test.id_key_table_keys;
  CREATE TABLE test.id_key_table (id_key INT(16)) ENGINE=MyISAM;
  CREATE TABLE test.id_key_table_keys (id_key INT(16)) ENGINE=MyISAM;

  SET X=1;
  WHILE X <= maxinttoload DO
    INSERT INTO test.id_key_table VALUES (X);
    SET X = X + 1;
  END WHILE;
  ALTER TABLE test.id_key_table ADD PRIMARY KEY (id_key);

  SET MAXLOOP = FLOOR(SQRT(maxinttoload));
  SET X = 2;
  WHILE X <= MAXLOOP DO
    DELETE FROM test.id_key_table WHERE MOD(id_key,X) = 0 AND id_key > X;
    SELECT MIN(id_key) INTO OKTOUSE FROM test.id_key_table WHERE id_key > X;
    SET X = OKTOUSE;
  END WHILE;
  OPTIMIZE TABLE test.id_key_table;

  INSERT INTO test.id_key_table_keys SELECT id_key FROM test.id_key_table;
  ALTER TABLE test.id_key_table_keys ADD PRIMARY KEY (id_key);
  OPTIMIZE TABLE test.id_key_table_keys;

END $$

DELIMITER ;

After running this, here are the tables and their contents:

mysql> call test.loadsampletables(25);
+-------------------+----------+----------+----------+
| Table             | Op       | Msg_type | Msg_text |
+-------------------+----------+----------+----------+
| test.id_key_table | optimize | status   | OK       |
+-------------------+----------+----------+----------+
1 row in set (0.20 sec)

+------------------------+----------+----------+----------+
| Table                  | Op       | Msg_type | Msg_text |
+------------------------+----------+----------+----------+
| test.id_key_table_keys | optimize | status   | OK       |
+------------------------+----------+----------+----------+
1 row in set (0.28 sec)

Query OK, 0 rows affected (0.29 sec)

mysql> select * from test.id_key_table;
+--------+
| id_key |
+--------+
|      1 |
|      2 |
|      3 |
|      5 |
|      7 |
|     11 |
|     13 |
|     17 |
|     19 |
|     23 |
+--------+
10 rows in set (0.00 sec)

mysql> select * from test.id_key_table_keys;
+--------+
| id_key |
+--------+
|      1 |
|      2 |
|      3 |
|      5 |
|      7 |
|     11 |
|     13 |
|     17 |
|     19 |
|     23 |
+--------+
10 rows in set (0.00 sec)

Here are the Triggers for the PermTemp table

mysql> DELIMITER $$
mysql>
mysql> CREATE TRIGGER test.AddPermTempKey AFTER INSERT ON test.id_key_table
    -> FOR EACH ROW
    -> BEGIN
    ->     INSERT IGNORE INTO test.id_key_table_keys VALUES (NEW.id_key);
    -> END $$
Query OK, 0 rows affected (0.09 sec)

mysql>
mysql> CREATE TRIGGER test.DeletePermTempKey AFTER DELETE ON test.id_key_table
    -> FOR EACH ROW
    -> BEGIN
    ->     DELETE FROM test.id_key_table_keys WHERE id_key = OLD.id_key;
    -> END $$
Query OK, 0 rows affected (0.08 sec)

mysql>
mysql> DELIMITER ;

Now, lets import a new batch of records, table test.weekly_batch, some keys used before, other keys brand spanking new:

mysql> CREATE TABLE test.weekly_batch (id_key INT(16)) ENGINE=MyISAM;
Query OK, 0 rows affected (0.04 sec)

mysql> INSERT INTO test.weekly_batch VALUES (17),(19),(23),(29),(31),(37),(41);
Query OK, 7 rows affected (0.00 sec)
Records: 7  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE test.weekly_batch ADD PRIMARY KEY (id_key);
Query OK, 7 rows affected (0.08 sec)
Records: 7  Duplicates: 0  Warnings: 0

Let's take test.weekly_batch and safely merge it into test.id_key_table_keys and form the table test.new_keys_to_load:

DELIMITER $$

DROP PROCEDURE IF EXISTS `test`.`ImportWeeklyBatch` $$
CREATE PROCEDURE `test`.`ImportWeeklyBatch` ()
TheStoredProcedure:BEGIN

  DECLARE RCOUNT INT;

  SELECT COUNT(1) INTO RCOUNT FROM information_schema.tables
  WHERE table_schema='test' AND table_name='weekly_batch';
  IF RCOUNT = 0 THEN
    LEAVE TheStoredProcedure;
  END IF;
  SELECT COUNT(1) INTO RCOUNT FROM test.weekly_batch;
  IF RCOUNT = 0 THEN
    LEAVE TheStoredProcedure;
  END IF;
  DROP TABLE IF EXISTS test.new_keys_to_load;
  CREATE TABLE test.new_keys_to_load (id_key INT(16));
  INSERT INTO test.new_keys_to_load (id_key)
  SELECT id_key FROM test.weekly_batch A
  LEFT JOIN test.id_key_table_keys B USING (id_key)
  WHERE B.id_key IS NULL;

  SELECT * FROM test.new_keys_to_load;

END $$

DELIMITER ;

Here is the result:

mysql> call test.importweeklybatch;
+--------+
| id_key |
+--------+
|     29 |
|     31 |
|     37 |
|     41 |
+--------+
4 rows in set (0.14 sec)

From this point, just use the new_keys_to_load table as the list of brand spanking new keys to import. Since new_keys_to_load is smaller than the PermTemp table, you should always use new_keys_to_load on the left side of the LEFT JOIN.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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