review.fuel-infra Code Review - packages/trusty/mysql-wsrep-5.6.git/blob

   1 /*
   2    Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; version 2 of the License.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12
  13    You should have received a copy of the GNU General Public License
  14    along with this program; if not, write to the Free Software
  15    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
  16 */
  17
  18 package com.mysql.clusterj.core.query;
  19
  20 import com.mysql.clusterj.ClusterJUserException;
  21 import com.mysql.clusterj.core.metadata.AbstractDomainFieldHandlerImpl;
  22
  23 import com.mysql.clusterj.core.query.PredicateImpl.ScanType;
  24 import com.mysql.clusterj.core.spi.QueryExecutionContext;
  25 import com.mysql.clusterj.core.store.Index;
  26 import com.mysql.clusterj.core.store.IndexScanOperation;
  27 import com.mysql.clusterj.core.store.Operation;
  28
  29 import com.mysql.clusterj.core.util.I18NHelper;
  30 import com.mysql.clusterj.core.util.Logger;
  31 import com.mysql.clusterj.core.util.LoggerFactoryService;
  32
  33 import java.util.ArrayList;
  34 import java.util.List;
  35
  36 /**
  37  * This class is responsible for deciding whether an index can be used
  38  * for a specific query. An instance of this class is created to evaluate
  39  * a query and to decide whether the index can be used in executing the
  40  * query. An inner class represents each candidateColumn in the index.
  41  *
  42  * An instance of this class is created for each index for each query, and an instance of
  43  * the candidate column for each column of the index. During execution of the query,
  44  * the query terms are used to mark the candidate columns and associate candidate columns
  45  * with each query term. Each query term might be associated with multiple candidate columns,
  46  * one for each index containing the column referenced by the query term.
  47  *
  48  */
  49 public class CandidateIndexImpl {
  50
  51     /** My message translator */
  52     static final I18NHelper local = I18NHelper.getInstance(CandidateIndexImpl.class);
  53
  54     /** My logger */
  55     static final Logger logger = LoggerFactoryService.getFactory()
  56             .getInstance(CandidateIndexImpl.class);
  57
  58     private String className = "none";
  59     private Index storeIndex;
  60     private String indexName = "none";
  61     private boolean unique;
  62     private boolean multiRange = false;
  63     private CandidateColumnImpl[] candidateColumns = null;
  64     private ScanType scanType = PredicateImpl.ScanType.TABLE_SCAN;
  65     private int fieldScore = 1;
  66
  67     public CandidateIndexImpl(
  68             String className, Index storeIndex, boolean unique, AbstractDomainFieldHandlerImpl[] fields) {
  69         if (logger.isDebugEnabled()) logger.debug("className: " + className
  70                 + " storeIndex: " + storeIndex.getName()
  71                 + " unique: " + Boolean.toString(unique)
  72                 + " fields: " + toString(fields));
  73         this.className = className;
  74         this.storeIndex = storeIndex;
  75         this.indexName = storeIndex.getName();
  76         this.unique = unique;
  77         this.candidateColumns = new CandidateColumnImpl[fields.length];
  78         if (fields.length == 1) {
  79             // for a single field with multiple columns, score the number of columns
  80             this.fieldScore = fields[0].getColumnNames().length;
  81         }
  82         int i = 0;
  83         for (AbstractDomainFieldHandlerImpl domainFieldHandler: fields) {
  84             CandidateColumnImpl candidateColumn = new CandidateColumnImpl(domainFieldHandler);
  85             candidateColumns[i++] = candidateColumn;
  86         }
  87         if (logger.isDebugEnabled()) logger.debug(toString());
  88     }
  89
  90     private String toString(AbstractDomainFieldHandlerImpl[] fields) {
  91         StringBuilder builder = new StringBuilder();
  92         char separator = '[';
  93         for (AbstractDomainFieldHandlerImpl field: fields) {
  94             builder.append(separator);
  95             builder.append(field.getName());
  96             separator = ' ';
  97         }
  98         builder.append(']');
  99         return builder.toString();
 100     }
 101
 102     /** The CandidateIndexImpl used in cases of no where clause. */
 103     static CandidateIndexImpl indexForNullWhereClause = new CandidateIndexImpl();
 104
 105     /** The accessor for the no where clause candidate index. */
 106     public static CandidateIndexImpl getIndexForNullWhereClause() {
 107         return indexForNullWhereClause;
 108     }
 109
 110     /** The CandidateIndexImpl used in cases of no where clause. */
 111     protected CandidateIndexImpl() {
 112         // candidateColumns will be null if no usable columns in the index
 113     }
 114
 115     @Override
 116     public String toString() {
 117         StringBuffer buffer = new StringBuffer();
 118         buffer.append("CandidateIndexImpl for class: ");
 119         buffer.append(className);
 120         buffer.append(" index: ");
 121         buffer.append(indexName);
 122         buffer.append(" unique: ");
 123         buffer.append(unique);
 124         if (candidateColumns != null) {
 125             for (CandidateColumnImpl column:candidateColumns) {
 126                 buffer.append(" field: ");
 127                 buffer.append(column.domainFieldHandler.getName());
 128             }
 129         } else {
 130             buffer.append(" no fields.");
 131         }
 132         return buffer.toString();
 133     }
 134
 135     public void markLowerBound(int fieldNumber, PredicateImpl predicate, boolean strict) {
 136         if (candidateColumns != null) {
 137             candidateColumns[fieldNumber].markLowerBound(predicate, strict);
 138         }
 139     }
 140
 141     public void markUpperBound(int fieldNumber, PredicateImpl predicate, boolean strict) {
 142         if (candidateColumns != null) {
 143             candidateColumns[fieldNumber].markUpperBound(predicate, strict);
 144         }
 145     }
 146
 147     public void markEqualBound(int fieldNumber, PredicateImpl predicate) {
 148         if (candidateColumns != null) {
 149             candidateColumns[fieldNumber].markEqualBound(predicate);
 150         }
 151     }
 152
 153     public void markInBound(int fieldNumber, InPredicateImpl predicate) {
 154         if (candidateColumns != null) {
 155             candidateColumns[fieldNumber].markInBound(predicate);
 156         }
 157     }
 158
 159     String getIndexName() {
 160         return indexName;
 161     }
 162
 163     CandidateColumnImpl lastLowerBoundColumn = null;
 164     CandidateColumnImpl lastUpperBoundColumn = null;
 165
 166     /** Evaluate the suitability of this index for the query. An instance represents each
 167      * index, with primary key and non-hash-key indexes having two instances, one for the
 168      * unique index and one for the btree index for the same column(s).
 169      * Unique indexes where all of the columns are compared equal return a score of 100.
 170      * Btree indexes get one point for each query term that can be used (maximum of two
 171      * points for each comparison). Greater than and less than get one point each.
 172      * Equals and In get two points each. Once a gap is found in query terms for either
 173      * upper or lower bound, processing for that bound stops.
 174      * The last query term (candidate column) for each of the lower and upper bound is noted.
 175      * The method is synchronized because the method modifies the state of the instance,
 176      * which might be shared by multiple threads.
 177      * @return the score of this index.
 178      */
 179     synchronized int getScore() {
 180         if (candidateColumns == null) {
 181             return 0;
 182         }
 183         int result = 0;
 184         boolean lowerBoundDone = false;
 185         boolean upperBoundDone = false;
 186         if (unique) {
 187             // all columns need to have equal bound
 188             for (CandidateColumnImpl column: candidateColumns) {
 189                 if (!(column.equalBound)) {
 190                     // not equal bound; can't use unique index
 191                     return result;
 192                 }
 193             }
 194             if ("PRIMARY".equals(indexName)) {
 195                 scanType = PredicateImpl.ScanType.PRIMARY_KEY;
 196             } else {
 197                 scanType = PredicateImpl.ScanType.UNIQUE_KEY;
 198             }
 199             return 100;
 200         } else {
 201             // range index
 202             // leading columns need any kind of bound
 203             // extra credit for equals
 204             for (CandidateColumnImpl candidateColumn: candidateColumns) {
 205                 if ((candidateColumn.equalBound)) {
 206                     scanType = PredicateImpl.ScanType.INDEX_SCAN;
 207                     if (!lowerBoundDone) {
 208                         result += fieldScore;
 209                         lastLowerBoundColumn = candidateColumn;
 210                     }
 211                     if (!upperBoundDone) {
 212                         result += fieldScore;
 213                         lastUpperBoundColumn = candidateColumn;
 214                     }
 215                 } else if ((candidateColumn.inBound)) {
 216                     scanType = PredicateImpl.ScanType.INDEX_SCAN;
 217                     multiRange = true;
 218                     if (!lowerBoundDone) {
 219                         result += fieldScore;
 220                         lastLowerBoundColumn = candidateColumn;
 221                     }
 222                     if (!upperBoundDone) {
 223                         result += fieldScore;
 224                         lastUpperBoundColumn = candidateColumn;
 225                     }
 226                 } else if (!(lowerBoundDone && upperBoundDone)) {
 227                     // lower bound and upper bound are independent
 228                     boolean hasLowerBound = candidateColumn.hasLowerBound();
 229                     boolean hasUpperBound = candidateColumn.hasUpperBound();
 230                     // keep going until both upper and lower are done
 231                     if (hasLowerBound || hasUpperBound) {
 232                         scanType = PredicateImpl.ScanType.INDEX_SCAN;
 233                     }
 234                     if (!lowerBoundDone) {
 235                         if (hasLowerBound) {
 236                             result += fieldScore;
 237                             lastLowerBoundColumn = candidateColumn;
 238                         } else {
 239                             lowerBoundDone = true;
 240                         }
 241                     }
 242                     if (!upperBoundDone) {
 243                         if (hasUpperBound) {
 244                             result += fieldScore;
 245                             lastUpperBoundColumn = candidateColumn;
 246                         } else {
 247                             upperBoundDone = true;
 248                         }
 249                     }
 250                     if (lowerBoundDone && upperBoundDone) {
 251                         continue;
 252                     }
 253                 }
 254             }
 255             if (lastLowerBoundColumn != null) {
 256                 lastLowerBoundColumn.markLastLowerBoundColumn();
 257             }
 258             if (lastUpperBoundColumn != null) {
 259                 lastUpperBoundColumn.markLastUpperBoundColumn();
 260             }
 261         }
 262         return result;
 263     }
 264
 265     public ScanType getScanType() {
 266         return scanType;
 267     }
 268
 269     /* No bound is complete yet */
 270     private final int BOUND_STATUS_NO_BOUND_DONE = 0;
 271     /* The lower bound is complete */
 272     private final int BOUND_STATUS_LOWER_BOUND_DONE = 1;
 273     /* The upper bound is complete */
 274     private final int BOUND_STATUS_UPPER_BOUND_DONE = 2;
 275     /* Both bounds are complete */
 276     private final int BOUND_STATUS_BOTH_BOUNDS_DONE = 3;
 277
 278     /** Set bounds for the operation defined for this index. This index was chosen as
 279      * the best index to use for the query.
 280      * Each query term (candidate column) is used to set a bound. The bound depends on
 281      * the type of query term, whether the term is the last term, and whether the
 282      * bound type (upper or lower) has already been completely specified.
 283      * Equal and In query terms can be used for an equal bound, a lower bound, or an upper
 284      * bound. Strict bounds that are not the last bound are converted to non-strict bounds.
 285      * In query terms are decomposed into multiple range bounds, one range for each
 286      * value in the query term.
 287      * @param context the query execution context, containing the parameter values
 288      * @param op the index scan operation
 289      */
 290     void operationSetBounds(QueryExecutionContext context, IndexScanOperation op) {
 291         if (multiRange) {
 292             // find how many query terms are inPredicates
 293             List<Integer> parameterSizes = new ArrayList<Integer>();
 294             for (CandidateColumnImpl candidateColumn:candidateColumns) {
 295                 if (candidateColumn.hasInBound()) {
 296                     parameterSizes.add(candidateColumn.getParameterSize(context));
 297                 }
 298             }
 299             if (parameterSizes.size() > 1) {
 300                 throw new ClusterJUserException(local.message("ERR_Too_Many_In_For_Index", indexName));
 301             }
 302             // if only one column in the index, optimize
 303             if (candidateColumns.length == 1) {
 304                 candidateColumns[0].operationSetAllBounds(context, op);
 305             } else {
 306                 // set multiple bounds; one for each item in the parameter (context)
 307                 for (int parameterIndex = 0; parameterIndex < parameterSizes.get(0); ++parameterIndex) {
 308                     int boundStatus = BOUND_STATUS_NO_BOUND_DONE;
 309                     for (CandidateColumnImpl candidateColumn:candidateColumns) {
 310                         if (logger.isDetailEnabled()) logger.detail(
 311                                 "parameterIndex: " + parameterIndex
 312                                 + " boundStatus: " + boundStatus
 313                                 + " candidateColumn: " + candidateColumn.domainFieldHandler.getName());
 314                         // execute the bounds operation if anything left to do
 315                         if (boundStatus != BOUND_STATUS_BOTH_BOUNDS_DONE) {
 316                             boundStatus = candidateColumn.operationSetBounds(context, op, parameterIndex, boundStatus);
 317                         }
 318                     }
 319                     // after all columns are done, mark the end of bounds
 320                     op.endBound(parameterIndex);
 321                 }
 322             }
 323         } else {
 324             // not multi-range
 325             int boundStatus = BOUND_STATUS_NO_BOUND_DONE;
 326             for (CandidateColumnImpl candidateColumn:candidateColumns) {
 327                 if (logger.isDetailEnabled()) logger.detail("boundStatus: " + boundStatus
 328                         + " candidateColumn: " + candidateColumn.domainFieldHandler.getName());
 329                 // execute the bounds operation for each query term
 330                 if (boundStatus != BOUND_STATUS_BOTH_BOUNDS_DONE) {
 331                     boundStatus = candidateColumn.operationSetBounds(context, op, -1, boundStatus);
 332                 }
 333             }
 334         }
 335     }
 336
 337     void operationSetKeys(QueryExecutionContext context,
 338             Operation op) {
 339         for (CandidateColumnImpl candidateColumn:candidateColumns) {
 340             // execute the equal operation
 341             candidateColumn.operationSetKeys(context, op);
 342         }
 343     }
 344
 345     /**
 346      * This class represents one column in an index, and its corresponding query term(s).
 347      * The column might be associated with a lower bound term, an upper bound term,
 348      * an equal term, or an in term.
 349      */
 350     class CandidateColumnImpl {
 351
 352         protected AbstractDomainFieldHandlerImpl domainFieldHandler;
 353         protected PredicateImpl lowerBoundPredicate;
 354         protected PredicateImpl upperBoundPredicate;
 355         protected PredicateImpl equalPredicate;
 356         protected InPredicateImpl inPredicate;
 357         protected Boolean lowerBoundStrict = null;
 358         protected Boolean upperBoundStrict = null;
 359         protected boolean equalBound = false;
 360         protected boolean inBound = false;
 361         protected boolean lastLowerBoundColumn = false;
 362         protected boolean lastUpperBoundColumn = false;
 363
 364         protected boolean hasLowerBound() {
 365             return lowerBoundPredicate != null || equalPredicate != null || inPredicate != null;
 366         }
 367
 368         /** Set all bounds in the operation, ending each bound with an end_of_bound.
 369          *
 370          * @param context the query context
 371          * @param op the operation
 372          */
 373         public void operationSetAllBounds(QueryExecutionContext context, IndexScanOperation op) {
 374             inPredicate.operationSetAllBounds(context, op);
 375         }
 376
 377         public int getParameterSize(QueryExecutionContext context) {
 378             // TODO Auto-generated method stub
 379             return inPredicate.getParameterSize(context);
 380         }
 381
 382         protected boolean hasUpperBound() {
 383             return upperBoundPredicate != null || equalPredicate != null || inPredicate != null;
 384         }
 385
 386         protected boolean hasInBound() {
 387             return inBound;
 388         }
 389
 390         private CandidateColumnImpl(AbstractDomainFieldHandlerImpl domainFieldHandler) {
 391             this.domainFieldHandler = domainFieldHandler;
 392         }
 393
 394         private void markLastLowerBoundColumn() {
 395             lastLowerBoundColumn = true;
 396         }
 397
 398         private void markLastUpperBoundColumn() {
 399             lastUpperBoundColumn = true;
 400         }
 401
 402         private void markLowerBound(PredicateImpl predicate, boolean strict) {
 403             lowerBoundStrict = strict;
 404             this.lowerBoundPredicate = predicate;
 405         }
 406
 407         private void markUpperBound(PredicateImpl predicate, boolean strict) {
 408             upperBoundStrict = strict;
 409             this.upperBoundPredicate = predicate;
 410         }
 411
 412         private void markEqualBound(PredicateImpl predicate) {
 413             equalBound = true;
 414             this.equalPredicate = predicate;
 415         }
 416
 417         public void markInBound(InPredicateImpl predicate) {
 418             inBound = true;
 419             this.inPredicate = predicate;
 420         }
 421
 422         /** Set bounds into each predicate that has been defined.
 423          *
 424          * @param op the operation
 425          * @param index for inPredicates, the index into the parameter
 426          * @param boundStatus
 427          */
 428         private int operationSetBounds(
 429                 QueryExecutionContext context, IndexScanOperation op, int index, int boundStatus) {
 430
 431             if (logger.isDetailEnabled()) logger.detail("column: " + domainFieldHandler.getName()
 432                     + " boundStatus: " + boundStatus
 433                     + " lastLowerBoundColumn: " + lastLowerBoundColumn
 434                     + " lastUpperBoundColumn: " + lastUpperBoundColumn);
 435             switch(boundStatus) {
 436                 case BOUND_STATUS_BOTH_BOUNDS_DONE:
 437                     // cannot set either lower or upper bound
 438                     return BOUND_STATUS_BOTH_BOUNDS_DONE;
 439                 case BOUND_STATUS_NO_BOUND_DONE:
 440                     // can set either/both lower or upper bound
 441                     if (equalPredicate != null) {
 442                         equalPredicate.operationSetBounds(context, op, true);
 443                     }
 444                     if (inPredicate != null) {
 445                         inPredicate.operationSetBound(context, op, index, true);
 446                     }
 447                     if (lowerBoundPredicate != null) {
 448                         lowerBoundPredicate.operationSetLowerBound(context, op, lastLowerBoundColumn);
 449                     }
 450                     if (upperBoundPredicate != null) {
 451                         upperBoundPredicate.operationSetUpperBound(context, op, lastUpperBoundColumn);
 452                     }
 453                     break;
 454                 case BOUND_STATUS_LOWER_BOUND_DONE:
 455                     // cannot set lower, only upper bound
 456                     if (equalPredicate != null) {
 457                         equalPredicate.operationSetUpperBound(context, op, lastUpperBoundColumn);
 458                     }
 459                     if (inPredicate != null) {
 460                         inPredicate.operationSetUpperBound(context, op, index);
 461                     }
 462                     if (upperBoundPredicate != null) {
 463                         upperBoundPredicate.operationSetUpperBound(context, op, lastUpperBoundColumn);
 464                     }
 465                     break;
 466                 case BOUND_STATUS_UPPER_BOUND_DONE:
 467                     // cannot set upper, only lower bound
 468                     if (equalPredicate != null) {
 469                         equalPredicate.operationSetLowerBound(context, op, lastLowerBoundColumn);
 470                     }
 471                     if (inPredicate != null) {
 472                         inPredicate.operationSetLowerBound(context, op, index);
 473                     }
 474                     if (lowerBoundPredicate != null) {
 475                         lowerBoundPredicate.operationSetLowerBound(context, op, lastLowerBoundColumn);
 476                     }
 477                     break;
 478             }
 479             if (!hasLowerBound()) {
 480                 // if this has no lower bound, set lower bound done
 481                 boundStatus |= BOUND_STATUS_LOWER_BOUND_DONE;
 482             }
 483             if (!hasUpperBound()) {
 484                 // if this has no upper bound, set upper bound done
 485                 boundStatus |= BOUND_STATUS_UPPER_BOUND_DONE;
 486             }
 487             return boundStatus;
 488         }
 489
 490         private void operationSetKeys(QueryExecutionContext context, Operation op) {
 491             equalPredicate.operationEqual(context, op);
 492         }
 493
 494     }
 495
 496     /** Determine whether this index supports exactly the number of conditions.
 497      * For ordered indexes, any number of conditions are supported via filters.
 498      * For hash indexes, only the number of columns in the index are supported.
 499      * @param numberOfConditions the number of conditions in the query predicate
 500      * @return if this index supports exactly the number of conditions
 501      */
 502     public boolean supportsConditionsOfLength(int numberOfConditions) {
 503         if (unique) {
 504             return numberOfConditions == candidateColumns.length;
 505         } else {
 506             return true;
 507         }
 508     }
 509
 510     public Index getStoreIndex() {
 511         return storeIndex;
 512     }
 513
 514     public boolean isMultiRange() {
 515         return multiRange;
 516     }
 517
 518 }