Google patents database cleanup method using status flags
Google has been granted a patent for a method to manage database storage by using small status flags, or hint bits, to track which data entries are no longer needed. When enough entries are marked as dead, the system groups them together, removes them from the main index, and sends a record of this cleanup to backup servers to keep them in sync.
In the filing’s own words
A system includes data processing hardware and memory hardware. The memory hardware store instructions that cause the data processing hardware to obtain one or more hint bits for a B-tree index page of a database, each hint bit representing a status of a corresponding tuple of the B-tree index page and determine, using the one or more hint bits, that a threshold amount of tuples of the B-tree index page are dead. Responsive to determining that the threshold amount of tuples of the B-tree index page are dead, the instructions cause the data processing hardware to generate a list of dead tuples, determine, based on the list of dead tuples, a transaction identifier, delete, from the B-tree index page, each tuple in the list of dead tuples, and generate, using the transaction ID, a write-ahead logging record for the deletion of each tuple in the list of dead tuples.
What exactly they claim (claim 1)
1. A computer-implemented method comprising: obtaining, by a computing system, one or more hint bits for a B-tree index page of a database, each hint bit of the one or more hint bits representing a status of a corresponding tuple of the B-tree index page; determining, by the computing system and using the one or more hint bits, that a threshold amount of tuples of the B-tree index page are dead; responsive to determining that the threshold amount of tuples of the B-tree index page are dead: generating, by the computing system and using the B-tree index page, a list of dead tuples; determining, by the computing system and based on each tuple in the list of dead tuples, a transaction identifier; deleting, by the computing system and from the B-tree index page, each tuple in the list of dead tuples; and generating, by the computing system and using the transaction identifier, a write-ahead logging record for the deletion of each tuple in the list of dead tuples; and propagating the write-ahead logging record to one or more secondary nodes of the database to enable the one or more secondary nodes to delete each tuple in the list of dead tuples.
Facts
- Company
- Google (Google LLC)
- Official title
- Asynchronous handling hint bits on index pages using garbage collection
- Patent number
- US12748742B2
- Application number
- 19177239
- Filed
- Apr 11, 2025
- Granted
- Sep 29, 2026
- Inventors
- 3
- Claims
- 20
Classified under
G06F 16/2246 Physics & computingG06F 12/0253 Physics & computingMore from Google in AI & software
- Google patents video search that answers questions using AI descriptions Sep 15, 2026
- Google patents photo tool that removes people and their gear Sep 15, 2026
- Google patents AI that writes live meeting notes and summaries Sep 15, 2026
- Google patents AI tool that turns messy emergency notes into clear messages Sep 3, 2026
- Google patents AI that clicks through apps to finish tasks for you Sep 24, 2026
Summaries are simplified from the filing’s own abstract and first claim. A patent filing is not a product announcement.
Patent data and drawings: U.S. Patent and Trademark Office (USPTO). Nebula is not affiliated with or endorsed by the USPTO.