CODEWITHSUNDEEP
sqlite
Andreas
Andreas

Reputation: 5301

How is rowid determined on sqlite insertion?

I´d like to predict (reverse engineer really) the rowid of any to-be-inserted row in a sqlite table (to reconstruct a stream of sqlite insertions using the rowid of some tables as foreign key in other tables). The insertion may happen after an arbitrary sequence of insertions and deletions. How is the rowid determined by sqlite on insertion?

Is it an ever incrementing counter?

int64_t next_rowid() {
  static int64_t r = 0;
  return ++r;
}

Maybe the smallest row not in use?

// Algorithm description, not (likely) working code
static sorted_set<int64_t> deleted;
static int64_t top = 0;
int64_t next_rowid() {
  if(deleted.size()==0) deleted.push(++top);
  return deleted.pop_front();
}
void delete_rowid(int64_t r) {
  deleted.push(r);
}

Some other scheme?

Unspecified?

Upvotes: 0

Views: 262

Answers (2)

Michał Zaborowski
Michał Zaborowski

Reputation: 4387

https://sqlite.org/autoinc.html -

SQLite is single thread, so for most cases it performs select max(id) +1 from the_table. From that perspective it is really hard to tell what was the sequence. You can however provide valid sequence threating deleted stuff as not present. Or maybe I missed something.

Edit

As CL spotted. Autoincrement works in more stable way. So you can't get same id twice. And from that you can see that something was deleted meanwhile...

Upvotes: 2

MikeT
MikeT

Reputation: 56948

First, there are 2 types of rowid determination algorithms. Depending upon whether or not AUTOINCREMENT has been specified.

AUTOINCREMENT means that the rowid is guaranteed to increase within the limitations of the size of the number (9223372036854775807). If that number is reached, then any subsequent insert attempt fails with an SQLITE_FULL exception.

Without AUTOINCREMENT in the above scenario the algorithm will try to find an unused rowid and therefore the resultant rowid may be lower than other existing rowids.

Neither of the algorithms guarantee an increment of 1, rather that usually they will increment by 1.

AUTOINCREMENT results in a table sqlite_sequence being created, the last used rowid is held in the sequence column, Note! it can be manipulated/altered so add 1 record then change it to 100 and next insert will likely be 101.

The name column is the name of the table that the row is for.

  • I changed the name column, as a test, to a non-existent table name (last sequence was the 101) inserting a record still resulted in 102, so it would appear that in the absence of the respective sequence in sqlite_sequence the algorithm still locates a higher rowid.

  • I then lowered the sequence to 2, the next rowid was 103.

  • So the guarantee of a higher rowid seems to be thorough.

  • I next added a 2nd row to sqlite_sequence for the same table with a sequence number of 600. Insert came up with a rowid of 104.

  • As SQLite possibly selects the first row according to id, I then changed the id of from 2 (1 is the one that was changed to a non-existent table name) to 20. 3 is the rowid of the rouge/2nd entry row. The inserted rowid was 601.

  • As an attempt to try to fool SQLite I deleted the newly added row in the table and the row with a rowid of 3, sequence value of 601 in the sqlite_sequence table. SQLite was fooled, the rowid of the inserted row was 105.

As such the algorithms appear to be along the lines of :-

  • a) for where AUTOINCREMENT isn't specified

    • 1 greater than the highest rowid in the table in which the row is being inserted unless it is greater than 9223372036854775807, in which case an unused rowid will be sought.

  • b) 1 greater than the greater of the highest rowid in the table into which the row is being inserted and the sequence stored in the first row for the table in the sqlite_sequence table. Noting that the sqlite_sequence table may be updated but then that the insert does not take place e.g. if the insert fails due to constraints.

Much of the above is based upon this

Upvotes: 0

Related Questions