A query of spatial data is received by a database comprising a columnar data store storing data in a column-oriented structure. Thereafter, a minimal bounding rectangle associated with the query is identified using a tree-order scanning technique. A spatial data set that corresponds to the received query is then mapped to the physical storage in the database using the identified minimal bounding rectangle. Next, the spatial data set is then retrieved. Related apparatus, systems, techniques and articles are also described.