Meaning of "pushing x down" and "pulling x up" in database query handling

Question

In this book there is a lot of mention of "pushing x down". For example:

Pushing NOT operations down and eliminating them

NOT operations need to be pushed downwards for correctness reasons. Attention has to be paid to the IS NOT NULL and IS NULL predicates. XXX complete set of rules go into some table

...

Typical steps during this rewrite phase are unnesting nested queries, pushing selections down, and introducing index structures.

...

When pushing down projections, we only apply them just before a pipeline breaker

...

Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

...

In this section, we consider pushing down (pulling up) unary operators into (from) the arguments of binary operators. Thus, we are interested in equivalences of the form $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ and $f(e_1 ◦ e_2) ≡ e_1 ◦ f(e_2)$.

From that last example I can vaguely see that e.g. $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ there is a "moving out" of $e_2$ from the equation, but I'm not sure what direction up/down and not sure what the meaning/purpose is in doing this. Wondering what exactly this means.

Answer 1

I would normally say "pushing inward"/"pulling outward", but "down"/"up" make sense if you are thinking in terms of syntax trees and, being a computer scientist, your trees grow downward.

In (classical) logic there are rules like De Morgan's rule which says $\neg(P\land Q)\equiv(\neg P)\lor(\neg Q)$ and many others that allow you to move negation either outward/upward toward the outermost connective (reading the equivalence from right to left), or inward/downward towards the leaves of the syntax tree (reading the equivalence left to right). If we actually draw out the syntax tree it will look like

    ¬             ∨
    |            / \
    ∧      ≡    ¬   ¬
   / \          |   |
  P   Q         P   Q

which illustrates the down/up movement. In general, we can use any available equivalences for any sort of expression to move operations around. In the case of negation, since we have $\neg\neg P\equiv P$ it is often desirable to try to move them toward each other. Systematically moving them towards the leaves, i.e. inward/downward, is one way to accomplish this. Often these types of cancellations are one of the goals of applying these equivalences. There are other concerns too. For example, if it is possible to remove duplicates before a join rather than after, that could be extremely advantageous.

Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

This just states that sometimes the available equivalences are not so simple, and an equivalence might simplify a selection at the cost of making a join more complicated or vice versa and so the equivalences can't just be blindly applied in a fixed direction (at least not if you want a good result).