You might do well to determine how the new_key is generated. Without this information there's little helping you.
If it is, for example, an incremental number, then it would be better to choose MAX(columnkey)+1
(with the table locked to prevent conflicts), or better still, declare it PRIMARY KEY AUTO_INCREMENT and insert the NULL value for the key. This will set the key automatically. Recover its value with LAST_INSERT_ID()
:
INSERT INTO ... (all columns except key) VALUES (all values)
SELECT LAST_INSERT_ID() AS newkey;
Or you could use a timestamp of sufficient granularity.
If you want to avoid "holes" in the numbering (not necessarily a bad practice, but please have a better reason to do so than "it looks nicer"!), you can LEFT JOIN
the table to itself on condition that the right-hand table ID is one greater than the left-hand side. Those rows where the right side is NULL indicate that their counterpart ID is available (again, lock the tables - in this case, with MySQL, twice):
-- You need an index on mykey
SELECT a.mykey+1 AS available
FROM mytable AS a
LEFT JOIN mytable AS b ON (a.mykey+1 = b.mykey)
WHERE b.mykey IS NULL
ORDER BY a.mykey LIMIT 20