[Blog](/blog/.md) # How we do indices in FoundationDB Indices turn full table scans into quick lookups. Here's how Tigris builds database indices on FoundationDB so object metadata queries stay low-latency. Author [![Xe Iaso](https://avatars.githubusercontent.com/u/529003?v=4)](https://xeiaso.net) [Xe Iaso](https://xeiaso.net) Senior Cloud Whisperer Published2026-10-27 Reading9 min Tags [Engineering](/blog/tags/engineering/.md)[foundationdb](/blog/tags/foundationdb/.md)[database](/blog/tags/database/.md)+2 Contents * [Databases and you](#databases-and-you) * [Indices in FoundationDB](#indices-in-foundationdb) * [Where can you use indices in Tigris?](#where-can-you-use-indices-in-tigris) * [The gory details](#the-gory-details) * [Adding to the indices](#adding-to-the-indices) * [An index is just more keys](#an-index-is-just-more-keys) The pithy way to think about Tigris is that we’re a database consultancy for an internal SRE client who itself is an SRE consultancy for an internal object storage client. As such, we have a lot of opinions about how databases should work and how to operate them at cloud scale. This mix of expertise lets us take something like [FoundationDB](https://www.foundationdb.org/) (an ordered key-value store that is microservices: the database) and implement database indices on top of it. But what are indices (also spelled indexes), why do they matter, and how do they let us give you what you really want: better object storage? ## Databases and you[​](#databases-and-you "Direct link to Databases and you") At some level a database is just a bunch of rows of records with a query language to better select parts of records based on specific criteria. Let’s imagine a database schema like this: ``` CREATE TABLE IF NOT EXISTS customers ( id INTEGER PRIMARY KEY AUTOINCREMENT , created_at TEXT NOT NULL DEFAULT CURRENT_TIMESTAMP , updated_at TEXT , deleted_at TEXT , name TEXT NOT NULL , email_address TEXT NOT NULL ); ``` This roughly maps to the following Go structure: ``` type Customer struct { ID int32 CreatedAt string // XXX sqlite has no time type UpdatedAt *string DeletedAt *string Name string EmailAddress string } ``` When the database server loads this all into memory, it basically puts it into a big slice of customer values. When you do a query such as: ``` SELECT * FROM customers WHERE email_address = 'xe@tigrisdata.com'; ``` Under the hood it turns into a for loop like this: ``` var result []Customer for _, customer := range db.Customers { if customer.EmailAddress == "xe@tigrisdata.com" { result = append(result, customer) } } // Draw the rest of the owl here ``` For decently small database tables that can fit into memory, this is fine. The problems here are twofold: 1. Any time you search for customers with any given email address, you have to scan over all of the records in the table (database nerds call this a full table scan). 2. Any time you want to make sure that two customers can’t share the same email address, you have to do that full table scan in your application code instead of that invariant being enforced by the database. To solve both of these problems, the database elders gave us [database indices](https://en.wikipedia.org/wiki/Database_index). You can think about an index as basically a hash table of values to row IDs, kinda like this: ``` type CustomerByEmailAddress map[string][]int32 ``` Or the following SQL: ``` CREATE INDEX customer_by_email_address ON customers(email_address); ``` Assuming you have records in your customers table along the lines of: ``` INSERT INTO customers ( id, name, email_address ) VALUES ( 1, 'Xe Iaso', 'xe@tigrisdata.com' ) , ( 2, 'Ovais Tariq', 'redacted@tigrisdata.com' ); ``` The contents of the `customer_by_email_address` index would look something like this: ``` CustomerByEmailAddressIdx := CustomerByEmailAddress{ "xe@tigrisdata.com": []int32{1}, "redacted@tigrisdata.com": []int32{2}, } ``` So then to look up the rows that contain the email address `xe@tigrisdata.com`, the database engine does a for loop like this: ``` var result []Customer rows, ok := db.CustomerByEmailAddressIdx["xe@tigrisdata.com"] if ok { for _, id := range rows { result = append(result, db.Customers[id]) } } // Draw the rest of the owl here ``` This converts your database interaction from having to read every row to only having to read a few rows at most. FIG 01Finding one customer, with and without an index ``` customers customer_by_email_address WHERE email_address = ... the same query, with the index ┌─────┬─────────────────────┐ ┌─────────────────────┬─────┐ │ id │ email_address │ │ email_address │ id │ ├─────┼─────────────────────┤ ├─────────────────────┼─────┤ │ 1 │ xe@tigrisdata.com │ ◀ read │ ana@example.com │ 2 │ │ 2 │ ana@example.com │ ◀ read │ bo@example.com │ 4 │ │ 3 │ dev@example.com │ ◀ read │ cy@example.com │ 5 │ │ 4 │ bo@example.com │ ◀ read │ dev@example.com │ 3 │ │ 5 │ cy@example.com │ ◀ read │ xe@tigrisdata.com │ 1 │ ▶ row 1 └─────┴─────────────────────┘ └─────────────────────┴─────┘ reads all 5 rows reads 1 entry, then 1 row ``` A unique index is basically the same thing but it has the constraint that each value can only point to one row: ``` CREATE UNIQUE INDEX customer_by_email_address ON customers(email_address); ``` Which is roughly Go type: ``` type CustomerByEmailAddress map[string]int32 ``` As an added bonus, if you try and insert two customers with the same email address, the database engine will stop you: ``` SQLite-3.54 in-memory-> INSERT INTO customers ;-> ( id, name, email_address ) ;-> VALUES ;-> ( 3, 'Xe Iaso but again', 'xe@tigrisdata.com' ); Error near line 33: UNIQUE constraint failed: customers.email_address ``` ## Indices in FoundationDB[​](#indices-in-foundationdb "Direct link to Indices in FoundationDB") This is all well and good if you’re using a relational database engine like SQLite, but how would you do it in FoundationDB? FoundationDB is basically a sorted map spread across a cluster, so you have to implement things on top of its primitives. Basically at a high level when you use indices in a relational database you need to ensure that the following things happen with regards to indices: 1. Inserting or removing data is reflected in the index in the same transaction, or at least fast enough that users don’t notice the churn. 2. Querying for data consults any indices first and does a full table scan only as a last resort. A full table scan is especially disastrous in a FoundationDB environment because [FoundationDB transactions have rather strict limits](https://apple.github.io/foundationdb/known-limitations.html): a transaction can’t run for more than five seconds or write more than 10 MB. The docs advise that if your architecture requires you to exceed one of those, you should consider a different architecture. ### Where can you use indices in Tigris?[​](#where-can-you-use-indices-in-tigris "Direct link to Where can you use indices in Tigris?") The main place we expose indices to users is with [Object Metadata Queries](https://www.tigrisdata.com/docs/objects/query-metadata/). They let you filter ListObjectsV2 calls via SQL-like queries like this: ``` WHERE `Last-Modified` > "2023-01-15T08:30:00Z" AND `Content-Type` = "text/javascript" ``` In order to make these queries efficient (and avoid the disastrous latency of full table scans), we have indices on the `Last-Modified` field. You can also filter and order by `Content-Type` and `Content-Length`, but we don’t currently have indices for those fields. This lets you write queries like this: ``` WHERE `Last-Modified` > "2022-06-10T14:20:00Z" AND `Content-Type` = "text/plain" AND key REGEXP ".*\.txt$" ``` This would let you filter for objects whose keys end in `.txt`, have a `text/plain` `Content-Type`, and were last modified some time after June 10, 2022. You can also use those fields for changing how results are ordered: ``` WHERE `Last-Modified` > "2023-08-14T11:30:00Z" AND `Content-Length` < 65536 ORDER BY `Content-Type` ``` This would let you find objects smaller than 64 KiB, last modified after August 14, 2023, and order them by the `Content-Type` in the results. ### The gory details[​](#the-gory-details "Direct link to The gory details") For the sake of argument, let’s say you list a bucket 5 objects at a time (`max-keys=5`) with a query like this: ``` WHERE `Content-Length` > 0 ORDER BY `Last-Modified` DESC ``` This gets compiled to our internal query DSL in memory (and thus has no real analogue in text), but you can kinda visualize it like this: ``` indexRange {"Bucket": "$bucket", "Index": "Last-Modified"} from "$max" to "$min" # reverse walk for ordering by later | pointRead {"Bucket": "$bucket", "Table": "global"} by "$key" | dropIf rowMissing or rowDoesNotMatchIndexEntry # stale entry → cleaner | filter {"Content-Length": {"$gt": 0}} # in memory, per row | take 6 # max-keys + 1 | resumeToken = lastIndexEntry ``` Internally this queries the index first and then goes about to read the actual data. The flow looks kinda like this: FIG 02A metadata query: Content-Length > 0, newest first, max-keys 5 ``` ┌───────────┐ ┌─────────┐ ┌────────┐ ┌──────────────┐ │ S3 client │ │ gateway │ │ server │ │ FoundationDB │ └─────┬─────┘ └────┬────┘ └────┬───┘ └───────┬──────┘ │ ListObjectsV2 │ │ │ │ + X-Tigris-Query │ │ │ │────────────────────────▶│ │ │ │ │ SQL → filter, sort │ │ │ │ │ │ │ │ Read(..., limit 6) │ │ │ │──────────────────────────▶│ │ │ │ │ plan: Last-Modified │ │ │ │ index, newest first │ │ │ │ │ │ │ │ get_range(index) │ │ │ │────────────────────────▶│ │ │ ┌─ loop ─┼─────────────────────────┼────┐ │ │ │ │ until 6 rows pass │ │ │ │ │ │ │ │ │ │ │ │ index entry │ │ │ │ │ │◀────────────────────────│ │ │ │ │ │ get(object row) │ │ │ │ │ │────────────────────────▶│ │ │ │ │ │ row │ │ │ │ │ │◀────────────────────────│ │ │ │ │ │ stale? send to cleaner │ │ │ │ │ │ match? keep the row │ │ │ │ └────────┼─────────────────────────┼────┘ │ │ │ │ │ │ 6 rows + resume token │ │ │ │◀──────────────────────────│ │ │ │ keep 5, IsTruncated │ │ │ │ │ │ │ 5 rows + │ │ │ │ NextContinuationToken │ │ │ │◀────────────────────────│ │ │ │ │ │ │ ``` Or basically: you start out by assembling a query plan, walking the relevant index in order, reading the row each entry points to, and filtering as you go until you hit the limit. Then you throw the results back to the user with a continuation token so they can iterate in future calls. The index is already sorted, so there’s no separate sort step. Fun fact: this is basically the same thing that happens in your MySQL or Postgres databases when you are doing queries that way. They don’t usually return continuation tokens though. ### Adding to the indices[​](#adding-to-the-indices "Direct link to Adding to the indices") Tigris implements indices as FoundationDB keyspaces kinda like this: FIG 03One Last-Modified index entry, as a FoundationDB key ``` key ──┬─ "glob_sidx" ‖ 7 ‖ 42 index keyspace prefix ├─ 02 "kvs" 00 sub-index ├─ 02 "Last-Modified" 00 field name ├─ 15 1e type 30 ├─ 02 "2026-10-22T19:00:00Z" 00 value, as RFC3339Nano text ├─ 14 position 0 └─ 02 "photos/a.jpg" 00 primary key: the object name value 3 fixed bytes EncodedEmptyTableData 02 … 00 is a string, 14 is the integer 0, 15 xx is a one-byte integer ``` When we insert or update objects into FoundationDB, we also add index rows in the same transaction. This is the same idea MySQL and Postgres use. Indices being keyspaces means that we can easily query a range of keys in the keyspace of that index and then read them out really cheaply. That isn’t free. Every object write now also writes an index key, so each index adds work to every write. The executor also doesn’t trust index entries blindly: if the row an entry points to is gone or has a different timestamp, it skips the entry and queues it for a cleaner. That’s the `dropIf` step in the plan above. Something that struck me as a bit odd when I was researching this is that the objects that the indexes are pointing to are in the FoundationDB key instead of the value, like they were in my trivial Go example above. However, after some thinking and reading through the documentation, I think that this is one of the more clever abuses of FoundationDB at Tigris. Why? This lets you query key ranges with a simple range read instead of having to recursively read values from the database. The main primitives of FoundationDB are `get` for reading a single value out of the database, `set` for updating a value in the database, `clear` for removing a value from the database, `clear_range` for removing a range of values from the database, and `get_range` for reading many keys from the database. Of these, `get_range` keeps turning out to be the useful one. Let’s imagine that you have a bucket with a few image files that were generated once a month since February. The indices for that could look like this: FIG 04Five index entries, one for each monthly render ``` Last-Modified index for bucket renders, in key order (…, "Last-Modified", 30, "2026-02-20T09:00:00Z", 0, "renders/2026-02.webp") (…, "Last-Modified", 30, "2026-03-20T09:00:00Z", 0, "renders/2026-03.webp") (…, "Last-Modified", 30, "2026-04-20T09:00:00Z", 0, "renders/2026-04.webp") (…, "Last-Modified", 30, "2026-05-20T09:00:00Z", 0, "renders/2026-05.webp") (…, "Last-Modified", 30, "2026-06-20T09:00:00Z", 0, "renders/2026-06.webp") FoundationDB sorts keys byte by byte, so the entries sort by time ``` If you want to query the data from February 20th through April 20th, you can do that in a single `get_range` call: FIG 05A Last-Modified range becomes one get\_range call ``` ┌────────────────────────────────────────────────────┐ │ WHERE `Last-Modified` >= "2026-02-20T00:00:00Z" │ │ AND `Last-Modified` < "2026-04-21T00:00:00Z" │ └──────────────────────────┬─────────────────────────┘ │ ▼ ┌────────────────────────────────────────────────────┐ │ get_range( │ │ begin = (…, "Last-Modified", 30, "2026-02-20"), │ │ end = (…, "Last-Modified", 30, "2026-04-21"), │ │ ) │ └──────────────────────────┬─────────────────────────┘ │ ▼ begin ▶ 2026-02-20 2026-02-20 renders/2026-02.webp returned 2026-03-20 renders/2026-03.webp returned 2026-04-20 renders/2026-04.webp returned end ▶ 2026-04-21 2026-05-20 renders/2026-05.webp not read 2026-06-20 renders/2026-06.webp not read ``` And that’s most of a Tigris metadata query: one range read over the index, plus a point read for each entry it returns. ## An index is just more keys[​](#an-index-is-just-more-keys "Direct link to An index is just more keys") Databases aren’t magic! They’re carefully planned layers of abstraction on top of something like a key-value store, and an index is just more keys, sorted so that the question you want to ask becomes one range read. That ordering is how databases (or object storage services) can return results as fast as possible so you can move on with life and go make your impact on the world the way that really matters: via the creation of business to business software as a service applications. Do it on top of Tigris and get S3-compatible storage everywhere on the globe! Want to filter your buckets without a full scan? Object Metadata Queries let you filter and sort ListObjectsV2 results by Last-Modified, Content-Type, and Content-Length, and Last-Modified queries read an index instead of the whole bucket. [Read the metadata query docs→](https://www.tigrisdata.com/docs/objects/query-metadata/) ## Share [X](https://twitter.com/intent/tweet?text=Check%20out%20this%20post%20on%20the%20%40tigrisdata%20blog%3A%20How%20we%20do%20indices%20in%20FoundationDB%0A%0A\&url=https%3A%2F%2Fwww.tigrisdata.com%2Fblog%2Ffdb-indices)[Hacker News](https://news.ycombinator.com/submitlink?u=https%3A%2F%2Fwww.tigrisdata.com%2Fblog%2Ffdb-indices\&t=How%20we%20do%20indices%20in%20FoundationDB)[LinkedIn](https://www.linkedin.com/sharing/share-offsite/?url=https%3A%2F%2Fwww.tigrisdata.com%2Fblog%2Ffdb-indices)[Email](mailto:?subject=How%20we%20do%20indices%20in%20FoundationDB\&body=Hey!%0A%0ACheck%20out%20this%20article%20on%20the%20Tigris%20blog%3A%20https%3A%2F%2Fwww.tigrisdata.com%2Fblog%2Ffdb-indices)Copy link