💻 computer science

Direct Access for Answers to Conjunctive Queries with Aggregation

This paper establishes that the fine-grained complexity conditions for direct access to conjunctive query answers, previously known for unannotated databases, extend to queries with aggregation and semiring annotations (provided the annotation is excluded from the ordering), while also deriving new tractability conditions for count-distinct aggregation and analyzing the impact of including aggregate values in the order or using specific semiring properties.

Original authors: Idan Eldar, Nofar Carmeli, Benny Kimelfeld

Published 2026-04-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Idan Eldar, Nofar Carmeli, Benny Kimelfeld

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library containing millions of books. You want to find specific information, like "all the books written by authors from France in the 19th century."

In the world of computer databases, this is called a query. Usually, when you ask a computer for this, it goes through the library, finds every single matching book, writes them all down on a giant list, and then hands you the list. If there are millions of matches, this list is huge, takes a long time to write, and takes up a lot of space.

Direct Access is a magic trick. Instead of writing the whole list, the computer builds a special, compact "map" or "index." This map is small and quick to build. When you ask, "What is the 5,000th book on this list?" the computer uses the map to jump straight to that specific book instantly, without ever having to look at books 1 through 4,999.

This paper is about making that magic trick work when the questions get more complicated. Specifically, it tackles two new challenges:

Aggregation: Asking for summaries, like "Count how many books" or "Sum up the total pages."
Ordering: Asking for the results to be sorted in a specific way, like "Sort by author, then by year, then by the total page count."

Here is the breakdown of their findings using simple analogies.

1. The "Magic Box" (Semirings)

To handle math like "Sum" or "Count" inside the database, the authors use a concept called a Commutative Semiring.

The Analogy: Think of a "Magic Box" where you can drop in numbers.
- If you want to Count, the box adds a "1" for every item.
- If you want to Sum, the box adds the actual numbers.
- If you want Min/Max, the box keeps only the smallest or largest number it sees.
The paper shows that for most of these "Magic Boxes" (like Sum, Count, Min, Max), the old rules for building the "Direct Access Map" still work perfectly. You can build the map quickly and jump to any answer instantly.

2. The "Count-Distinct" Problem

There is one tricky "Magic Box": Count-Distinct. This asks, "How many unique authors are there?" (If an author wrote 5 books, they only count as 1).

The Problem: You can't easily put this into the "Magic Box" math because the answer depends on the whole group, not just adding things up.
The Finding: The authors discovered that for "Count-Distinct," the rules are stricter. The "Direct Access Map" is much harder to build. You can only do it efficiently if the question is very simple. If the question is complex, the map becomes too slow to build, and you might as well just write the whole list.

3. The "Sorting" Challenge (The Hard Part)

The most interesting part of the paper is what happens when you ask the computer to sort the results by the answer itself.

Scenario A (Easy): "Show me books sorted by Author, then by Year." (The summary number is just at the end).
- Result: Easy. The map works great.
Scenario B (Hard): "Show me books sorted by Total Page Count, then by Author."
- The Problem: To sort by the page count, the computer needs to know the page count before it knows which author it is. But to know the page count, it has to look at all the books for that author first. It's a "chicken and egg" problem.
- The Finding: For many common math operations (like Sum or Count), if you try to sort by the result, the "Direct Access Map" breaks. It becomes impossible to build the map quickly. The computer is forced to do the hard work of calculating everything before it can sort it.

4. The "Local Annotation" Loophole

The authors found a special case where they can cheat the "Hard" rule.

The Scenario: Imagine a database where only one table has the "Magic Box" numbers (like the "Goals" table in a soccer database), and all other tables are just plain text (like "Teams" or "Sponsors").
The Analogy: Imagine a factory where only one machine adds a special "price tag" to the products, and the rest of the assembly line just moves them along.
The Finding: If the "price tag" (the aggregate value) only comes from one specific source, they can build a special map that does allow sorting by that price tag, even if the general rules say it's impossible. This is a huge win for real-world applications where data often comes from a single source of truth.

5. The "Idempotent" Superpower

Finally, they looked at operations where doing the same thing twice doesn't change the result.

The Analogy: If you take the Maximum of a list of numbers, adding the same number again doesn't change the maximum. (Max of 5, 10, 5 is still 10). This is called Idempotence.
The Finding: For these specific types of "Magic Boxes" (Min, Max, and Count-Distinct on small lists), the authors found that even if the data is complex, you can still build the map efficiently, provided you follow their specific structural rules.

Summary: What does this mean for you?

This paper is a guide for computer scientists building database engines. It tells them:

Good News: You can build super-fast "jump-to-any-answer" tools for most summary questions (Sum, Count, Min, Max).
Bad News: If you try to sort your results by the summary number (e.g., "Show me the top 10 customers by total spending"), it's often impossible to do instantly for complex questions. You have to calculate everything first.
The Exception: If your data comes from a specific, simple structure (like a single source of truth), you might be able to bypass the bad news and build the fast map anyway.

In short, the authors mapped out exactly where the "Direct Access" magic works and where it hits a wall, helping engineers design faster and smarter database systems.

1. Problem Statement

The paper investigates the fine-grained complexity of evaluating Conjunctive Queries (CQs) enhanced with grouping and aggregation (e.g., COUNT, SUM, MIN, MAX, COUNT-DISTINCT). Specifically, it addresses the problem of Direct Access: constructing a compact data structure $S$ from an input database $D$ in log-linear time ( $O(|D| \log |D|)$ ) that allows retrieving the $i$ -th answer of the query in logarithmic time ( $O(\log |D|)$ ).

