1. A computer system, the computer system comprising: one or more hardware processors; system memory coupled to the one or more hardware processors, the system memory storing instructions that are executable by the one or more hardware processors; and the one or more hardware processors executing the instructions stored in the system memory to optimize a query, including the following: access a query plan search space for a query of a distributed database, the query plan search space including a hierarchical structure of a root group of logical operators, one or more intermediate groups of logical operators, and one or more leaf groups of logical operators; and formulate an annotated query plan search space for the query, including: identify a distribution property for a child group of at least one other group, the at least one other group selected from among: the root group and the one or more intermediate groups, the distribution property indicating type of distribution relevant to the child group, the distribution property identifying a column that data for a parent group is distributed on, the parent group being above the child group in the hierarchical structure; and annotate the child group with the type of distribution by attaching an indication of the identified column to the child group to propagate the identified type of distribution to the child group for use in query plan pruning.