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 data attributes in accordance with at least a portion of a data set producing query results; (ii) analyze the query results with respect to the one or more target attributes and one or more auxiliary attributes to determine a relative selectivity for each of the one or more target attributes and the one or more auxiliary attributes, wherein the one or more auxiliary attributes were not included in the query; 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.