Technologies are provided for using a multi-user execution plan cache to process database queries. A database query processor can be configured to store execution plans in a multi-user execution plan cache. The query processor can determine whether an execution plan is shareable by multiple database users. If the execution plan is shareable, it can be stored in the cache in association with a sharing user identifier. When a database query is received, the query processor can determine that the query can be performed using the cached execution plan. If the cached execution plan is shareable, the database query can determine whether the cached execution plan is valid for a database user associated with the received database query. If the cached execution plan is valid for the database user, the query processor uses the cached execution plan to perform the query for the associated database user.