1. Apparatus for rewriting a query during a database query processing operation, comprising: a memory; and at least one processor coupled to the memory and operative to: (i) process the query having one or more target attributes in accordance with at least a portion of a data set producing query results comprising the one or more target attributes and one or more auxiliary attributes, wherein the one or more auxiliary attributes are not included in the query; (ii) compare the query results to at least the portion of the data set to determine a relative selectivity for the one or more auxiliary attributes; and (iii) append the query with at least one new predicate corresponding to at least one of the one or more auxiliary attributes having a high relative selectivity to form a rewritten query; wherein the operation of appending the query with at least one new predicate comprises: selecting at least one of the one or more auxiliary attributes based at least in part on a ranking of the determined relative selectivity for the one or more auxiliary attributes; and appending the query with at least one new predicate corresponding to the selected at least one of the one or more auxiliary attributes to form the rewritten query.