PHP MySQL encuentra el número faltante más pequeño en la columna

Si el Order columna está indexada, podría obtener el primer número faltante con SQL, sin leer la tabla completa usando un LEFT JOIN excluyente:

SELECT t1.`Order` + 1 AS firstMissingOrder
FROM tabla t1
LEFT JOIN tabla t2 ON t2.`Order` = t1.`Order` + 1
WHERE t2.`Order` IS NULL
  AND t1.`Order` <> (SELECT MAX(`Order`) FROM tabla)
ORDER BY t1.`Order`
LIMIT 1

o (quizás más intuitivo)

SELECT t1.`Order` + 1 AS firstMissingOrder
FROM tabla t1
WHERE NOT EXISTS (
    SELECT 1
    FROM tabla t2
    WHERE t2.`Order` = t1.`Order` + 1
) 
    AND t1.`Order` <> (SELECT MAX(`Order`) FROM tabla)
ORDER BY t1.`Order`
LIMIT 1

MySQL convertirá la segunda consulta en la primera. Así que son prácticamente iguales.

Actualizar

Strawberry mencionó un buen punto:el primer número que falta podría ser 1 , que no está cubierto en mi consulta. Pero no pude encontrar una solución que fuera a la vez elegante y rápida.

Podríamos ir en sentido contrario y buscar el primer número después de un espacio. Pero necesitaría volver a unirse a la tabla para encontrar el último número existente antes de ese espacio.

SELECT IFNULL(MAX(t3.`Order`) + 1, 1) AS firstMissingOrder
FROM tabla t1
LEFT JOIN tabla t2 ON t2.`Order` = t1.`Order` - 1
LEFT JOIN tabla t3 ON t3.`Order` < t1.`Order`
WHERE t1.`Order` <> 1
  AND t2.`Order` IS NULL
GROUP BY t1.`Order`
ORDER BY t1.`Order`
LIMIT 1

MySQL (en mi caso, MariaDB 10.0.19) no puede optimizar esa consulta correctamente. Se tarda aproximadamente un segundo en una tabla indexada (PK) de 1 millón de filas, aunque el primer número que falta es 9. Espero que el servidor deje de buscar t1.Order=10 , pero parece no hacer eso.

Otra forma, que es rápida pero se ve fea (en mi humilde opinión), es usar la consulta original en una subselección solo si Order=1 existe De lo contrario, devuelve 1 .

SELECT CASE
    WHEN NOT EXISTS (SELECT 1 FROM tabla WHERE `Order` = 1) THEN 1
    ELSE (
        SELECT t1.`Order` + 1 AS firstMissingOrder
        FROM tabla t1   
        LEFT JOIN tabla t2 ON t2.`Order` = t1.`Order` + 1
        WHERE t2.`Order` IS NULL
          AND t1.`Order` <> (SELECT MAX(`Order`) FROM tabla)
        ORDER BY t1.`Order`
        LIMIT 1
    )
END AS firstMissingOrder

O usando UNION

SELECT 1 AS firstMissingOrder FROM (SELECT 1) dummy WHERE NOT EXISTS (SELECT 1 FROM tabla WHERE `Order` = 1)
UNION ALL
SELECT firstMissingOrder FROM (
    SELECT t1.`Order` + 1 AS firstMissingOrder
    FROM tabla t1
    LEFT JOIN tabla t2 ON t2.`Order` = t1.`Order` + 1
    WHERE t2.`Order` IS NULL
      AND t1.`Order` <> (SELECT MAX(`Order`) FROM tabla)
    ORDER BY t1.`Order`
    LIMIT 1
) sub
LIMIT 1