Systems and methods are disclosed to implement the automatic creation of an auto-partitioning second index (APSI) for a storage object in a storage service. According to embodiments, when a query to the storage object is received specifying a sort condition based on an attribute of the storage object, the storage service may determine that an APSI should be created to optimize for queries with that type of sort condition. The storage service then automatically creates a new APSI that is partitioned according to an auto-generated partition key and stores the data in sorted order in each partition based on the attribute as a sort key. Later queries to the storage object specifying the same type of sort condition are forwarded to the new APSI. A query directed to the APSI is divided into subqueries sent to APSI's partitions in parallel, and results are aggregated to produce the final query result.