Efficient social network data query processing on MapReduce

Liu Liu, Jiangtao Yin, Lixin GaoHotPlanet@SIGCOMM 2013 · DOI

TL;DR

This paper tackles the challenge of efficiently querying massive social network datasets stored in RDF format using MapReduce. They introduce two novel primitives, "multiple-join-with-filter" and "Select-Join," to optimize the translation of SPARQL queries into MapReduce jobs, achieving up to a 2x speedup compared to existing methods.

What Problem Does This Paper Address?

Social networks are growing exponentially, and analyzing this data is crucial for businesses and online services. This data is increasingly represented using the Resource Description Framework (RDF), and SPARQL is the standard query language for RDF. However, querying billions of RDF triples with SPARQL is computationally expensive. While MapReduce is a popular framework for big data processing, existing methods for translating SPARQL queries to MapReduce jobs are inefficient. They typically follow a two-layer approach: first translating SPARQL to SQL joins, and then mapping SQL joins to MapReduce jobs. This indirect mapping leads to an excessive number of MapReduce jobs and intermediate data, hindering performance.

Methods

The authors propose two core primitives to optimize SPARQL query processing on MapReduce:

  • Multiple-join-with-filter Primitive: This primitive enhances the traditional SQL multiple join. Instead of just joining on a single key, it allows for an additional "filter key" to be defined on other variables within the participating tables. This enables more efficient filtering of results simultaneously during the join operation, reducing the need for separate filtering steps and potentially merging multiple join operations into a single MapReduce job.
  • Select-Join Primitive: This primitive addresses the inefficiency of the "SELECTION" stage in existing translation methods, which typically uses a dedicated MapReduce job to generate intermediate base tables. The Select-Join primitive merges the SELECTION stage directly into the JOIN stage. This is achieved by using two sets of map/reduce routines: one for generating base tables (Select group) and another for performing the join (Join group). This integration eliminates an entire MapReduce job and reduces intermediate data. An optimization called "Skip Write" is also introduced within the Select group, which bypasses the reduce side for writing base tables, further improving efficiency.

These primitives are integrated into a workflow generation algorithm that intelligently translates SPARQL queries into an optimized MapReduce job sequence.

Datasets

The paper evaluates their proposed methods using two benchmarks:

  • Social Network Intelligence Benchmark (SNIB): This benchmark simulates a social network similar to Facebook/Twitter, with data derived from public sources like DBpedia and FOAF. Datasets of 2000, 4000, and 8000 users were generated.
  • Lehigh University Benchmark (LUBM): This benchmark represents university systems and is commonly used for testing OWL knowledge base systems. Datasets with 500, 1000, and 1500 universities were generated.

Key Insights and Ideas

  • SQL Join Semantics are a Mismatch for SPARQL: The paper highlights that the rigid structure of SQL joins, designed for well-defined relational tables, doesn't naturally fit the more flexible and often redundant nature of RDF-generated base tables from SPARQL queries.
  • MapReduce Flexibility is Key: The authors leverage the inherent flexibility of MapReduce to combine logical stages (like selection and join) that are treated separately in traditional database systems.
  • Reducing Job Count is Crucial: A significant portion of the performance gain comes from reducing the number of MapReduce jobs required to execute a query. Fewer jobs mean less overhead, less intermediate data shuffling, and faster overall execution.
  • "Filter Key" is a Powerful Concept: The multiple-join-with-filter primitive's ability to use additional filter keys during joins is a novel way to prune the search space more effectively than standard SQL joins.
  • Eliminating Intermediate Tables: The Select-Join primitive's ability to avoid generating intermediate base tables for the SELECTION stage is a major performance booster, especially for queries where the initial selection is not highly selective.

Key Results

The proposed primitives and translation algorithm achieved significant performance improvements:

  • Up to 2x Speedup: The paper reports up to a 2x speedup in query running time compared to the traditional two-layer mapping scheme.
  • Reduced MapReduce Jobs: The primitives effectively reduce the number of MapReduce jobs required for query execution. For example, a triangle pattern query that previously required 4 jobs was reduced to 3 jobs using the proposed methods.
  • Star Pattern Queries: The Select-Join primitive reduced star pattern queries from 2 MapReduce jobs to 1, eliminating intermediate data and achieving a 1.5x speedup on average.
  • Chain and Triangle Patterns: These more complex patterns also benefited significantly from the combined primitives, demonstrating substantial speedups.

Limitations and Future Work

  • Join Order Optimization: The paper acknowledges that finding the optimal join sequence is not the focus of their current work and leaves it for future research.
  • Further Investigation into Join Order: The authors plan to investigate the join order within their workflow translation to explore the feasibility of even better query performance.

Summary updated

BibTeX
@inproceedings{liu2013efficient,
  author = {Liu Liu and Jiangtao Yin and Lixin Gao},
  title = {{Efficient social network data query processing on MapReduce}},
  booktitle = {HotPlanet@SIGCOMM},
  year = {2013},
  doi = {10.1145/2491159.2491169},
}

Loading related content...

Figure