Этот вопрос может быть немного не по теме, так как это скорее дизайн решения, чем строго программирование, но из ваших требований звучит так, что у вас есть хороший кандидат на HBase или Cassandra ,или, может быть, MongoDB (хотя я не уверен, насколько хорошо MongoDB оптимизирован для запроса нескольких атрибутов из тысяч).