PimBeam: Efficient Regular Path Queries over Graph Database Using Processing-in-Memory

Abstract: Regular path queries (RPQs) in graph databases are bottlenecked by the memory wall. Emerging processing-inmemory (PIM) technologies offer a promising solution to dispatch and execute path matching tasks in parallel within PIM modules. We present an efficient PIM-based data management system specifically for graph databases. Our solution, called PimBeam, facilitates efficient batch RPQs and graph updates by implementing a PIM-friendly dynamic graph partitioning algorithm. This algorithm effectively addresses graph skewness issues while maintaining graph locality with low overhead for handling RPQs. PimBeam streamlines label filtering queries by adding a filtering module on the PIM side and leveraging the parallelism of PIM. For the graph updates, PimBeam enhances processing efficiency by amortizing the host CPU’s update overhead to PIM modules. Evaluation results of PimBeam demonstrate its superiority over the state-of-the-art traditional graph database and other PIMbased architectures.