Page History

...

(P1) OR (P2) => (P1, P2)
(P1) OR (ALL) => (ALL)
(P1) OR () => (P1)
(P1, P2) OR (P2, P3) => (P1, P2, P3)


(:1) OR (:2) => (:1, :2)
(P1, :1) OR (P2, :2) => (P1, P2, :1, :2)

...

Joins are very common, so it is crucial to support partition extraction for them as well. General solution might be extremely complex, so we need to define reasonable bounds where could operateoptimization is applicable, and improve them iteratively in future.  We start with query AST obtained from parser. Proposed flow to extract partitions is explained below. Some of explained these steps could be merged to improve performance.

1. Look for non-equality JOIN conditions. When one is found, exit. This way join type space is reduced to equijoins.
2. Build co-location tree, which is another tree showing explaining how PARTITIONED tables are joined together
   1. Copy current JOIN AST into separate tree
   2. If table is REPLICATED and do not have node filter, then mark it as "ANY" and remove from the tree, as it doesn't affect JOIN outcome. Otherwise - exit, no need to bother with custom filters.
   3. If CROSS JOIN is found, then exit (might be improved in future)
   4. If tables are joined on their affinity columns and has equal affinity functions, then mark them as belonging to the same co-location group. Otherwise - assign them to different co-location groups. Repeat this for all tables and joins in the tree. Functions are equal if and only if the following is true:
      1. Affinity function is deterministic (e.g. RendezvousAffintiyFunction is deterministic, while FairAffinityFunction is not)
      2. Both affinity functions are equal
      3. There are no custom node filters
      4. There are no custom affinity key mappers
   5. Every subquery is assigned it's own co-location group unconditionally (may be improved in future)
   6. At this point we have a co-location tree with only PARTITIONED caches, only equi-joins, where every table is assigned to a single co-location group.
3. Extract partitions from expression tree with two additional rules:
   1. Every group of partitions is assigned respective co-location group from co-location tree

   2. REPLICATED caches with "ANY" policy should be eliminated as follows:

      Code Block
      language sql title ANY algebra linenumbers true
      (P1, :2) AND (ANY) => (P1, :2) (P1, :2) OR (ANY) => (P1, :2)

      
      

   3. If partition tree contain rules from different co-location groups, then exit.

4. At this point we have partition tree over a single co-location group. All outstanding arguments could be passed through the same affinity function to get target partitions.

...

interface PartitionNode {
    Collection<Integer> apply(Object[] args);
}


class PartitionGroup implements PartitionNode {
    Collection<Object> parts; // Concrete partitions, arguments or both.
}


class PartitionExpression implements PartitionNode {
    PartitionNode left;
    PartitioNodePartitionNode right;
}

Partition tree is enriched with {{AffinityTopologyVersion}} it  it was built on, and affinity function descriptor. Descriptor can only be defined for well-known affinity functions, such as {{RendezvousAffinityFunction}}, and defines the logic on how to convert an object to partition. 

class PartitionInfo {
    PartitionNode tree;
    AffintiyTopologyVersion affTopVer;
    AffinityFunctionDecriptor affFunc;
}

...

1. Whether partition pruning is applicable
2. Formatted partition tree
3. Affinity topology version of the plan
4. If not applicable - explain why (e.g. non-equi joinequijoin, incompatible affinity functions, etc.)

...