The answers must be returned in a specific lexicographic order defined by the user. The core challenge arises because:

The number of answers can be super-linear (e.g., cubic) relative to the input size, making materialization impossible.
The query includes an aggregate value (or annotation) which must be computed and potentially included in the sorting order.
The complexity depends heavily on whether the aggregate value is part of the lexicographic order and the specific properties of the aggregate function (e.g., whether it can be modeled by a commutative semiring).

2. Methodology and Framework

The authors analyze the problem using two primary formalisms:

Aggregate CQs (AggCQs): Standard SQL-like queries with aggregate functions (e.g., COUNT, SUM).
Annotated CQs ( $CQ^\star$ ): Queries over databases where tuples are annotated with elements from a commutative semiring $(K, \oplus, \otimes, \bar{0}, \bar{1})$ . The aggregate value is computed by multiplying annotations along a join path and summing them over projections. This framework generalizes many aggregate functions (Sum, Min, Max, Count) but excludes COUNT-DISTINCT in general cases.

Key Concepts:

Free-Connex: A structural property of the query hypergraph ensuring the existence of a join tree where the set of free variables forms a connected subtree.
Disruptive Trio: A specific configuration of three free variables $(x_1, x_2, x_3)$ where $x_1$ and $x_2$ are neighbors of $x_3$ but not of each other, and $x_3$ appears after both in the lexicographic order. The presence of a disruptive trio typically implies intractability.
Locally Annotated Databases: A specific case where all relations except one are annotated with the multiplicative identity ( $\bar{1}$ ). This models the translation of standard aggregate queries into semiring annotations.
Idempotent Addition: Semirings where $a \oplus a = a$ (e.g., Min, Max, and Count-Distinct over small domains).

3. Key Contributions and Results

The paper establishes dichotomy theorems (classifying queries as either tractable or intractable) under standard fine-grained complexity assumptions (SparseBMM, HYPERCLIQUE, 3SUM, HSC).

A. Aggregation/Annotation Not in the Order

When the aggregate value is the last element in the output tuple (or not part of the order):

General Semirings: The tractability condition for standard CQs holds. A query admits efficient direct access if and only if it is free-connex and has no disruptive trio.
Specific Aggregates: This result applies to SUM, MIN, MAX, COUNT, and AVG (computed via Sum/Count).
Count-Distinct Exception: COUNT-DISTINCT cannot be efficiently modeled by a general semiring. The authors prove that for COUNT-DISTINCT, the tractability condition is stricter: the aggregated variable must be treated as a free variable (i.e., it must appear in the head of the query). If the aggregated variable is existential, the problem becomes intractable.

B. Aggregation/Annotation Included in the Order

When the aggregate value appears earlier in the lexicographic order (e.g., sorting by COUNT then by ID):

General Semirings: The condition becomes more restrictive. Direct access is tractable if and only if:
1. The query is free-connex with no disruptive trio.
2. Crucial Condition: There exists an atom in the query that contains all variables that appear after the annotation in the order (specifically, the neighborhood of the variables following the annotation, intersected with free variables).
Hardness: If this condition is not met, direct access is intractable assuming the 3SUM conjecture (for numerical/counting semirings) or standard hypotheses (SparseBMM/HYPERCLIQUE).
Implication: Simply adding an aggregate to the order of a previously tractable query can render it intractable.

C. Locally Annotated Databases

The paper addresses the specific scenario where the database is locally annotated (only one relation has non-trivial annotations), which is the standard translation for AggCQs.

Full CQs (No Projection): The authors introduce the concept of R-deannotation, transforming the annotated query into a standard CQ where the annotation is replaced by a new variable. They prove that direct access is tractable if the deannotated query is free-connex and has no disruptive trio. This allows for more tractable cases than the general semiring case.
Idempotent Semirings (Min, Max, Count-Distinct): For semirings with idempotent addition, the authors show that the "locally annotated" property is preserved even after eliminating existential variables (projection). They define carrying variables (free variables connected to the annotated relation via existential paths) and prove that the complexity depends on the structure of the query restricted to these variables.
Result: This leads to a dichotomy for MIN, MAX, and COUNT-DISTINCT (over logarithmic domains) where the tractability condition is determined by the structure of the carrying variables.

4. Technical Significance

Unified Framework: The paper successfully unifies the study of direct access for standard CQs and aggregate queries, showing that while the general principles (free-connex, disruptive trio) hold, the inclusion of aggregation in the sorting order introduces significant new constraints.
Refined Complexity Bounds: It provides precise lower bounds for COUNT-DISTINCT, showing it is strictly harder than COUNT or SUM in the context of direct access with ordering.
Algorithmic Innovations:
- The use of R-deannotation to reduce annotated problems to standard CQ problems.
- The construction of locally annotated databases to handle the specific structure of aggregate translations.
- The use of 3SUM reductions to prove hardness when the annotation is part of the order, a technique not previously applied to this specific query evaluation problem.
Practical Relevance: The results guide database system designers on which query patterns allow for efficient "on-the-fly" answer retrieval without materialization, particularly for ranking and pagination tasks involving aggregates.

5. Conclusion

The paper establishes that while direct access for aggregate queries is often possible, the position of the aggregate value in the output order is a critical determinant of complexity.

If the aggregate is last, standard structural conditions apply.
If the aggregate is in the middle, a "neighborhood containment" condition is required.
Special properties like local annotation and idempotent addition can relax these conditions, enabling efficient access for MIN, MAX, and COUNT-DISTINCT in scenarios where general semiring approaches would fail.

The work lays the foundation for future research into dynamic updates, self-joins, and broader classes of queries beyond the free-connex restriction.