...

(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

Joins represent complex case to analyze. But it is are very common, so it is crucial to support partition extraction for them as well.

Important observations:

...

(P1, :2) AND (ANY) => (P1, :2)
(P1, :2) OR (ANY) => (P1, :2)

...

Flow:

Create a list of involved caches:

class TableDescriptor {
    String cacheName;
    String affColumnName; 


    // PARTITIONED or REPLICATED
    CacheMode cacheMode; 


    // Actual affinity function, needed to compare two tables in JOIN
    AffinityFunction affinityFunc;


	// Custom affinity: node filter OR not RendezvousAffinityFunction OR custom AffinityKeyMapper
    boolean customAffinity; 


    // If after left join.
    boolean replaceWithAll;
  
    // If REPLICATED with non-custom affinity, so relevant data is everywhere.
    boolean replaceWithAny;
}

General solution might be extremely complex, so we need to define reasonable bounds where could operate, 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 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 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 defined 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 a single co-location group.
3. Extract partitions from expression tree with two additional rules:
   1. Every partition group 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.

Query Rewrite

TODO

...

Subqueries

TODO

OR

TODO

Theory

...