Package org.intermine.sql.precompute

Class QueryOptimiser

  • public final class QueryOptimiser
extends java.lang.Object
    A static class providing the code to optimise a query, given a database (presumably with a table describing the available precomputed tables).
    Author:
    Matthew Wakeling, Andrew Varley

    • Method Detail

      • optimise

        public static java.lang.String optimise​(java.lang.String query,
                                        Database database)
                                 throws java.sql.SQLException
        Runs the optimiser through the query represented in the String, given the database. If anything goes wrong, then the original String is returned.
        Parameters:
        query - the query to optimise
        database - the database to use to find precomputed tables
        Returns:
        a String representing the optimised query
        Throws:
        java.sql.SQLException - if a database error occurs

      • optimise

        public static java.lang.String optimise​(java.lang.String query,
                                        Database database,
                                        QueryOptimiserContext context)
                                 throws java.sql.SQLException
        Runs the optimiser through the query represented in the String, given the database. If anything goes wrong, then the original String is returned.
        Parameters:
        query - the query to optimise
        database - the database to use to find precomputed tables
        context - a QueryOptimiserContext, to alter settings
        Returns:
        a String representing the optimised query
        Throws:
        java.sql.SQLException - if a database error occurs

      • optimise

        protected static Query optimise​(Query query,
                                Database database)
                         throws java.sql.SQLException
        Runs the optimiser through the query, given the database.
        Parameters:
        query - the Query to optimise
        database - the database to use to find precomputed tables
        Returns:
        the optimised Query
        Throws:
        java.sql.SQLException - if a database error occurs

      • optimise

        protected static Query optimise​(Query query,
                                Database database,
                                QueryOptimiserContext context)
                         throws java.sql.SQLException
        Runs the optimiser through the query, given the database.
        Parameters:
        query - the Query to optimise
        database - the database to use to find precomputed tables
        context - a QueryOptimiserContext, to alter settings
        Returns:
        the optimised Query
        Throws:
        java.sql.SQLException - if a database error occurs

      • optimise

        public static BestQuery optimise​(java.lang.String query,
                                 Query originalQuery,
                                 java.lang.Object precompLookup,
                                 java.sql.Connection explainConnection,
                                 QueryOptimiserContext context)
                          throws java.sql.SQLException
        Runs the optimiser through the query represented in the String and Query, given the Connection and an object to lookup a PrecomputedTable
        Parameters:
        query - the query String to optimise
        originalQuery - the Query object to optimise - or optionally null
        precompLookup - a Database or Connection to lookup a PrecomputedTableManager
        explainConnection - the database connection to use, or null if precompLookup is a Database
        context - a QueryOptimiserContext, to alter settings
        Returns:
        a BestQuery object
        Throws:
        java.sql.SQLException - if a database error occurs

      • optimiseWith

        public static BestQuery optimiseWith​(java.lang.String query,
                                     Query originalQuery,
                                     Database database,
                                     java.sql.Connection connection,
                                     QueryOptimiserContext context,
                                     java.util.Set<PrecomputedTable> precomputedTables,
                                     OptimiserCache cache)
                              throws java.sql.SQLException
        Runs the optimiser through the query repesented in the String and Query, given the Connection and a set of PrecomputedTables.
        Parameters:
        query - the query String to optimise
        originalQuery - the Query object to optimise - or optionally null
        database - a Database
        connection - the database connection to use, or null if database is a Database
        context - a QueryOptimiserContext, to alter settings
        precomputedTables - a Set of PrecomputedTables
        cache - an OptimiserCache
        Returns:
        a BestQuery object
        Throws:
        java.sql.SQLException - if a database error occurs

      • remapAliasesToAvoidPrecomputePrefix

        protected static void remapAliasesToAvoidPrecomputePrefix​(Query query)
        Remaps the aliases of any table that starts with the ALIAS_PREFIX, to avoid clashes with future precomputed tables.
        Parameters:
        query - the query to remap

      • recursiveOptimiseCheckSubquery

        public static void recursiveOptimiseCheckSubquery​(java.util.Set<PrecomputedTable> precomputedTables,
                                                  Query query,
                                                  BestQuery bestQuery)
                                           throws BestQueryException,
                                                  java.sql.SQLException
        Recursively optimises the query, given the set of precomputed tables, and updates the BestQuery object with each Query found. This method looks for simple subqueries to optimise, and calls recursiveOptimise.
        Parameters:
        precomputedTables - a Set of PrecomputedTable objects to use
        query - a query to optimise
        bestQuery - a BestQuery object to update with each optimised Query object
        Throws:
        BestQueryException - if the BestQuery decides to cut short the search
        java.sql.SQLException - if a database error occurs

      • recursiveOptimise

        public static void recursiveOptimise​(java.util.Set<PrecomputedTable> precomputedTables,
                                     Query query,
                                     BestQuery bestQuery,
                                     Query originalQuery)
                              throws BestQueryException,
                                     java.sql.SQLException
        Recursively optimises the query, given the set of precomputed tables, and updates the BestQuery object with each Query found. When this method returns, either bestQuery will hold the fastest Query, or the bestQuery object will have decided to cut short proceedings. Either way, use the Query in bestQuery for best results. NOTE: the Query passed into this method at the top level should never be used again by anything (except when this method is called by this method), because this method alters the query. Therefore it is recommended that all Queries are passed into this method as fresh clones of the Query you wish to optimise.
        Parameters:
        precomputedTables - a Set of PrecomputedTable objects to use
        query - a query to optimise
        bestQuery - a BestQuery object to update with each optimised Query object
        originalQuery - the original Query, as passed to the first instance of recursiveOptimise.
        Throws:
        BestQueryException - if the BestQuery decides to cut short the search
        java.sql.SQLException - if a database error occurs

      • mergeMultiple

        protected static java.util.SortedMap<PrecomputedTable,​java.util.Set<Query>> mergeMultiple​(java.util.Set<PrecomputedTable> precomputedTables,
                                                                                                Query query,
                                                                                                Query originalQuery)
        Iteratively calls merge on query with all the PrecomputedTables in a Set, returning the results in a Map from the PrecomputedTable to the Set that merge returns.
        Parameters:
        precomputedTables - a Set of PrecomputedTable objects to iterate through
        query - the Query to pass in to merge
        originalQuery - the original Query, as passed to the first instance of recursiveOptimise.
        Returns:
        a Map from all PrecomputedTable objects that produced a non-empty Set, to the Set that was produced by merge

      • merge

        protected static java.util.Set<Query> merge​(PrecomputedTable precomputedTable,
                                            Query query,
                                            Query originalQuery)
        Finds all the possible uses of a given precomputed table in the query, and returns them as a Set of new Queries. If there is no scope for the PrecomputedTable to replace any part of the Query, then this method will return an empty Set. If there are two independent opportunities to insert the PrecomputedTable, then this method will return three Query objects in the Set - one with the first opportunity used, one with the second opportunity used, and one with both. A PrecomputedTable is deemed to "fit", if it
        1. Contains no other tables than those present in the Query
        2. Contains no constraints that restrict the output more than the constraints of the Query. Constraints that equal a constraint in the Query can be missed out of the resulting Query
        3. A similar restriction on the HAVING clauses as the WHERE clauses.
        4. Contains all the items in the SELECT list that are present in the Query's SELECT from the tables that are to be replaced
        5. If the PrecomputedTable is DISTINCT, then the Query must also be DISTINCT.
        This type of precomputed table can be fitted multiple times. Note that a subquery could be replaced completely by a precomputed table, or can be optimised in-place by another precomputed table (in which case merge should call itself with the subquery). Alternatively, If the PrecomputedTable contains a GROUP BY, then all fields in the Query's SELECT list and all primary keys, that are not to be replaced by the PrecomputedTable must be in the Query's GROUP BY clause, and the fields in the GROUP BY for the tables that are being replaced must match completely. Also, all the fields in the SELECT list of the query must be present in the PrecomputedTable. This type of PrecomputedTable can only be fitted once.
        Parameters:
        precomputedTable - the PrecomputedTable to use in the new Queries
        query - the Query object to try to fit the PrecomputedTable into
        originalQuery - the original Query, as passed to the first instance of recursiveOptimise.
        Returns:
        a Set of Query objects, one for each combination of the PrecomputedTable in the query

      • mergeGroupBy

        protected static java.util.Set<Query> mergeGroupBy​(PrecomputedTable precomputedTable,
                                                   Query query,
                                                   Query originalQuery)
        Tries to match a PrecomputedTable with a GROUP BY clause to this query. See merge for a description of how this works. In fact, we aren't implementing this properly. We are imposing the restriction that there can be no more tables than in the PrecomputedTable, therefore the first restriction mentioned above is followed automatically. A PrecomputedTable is deemed to fit if it
        1. Contains exactly the same set of tables as the Query
        2. Contains exactly the same WHERE clause as the Query
        3. Contains all the items in the SELECT list that are present in the Query's SELECT list.
        4. Contains exactly the same GROUP BY clause
        So, this leaves very little leeway for optimising different Queries - these are the things that can be different from the PrecomputedTable:
        1. The HAVING clause may be different, although each constraint in the PrecomputedTable must EQUAL or IMPLIES some constraint in the Query.
        2. the DISTINCT status can be different, but if the PrecomputedTable is DISTINCT, then the Query must also be DISTINCT.
        Parameters:
        precomputedTable - the PrecomputedTable to use in the new Query
        query - the Query object to try to fit the PrecomputedTable into
        originalQuery - the original query object
        Returns:
        a Set containing maybe a new Query object with the PrecomputedTable inserted

      • compareConstraints

        protected static boolean compareConstraints​(java.util.Set<AbstractConstraint> set1,
                                            java.util.Set<AbstractConstraint> set2,
                                            java.util.Set<AbstractConstraint> equalsSet)
        Compares 2 sets of AbstractConstraints
        Parameters:
        set1 - the first set
        set2 - the second set
        equalsSet - a Set that should be passed in empty - it will be populated with those AbstractConstraints that have an equal in the other set. Note that if the return value is false, then the contents of this Set is undefined
        Returns:
        true if every element of set1 is equal or less restrictive than some element in set2

      • compareConstraints

        protected static boolean compareConstraints​(java.util.Set<AbstractConstraint> set1,
                                            java.util.Set<AbstractConstraint> set2,
                                            java.util.Set<AbstractConstraint> equalsSet,
                                            java.util.Map<AbstractTable,​AbstractTable> tableMap,
                                            java.util.Map<AbstractTable,​AbstractTable> reverseTableMap)
        Compares 2 sets of AbstractConstraints
        Parameters:
        set1 - the first set
        set2 - the second set
        equalsSet - a Set that should be passed in empty - it will be populated with those AbstractConstraints that have an equal in the other set. Note that if the return value is false, then the contents of this Set is undefined
        tableMap - a Map from Table to Table
        reverseTableMap - the reverse of tableMap
        Returns:
        true if every element of set1 is equal or less restrictive than some element in set2

      • compareSelectLists

        protected static boolean compareSelectLists​(java.util.List<SelectValue> list1,
                                            java.util.List<SelectValue> list2)
        Compares two Lists of SelectValues, and returns true if all the items in the first List are present in the second List, ignoring the SelectValue alias.
        Parameters:
        list1 - the list of items that must be present in list2
        list2 - the list of items to look in
        Returns:
        true if every item in list1 is present in list2, ignoring SelectValue aliases TODO: take this function out - we don't need it.

      • remapAliases

        protected static void remapAliases​(java.util.Map<AbstractTable,​AbstractTable> map,
                                   java.util.Set<AbstractTable> tables)
        Alters all the aliases of the tables being mapped to, to equal the alias of the table mapping to them. After this operation (where the AbstractTables of the PrecomputedTable are mapped to the AbstractTables of the Query), the Constraint objects of the Query and the PrecomputedTable can be directly compared with their standard compare methods.
        Parameters:
        map - the Map from AbstractTable objects with the source alias, to other AbstractTable objects with the destination alias
        tables - a Set of tables which the values of the map happen to be in. This permits this method to check that none of the tables that it is about to change the alias of will clash with any pre-existing table aliases. Pre-existing table aliases will be renamed as necessary.

      • findTableForAlias

        protected static AbstractTable findTableForAlias​(java.lang.String alias,
                                                 java.util.Set<AbstractTable> set)
        Finds a table in a Set with the given alias.
        Parameters:
        alias - the alias to look for
        set - the Set to look in
        Returns:
        an AbstractTable that has the alias or null if there isn't one

      • reconstructAbstractValue

        protected static AbstractValue reconstructAbstractValue​(AbstractValue original,
                                                        Table precomputedSqlTable,
                                                        java.util.Map<AbstractValue,​SelectValue> valueMap,
                                                        java.util.Set<AbstractTable> tableSet,
                                                        boolean groupBy)
                                                 throws QueryOptimiserException
        Reconstructs an AbstractValue, to form the part of an SQL Query that has been replaced with a PrecomputedTable. If the AbstractValue is present in the SELECT list of the PrecomputedTable, then a new Field replaces the AbstractValue, that is that particular field in the PrecomputedTable. Otherwise, the original AbstractValue will be returned.
        Parameters:
        original - the original AbstractValue
        precomputedSqlTable - the Table object representing the PrecomputedTable, which the new AbstractValue should refer to.
        valueMap - a mapping from AbstractValue in the PrecomputedTable onto the SelectValue that contains it.
        tableSet - a Set of all the tables that are being replaced - ie the Set of tables in the PrecomputedTable. We use this to work out which unrepresented AbstractValues are problems.
        groupBy - true if the PrecomputedTable contains a GROUP BY clause
        Returns:
        a remapped AbstractValue
        Throws:
        QueryOptimiserException - if there is an AbstractValue that cannot be constructed, because it is not present in the PrecomputedTable

      • reconstructSelectValues

        protected static void reconstructSelectValues​(java.util.List<SelectValue> oldSelect,
                                              Table precomputedSqlTable,
                                              java.util.Map<AbstractValue,​SelectValue> valueMap,
                                              java.util.Set<AbstractTable> tableSet,
                                              boolean groupBy,
                                              Query newQuery)
                                       throws QueryOptimiserException
        Populates the SELECT list of a new Query object, given an old Query's SELECT list to use as a reference, a valueMap (to pass to reconstructAbstractValue), and a Table to represent the PrecomputedTable.
        Parameters:
        oldSelect - the old Query's SELECT list to use a pattern
        precomputedSqlTable - the Table object that remapped AbstractValues should refer to
        valueMap - a mapping from AbstractValue in the PrecomputedTable onto the SelectValue that contains it
        tableSet - a Set of all the tables that are being replaced - ie the Set of tables in the PrecomputedTable. We use this to work out which unrepresented AbstractValues are problems.
        groupBy - true if the PrecomputedTable contains a GROUP BY clause
        newQuery - the new Query object to populate
        Throws:
        QueryOptimiserException - if reconstructAbstractValue finds an AbstractValue that cannot be constructed, given the PrecomputedTable

      • reconstructAbstractConstraints

        protected static void reconstructAbstractConstraints​(java.util.Set<AbstractConstraint> oldConstraints,
                                                     Table precomputedSqlTable,
                                                     java.util.Map<AbstractValue,​SelectValue> valueMap,
                                                     java.util.Set<AbstractTable> tableSet,
                                                     boolean groupBy,
                                                     java.util.Set<AbstractConstraint> newConstraints,
                                                     java.util.Set<AbstractConstraint> constraintEqualsSet,
                                                     Field firstPrecompOrderBy,
                                                     int precompOrderBySize,
                                                     Field orderByField,
                                                     boolean firstPrecompOrderByHasNoNulls,
                                                     boolean reverseOrderBy)
                                              throws QueryOptimiserException
        Populates the WHERE list of a new Query object, given the old Query's WHERE (or HAVING) list to use as a reference.
        Parameters:
        oldConstraints - a Set of constraints from the old Query
        precomputedSqlTable - the Table object that remapped AbstractValues should refer to
        valueMap - a mapping from AbstractValue in the PrecomputedTable onto the SelectValue that contains it.
        tableSet - a Set of all the tables that are being replaced - ie the Set of tables in the PrecomputedTable. We use this to work out which unrepresented AbstractValues are problems.
        groupBy - true if the PrecomputedTable contains a GROUP BY clause
        newConstraints - the Set of Constraints in the Query that is being created
        constraintEqualsSet - a Set of Constraints that are present in both the original query and the precomputed table - therefore they can be left out of the new Query
        firstPrecompOrderBy - a Field that the column corresponding to the first order by field in the precomputed table would be mapped onto in the destination query
        precompOrderBySize - the number of elements in the precomputed table's order by clause
        orderByField - a Field that can replace the firstPrecompOrderBy field
        firstPrecompOrderByHasNoNulls - true if the firstPrecompOrderBy field does not permit null values
        reverseOrderBy - true if the firstPrecompOrderBy was an OrderDescending
        Throws:
        QueryOptimiserException - if reconstructAbstractValue finds an AbstractValue that cannot be constructed, given the PrecomputedTable

      • reconstructAbstractConstraint

        protected static AbstractConstraint reconstructAbstractConstraint​(AbstractConstraint oldConstraint,
                                                                  Table precomputedSqlTable,
                                                                  java.util.Map<AbstractValue,​SelectValue> valueMap,
                                                                  java.util.Set<AbstractTable> tableSet,
                                                                  boolean groupBy,
                                                                  Field firstPrecompOrderBy,
                                                                  int precompOrderBySize,
                                                                  Field orderByField,
                                                                  boolean firstPrecompOrderByHasNoNulls,
                                                                  boolean reverseOrderBy)
                                                           throws QueryOptimiserException
        Reconstructs an AbstractConstraint object, using reconstructAbstractValue.
        Parameters:
        oldConstraint - the constraint to reconstruct
        precomputedSqlTable - the Table object that remapped AbstractValues should refer to
        valueMap - a mapping from AbstractValue in the PrecomputedTable onto the SelectValue that contains it.
        tableSet - a Set of all the tables that are being replaced - ie the Set of tables in the PrecomputedTable. We use this to work out which unrepresented AbstractValues are problems.
        groupBy - true if the PrecomputedTable contains a GROUP BY clause
        firstPrecompOrderBy - a Field that the column corresponding to the first order by field in the precomputed table would be mapped onto in the destination query
        precompOrderBySize - the number of elements in the precomputed table's order by clause
        orderByField - a Field that can replace the firstPrecompOrderBy field
        firstPrecompOrderByHasNoNulls - true if the firstPrecompOrderBy field does not permit null values
        reverseOrderBy - true if the firstPrecompOrderBy was an OrderDescending
        Returns:
        an AbstractConstraint that uses AbstractValues reconstructed by reconstructAbstractValue
        Throws:
        QueryOptimiserException - if reconstructAbstractValue finds an AbstractValue that cannot be constructed, given the PrecomputedTable

      • reconstructAbstractValues

        public static void reconstructAbstractValues​(java.util.Collection<AbstractValue> oldValues,
                                             Table precomputedSqlTable,
                                             java.util.Map<AbstractValue,​SelectValue> valueMap,
                                             java.util.Set<AbstractTable> tableSet,
                                             boolean groupBy,
                                             java.util.Collection<AbstractValue> newValues)
                                      throws QueryOptimiserException
        Reconstructs a Collection of AbstractValue objects, calling reconstructAbstractValue on each one before adding it to another Collection. Reconstructed values will be added to the destination Collection in the same order as the iterator of the original Collection.
        Parameters:
        oldValues - the Collection of AbstractValue objects to reconstruct
        precomputedSqlTable - the Table object that remapped AbstractValues should refer to
        valueMap - a mapping from AbstractValue in the PrecomputedTable onto the SelectValue that contains it.
        tableSet - a Set of all the tables that are being replaced - ie the Set of tables in the PrecomputedTable. We use this to work out which unrepresented AbstractValues are problems.
        groupBy - true if the PrecomputedTable contains a GROUP BY clause
        newValues - the Collection to put the reconstructed AbstractValues in
        Throws:
        QueryOptimiserException - if reconstructAbstractValue finds an AbstractValue that cannot be constructed, given the PrecomputedTable

      • addNonCoveredFrom

        public static <T> void addNonCoveredFrom​(java.util.Set<T> input,
                                         java.util.Set<T> subtract,
                                         java.util.Set<T> output)
        Adds all required FROM items to the FROM list of the new query. Adds all items in input, minus the items in subtract, to the Set output.
        Type Parameters:
        T - The element type
        Parameters:
        input - a Set of items to be added to the output
        subtract - a Set of items to miss out
        output - a destination Set to add items to