In accordance with embodiments, there are provided mechanisms and methods for facilitating metadata-based statistics-oriented query processing for large datasets in an on-demand services environment. In one embodiment and by way of example, a method comprises evaluating metadata associated with a query placed on behalf of a tenant in a multi-tenant environment, and computing process statistics for the query based on the metadata, where the process statistics reveal an estimation of resources needed for execution of the query within a predictable amount of time and using fewer than or equal to an allocated number of scans of a database. The method may further include associating, based on the process statistics, a set of rules and the estimated resources to process the query, and executing the query based on the set of rules and using the estimated resources such that the query is processed within the predictable amount of time and using fewer than or equal to the allocated number of scans of the database.