Almost 40 years ago, IBM started research on join order optimisation by applying a classical technique called dynamic programming. This technique is still used by commercial database systems. However, research on the topic has stagnated. In revisiting the issue, a team led by Prof TAY Yong Chiang from the Department of Mathematics in NUS has discovered a new approach, based on sorting, that is much faster than the current techniques. They believe this approach will establish itself as another paradigm in query optimisation, and revive research in join ordering.
Their interest in this topic was motivated by social network services. Such a network needs a database system to properly manage its valuable data. However, many social network services are started by small teams with limited resources, who typically use free, off-the-shelf database systems, like MySQL. Some well-known social networks have discovered that such a generic system does not scale well when their services go viral.
The research team aims to replace MySQL with sonSQL, a database system that is tailored for social network data. In particular, the tables in sonSQL are specifically designed for social network data. This specific design makes it possible to provide an intuitive interface to help a naïve user translate the social network design into a set of tables for storing the data, as illustrated in the figure below. (More details on sonSQL can be found at http://sonsql.comp.nus.edu.sg/).
The sonSQL table design also facilitates various optimisations that make the system scalable. The next step in their research lies in applying the sorting technique and its theory to sonSQL’s table design.
Figure shows an intuitive interface for translating a social network design into a set of sonSQL tables for storing data [Image credit: Tay Yong Chiang].
References
1. Z Bao, J Zhou, YC Tay. “sonSQL: An extensible relational DBMS for social network start-ups (demo).” Proceedings of 32nd International Conference on Conceptual Modeling (ER 2013), Hong Kong, China (LNCS 8217) 495.
2. Y Zeng, AN Lu, Lu X, CX Tian, YC Tay. “SAM: A sorting approach for optimizing multijoin queries.” Proceedings of 26th International Conference on Database and Expert Systems Applications (DEXA 2015), Valencia, Spain (2015) 367.
