1. A computer-implemented method, comprising: receiving a spatial query on spatial data that specifies a query window, where the spatial data has an associated spatial data index; constructing a query window index structure describing a geometry of the query window; and comparing the query window index structure to the spatial data index to determine a spatial relationship between the query window and the spatial data.