<commit_before>\section{Motivating Example}
Consider an epidemiologist tasked with an initial
exploratory analysis of data collected for individuals across
a battery of exams. In particular, she is interested in exploring
the relationship between income and the immune system,
controlling for factors such as weight and gender.

While careful modeling techniques will be necessary before putting
results into the final research paper, the epidemiologist is anxious
to get a quick and accurate view into the data. However,
the data has been collected through CDC surveys (see Section~\ref{subsec:datasets} for details),
and there is a significant amount of missing data across all
relevant attributes. The researcher must develop a strategy
for handling the missing values. She could drop any records with
missing values and continue her analysis with the remaining data,
or she could fit a model on the base tables which can take advantage of existing correlations between attributes to fill in the missing values.
If she drops the records with missing data, she will throw away the majority of her data set, as many records have missing fields.
Fitting a model on the dataset will take more programming effort and may take a long time to run.

\todo{Clarify. Can we get a little more detail on why they might change the imputation strategy?}
To complicate matters further, the epidemiologist realizes that
some of the steps she is interested in, including filtering and grouping,
are impacted differently by missing data, and that these step may change
repeatedly, as she wants to run various queries during the exploration phase.

Rather than work through
the implications of each case, she submits a query, as shown in Figure~\ref{fig:example-query}, to ImputeDB.\@ The system, parameterized by a value indicating
a tradeoff between information loss and runtime cost, then finds
the optimal query plan, as shown in Figure~\ref{xxx}.

Tens of queries later, the epidemiologist has the holistic view of the
data that they required before carefully crafting their own tailored
imputation model. Knowing that there may be a need to explore
this data set further, they can easily incorporate their imputation model
into ImputeDB for future use.

\begin{figure}
\begin{lstlisting}[language=SQL]
SELECT income, AVG(white_blood_cell_ct)
FROM demo, exams, labs
WHERE gender = 2 AND 
      weight >= 120 AND
      demo.id = exams.id AND 
      exams.id = labs.id
GROUP BY demo.income
\end{lstlisting}
\caption{A typical public health query on CDC's NHANES data}
\label{fig:example-query}
\end{figure}

\todo{add a small comment about the number of plans in the plancache
to highlight size of search space}
\todo{add a figure with the resulting query plan, and what its doing}<commit_msg>paper: add query plan trees<commit_after>\section{Motivating Example}
Consider an epidemiologist tasked with an initial
exploratory analysis of data collected for individuals across
a battery of exams. In particular, she is interested in exploring
the relationship between income and the immune system,
controlling for factors such as weight and gender.

While careful modeling techniques will be necessary before putting
results into the final research paper, the epidemiologist is anxious
to get a quick and accurate view into the data. However,
the data has been collected through CDC surveys (see Section~\ref{subsec:datasets} for details),
and there is a significant amount of missing data across all
relevant attributes. The researcher must develop a strategy
for handling the missing values. She could drop any records with
missing values and continue her analysis with the remaining data,
or she could fit a model on the base tables which can take advantage of existing correlations between attributes to fill in the missing values.
If she drops the records with missing data, she will throw away the majority of her data set, as many records have missing fields.
Fitting a model on the dataset will take more programming effort and may take a long time to run.

\todo{Clarify. Can we get a little more detail on why they might change the imputation strategy?}
To complicate matters further, the epidemiologist realizes that
some of the steps she is interested in, including filtering and grouping,
are impacted differently by missing data, and that these step may change
repeatedly, as she wants to run various queries during the exploration phase.

Rather than work through
the implications of each case, she submits a query, as shown in Figure~\ref{fig:example-query}, to ImputeDB.\@ The system, parameterized by a value indicating
a tradeoff between information loss and runtime cost, then finds
the optimal query plan, as shown in Figure~\ref{xxx}.

Tens of queries later, the epidemiologist has the holistic view of the
data that they required before carefully crafting their own tailored
imputation model. Knowing that there may be a need to explore
this data set further, they can easily incorporate their imputation model
into ImputeDB for future use.

\begin{figure}
\begin{lstlisting}[language=SQL]
SELECT income, AVG(white_blood_cell_ct)
FROM demo, exams, labs
WHERE gender = 2 AND 
      weight >= 120 AND
      demo.id = exams.id AND 
      exams.id = labs.id
GROUP BY demo.income
\end{lstlisting}
\caption{A typical public health query on CDC's NHANES data}
\label{fig:example-query}
\end{figure}

\begin{figure}
  \Tree
  [.$\pi_{\text{income, AVG(white\_blood\_cell\_ct)}}$
    [.$g_{\text{income, AVG(white\_blood\_cell\_ct)}}$
      [.$\mu_{\text{demo.income}}$
        [.$\bowtie_{\text{exams.id} = \text{demo.id}}$
          [.$\mu_{\text{labs.white\_blood\_cell\_ct}}$
            [.$\bowtie_{\text{exams.id} = \text{labs.id}}$
              [.$\sigma_{\text{exams.weight} \geq 120}$ 
                [.$\mu_{\text{exams.weight}}$ exams ] 
              ] 
              labs 
            ]
          ]
        [.$\sigma_{\text{demo.gender} = 2}$ demo ]
      ] 
    ] 
  ] 
]
\caption{A plan for the query in Fig.~\ref{fig:example-query}, optimized for quality.}
\label{fig:quality-plan}
\end{figure}

\begin{figure}
  \Tree
  [.$\pi_{\text{income, AVG(white\_blood\_cell\_ct)}}$
    [.$g_{\text{income, AVG(white\_blood\_cell\_ct)}}$
      [.$\delta_{\text{demo.income, labs.white\_blood\_cell\_ct}}$
        [.$\bowtie_{\text{exams.id} = \text{labs.id}}$
          [.$\bowtie_{\text{demo.id} = \text{exams.id}}$
            [.$\sigma_{\text{demo.gender} = 2}$ demo ]
            [.$\sigma_{\text{exams.weight} \geq 120}$ [.$\mu_{\text{exams.weight}}$ exams ] ] ] labs ] ] ] ]
\caption{A plan for the query in Fig.~\ref{fig:example-query}, optimized for performance.}
\label{fig:fast-plan}
\end{figure}

First, consider the plan in Fig.~\ref{fig:fast-plan}.
This plan will be generated for the query in Fig.~\ref{example-query} when the optimizer is requested to produce the fastest possible plan, without considering the accuracy penalty.
There are several features of this query plan that highlight the subtleties of optimizing queries which contain imputation operators.
First, this plan will drop tuples which contain null values, rather than 

\todo{add a small comment about the number of plans in the plancache
to highlight size of search space}
\todo{add a figure with the resulting query plan, and what its doing}
{'fraction_non_alphanumeric': 0.07403872375238614, 'fraction_numerical': 0.00218161985274066, 'mean_word_length': 4.086685159500694, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '67255', 'n_tokens_mistral': 1996, 'n_tokens_neox': 1879, 'n_words': 958}