  Distributed RDF systems partition data across multiple computer nodes
(workers). Some systems perform cheap hash partitioning, which may result in
expensive query evaluation, while others apply heuristics aiming at minimizing
inter-node communication during query evaluation. This requires an expensive
data preprocessing phase, leading to high startup costs for very large RDF
knowledge bases. Apriori knowledge of the query workload has also been used to
create partitions, which however are static and do not adapt to workload
changes; hence, inter-node communication cannot be consistently avoided for
queries that are not favored by the initial data partitioning.
  In this paper, we propose AdHash, a distributed RDF system, which addresses
the shortcomings of previous work. First, AdHash applies lightweight
partitioning on the initial data, that distributes triples by hashing on their
subjects; this renders its startup overhead low. At the same time, the
locality-aware query optimizer of AdHash takes full advantage of the
partitioning to (i)support the fully parallel processing of join patterns on
subjects and (ii) minimize data communication for general queries by applying
hash distribution of intermediate results instead of broadcasting, wherever
possible. Second, AdHash monitors the data access patterns and dynamically
redistributes and replicates the instances of the most frequent ones among
workers. As a result, the communication cost for future queries is drastically
reduced or even eliminated. To control replication, AdHash implements an
eviction policy for the redistributed patterns. Our experiments with synthetic
and real data verify that AdHash (i) starts faster than all existing systems,
(ii) processes thousands of queries before other systems become online, and
(iii) gracefully adapts to the query load, being able to evaluate queries on
billion-scale RDF data in sub-seconds.
