Lab Technical Report LAB-TR-0030
Upper Bounds on Record Loss from Identifier Counters in Android Media and Message Stores
Lab Technical Report, preprint, not peer reviewed
28 October 2026
Abstract
Examiners read a gap in a database’s row identifiers as deleted records and sometimes report its size. In a table with an AUTOINCREMENT counter, the counter minus the live row count is an upper bound on rows removed; in an ordinary rowid table, the unused identifiers below the newest row are a lower bound. Skipped inserts, explicit identifiers, restores and counter edits move both without a deletion. We tested 21 mechanisms on 2,360 synthetic SQLite fixtures: the bounds held in all 1,680 fixtures with engine-chosen identifiers and failed silently in 248 of 660 where they did not. We read the media, message, call and contact stores of 14 Android phones. The media counter had been set near 109 on 7, inflating the raw difference by a billion; after rebasing, a median 64 percent of issued media identifiers had no live row, against 14 percent for SMS and 11 for chat. The store’s tombstone table, limited to images and videos, covered a median 39 percent of them. Reading a call log without its write-ahead log changed the bound on 8 of 13 phones. A removal count from a counter is a bound, valid for a stated store, release and log state.
CCS Concepts • Applied computing → System forensics; • Information systems → Data management systems.
Keywords SQLite, AUTOINCREMENT, sqlite_sequence, deleted records, Android, MediaStore, message stores, mobile forensics, empirical study
ACM Reference FormatDaniel Addai, Sanders Larweh Tetteh, Selorm Adjabeng, and Kingsley Albert Egyir. 2026. Upper Bounds on Record Loss from Identifier Counters in Android Media and Message Stores. Lab Technical Report LAB-TR-0030, version 1.0. SectraTEK Lab, Prudential Associates. Preprint, not peer reviewed. https://lab.sectratek.com/research/reports/lab-tr-0030/
1 Introduction
Phones keep messages, calls and media in SQLite tables whose rows carry integer identifiers that only grow. When an identifier is missing, examiners read the gap as a deletion, and published practice turns the arithmetic into a number of deleted messages [11], [15], [21]. SQLite documents what its counters do [23]. We found no study of what the gaps of Android stores can prove, or of how wrong the arithmetic is when an application does something other than insert and delete.
A motivating example. Take a table whose key is INTEGER PRIMARY KEY AUTOINCREMENT. In the first copy, 1,000 records are inserted, followed by 300 inserts that repeat an existing key and are skipped by INSERT OR IGNORE; nothing is deleted. In the second copy, 1,300 records are inserted and the newest 300 are deleted. We ran both with SQLite 3.50.4. Both tables end with 1,000 rows, a highest identifier of 1,000 and a counter of 1,300. The counter minus the row count is 300 in each. A report of “300 deleted records” is right for the second table and wrong for the first, and nothing in either table tells them apart.
The problem. An examiner who reads a counter needs to know which bound it gives, which operations break the bound, how often the stores of real phones present those operations, and what independent evidence can tighten it. We ask four questions about the SQLite stores of Android phones.
- RQ1 (Meaning). What does each counter state license about rows removed, in tables with and without AUTOINCREMENT, and which operations move it without a deletion?
- RQ2 (Rule). Can a decision rule bound the removals from what one table shows, and with what error on fixtures that follow the documented semantics?
- RQ3 (Stores). Which Android stores have which kind of counter, and what are the base rates of gaps, counter sets and anomalies on the 14 research phones, with the write-ahead log applied and without it?
- RQ4 (Tombstones and clean-up). How does the counter bound compare with the media store’s own tombstone table, and how do removals relate to clean-up applications installed on the phones?
Table 1 summarises the answers.
| RQ | Answer | Evidence |
|---|---|---|
| RQ1 Meaning | An AUTOINCREMENT counter minus the live count is an upper bound on rows removed; for plain and implicit-rowid tables the unused ids up to the newest row are a lower bound. Skipped inserts and upserts, explicit ids, counter sets, restores, counter edits and stopped multi-row OR FAIL inserts move the numbers or hide removals. | Sections 3.1, 4.1; Table 2; Figure 2 |
| RQ2 Rule | On 2,360 fixtures the rule’s bounds held in all 1,680 where SQLite chose the ids; where it did not they failed silently in 248 of 660 bounded fixtures, and the rule withheld 20. | Sections 3.2, 4.2; Table 2 |
| RQ3 Stores | All record tables were AUTOINCREMENT except sms on the non-Samsung phones. The media counter was set near 109 on 7 of 14 phones. After rebasing, a median 64 percent of issued media ids had no live row (calls 51, SMS 14, chat messages 11). Reading without the log changed the bound on 8 of 13 call logs. | Sections 4.3 to 4.5; Tables 3, 4; Figure 3 |
| RQ4 Tombstones, clean-up | The media tombstone table, which lists images and videos only, covered a median 39 percent of the ids without a live row, so it cannot show how loose the bound is. Clean-up applications: not measurable on these phones. | Sections 4.6 and 4.8; Figure 4 |
Contributions. This report makes four contributions.
- Two bounds with conditions: an upper bound on rows removed from an AUTOINCREMENT counter and a lower bound from the unused identifiers of a rowid table, with a table of the operations that move them, including skipped and upserted inserts that consume identifiers (Sections 3.1 and 4.1).
- A decision rule with a rebasing step for counters set to a large value, and its error on 2,360 synthetic fixtures built to the documented semantics, with the failures listed (Sections 3.2 and 4.2).
- A measurement of the counters in the media, message, call and contact stores of 14 Android phones: counter kind by vendor, media counters set near 109, base rates of removal, the effect of the log, and a census of 174,730 tables (Sections 4.3 to 4.5 and 4.7).
- A comparison of the counter bound with the media store’s tombstone table (images and videos only), and a reporting guide for examiners (Sections 4.6 and 5).
Scope. The fixtures show what the rule does under stated mechanisms, not how often a mechanism occurs. The phone results describe 14 research phones, 12 of them Samsung.
2 Background and Related Work
2.1 What SQLite guarantees
Without AUTOINCREMENT, a row inserted into an empty table receives id 1 and every later row, as a rule, the largest existing id plus one [23]; an insert that names no id leaves the choice to SQLite [24]. With the keyword, SQLite records the largest id used by a committed insert in the table sqlite_sequence; ids of rolled-back transactions are ignored, the counter does not follow an UPDATE of an id, and ordinary statements can edit the table [23]. The documentation adds that a failed insert may leave a gap. REPLACE deletes the conflicting row before it inserts the new one, and IGNORE skips the row [25]; neither page says whether a skipped or updated row consumes an id. A forum thread reports that an upsert does, and the SQLite author answers by quoting the documented gap rule [27]; Section 4.1 shows the same for INSERT OR IGNORE. VACUUM may change the ids of tables without an integer primary key [26]. The table sqlite_sequence is written when an inserting statement ends, a point Section 4.1 returns to.
2.2 Gap methods in practice
The practitioner sources we found read iOS Messages. A cookbook recipe finds missing primary-key values and applies them to counting deleted messages in an iPhone SMS database [11]. A Belkasoft article lists gaps with a window function and dates each gap by the neighbouring rows, on the premise that a gap is a user deletion [15]. A Vestige article subtracts the live count from the highest identifier and uses a deletion-log counter as a cross-check [21]. A blog post shows identifier reuse in tables without AUTOINCREMENT [10]. A GIAC paper treats missing records as a subject of its own [20]; we read its abstract page only. An iLEAPP artifact lists each gap, the timestamps around it and the difference between the counter and the highest live id, and states that a gap does not by itself establish a deletion [12]. None of these gives a bound, tests the operations that break it, or measures it on Android.
2.3 Recovering the content of deleted rows
Research on deleted SQLite records recovers content from free pages, freeblocks and the write-ahead log [13], [16], [19], [22], tests it on corpora [17] and surveys it [14]. The Lab’s earlier report measured what survives of a deleted row on 47 devices [3]. A count from a counter needs no content and survives where freed cells are zeroed, but says nothing about what a row held.
2.4 Android stores and clean-up applications
The Android media provider keeps a table of deleted media ids, deleted_media on the phones, with the id and a generation number. Its source adds an id when an image or a video is deleted, or stops being visible media (trashed, pending, or no longer an image or video), and removes it when the item is visible again; the table serves the photo picker and holds no other file types [8]. A public class for records of deleted media items was added in a later API version than any phone here runs [4]. The source sets the id counter from a value persisted outside the database, by inserting a row with an explicit id and deleting it; the default is 109 when no value exists, and each time the provider stores the value it stores it 1,000 above the counter [7]. After a database inconsistency it can re-insert rows from a backup with their earlier ids [6]. The platform telephony provider declares sms without AUTOINCREMENT and pdu, part and threads with it [9]; the call log declares calls with it [5]. A study of file-wiping applications on Android identified the artifacts that show the applications ran, not the effect on identifier counters [18].
Position of this work. The arithmetic is not new; practitioners use it on iOS. What we add is its direction, which depends on the kind of table; a test of the operations that break it; and its measured size on Android stores, including counter sets, vendor differences and the effect of the log, which the iOS sources do not meet.
3 Method
3.1 Quantities and bounds
Let a table hold N live rows with lowest and highest id m and M. If its key is declared INTEGER PRIMARY KEY AUTOINCREMENT (AI), SQLite keeps a counter s, the largest id used by a committed insert [23]. Other tables are plain (an integer primary key without the keyword) or implicit (no integer primary key). Write B = m − 1 for the ids below the lowest live row, I for the ids between m and M that no live row holds, and, in an AI table, T = s − M. An AI table has s − N = B + I + T ids without a live row (Figure 1).
Two quantities must be kept apart. A row removed existed in the table and no longer does. A record lost exists neither in the table nor in another table that holds it, such as a recycle bin. An application that updates by deleting and inserting removes rows and loses no records. Our bounds concern rows. Assumption E says that SQLite chose every id: no insert named an id, no statement changed one, the counter was not edited, the table was not recreated or restored from a copy, and no multi-row insert under OR FAIL stopped part-way (Section 4.1).
Proposition 1 (AI tables). Under E, the rows removed number at most s − N, with equality when every id issued became a row. Argument. An automatically chosen id is larger than every id used before, and the counter holds the largest id of a committed insert [23]. Every row ever written therefore holds one of the ids 1 to s, so at most s rows were written, and the N live rows are among them. Equality needs every id up to s to have gone to a row; a skipped insert or an upsert that updated spends an id without one (Section 4.1).
Proposition 2 (plain and implicit tables). Under E, the rows removed number at least B + I. Argument. A row inserted when M − 1 was the largest id received id M, and so on down to the first row of an empty table, which received 1 [23]. Every id from 1 to M was used since the table was last empty, and those that no live row holds belonged to rows removed. The ids above M leave no trace, because the next insert reuses them.
The bounds point in opposite directions. The counter overstates when ids are consumed without a row. The rowid bound understates when the newest rows are removed. Neither estimates the records lost, which also needs evidence that no removal was a replacement or a move.
3.2 Decision rule
The rule (Listing 1) takes what one table shows: its kind, N, m, M, s and the lengths of its gap runs. It returns bounds, not a count, and withholds them when the counter contradicts the rows. A run of 106 or more ids is read as a counter set, not as removal, and is removed from the bound except for one id, the row that sets the counter.
Listing 1: Decision rule, version 2. Runs are the gaps B, the interior gaps and, for AI tables, T.
big := runs of at least 10^6 ids # a counter set
AI table:
N > 0 and no counter row -> withhold (counter missing)
N > 0 and s < M -> withhold (counter low)
else upper := s - N - sum(r - 1 for r in big); lower := 0
plain or implicit table:
lower := B + I - sum(big); upper := noneVersion 1 withheld the bounds whenever a run of 106 ids was present. We changed it after reading the media stores (Section 4.4), and report both. A second change added B to the lower bound, which the first fixture run had omitted.
3.3 Synthetic fixtures
Each fixture is a SQLite database built in memory with SQLite 3.50.4 (Python 3.14.5) by executing the operations of one of 21 mechanisms (Table 2) on a table of one kind, with 200 or 2,000 initial rows and 20 seeds. Where a fraction applies it varied from 2 to 40 percent, and about half of the fixtures ended with new inserts. The generator’s bookkeeping gives, by construction, the rows created, the rows removed and the records lost; the rule sees only the final database. Mechanisms M13 to M16 and M18 to M20 break assumption E; M00 to M12 and M17 do not. A bounded verdict is sound if the lower bound does not exceed the rows removed and the upper bound is not below them; a silent failure is a bounded verdict that is not sound. This design was fixed before the first run. There were 2,360 fixtures: 19 mechanisms on three kinds and two on AI tables only.
3.4 Collection study
Evidence. Full file system extractions of 14 Android phones from the Lab’s research corpus, read only: 12 Samsung phones and two others, on Android 10 to 14 (5) and Android 16 (9). A comparison of hashed device identifiers found 14 different phones, as in LAB-TR-0024 [1], and the main files of the media store differ for all 14 phones.
Stores. We read five providers: the media provider (files in the external and internal database), the telephony provider (sms, pdu, part, threads), the call log (calls), the Google messaging application (messages, conversations, parts) and the contacts provider (raw_contacts). A runner copied each database and its -wal file to a private working folder, opened the copy with SQLite so that the log was applied, read the schema, sqlite_sequence, the row count, the list of ids and, for an order check, one or two time columns, and deleted the copy. It also read the main file alone. For each store and database name we used the first user-0 copy in path order; copies with the same main file counted once. Stores of additional profiles and rollback snapshots were read separately and are not mixed with the primary user’s.
Witnesses and census. The media provider’s deleted_media table (tombstones), and the recycle-bin tables of the telephony provider where present, were read as in-store records of removal; for the live rows of the media store we also counted the media types and the trashed and pending flags. The census read every other file with a database name (an extension such as .db or .sqlite, or a place in an Android databases folder) of 512 bytes to 16 MiB, log applied, for the counters of its rowid tables (tables without rowid, virtual tables and their shadow tables were left out): 23,651 database files of 25,099 candidates (the others lacked the SQLite header or could not be read). Identical copies under several paths were not merged in the census. Files were assigned to families by path as in LAB-TR-0023 [3]. Package lists were read to find clean-up applications: a pre-stated list of name keywords for third-party packages (clean, boost, junk, optimiz, speedup and similar), and the package names of the platform storage manager, the Samsung device-care and security components and two file managers, chosen by the authors for their storage-management role and not checked against vendor documentation.
Pre-statement. The sample, stores, tables and measures were fixed in the runner before the first full run. Three changes followed it and are marked where they appear: rebasing of counter sets and the addition of B to the lower bound (both Section 3.2), and a check for updated copies of two file managers, added to the package step. The runner was run twice, before and after adding the rebasing fields; the second run reproduced every row count, counter and extreme id of the first on all 118 store instances compared (distinct by store, database name, instance class and main-file hash).
4 Results
4.1 What moves a counter
Table 2 lists 21 mechanisms with their effect on the counters and the result on the fixtures. Deleting rows moved the AI bound exactly: the difference s − N equalled the records lost in every fixture of M01 to M05 and M17. A skipped INSERT OR IGNORE and an upsert that updated each consumed one id, so a table with no deletion showed a difference equal to the number of skipped attempts (M08, M09). Failed inserts and rolled-back inserts consumed none in SQLite 3.50.4 (M06, M07), although the documentation allows a gap [23]. Replacing a row, deleting and re-inserting it, and moving it to a bin each removed one row and lost no record (M10 to M12). Figure 2 shows the error of s − N against the records lost.
One mechanism outside the fixtures. A multi-row INSERT OR FAIL that stops at a conflict keeps the rows it wrote but does not advance the counter. In SQLite 3.50.4, a table of one row received such a statement that wrote two rows. It then showed three rows, highest id 3 and counter 1, and the rule withholds the bound (counter low). After the two rows were deleted it showed one row, highest id 1 and counter 1: the bound was 0 although two rows had been removed. The next insert repairs the counter. We found this with a separate check that is not part of the fixtures: 3,000 random operation sequences per table kind (inserts, skipped, replaced and upserted inserts, rolled-back transactions and savepoints, deletions, VACUUM), with the bounds tested after every statement. Without OR FAIL the upper bound failed in none of 74,509 checks of AUTOINCREMENT tables, and the lower bound in none of 75,007 checks of plain and 75,586 of implicit tables. With it the upper bound failed in 2,206 of 70,136 checks. The check was written by the same authors and uses the same engine as the fixtures.
| Mechanism | Effect on the counters | Rows removed | Records lost | AI error | AI | Pl | Im |
|---|---|---|---|---|---|---|---|
| M00 no removal | No change. | 0 | 0 | 0 | 40 | 40 | 40 |
| M01 delete scattered | +1 to s − N per row; +1 to the rowid bound unless newest. | 504 | 504 | 0 | 40 | 40 | 40 |
| M02 delete oldest | As M01; the oldest rows fall in B. | 544 | 544 | 0 | 40 | 40 | 40 |
| M03 delete newest | AI: counted in T. Rowid: no trace (ids reused). | 483 | 483 | 0 | 40 | 40 | 40 |
| M04 delete block | As M01. | 338 | 338 | 0 | 40 | 40 | 40 |
| M05 delete all, continue | AI: counted. Rowid: ids restart at 1, no trace. | 2,000 | 2,000 | 0 | 40 | 40 | 40 |
| M06 rolled-back inserts | None; rolled-back ids are reused. | 0 | 0 | 0 | 40 | 40 | 40 |
| M07 failed inserts | None in SQLite 3.50.4. | 0 | 0 | 0 | 40 | 40 | 40 |
| M08 insert or ignore | +1 to s − N per skipped insert; none for rowid. | 0 | 0 | +200 | 40 | 40 | 40 |
| M09 upsert | As M08. | 0 | 0 | +200 | 40 | 40 | 40 |
| M10 insert or replace | +1 per replaced row: a row is removed, the record kept. | 200 | 0 | +200 | 40 | 40 | 40 |
| M11 delete and reinsert | As M10. | 200 | 0 | +200 | 40 | 40 | 40 |
| M12 move to bin | As M10; the record stays in the bin. | 200 | 0 | +200 | 40 | 40 | 40 |
| M13 explicit small ids* | Adds each jump to s − N and to the rowid bound. | 0 | 0 | +4,948 | 40 | 0 | 0 |
| M14 seeded counter* | Adds about 109 to s − N; the rule rebases. | 1 | 0 | ≈ 109 | 40 | 40 | 40 |
| M15 restore keeping ids* | Gaps kept; T lost if the newest rows were deleted. | 350 | 350 | 0 | 32 | 40 | 40 |
| M16 restore with new ids* | History erased; both bounds restart. | 427 | 427 | -427 | 0 | 40 | 40 |
| M17 vacuum | None for integer keys or indexed implicit ids; an implicit table without an index is renumbered (separate test). | 294 | 294 | 0 | 40 | 40 | 40 |
| M18 counter lowered* | Hides T and any removal above the new value. | 100 | 100 | -100 | 0 | – | – |
| M19 counter raised* | Adds the increase to s − N. | 490 | 490 | +2,539 | 40 | – | – |
| M20 rowid changed* | Counter unchanged; gaps appear in the rowid bound. | 222 | 222 | +163 | 20+20w | 0 | 0 |
4.2 The rule on the fixtures
Under assumption E (M00 to M12 and M17, 1,680 fixtures), the bounds were sound in all 1,680, for each of the three kinds. The AI upper bound equalled the rows removed in every fixture of M00 to M07, M10 to M12 and M17; skipped inserts (M08, M09) made it exceed them by the number of skips. The lower bound of the other kinds equalled the rows removed in 33 to 40 of the 40 fixtures of each of M01, M02, M04 and M10 to M12 and in 25 to 31 after VACUUM (M17), and was zero in all fixtures of M03 and M05, where only the newest rows or all rows were removed. Where E does not hold (M13 to M16, M18 to M20, 680 fixtures), the rule withheld 20 (a counter below the highest id, M20 on AI tables) and returned 412 sound and 248 unsound bounds. The silent failures were: a restore with new ids (M16, AI, 40 of 40, the history is erased); a lowered counter (M18, 40 of 40); a restore that kept ids after the newest rows were deleted (M15, AI, 8 of 40); and explicit ids or changed ids in tables without a counter (M13, M20, 80 each). The upper bound was sound but loose after explicit jumps (M13) and a raised counter (M19), and tight after a counter set to 109 only because of the rebasing step (M14); with version 1 of the rule those 40 fixtures were withheld.
4.3 Stores and counters on 14 phones
Table 3 gives the counter kind and the bound for each record table. Every table was AUTOINCREMENT except sms on the two non-Samsung phones, where it is a plain integer key, as in the platform source [9]; on the 11 Samsung phones that have the store it is AUTOINCREMENT. The same table therefore yields an upper bound on one phone and a lower bound on another. Figure 3 shows, for each table, the share of issued ids with no live row on each phone. On the two plain tables the lower bound was 16,213 ids of a pooled span of 38,021, all on one phone; on the other it was zero.
The bound was positive in 14 of 14 media tables, 12 of 13 call logs, 10 of 10 AUTOINCREMENT sms tables and 10 of 10 chat message tables. Almost all of it lay between live rows: the top gap was zero in every call, SMS, MMS and chat table, and the gap below the lowest row held 12.4 percent of the call-log bound (consistent with trimming of the oldest calls) and under 5 percent in the other tables. For a plain table, whose top gap is invisible, this suggests the loss is small here; it is not evidence that no newest rows were removed.
| Store | Table | Phones | Counter | Bound > 0 | Median bound | No-live share | Location (interior / below / above) | Order |
|---|---|---|---|---|---|---|---|---|
| Media provider | files (external) | 14 | AI | 14 of 14 | 2,930 | 64 (19–83) | 100 / 0 / 0 | 0.1 |
| Media provider | files (internal) | 14 | AI | 7 of 14 | 0 | 0 (0–2) | 97.1 / 0 / 2.9 | 0 |
| Call log | calls | 14 | AI | 12 of 13 | 599 | 51 (21–82) | 87.6 / 12.4 / 0 | 1.4 |
| Telephony | sms | 13 | AI 11, plain 2 | 10 of 10 | 430 | 14 (4–42) | 98.4 / 1.6 / 0 | 1.1 |
| Telephony | pdu (MMS) | 13 | AI | 12 of 12 | 914 | 10 (5–25) | 96.6 / 3.4 / 0 | 1.2 |
| Telephony | threads | 13 | AI | 11 of 13 | 66 | 33 (12–44) | 95.7 / 4.3 / 0 | – |
| Google messaging | messages | 11 | AI | 10 of 10 | 1,974 | 11 (6–27) | 99.8 / 0.2 / 0 | 17.6 |
| Contacts provider | raw_contacts | 14 | AI | 12 of 14 | 470 | 52 (36–78) | 99 / 0.7 / 0.3 | – |
4.4 Counters set near 109
The media provider’s counter was set near 109 on 7 of 14 phones (4 of 5 on Android 10 to 14 and 3 of 9 on Android 16), as the source predicts when no persisted value exists [7]. The same code stores the counter 1,000 above its last value, so after a rollback the counter can sit about a thousand above the last id issued; the rule does not rebase such small sets (Section 6). On six of the seven the lowest live id was within about 6,000 of 109, so the raw difference s − N overstated the removal by about a billion; on the seventh, live rows also lay far below the set value. Over all 14 media tables, with the runs removed (Listing 1), the bound ranged from 17 to 163,220 rows and the share of issued ids with no live row from 3 to 97 percent (median 64). A set counter is consistent with a recreated database or a lost persisted id (Section 2.4); it says nothing about what was removed before. In the 2 rollback snapshots of the external media database, the counter was not above that of the live database (2 of 2).
4.5 The write-ahead log
Reading a store without its log changed the answer for several tables (Table 4). The bound differed for 9 of 14 media tables and 8 of 13 call logs, with the live count of a call log differing by up to 22 rows; the telephony and chat tables did not change. The counter itself differed in 10 call logs: the newest inserts were in the log. This repeats, for counters, the effect the Lab reported for another store [2].
sms; pdu, part and threads did not differ either.| Table | Phones | Live count | Counter | Bound |
|---|---|---|---|---|
Media provider, files (external) | 14 | 9 | 4 | 9 |
Call log, calls | 13 | 7 | 10 | 8 |
Contacts provider, raw_contacts | 14 | 3 | 2 | 2 |
Telephony, sms, pdu, part, threads | 13 | 0 | 0 | 0 |
Google messaging, messages | 11 | 0 | 0 | 0 |
4.6 Counter bound against the tombstone table
The media provider keeps deleted_media, a tombstone table for the photo picker; its source writes to it for images and videos only (Section 2.4). It is therefore not a general deletion log and cannot record the removal of other file types. 13 phones had the table; it held 41,025 tombstones. Of the 413,527 ids without a live row (counter sets excluded), 39,836 were tombstoned (9.6 percent pooled). Per phone the share ranged from 0.8 to 99 percent, median 39 (quartiles 12 to 70); restricted to ids above the oldest tombstone it was 46 percent (Figure 4). The counter bound was within 1.2 times the tombstones on 3 phones, and a median 2.6 times on the 13, up to 124 times. These ratios do not measure how loose the bound is. Of the 201,588 live rows on the 14 phones, 111,670 (55 percent) were images or videos, and the types of deleted rows are not visible. The untombstoned ids may be removals of other types, removals that left no tombstone, or ids consumed without a row. In 1,189 of 41,025 tombstones, on 7 phones, the id was live again: 34 of those rows were in the trash, 0 were pending and 43 were images or videos. The source also adds a tombstone when an item stops being visible media without being deleted; we did not test which cases apply. A tombstone therefore does not prove that the row is absent now.
The Samsung telephony provider keeps a recycle bin for messages. It held rows on 3 of 10 AUTOINCREMENT phones. On one phone the bin held more rows than the table had ids without a live row. We did not compare their ids; a bin row need not have passed through this table’s counter, for example after a restore or import with supplied ids.
4.7 Other tables
The census read 174,730 rowid tables. Of 14,347 AUTOINCREMENT tables that had ever been written, 3,254 (23 percent) held no row; of 10,540 non-empty ones, 4,875 (46 percent) had a positive bound, and 1,580 (11 percent of those written) contained a run of 106 ids. Among tables with 100 or more issued ids, the median share without a live row was 95 percent, against 64 for media, 51 for calls and 11 for chat messages (Table 5). Where a table is a queue or a cache, the ids issued follow its traffic, and the bound measures traffic rather than deletion; we did not classify tables by role. Of 3,623 plain tables with two or more rows, 1,346 (37 percent) had a positive lower bound; of 16,463 implicit tables, 7,121 (43 percent). 3 AI tables had a counter below their highest id.
| Family | AI written | Empty (%) | No-live share (%) | Plain gap (%) |
|---|---|---|---|---|
| OS system | 453 | 6 | 83 | 12 |
| Platform app | 2,545 | 17 | 99 | 53 |
| OEM or carrier app | 6,336 | 14 | 64 | 44 |
| Third-party app | 5,002 | 39 | 99 | 47 |
| All families | 14,347 | 23 | 95 | 42 |
4.8 Clean-up applications
No phone had a third-party package whose name matched the pre-stated clean-up keywords. Storage-care components on the pre-stated list were present on 14 of 14 phones, and updated copies of the two file managers on the list on 2 and 8. For these 10 copies the first-install time was not recorded in 8 and was a date at the turn of 2009 in 2, which cannot be an installation date on these phones, so no removal could be placed before or after an installation. With no third-party cleaner and no usable install time, the relation between removals and clean-up applications is not measurable on these phones, and we make no claim about it.
5 Discussion
What a counter supports. Table 6 gives the statement each reading supports. An AUTOINCREMENT difference is an upper bound on rows removed, valid if no id was supplied or edited and if the application does not skip inserts; the application source can settle the second condition, and the table cannot. The media provider’s tombstone table covers images and videos only, so it cannot test the bound for other file types. For plain tables the statement reverses: the unused ids are removals, and the newest are invisible.
| State of the table | Supported statement | Check before reporting |
|---|---|---|
| AUTOINCREMENT, counter consistent | At most s − N rows were removed. | Skipped inserts, explicit ids, restores, counter edits, a multi-row OR FAIL insert stopped part-way; replacement and moves remove rows without losing records. |
| AUTOINCREMENT, counter set (run ≥ 106) | At most s − N − (run − 1) rows were removed since the set. | Says nothing about removals before the set; the database was recreated or its persisted id was lost. |
| AUTOINCREMENT, counter below highest id or missing | No bound. | Edited counter, changed ids, or a recreated table. |
| Plain or implicit rowid | At least B + I rows were removed. | The newest removals leave no trace; explicit ids inflate the bound. |
| No gap in either kind | No removal is shown. | Not evidence that none occurred. |
| Any kind, store read without its log | The statement concerns the main file only. | Read the log; the bound changed for many call logs and media stores. |
Neighbours do not date a gap. The practitioner method dates a gap by the rows around it [15]. On the chat table the time column ran backwards between neighbouring ids for a median 17.6 percent of pairs (up to 96 percent), and for 1.2 percent of MMS and 1.4 percent of call-log pairs; media ids followed the insertion generation, with a median 0.1 percent of pairs reversed. Where ids do not follow time, the neighbours bound nothing.
What would tighten the bound. Three sources would: a record inside the store (a bin, an audit table, or tombstones for the types they cover); the application’s code, to show that it does not skip inserts or supply ids; and a second copy, such as a snapshot, to show the counter never fell. Each is available for some stores and absent for most.
6 Threats to Validity
Internal validity. The generator, the rule and the runner were written by the same authors and checked against SQLite 3.50.4, not against an independent implementation. The mechanisms are those we thought of; the fixtures therefore bound what the rule does for them and nothing else. The rule’s threshold of 106 ids was chosen after reading the media stores and is untested on counters set to smaller values. Counter sets below 106 (the provider stores its counter 1,000 above the last value) are not rebased and add to the bound. The upper bound also fails after an INSERT OR FAIL that stops part-way (Section 4.1); we did not measure how often phones do this. The tombstone table lists images and videos only, so the comparison cannot test the bound for other types, and it ignores ids that were removed and returned. The statements about the provider source (Section 2.4) come from one snapshot of the main branch, dated March 2025, and were not matched to the release of each phone.
Construct validity. The bounds are on rows. Whether a removed row was a lost record needs records inside the store, as listed in Section 5. The share of issued ids without a live row is a ratio of counters, not a rate of deletion by users. Id order was compared with one or two time columns per table; a column that is not the insertion time (message time, received time) overstates disorder.
External validity. 14 research phones from one collection are not a sample of phones in use; 12 are Samsung and the releases span Android 10 to 16. Behaviour of the media counter depends on the provider release and on a persisted value we did not observe. The results apply to the stores read and say nothing about third-party applications beyond the census.
Conclusion validity and limitations. No hypothesis is tested; per-phone shares are summarised by medians and quartiles. The clean-up question could not be answered here. We did not decode any row, so the contents of the removed records are not examined, and we did not install or remove applications on any phone.
7 Conclusion
A counter minus a row count is not a count of deleted records. In an AUTOINCREMENT table it is an upper bound on rows removed, which skipped inserts, explicit ids and counter sets raise and restores and counter edits lower; in a plain table the unused ids are a lower bound, and the newest removals leave no trace. On 2,360 fixtures the bounds held wherever SQLite chose the ids, and failed silently in 248 of 660 where it did not; a separate check found one more exception, a multi-row INSERT OR FAIL that stops part-way. On 14 Android phones the media store’s counter had been set near a billion on 7, the same sms table had different counter kinds on different vendors, reading without the log changed the call-log bound on 8 of 13 phones, and the media store’s tombstone table, which lists images and videos only, covered a median 39 percent of the gap. Examiners can use the bounds if they state the store, the release, the counter kind and the log state. What remains open is the frequency of the breaking mechanisms on phones in use, the behaviour of third-party message stores, and the relation of removals to clean-up applications.
Artifact Availability
The decision rule (Listing 1), the generator of the 21 mechanisms of Table 2, the random-sequence check of Section 4.1, a generic reader that applies the rule to the counters of SQLite files named in a configuration file, and a self-test will be released in the Lab's public artifacts repository, with no release date set (Python standard library only; code under the MIT licence, data and text under CC BY 4.0). The package is not public yet, and the sentences that follow describe it as planned. With SQLite 3.50.4 they reproduce Table 2, Figure 2 (re-drawn), the example of Section 1, the counts of Section 4.2 and the checks of Section 4.1; the package holds no data of any phone. The phone results (Tables 3 to 5, Figures 3 and 4, Sections 4.3 to 4.8) come from the Lab’s research corpus, which cannot be released; the readers that extract the stores from the corpus archives, the tombstone comparison, the census and the package-list step are not released, and the counter reader is run on invented files only.
Data Handling Statement
The evidence for this study is drawn from the Lab’s research corpus of mobile device extractions and was read only, together with synthetic data, namely the SQLite fixtures, which hold invented rows. From the extractions, the runner read the databases of five providers and of the census: schemas, counters, row counts, row identifiers, one or two time columns per table for an order check, the identifiers and generation numbers of the media tombstone table, counts of live media rows by media type and by trashed and pending flag, and package names; no message text, number, name or file name was read into a result. The report gives aggregate counts and device classes. It contains no identifiers, personal data, message or file content, or case information. Only aggregate statistics, counts, OS versions, device classes and generic families are reported; no names, numbers, accounts, identifiers, application names or file paths of the collection appear in this paper or its figures. Figures 3 and 4 show one anonymous value per phone, not linked to a device, model or vendor.
Declaration of AI Assistance
The authors conceived the research questions and directed the work. The measurement code, the data checks and the first draft of this report were produced with AI assistance (Anthropic Claude). The authors reviewed the results and the text and are responsible for the content.
References
- Daniel Addai, Sanders Larweh Tetteh, Selorm Adjabeng, and Kingsley Albert Egyir. 2026. How Much of a Full File System Extraction Is Needed? Measuring Over-Collection and Third-Party Data in iOS and Android Extractions. Lab Technical Report LAB-TR-0024, version 1.0. SectraTEK Lab, Prudential Associates. https://lab.sectratek.com/research/reports/lab-tr-0024/
- Daniel Addai. 2026. Screen Time on iOS 15 to 27: Mostly Empty Usage Tables and Counts That Change Without the Write-Ahead Log. Lab Technical Report LAB-TR-0009, version 1.0. SectraTEK Lab, Prudential Associates. https://doi.org/10.5281/zenodo.23717933
- Daniel Addai, Kingsley Albert Egyir, Sanders Larweh Tetteh, and Selorm Adjabeng. 2026. Zeroed Cells, Kept Pages, Pending Logs: What SQLite Leaves of a Deleted Row on 47 iOS and Android Devices. Lab Technical Report LAB-TR-0023, version 1.0. SectraTEK Lab, Prudential Associates. https://lab.sectratek.com/research/reports/lab-tr-0023/
- Android Developers. [n. d.].
MediaStore.DeletedFiles. Retrieved October 28, 2026 from https://developer.android.com/reference/android/provider/MediaStore.DeletedFiles (Page read in full. The class is marked as added in a later API version than the phones here run, and it names a tabledeleted_files, not thedeleted_mediatable read on the phones.) - Android Open Source Project. 2026.
platform/packages/providers/ContactsProvider,src/com/android/providers/contacts/CallLogDatabaseHelper.java, main branch (commit cf86ae5). Retrieved October 28, 2026 from https://android.googlesource.com/platform/packages/providers/ContactsProvider/+/refs/heads/main/src/com/android/providers/contacts/CallLogDatabaseHelper.java (Raw text read.) - Android Open Source Project. 2026.
platform/packages/providers/MediaProvider,src/com/android/providers/media/DatabaseBackupAndRecovery.java, main branch (commit a183e2b, March 10, 2025). Retrieved October 28, 2026 from https://android.googlesource.com/platform/packages/providers/MediaProvider/+/refs/heads/main/src/com/android/providers/media/DatabaseBackupAndRecovery.java (Raw text read:recoverDataand the insert of backed-up rows with their ids.) - Android Open Source Project. 2026.
platform/packages/providers/MediaProvider,src/com/android/providers/media/DatabaseHelper.java, main branch (commit a183e2b, March 10, 2025). Retrieved October 28, 2026 from https://android.googlesource.com/platform/packages/providers/MediaProvider/+/refs/heads/main/src/com/android/providers/media/DatabaseHelper.java (Raw text read: the table definitions, thedeleted_mediadefinition and the next-row-id code. The table definitions agree with the schemas on the phones.) - Android Open Source Project. 2026.
platform/packages/providers/MediaProvider,src/com/android/providers/media/photopicker/data/ExternalDbFacade.java, main branch (commit a183e2b, March 10, 2025). Retrieved October 28, 2026 from https://android.googlesource.com/platform/packages/providers/MediaProvider/+/refs/heads/main/src/com/android/providers/media/photopicker/data/ExternalDbFacade.java (Raw text read:onFileDeleted,onFileUpdated,addDeletedMedia,removeDeletedMedia.) - Android Open Source Project. 2026.
platform/packages/providers/TelephonyProvider,src/com/android/providers/telephony/MmsSmsDatabaseHelper.java, main branch. Retrieved October 28, 2026 from https://android.googlesource.com/platform/packages/providers/TelephonyProvider/+/refs/heads/main/src/com/android/providers/telephony/MmsSmsDatabaseHelper.java (Raw text read in full: thesms,pdu,partandthreadsdefinitions. Main branch at commit bca387f, March 14, 2025.) - Damien Attoe. 2025. ROWID Reuse in SQLite Databases. Digital4n6 with Damien (blog), January 31, 2025. Retrieved October 28, 2026 from https://digital4n6withdamien.blogspot.com/2025/01/rowid-reuse-in-sqlite-databases.html
- Chapin Bryce and Preston Miller. 2017. Python Digital Forensics Cookbook. Packt Publishing, Birmingham, UK. ISBN 978-1-78398-746-7. (Not re-verified: recipe “Identifying gaps in SQLite databases” known from the publisher’s chapter listing and search excerpts; the page returned an access error.)
- iLEAPP project. 2026.
scripts/artifacts/SMSmissingROWIDs.py(artifact SMS_Missing_ROWIDs), main branch, blob 863ab513. Retrieved October 28, 2026 from https://github.com/abrignoni/iLEAPP/blob/main/scripts/artifacts/SMSmissingROWIDs.py - Sangjun Jeon, Jewan Bang, Keunduck Byun, and Sangjin Lee. 2012. A recovery method of deleted record for SQLite database. Personal and Ubiquitous Computing 16, 6 (2012), 707–715. https://doi.org/10.1007/s00779-011-0428-7 (Bibliographic data from Crossref; full text not read.)
- Seonghyeon Lee, Sooyoung Park, Insoo Lee, and Jongmoo Choi. 2025. A comprehensive analysis and evaluation of SQLite deleted record recovery techniques: a survey. Forensic Science International: Digital Investigation 55 (2025), 302031. https://doi.org/10.1016/j.fsidi.2025.302031 (Bibliographic data from Crossref; full text not read.)
- James McGee. [n. d.]. Lagging for the Win: Querying for Negative Evidence in the sms.db. Belkasoft. Retrieved October 28, 2026 from https://belkasoft.com/lagging-for-win
- Christian Meng and Harald Baier. 2019. bring2lite: A structural concept and tool for forensic data analysis and recovery of deleted SQLite records. Digital Investigation 29, Supplement (2019), S31–S41. https://doi.org/10.1016/j.diin.2019.04.017 (Bibliographic data from Crossref; full text not read.)
- Sebastian Nemetz, Sven Schmitt, and Felix Freiling. 2018. A standardized corpus for SQLite database forensics. Digital Investigation 24, Supplement (2018), S121–S130. https://doi.org/10.1016/j.diin.2018.01.015 (Bibliographic data from Crossref; full text not read.)
- Dong Bin Oh, Somi Lim, Suji Lee, Yesong Jo, Gahyun Choi, Bumyun Kim, and Huy Kang Kim. 2026. Forensic analysis and evaluation of file-wiping applications in Android OS. Journal of Forensic Sciences 71, 1 (2026), 338–352. https://doi.org/10.1111/1556-4029.70174 (Article page read; it does not mention MediaStore or identifier gaps.)
- Dirk Pawlaszczyk and Christian Hummert. 2021. Making the invisible visible: techniques for recovering deleted SQLite data records. International Journal of Cyber Forensics and Advanced Threat Investigations 1, 1–3 (2021), 27–41. https://doi.org/10.46386/ijcfati.v1i1-3.17 (Bibliographic data from Crossref; full text not read.)
- Shafik G. Punja and Ian Whiffin. 2021. Missing SQLite Records Analysis. GIAC research paper 40195, March 12, 2021. Retrieved October 28, 2026 from https://www.giac.org/research-papers/40195 (Abstract page read; the PDF was not read.)
- Alyssa Rhodes. 2023. Forensic challenges and solutions with the new iPhone message deletion. Vestige, June 13, 2023. Retrieved October 28, 2026 from https://www.vestigeltd.com/resources/articles/forensic-challenges-and-solutions-with-the-new-iphone-message-deletion/
- Paul Sanderson. 2018. SQLite Forensics. Independently published. ISBN 978-1980293071. (Not re-verified: details from retailer listings and a review.)
- SQLite. [n. d.]. SQLite Autoincrement. Retrieved October 28, 2026 from https://www.sqlite.org/autoinc.html
- SQLite. [n. d.]. CREATE TABLE (ROWID and the INTEGER PRIMARY KEY). Retrieved October 28, 2026 from https://www.sqlite.org/lang_createtable.html
- SQLite. [n. d.]. ON CONFLICT clause. Retrieved October 28, 2026 from https://www.sqlite.org/lang_conflict.html
- SQLite. [n. d.]. VACUUM. Retrieved October 28, 2026 from https://www.sqlite.org/lang_vacuum.html
- SQLite User Forum. 2021. INTEGER PRIMARY KEY AUTOINCREMENT with UPSERT skips numbers. Thread of April 6, 2021. Retrieved October 28, 2026 from https://www.sqlite.org/forum/info/98d4fb9ced866287