On Tue, Aug 30, 2016 at 1:10 PM, Nicolas Grilly <nicolas@vocationcity.com > wrote:
We are developing a multitenant application which is currently based on MySQL, but we're thinking of migrating to PostgreSQL.We rely on clustered indexes to preserve data locality for each tenant. Primary keys start with the tenant ID. This way, rows belonging to the same tenant are stored next to each other. Because all requests hit only one tenant, this is a great performance improvement.PostgreSQL doesn't have clustered indexes — I'm aware of the CLUSTER command but it's a one-time operation — and I'm wondering if this can be a problem or not.Let's say we have a table containing data for 10,000 tenants and 10,000 rows per tenant, for a total of 100,000,000 rows. Let's say each 8 KB block contains ~10 rows. Let's way we want to compute the sum of an integer column for all rows belonging to a given tenant ID.In MySQL/InnoDB, rows are stored in the leaf nodes of a B-tree. To compute the sum, MySQL has to read at least 1,000 blocks (each block containing ~10 rows). I deliberately neglect the cost of walking the B-tree intermediate nodes.By comparison, PostgreSQL has to read at least 10,000 blocks (each block containing ~10 rows, but most of the time, only one row will match the tenant ID, other rows belonging to other tenants).A few questions:- Am I missing something?- Am I overestimating the benefit of a clustered index in our case, and the cost of not having one in PostgreSQL?- Is there another technical solution to this problem?
After a few days thinking and researching about this, I've come to the following conclusion:
1) Trying to preserve data locality in a multi-tenant application is a legitimate requirement (because it can significantly improve performance).
2) But index organized tables are not the right answer.
3) Partitioning by tenant_id, sorting heap rows by tenant_id, and/or creating covering indexes (for index-only scans) are better solutions.
I found at least two examples of well-known companies using PostgreSQL at scale for a multi-tenant application, and taking specific steps to preserve data locality:
- Heap shards its data by customer_id (all rows in a logical shard belong to the same customer — except for small customers, but it's easy to make their queries fast anyway) [1].
- Instagram uses pg_reorg (the ancestor of pg_repack) to keep likes created by the same user contiguous on disk [2].
At first, I thought that index organized tables (aka clustered indexes) were the solution, and that missing them in PostgreSQL could be an issue, but I was wrong. They are not the right tool for the job.
Index organized tables are a powerful tool for an application that needs very fast lookups and range scans on the primary key. But they also have significant drawbacks [3]:
- Lookups on secondary keys are slower (because they need one more indirection).
- The index is bigger (because rows are stored directly in the index, instead of a heap).
- InnoDB can only use the primary key as clustering key, which is very restrictive (for example, in PostgreSQL, most recently inserted/updated rows are naturally clustered together, independently of the chosen primary key).
So, PostgreSQL uses heap organized tables instead of index organized tables, and this is a good thing, at least for the kind of queries my application needs. But, at scale, I still need to find a way to preserve data locality for each tenant.
The solutions I've identified are:
- Partition by tenant_id as suggested by Thomas Kellerer earlier in this thread. Declarative partitioning will make this easier in a future version of PostgreSQL. It's also possible to "shard" using Citus Data (like Heap or CloudFlare).
- Periodically sort rows by tenant_id in the heap, using something like pg_repack, as suggested by Kenneth Marshall and Ben Chobot.
- Create covering indexes, which let PostgreSQL do index-only scans (exactly like an index organized table), as suggested by Eduardo Morras and engineers at Heap [4].
It looks like I can move forward with our migration from MySQL to PostgreSQL, without worrying about the lack of clustered indexes, because there are better solutions to keep tenant data contiguous!
Thanks for all your comments.
Nicolas Grilly
[2] http://instagram-engineering.tumblr.com/post/40781627982/handling-growth-with-postgres-5-tips-from
[4] "Powering Heap", https://www.youtube.com/watch?v=NVl9_6J1G60
