ALT #| Note [Planning joins] ~~~~~~~~~~~~~~~~~~~~~~~~ The primary goal of the search query compiler is to generate a query with an efficient sequence of joins. Before the compiler runs, joins are implicit: joined tables are directly referenced using e:joined-column expressions, not declared explicitly. For example, a search query like some_attr>1 will be parsed to a query like this: (e:> (e:joined-column (joined-table (q:annotation <target> 'attribute <attr info>) <join condition>) 'value) (e:literal 1)) The goal of the join planner is to translate an expression containing e:joined-column expressions into a SQL query with explicitly-declared joins. From a high level, the planner tries the following strategies: 1. An e:or expression at the root of the query can be broken up into separate queries combined with q:union. 2. For other queries, the planner attempts to find a joined [alt text limit]

ALT Note [Outer loop selection] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ When planning joins, the main goal is to find a joined table that can be used to drive the query’s outer loop. For example, suppose we have the following query: (and -night nature (or forest beach)) After simplification, this will result in roughly the following: (e:and (e:not (e:is (e:joined-column <night> 'polarity) (e:literal 0))) (e:is (e:joined-column <nature> 'polarity) (e:literal 0)) (e:or (e:is (e:joined-column <forest> 'polarity) (e:literal 0)) (e:is (e:joined-column <beach> 'polarity) (e:literal 0))) A naïve translation of this query could just convert everything to LEFT JOINs: SELECT image.id FROM image LEFT JOIN <night> ON <...> LEFT JOIN <nature> ON <...> LEFT JOIN <forest> ON <...> LEFT JOIN <beach> ON <...> WHERE <night>.polarity IS NOT 0 AND <nature>.polarity IS 0 AND (<forest>.polarity IS 0 OR [alt text limit]

ALT Note [Subquery-driven outer loops] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ As discussed in Note [Outer loop selection], selecting the right outer loop is a critical part of selecting a good query plan, and this normally involves selecting a table that can be used as an inner JOIN. However, consider the following search query: (and (or nature city) (figure person:lexi)) This will be parsed to something like the following: (e:and (e:or (e:is (e:joined-column <nature> 'polarity) (e:literal 0)) (e:is (e:joined-column <city> 'polarity) (e:literal 0))) (e:in-query (e:column 'image 'id) <figure query>)) Here, neither <nature> nor <city> can be used as an outer loop, but the subquery actually can be! Since it is a restriction on `image.id`, SQLite is smart enough to use it like an inner JOIN. Currently, in these cases, we use a hack of treating the cost of this kind of outer loop as zero, as we will always have to perform the [alt text limit]

ALT Note [Use EXCEPT for top-level negation] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose we have a query with the following structure: (and (or $pos1 $pos2 $pos3) -$neg1 -$neg2 -$neg3) After distributing over the `or` term as described in Note [Distributing over e:or terms], we will end up pushing all three of the negated terms into each of the positive branches. If the terms are complex, this can result in a lot of duplicated logic, especially as the number of positive branches grows. One way to avoid this is to generate a q:except query. We plan the positive and negative parts separately, then combine them using EXCEPT: (q:except (q:union <pos1> <pos2> <pos3>) (q:union <neg1> <neg2> <neg3>)) An additional advantage of this approach is that the negated terms can be planned as if they were positive terms, which often allows them to more effectively utilize selective indexes. The main downside of this approach is that both the positive and [alt text limit]