We apply the BSP model to the design of new parallel algorithms for database transactions. The portable BSP cost model enables us to apply balance-preserving operations precisely when they are cost-effective. We have designed a new self-balancing frequency-adaptive parallel join algorithm. Theoretical analysis and timings on up to 16 processors indicate that our algorithm is as fast as classical hashing algorithms (or much faster in the presence of skew) and ensures a balanced output. An improved version of this algorithm has been applied to the materialized views maintenance problem in data warehousing (joint work with Fadila Bentayeb).
To learn about the project, please read:
Access to a Fujitsu AP3000 system is provided by FECIT.Project continued by Mostafa Bamha and Matthieu Exbrayat as subproject PDB (Scalable Parallel DataBase queries) of the CARAML project.
Gaétan HAINS