private Map < String , Set < String > > getMinimalSetOfNodesForShardedQuery ( String localNode , Map < String , Set < String > > clusterMap , Set < String > queryClusters ) { //approximate algorithm, the problem is NP-complete Map < String , Set < String > > result = new LinkedHashMap <> ( ) ; Set < String > uncovered = new HashSet <> ( ) ; uncovered . addAll ( queryClusters ) ; uncovered = uncovered . stream ( ) . filter ( x -> x != null ) . map ( x -> x . toLowerCase ( Locale . ENGLISH ) ) . collect ( Collectors . toSet ( ) ) ; //try local node first Set < String > nextNodeClusters = new HashSet <> ( ) ; Set < String > clustersForNode = clusterMap . get ( localNode ) ; if ( clustersForNode != null ) { nextNodeClusters . addAll ( clustersForNode ) ; } nextNodeClusters . retainAll ( uncovered ) ; if ( nextNodeClusters . size ( ) > 0 ) { result . put ( localNode , nextNodeClusters ) ; uncovered . removeAll ( nextNodeClusters ) ; } while ( uncovered . size ( ) > 0 ) { String nextNode = findItemThatCoversMore ( uncovered , clusterMap ) ; nextNodeClusters = new HashSet <> ( ) ; nextNodeClusters . addAll ( clusterMap . get ( nextNode ) ) ; nextNodeClusters . retainAll ( uncovered ) ; if ( nextNodeClusters . size ( ) == 0 ) { throw new OCommandExecutionException ( "Cannot execute a sharded query: clusters [" + uncovered . stream ( ) . collect ( Collectors . joining ( ", " ) ) + "] are not present on any node" + "\n [" + clusterMap . entrySet ( ) . stream ( ) . map ( x -> "" + x . getKey ( ) + ":(" + x . getValue ( ) . stream ( ) . collect ( Collectors . joining ( "," ) ) + ")" ) . collect ( Collectors . joining ( ", " ) ) + "]" ) ; } result . put ( nextNode , nextNodeClusters ) ; uncovered . removeAll ( nextNodeClusters ) ; } return result ; }
given a cluster map and a set of clusters involved in a query tries to calculate the minimum number of nodes that will have to be involved in the query execution with clusters involved for each node .