SQLite Forum

The opposite of AUTOINCREMENT
Login
> Can anybody suggest something simpler?

Simpler? Not by much, but more useful - definitely. I have done this for some project, not really an SQLite project but I did use SQLite to keep track of the Index keys used.

Let me first state that I'm with Jim - best is a trigger and ID table.

The query I use is a little complicated, but very fast, and most importantly, 100% suggests the best index-gap to use for the range to be inserted (which is what I needed, but may or may not be useful to you).


I've dusted it off and made a small script to demonstrate:

```
  -- SQLite version 3.30.1  [ Release: 2019-10-10 ]  on  SQLitespeed version 2.1.3.11.
  -- ================================================================================================

CREATE TABLE t(ID INT PRIMARY KEY, Val TEXT);


-- Making a small table with gaps from index 4 to 9 (6 IDs) and 12 to 15 (4 IDs)

INSERT INTO t(ID,Val) VALUES
 ( 1, 'A1')
,( 2, 'A2')
,( 3, 'A3')
,(10, 'A10')
,(11, 'A11')
,(16, 'A16')
,(18, 'A18')
;

-- Query to find the best Starting INSERT ID listed in order of suitability, best at the top.
-- Here I manually added a "3" binding in the first CTE as the RequiredSize
-- You can use LIMIT 1 to only see the best option, but I all in to see the working:

WITH AllGaps(cID, GapSize, RequiredSize) AS (
    SELECT ID, (MAX(ID) OVER w1) - (MIN(ID) OVER w1) - 1,  3
      FROM t
     WHERE ID+1 NOT IN (SELECT ID FROM t) OR (ID>1 AND ID-1 NOT IN (SELECT ID FROM t))
    WINDOW w1 AS (ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
     ORDER BY ID
), BestGaps(cID, GapSize) AS (
    SELECT cID+1, GapSize FROM AllGaps
     WHERE GapSize >= RequiredSize AND cID+1 NOT IN (SELECT ID FROM t)
    UNION ALL
    SELECT IFNULL(MAX(ID),0)+1, 0xFFFFFFFF FROM t
    ORDER BY GapSize ASC, cID+1 ASC
)
SELECT cID FROM BestGaps -- LIMIT 1
;

  --  cID     
  -- ----
  --  12 
  --   4 
  --  19 

-- Indeed, the best gap for inserting only 3 items is the 4 available indexes starting at 12, then the gap of 6 IDs starting at 4.
-- Note that the next AutoInc ID is always the last item, in case no suitable gaps are found.


-- =========================================================
-- In this next run I changed that to Required Size to 5:

WITH AllGaps(cID, GapSize, RequiredSize) AS (
    SELECT ID, (MAX(ID) OVER w1) - (MIN(ID) OVER w1) - 1,  5
      FROM t
     WHERE ID+1 NOT IN (SELECT ID FROM t) OR (ID>1 AND ID-1 NOT IN (SELECT ID FROM t))
    WINDOW w1 AS (ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
     ORDER BY ID
), BestGaps(cID, GapSize) AS (
    SELECT cID+1, GapSize FROM AllGaps
     WHERE GapSize >= RequiredSize AND cID+1 NOT IN (SELECT ID FROM t)
    UNION ALL
    SELECT IFNULL(MAX(ID),0)+1, 0xFFFFFFFF FROM t
    ORDER BY GapSize ASC, cID+1 ASC
)
SELECT cID FROM BestGaps -- LIMIT 1
;

  --      cID    
  -- ------------
  --       4     
  --      19     

-- Indeed now the only viable insert positions are the 6-ID gap starting at 4 and the ID at next autoinc ID: 19.


-- =========================================================
-- Now I'm just making a table with a million entries to test speed

WITH AX(AID) AS (
    SELECT 25 UNION ALL SELECT AID+1 FROM AX WHERE AID < 1000000
)
INSERT INTO t(ID,Val)
SELECT AID, 'A'||AID FROM AX
;


-- And here making some more gaps in the very large table

DELETE FROM t
 WHERE ID BETWEEN 5000 AND 5020   -- Make gap of Size 21
    OR ID BETWEEN 8000 AND 8002   -- Make Gap of Size 3
    OR ID BETWEEN 9000 AND 9010   -- Make Gap of Size 11
;


-- =========================================================
-- Again finding the most suitable gap with Size 3:

WITH AllGaps(cID, GapSize, RequiredSize) AS (
    SELECT ID, (MAX(ID) OVER w1) - (MIN(ID) OVER w1) - 1,  3
      FROM t
     WHERE ID+1 NOT IN (SELECT ID FROM t) OR (ID>1 AND ID-1 NOT IN (SELECT ID FROM t))
    WINDOW w1 AS (ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
     ORDER BY ID
), BestGaps(cID, GapSize) AS (
    SELECT cID+1, GapSize FROM AllGaps
     WHERE GapSize >= RequiredSize AND cID+1 NOT IN (SELECT ID FROM t)
    UNION ALL
    SELECT IFNULL(MAX(ID),0)+1, 0xFFFFFFFF FROM t
    ORDER BY GapSize ASC, cID+1 ASC
)
SELECT cID FROM BestGaps -- LIMIT 1
;

  --    cID   
  -- ---------
  --    8000    -- This is the best gap, exactly 3 long, starting at ID 8000
  --     12     -- 2nd best Size, etc.
  --     4    
  --     19   
  --    9000  
  --    5000  
  --  1000001   -- Next Autoinc ID


-- =========================================================
-- Again finding the most suitable gap with Size 5:

WITH AllGaps(cID, GapSize, RequiredSize) AS (
    SELECT ID, (MAX(ID) OVER w1) - (MIN(ID) OVER w1) - 1,  5
      FROM t
     WHERE ID+1 NOT IN (SELECT ID FROM t) OR (ID>1 AND ID-1 NOT IN (SELECT ID FROM t))
    WINDOW w1 AS (ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
     ORDER BY ID
), BestGaps(cID, GapSize) AS (
    SELECT cID+1, GapSize FROM AllGaps
     WHERE GapSize >= RequiredSize AND cID+1 NOT IN (SELECT ID FROM t)
    UNION ALL
    SELECT IFNULL(MAX(ID),0)+1, 0xFFFFFFFF FROM t
    ORDER BY GapSize ASC, cID+1 ASC
)
SELECT cID FROM BestGaps -- LIMIT 1
;

  --    cID   
  -- ---------
  --     4        -- Indeed Best gap.
  --     19   
  --    9000  
  --    5000  
  --  1000001 

  --    Item Stats:  Item No:           8             Query Size (Chars):  569
  --                 Result Columns:    1             Result Rows:         5
  --                 VM Work Steps:     16000174      Rows Modified:       0
  --                 Sort Operations:   2             Table-Scan Steps:    999947
  --                 Prepare Time:      -- --- --- --- --.----
  --                 Query Run:         0d 00h 00m and 00.535s
  --                 Full Query Time:   0d 00h 00m and 00.535s
  --                 Script Time:       0d 00h 00m and 02.177s
  --                 Query Result:      Success.
  -- ------------------------------------------------------------------------------------------------


-- =========================================================
-- Here I added your original query, which also runs very fast, and produce
-- exact available ranges, but without the option to request the best gap of
-- an arbitrary size.

with recursive
    result (newid) as
        (select candidate from
            (select 1 as candidate
                where candidate not in (select ID from t)
            union all select ID+1 as candidate from t
                where candidate not in (select ID from t)
            limit 50)
        union all select newid+1 as candidate from result
            where candidate not in (select ID from t)
        order by candidate
        limit 50)
    select newid from result;


  --     newid   
  -- ------------
  --       4     
  --       5     
  --       6     
  --       7     
  --       8     
  --       9     
  --      12     
  --      13     
  --      14     
  --      15     
  --      17     
  --      19     
  --      20     
  --      21     
  --      22     
  --      23     
  --      24     
  --     5000    
  --     5001    
  --     5002    
  --     5003    
  --     5004    
  --     5005    
  --     5006    
  --     5007    
  --     5008    
  --     5009    
  --     5010    
  --     5011    
  --     5012    
  --     5013    
  --     5014    
  --     5015    
  --     5016    
  --     5017    
  --     5018    
  --     5019    
  --     5020    
  --     8000    
  --     8001    
  --     8002    
  --     9000    
  --     9001    
  --     9002    
  --     9003    
  --     9004    
  --     9005    
  --     9006    
  --     9007    
  --     9008    

  --    Item Stats:  Item No:           9             Query Size (Chars):  495
  --                 Result Columns:    1             Result Rows:         50
  --                 VM Work Steps:     8000959       Rows Modified:       0
  --                 Sort Operations:   0             Table-Scan Steps:    999947
  --                 Prepare Time:      -- --- --- --- --.----
  --                 Query Run:         0d 00h 00m and 00.475s
  --                 Full Query Time:   0d 00h 00m and 00.475s
  --                 Script Time:       0d 00h 00m and 02.653s
  --                 Query Result:      Success.
  -- ------------------------------------------------------------------------------------------------

DROP TABLE t;

  --   Script Stats: Total Script Execution Time:     0d 00h 00m and 02.696s
  --                 Total Script Query Time:         0d 00h 00m and 02.649s
  --                 Total Database Rows Changed:     1000018
  --                 Total Virtual-Machine Steps:     71002402
  --                 Last executed Item Index:        10
  --                 Last Script Error:               
  -- ------------------------------------------------------------------------------------------------

  -- 2021-03-23 22:40:31.218  |  [Success]    Script Success.
  -- 2021-03-23 22:40:31.218  |  [Success]    Transaction Rolled back.
  -- -------  DB-Engine Logs (Contains logged information from all DB connections during run)  ------
  -- [2021-03-23 22:40:28.703] APPLICATION : Script D:\Documents\FindIDGaps.sql started at 22:40:28.703 on 23 March.
  -- ================================================================================================
```

Hope something in there might be useful.
Good luck!