This paper provides the first attempt for a full-fledged query optimizer for MapReduce-based spatial join algorithms. The optimizer develops its own taxonomy that covers almost all possible ways of doing a spatial join for any two input datasets. The optimizer comes in two flavors; cost-based and rule-based. Given two input data sets, the cost-based query optimizer evaluates the costs of all possible options in the developed taxonomy, and selects the one with the lowest cost. The rule-based query optimizer abstracts the developed cost models of the cost-based optimizer into a set of simple easy-to-check heuristic rules. Then, it applies its rules to select the lowest cost option. Both query optimizers are deployed and experimentally evaluated inside a widely used open-source MapReduce-based big spatial data system. Exhaustive experiments show that both query optimizers are always successful in taking the right decision for spatially joining any two datasets of up to 500GB each.
|Original language||English (US)|
|Title of host publication||GIS|
|Subtitle of host publication||Proceedings of the ACM International Symposium on Advances in Geographic Information Systems|
|Editors||Siva Ravada, Erik Hoel, Roberto Tamassia, Shawn Newsam, Goce Trajcevski, Goce Trajcevski|
|Publisher||Association for Computing Machinery|
|State||Published - Nov 7 2017|
|Event||25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2017 - Redondo Beach, United States|
Duration: Nov 7 2017 → Nov 10 2017
|Name||GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems|
|Other||25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2017|
|Period||11/7/17 → 11/10/17|
Bibliographical noteFunding Information:
1This work is partially supported by the National Science Foundation, USA, under Grants IIS-1525953, CNS-1512877, IIS-1218168.
2017 Association for Computing Machinery.
- Query Optimization
- Spatial Join