1. A method comprising: accessing a hierarchical spatial index comprising a plurality of leaf nodes and a plurality of non-leaf nodes, each leaf node of the plurality of leaf nodes representing a bounding region containing a spatial object stored in a spatial database, each non-leaf node of the plurality of non-leaf nodes representing a bounding region at least partially containing one or more spatial objects associated with one or more leaf nodes, wherein any child node descending from any of the plurality of non-leaf nodes is at least partially contained within the bounding region of its ancestor non-leaf nodes; determining a plurality of selected nodes selected from the plurality of non-leaf nodes; for each particular node in the plurality of selected nodes, determining a weight, the weight being based on a number of spatial objects contained within the bounding region of the particular node; determining a spatial partitioning comprising a plurality of partitions containing the plurality of selected nodes; generating a spatial histogram based on the spatial partitioning and the weights of the plurality of selected nodes; wherein the method is performed by one or more computing devices.