Abstract: We introduce factorized aggregations and worst-case optimal joins in DuckDB with an adaptive mechanism that only uses them when they enhance query performance. This builds on the adoption of a new hash table design (“Linear-Chained”) for equi-joins. Our first insight is that the collision-free chains of this new design enable efficient factorized and worst-case optimal processing. We further defer the decision to use factorization and worst-case optimal joins from optimization to runtime. Our second insight is that we can obtain accurate statistics, even if the join inputs lack these (e.g. because they are sub-queries or Parquet files), by leveraging runtime heuristics and constructing efficient on-the-fly sketches, during the hash join build. Finally, we show that machine learning models using these metrics can achieve close to optimal performance with a high accuracy. Furthermore, we propose heuristic-based approaches that offer comparable performance to these models, while relying on cheaper to obtain run-time statistics and being more explainable.

PDF

Abstract: While factorization and Worst-Case Optimal Join (WCOJ) algorithms promise significant performance improvements, their widespread adoption lacks behind because they are complex to implement and still face query optimization challenges. We aim to address this problem by proposing an adaptive, lightweight solution. We integrate factorized representations into DuckDB using pointers to hash table chains of a Linear-Chained hash table. This newly proposed hash table combines linear probing with chaining to insert a tuple only in a collision chain when their keys match, enabling collision-free chains. We use d-representations to (1) efficiently calculate aggregates and (2) perform cyclic joins in a worst-case optimal manner. By operating on d-representations, we avoid the explosion of intermediate results and efficiently reuse cached results, achieving speedups of up to 17.58x for aggregate computations and 16.77x for cyclic joins. To ensure that the new techniques are only employed when beneficial, we propose adaptive factorization, shifting the decision to use factorization from the planning stage to runtime. We then can collect statistics, which allows for accurate decision-making even in sub-queries or quering Parquet files. The metrics are then used by machine learning models to predict whether factorization would be beneficial. These models demonstrate an accuracy of 88% in our benchmarks.

PDF

Abstract: In this paper we present two clustering methods to determine users with similar opinions on the Covid-19 pandemic and the related public debate in Germany. We believe, they can help gaining an overview over similar-minded groups and could support the prevention of fake-news distribution. The first method uses a new approach to create a network based on retweet-relationships between users and the most retweeted characters (influencers). The second method extracts hashtags from users posts to create a “user feature vector” which is then clustered using a similarity matrix based on [1] to identify groups using the same language. With both approaches it was possible to identify clusters that seem to fit groups of different public opinion in Germany. However, we also found that clusters from one approach cannot be associated with clusters from the other due to filtering steps in the two methods.

arXiv

No further information providable, sorry :(