efficiently find first number that do not exist in a table?

Question

i have a table with about 528829 rows, it looks like

CREATE TABLE `ips` (
  `id` INTEGER PRIMARY KEY AUTOINCREMENT,
  `ip` INTEGER NOT NULL DEFAULT NULL,
  `scantime` INTEGER NULL DEFAULT NULL,
  `pingable` INTEGER NULL DEFAULT NULL
);

now i need to find the first number that do NOT exist in ip , starting from 0 and going up to 4294967295 (aka 0xFFFFFFFF ),

currently i just use

function isScanned($ip){
    static $isScannedStm=false;
    static $boundip=0;
    if($isScannedStm===false){
    global $db;
    $isScannedStm=$db->prepare('SELECT 1 FROM `ips` WHERE `ip` = :ip LIMIT 1');
    $isScannedStm->bindParam(':ip',$boundip,PDO::PARAM_INT);
    return isScanned($ip);
    }
    $boundip=$ip;
    $isScannedStm->execute();
    //var_dump($isScannedStm->fetch(PDO::FETCH_NUM));
    return !!($isScannedStm->fetch(PDO::FETCH_NUM));
}
//~~~
    while(isScanned($i)){
        ++$i;
    }

..it works, but with 528829 rows, it takes over 1 hour and 30 minutes on my Intel Atom C2750 @ 2.4GHz.. how can i find this value faster? preferably, much much faster?

Your create table `AUTOINCREMENT` should read as `AUTO_INCREMENT` http://dev.mysql.com/doc/refman/5.7/en/example-auto-increment.html if that's your actual code. — Funk Forty Niner, Jan 03 '16 at 22:26
@Fred-ii- nope, i use sqlite, and in SQLite, its AUTOINCREMENT , they can't agree on the name ^^ — hanshenrik, Jan 03 '16 at 22:27
Possible duplicate of [Find mininum not used value in mysql table](http://stackoverflow.com/questions/6464656/find-mininum-not-used-value-in-mysql-table) — JimL, Jan 03 '16 at 23:10
@JimL don't post a duplicate if you're going to post an answer. If the question gets closed because of it, then nobody else could add an additional / alternate answer in order to possibly improve the question. This is a form of monopoly. If my memory serves me right, this isn't the first time you do this and a minute after you posted an answer. — Funk Forty Niner, Jan 04 '16 at 12:51
@Fred-ii- the other question is for pure MySQL, this is for SQLite+PHP, they're not exactly duplicates. — hanshenrik, Jan 04 '16 at 12:55
@Fred-ii- ok, you seem to have excellent memory though. I very rarely post any answers ;) — JimL, Jan 04 '16 at 12:57

score 2 · Accepted Answer · edited May 23 '17 at 12:15

2

I have only tested this in MySQL, hopefully it works for SQLite as well

SELECT ips.ip+1 AS Missing 
FROM ips
LEFT JOIN ips AS next ON ips.ip+1 = next.ip
WHERE next.ip IS NULL 
ORDER BY ips.ip LIMIT 1;

Solution by Caspar and splattru: https://stackoverflow.com/a/6464763/1078488

edited May 23 '17 at 12:15

Community

1
1

answered Jan 03 '16 at 23:09

JimL

2,501
1
19
19

@hanshenrik Great! How was the performance compared to the old way of doing things? – JimL Jan 03 '16 at 23:49
1 hour 30 minutes turned into <5 seconds... holy shit. Run Time: real 4.073 user 3.880000 sys 0.192000. holy shit. and yes, im norwegian. – hanshenrik Jan 03 '16 at 23:55
@hanshenrik pretty good improvement, I think you owe Caspar a beer if you ever run into him/her ^^ and nice, always fun to run into (and help!) a fellow countryman – JimL Jan 03 '16 at 23:55
fun statistics, this runs consistently at 4.0X seconds. adding an UNIQUE INDEX on ip turns it down to consistently 1.3X seconds ^^ – hanshenrik Jan 04 '16 at 00:05
@hanshenrik pretty amazing results. Lmk if you do a bit of web/php/js related stuff, I could always need more "locals" on my chat list ^^ – JimL Jan 04 '16 at 00:17
Yes, yes, and yes. SO doesn't support private messages or anything like that, I'm "takeoded" on Skype and "Hans Henrik Bergan" on FB, feel free to to add me – hanshenrik Jan 04 '16 at 00:23

score 0 · Answer 2 · edited May 23 '17 at 12:23

You could consider performing a sort of "binary search". Where you start with the first half of the consecutive numbers [1, 2, 3, ... (n/2)]

If the number of results do not equal the number of consecutive values in the current list, then you can split the initial list and rerun through the same logic, continuing until you arrive at the first non-consecutive id.

Otherwise if the counts match you move on to the other half of consecutive ids.

Your query would then need to contain a WHERE...IN clause.

This is not going to fully function for you, however maybe this will help:

// Populate current set of consecutive integers
$list = array_fill(0, $count/2);
$listQuery = implode(',', $list);

global $db;

$isScannedStm = $db->prepare('
    SELECT 1 FROM `ips` 
    WHERE `ip` IN ('.$listQuery.') 
    GROUP BY `ip` 
    ORDER BY `ip` ASC
');
$isScannedStm->execute()

// Check num results 
if (count($list) !== $isScannedStm->fetch(PDO::FETCH_NUM)) {
    // Split the initial list in half 
    // OR loop through results and find when the ids are not consecutive   
}

There is probably an easier way to do this, maybe consider looking at this question

efficiently find first number that do not exist in a table?

2 Answers2