# Algorithm for segmenting input query into query/join tree

Wondering what algorithms look like for implementing a complex JOIN query handler. Taking a look at this paper Building Query Compilers they talk about Query Graphs and Join Trees and Cost Functions for determining how well join trees are when the engine figures out how to organize the steps in the query.

What I'm particularly looking for is the part of how they segment the input query into the query/join tree. Specifically, this relates to scheduling and queries. I understand how the cost functions work. I just don't understand how you take a relational algebra query tree and break them apart into distinct chunks of operations sequenced together. They usually just say "we have a query x and here is the corresponding tree": without a description of how the tree was obtained.

I'm confused as to why they would break apart conditional statements, and how they know where to break them apart, and how to order them (when do heuristics apply, etc.)

What follows is a brief overview of the algorithm, showing where I am confused.

Given a query tree as input, we first convert it to CNF. Then we construct a query graph, which is a graph over the WHERE + FROM portions of the query. This graph is only used for determining if the query is correct or not in some cases. Otherwise we can skip the query graph. Then we construct the JOIN tree by x... This is what I'm wondering. In the following algorithm it would be the last part.

\begin{align} & \texttt{Input}\ Q: \texttt{QueryTree} \\ & \texttt{Output}\ Q''': \texttt{JoinTree} \\ & \texttt{Begin} \\ & X : Q \rightarrow Q'\ //\ convert\ to\ CNF \\ & G : Q' \rightarrow Q''\ //\ convert\ to\ query\ graph \\ & Validate\ Q'' \\ & J : Q'' \rightarrow Q'''\ //\ convert\ to\ join\ tree (confused here) \\ & Return\ Q''' \\ & \texttt{End} \end{align}

The question is, how a database query engine goes through and figures out the order of operations.

• This seems like it would be covered in the book draft you referenced. Presumably the implementation part, Part V, will have more details on how to actually go about doing these things. But it is not an accident that the chapter you are reading, Chapter 3 of 36, Join Ordering, is itself over 100 pages long. There are many different ways of doing this. That said, I think you are interpreting query graphs as some kind of "dataflow" graph where they just reflect logical dependencies in the query. You can always cross join all of the tables, filter, and project, regardless of the query graph. – Derek Elkins left SE Mar 31 '18 at 0:44
• I think this falls within the general area of query optimization. – D.W. Apr 2 '18 at 15:49
• @DerekElkins from my initial understanding they only mention "conjunctive queries", "query graphs", and "join trees", with a brief definition. They don't explain how they are made. – Lance Pollard Apr 2 '18 at 18:45
• "A query graph is a convenient representation of a query. It is an undirected graph with nodes $R_1, \dotsc, R_n$. For every simple predicate in the conjunction $P$ whose attributes belong to the relations $R_i$ and $R_j$ , we add an edge between $R_i$ and $R_j$." That kind of explains the input query -> query graph part, but not the query graph -> join tree part, which they just give: "a join tree is a binary tree whose leaf nodes are the relations and whose inner nodes are joins (and possibly cross products)." not sure what that means. – Lance Pollard Apr 2 '18 at 18:47
• The most that is said about join ordering is "Left-deep trees directly correspond to an ordering (i.e. a permutation) of the relations.". Then it goes into cost functions which make sense... "In order to judge the quality of join trees...", so there is a gap missing about join trees (left-deep join trees would be good enough). – Lance Pollard Apr 2 '18 at 18:54