Maintaining multiple field dynamic values
One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists.