1. A method for optimizing queries over a vertically stored database having items that are partitioned into several partitions each having a partition signature representing items therein, the method comprising: decomposing a first query received from a user into multiple first subqueries; generating a signature for each first subquery in a way corresponding to the way of generating the partition signature; comparing the signature of each first subquery with partition signatures of all partitions, in order to obtain all partitions matching the first subquery; rewriting a second subquery translated from the first subquery based on the matching partitions, in order to obtain a rewritten second subquery; and composing rewritten second subqueries for all first subqueries to form a second query so that queries are executed over the database using the second query.