1. A non-transitory computer readable medium having computer instructions stored therein that when executed by a computer system cause the computer system to perform operations comprising: for each of at least two tenants in a multi-tenant database, computing the selectivity of different portions of that tenant's tenant-specific data based on at least two characteristics of that tenant's tenant-specific data other than characteristics identifying a user or tenant's access to data; storing an indication of the computed selectivity of different portions of that tenant's tenant-specific data; subsequent to the storing, receiving a query directed to tenant-specific data in the multi-tenant database of a particular one of the at least two tenants, wherein the query includes a plurality of query elements and has an associated query plan usable to implement the query; evaluating the associated query plan based on the stored indication of the computed selectivity of different portions of the particular tenant's tenant-specific data; based on the evaluating, modifying an ordering of query elements specified in the associated query plan to generate a modified query plan usable to implement the received query, wherein modification of the query plan is performed such that a first query element that is more selective of the particular tenant's tenant-specific data than a second query element is reordered within the query plan to be performed before the second query element; and providing, in place of the query plan, the modified query plan.