Methods and arrangements for storing and retrieving nested structures. A nested structure is obtained. There are created slices containing arbitrary sub-structures of the nested structure. The content of slices is stored in one or more columns of a column-oriented data store. At least one access plan for accessing slices in the data store is developed, to be used when a projection query is received. The access plan is executed to construct a nested structure that answers the projection query. Other variants and embodiments are broadly contemplated herein.