1. A method of generating an outlier index for a database and a given workload wherein the queries in the workload may have selection or group by conditions, the method comprising: identifying sub-relations of tuples in the database induced by selection and group by conditions in queries in the workload; generating a variance for values in each sub-relation; selecting sub-relations having higher variances; and generating outliers from the sub-relations having higher variances.