kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t...@apache.org
Subject [2/5] incubator-kudu git commit: Integrate ColumnPredicate into client and server
Date Sun, 20 Mar 2016 20:45:35 GMT
http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/predicate_encoder.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/predicate_encoder.cc b/src/kudu/common/predicate_encoder.cc
deleted file mode 100644
index 946a067..0000000
--- a/src/kudu/common/predicate_encoder.cc
+++ /dev/null
@@ -1,244 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#include "kudu/common/predicate_encoder.h"
-
-#include <algorithm>
-
-#include "kudu/common/partial_row.h"
-#include "kudu/common/row.h"
-#include "kudu/common/row_key-util.h"
-#include "kudu/common/types.h"
-
-namespace kudu {
-
-RangePredicateEncoder::RangePredicateEncoder(const Schema* key_schema,
-                                             Arena* arena)
-  : key_schema_(key_schema),
-    arena_(arena) {
-}
-
-void RangePredicateEncoder::EncodeRangePredicates(ScanSpec *spec, bool erase_pushed) {
-  // Step 1) Simplify all predicates which apply to keys.
-  //
-  // First, we loop over all predicates, find those that apply to key columns,
-  // and group them by the column they apply to. Bounds are simplified (i.e.
-  // the tightest bounds are retained). In this step, we retain the original indexes
-  // of the predicates that we've analyzed, so we can later remove them if necessary.
-  vector<SimplifiedBounds> key_bounds;
-  SimplifyBounds(*spec, &key_bounds);
-
-  // Step 2) Determine the length of the "equality" part of the key.
-  //
-  // The following pattern of predicates can be converted into range scans:
-  //
-  //   k1 = a AND k2 = b AND ... AND kN BETWEEN c AND d
-  //
-  // In other words, we can have a sequence of equality conditions, followed by
-  // a range predicate on one further column past that.
-  //
-  // In this step, we count how many key components have equality predicates applied.
-  int equality_prefix = CountKeyPrefixEqualities(key_bounds);
-
-  // We're only allowed to push the equality conditions and optionally one more.
-  int max_push_len = std::min<int>(equality_prefix + 1, key_bounds.size());
-
-  // Step 3) Prepare upper and lower bound key tuples
-  //
-  // Here we allocate tuples from the arena which will store the upper and lower
-  // bound. We initialize all elements of these tuples to their minimum value.
-  uint8_t* lower_buf = static_cast<uint8_t*>(
-      CHECK_NOTNULL(arena_->AllocateBytes(key_schema_->key_byte_size())));
-  uint8_t* upper_buf = static_cast<uint8_t*>(
-      CHECK_NOTNULL(arena_->AllocateBytes(key_schema_->key_byte_size())));
-  ContiguousRow lower_key(key_schema_, lower_buf);
-  ContiguousRow upper_key(key_schema_, upper_buf);
-
-  row_key_util::SetKeyToMinValues(&lower_key);
-  row_key_util::SetKeyToMinValues(&upper_key);
-
-  // Step 4) Construct upper/lower bound tuples
-  //
-  // We iterate through the predicates and copy the predicate bounds into
-  // the tuples, while also keeping track of how many elements have been
-  // set in each.
-  //
-  // For example, with a (year, month, day) primary key:
-  //
-  //   Predicate: year = 2015 AND month = 7 AND day <= 15
-  //   upper_key: (2015, 7, 15)    (len=3)
-  //   lower_key: (2015, 7, <min>) (len=2)
-  //
-  // Note that the 'day' component of the lower bound remains as '<min>'
-  // here because there is no lower bound range predicate on the 'day' column.
-  //
-  // While iterating, we also keep track of which original predicates were
-  // pushed down, so we can remove them later.
-  int lower_len = 0;
-  int upper_len = 0;
-  vector<bool> was_pushed(spec->predicates().size());
-  int n_pushed;
-  for (n_pushed = 0; n_pushed < max_push_len; n_pushed++) {
-    const ColumnSchema& col = key_schema_->column(n_pushed);
-    int size = col.type_info()->size();
-    const SimplifiedBounds& b = key_bounds[n_pushed];
-
-    // If we're still in the "equality" part of the key, we expect both
-    // the upper and lower bounds to be set.
-    if (n_pushed < equality_prefix) {
-      DCHECK(b.lower && b.upper);
-    }
-
-    if (b.lower) {
-      memcpy(lower_key.mutable_cell_ptr(n_pushed), key_bounds[n_pushed].lower, size);
-      lower_len++;
-    }
-    if (b.upper) {
-      memcpy(upper_key.mutable_cell_ptr(n_pushed), key_bounds[n_pushed].upper, size);
-      upper_len++;
-    }
-    for (int pred_idx : key_bounds[n_pushed].orig_predicate_indexes) {
-      was_pushed[pred_idx] = true;
-    }
-  }
-
-  // Step 4) Convert upper bound to exclusive
-  //
-  // Column range predicates are inclusive, but primary key predicates are exclusive.
-  // Here, we increment the upper bound key to convert between the two.
-  //
-  // Handling prefix conditions on the upper bound is slightly subtle.
-  // Consider, for example:
-  //
-  //   Predicate: year = 2015 AND month <= 7
-  //   upper_key: (2015, 7, <min>)  (len=2)
-  //
-  // Conceptually, what we'd like to do is set upper_key <= (2015, 7, <max>),
-  // and then increment it to: upper_key < (2015, 8, <min>). However, there is
-  // no such concept of a "<max>" value for a column (strings can always be
-  // incremented further). So, instead, we leave the remaining components
-  // as "<min>", and increment the prefix, which yields the same result.
-  if (upper_len) {
-    if (!row_key_util::IncrementKeyPrefix(&upper_key, upper_len, arena_)) {
-      // If the upper bound is already the very maximum key, we can't increment
-      // it any more. In that case, it's equivalent to setting no bound at all,
-      // so we reset the length back to 0.
-      //
-      // For example, consider:
-      //   Predicate: year <= MAX_INT
-      //   upper_key; (MAX_INT, <min>, <min>) (len=1)
-      //
-      // IncrementKeyPrefix(1) here will return false since MAX_INT cannot be
-      // further incremented. However, the predicate is itself tautological, so
-      // we can just remove it.
-      upper_len = 0;
-    }
-  }
-
-  VLOG(4) << "Lower: " << key_schema_->DebugRowKey(lower_key) << "(" << lower_len << ")";
-  VLOG(4) << "Upper: " << key_schema_->DebugRowKey(upper_key) << "(" << upper_len << ")";
-
-  // Step 5. Erase the pushed predicates from the ScanSpec.
-  if (erase_pushed) {
-    ErasePushedPredicates(spec, was_pushed);
-  }
-
-  // Step 6. Add the new range predicates to the spec.
-  if (lower_len) {
-    EncodedKey* lower = EncodedKey::FromContiguousRow(ConstContiguousRow(lower_key)).release();
-    pool_.Add(lower);
-    spec->SetLowerBoundKey(lower);
-  }
-  if (upper_len) {
-    EncodedKey* upper = EncodedKey::FromContiguousRow(ConstContiguousRow(upper_key)).release();
-    pool_.Add(upper);
-    spec->SetExclusiveUpperBoundKey(upper);
-  }
-}
-
-void RangePredicateEncoder::SimplifyBounds(const ScanSpec& spec,
-                                           vector<SimplifiedBounds>* key_bounds) const {
-  key_bounds->clear();
-  key_bounds->resize(key_schema_->num_key_columns());
-
-  for (int i = 0; i < spec.predicates().size(); i++) {
-    const ColumnRangePredicate& pred = spec.predicates()[i];
-    int idx = key_schema_->find_column(pred.column().name());
-    if (idx == -1 || idx >= key_bounds->size()) {
-      continue;
-    }
-    const ColumnSchema& col = key_schema_->column(idx);
-
-    // Add to the list of pushable predicates for this column.
-    CHECK(pred.range().has_lower_bound() || pred.range().has_upper_bound());
-    (*key_bounds)[idx].orig_predicate_indexes.push_back(i);
-
-    if (pred.range().has_upper_bound()) {
-      // If we haven't seen any upper bound, or this upper bound is tighter than
-      // (less than) the one we've seen already, replace it.
-      if ((*key_bounds)[idx].upper == nullptr ||
-          col.type_info()->Compare(pred.range().upper_bound(),
-                                   (*key_bounds)[idx].upper) < 0) {
-        (*key_bounds)[idx].upper = pred.range().upper_bound();
-      }
-    }
-
-    if (pred.range().has_lower_bound()) {
-      // If we haven't seen any lower bound, or this lower bound is tighter than
-      // (greater than) the one we've seen already, replace it.
-      if ((*key_bounds)[idx].lower == nullptr ||
-          col.type_info()->Compare(pred.range().lower_bound(),
-                                   (*key_bounds)[idx].lower) > 0) {
-        (*key_bounds)[idx].lower = pred.range().lower_bound();
-      }
-    }
-  }
-}
-
-int RangePredicateEncoder::CountKeyPrefixEqualities(
-    const vector<SimplifiedBounds>& key_bounds) const {
-
-  int i = 0;
-  for (; i < key_schema_->num_key_columns(); i++) {
-    if (!key_bounds[i].lower || !key_bounds[i].upper) {
-      break;
-    }
-    ColumnRangePredicate pred(key_schema_->column(i),
-                              key_bounds[i].lower,
-                              key_bounds[i].upper);
-    if (!pred.range().IsEquality()) break;
-  }
-  return i;
-}
-
-void RangePredicateEncoder::ErasePushedPredicates(
-    ScanSpec *spec, const vector<bool>& should_erase) const {
-  int num_preds = spec->predicates().size();
-  CHECK_EQ(should_erase.size(), num_preds);
-
-  vector<ColumnRangePredicate> new_preds;
-  new_preds.reserve(num_preds);
-
-  for (int i = 0; i < num_preds; i++) {
-    if (!should_erase[i]) {
-      new_preds.push_back(spec->predicates()[i]);
-    }
-  }
-  spec->mutable_predicates()->swap(new_preds);
-}
-
-} // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/predicate_encoder.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/predicate_encoder.h b/src/kudu/common/predicate_encoder.h
deleted file mode 100644
index 70df381..0000000
--- a/src/kudu/common/predicate_encoder.h
+++ /dev/null
@@ -1,83 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-#ifndef KUDU_COMMON_PREDICATE_ENCODER_H
-#define KUDU_COMMON_PREDICATE_ENCODER_H
-
-#include <gtest/gtest_prod.h>
-#include <vector>
-
-
-#include "kudu/common/encoded_key.h"
-#include "kudu/common/row.h"
-#include "kudu/common/scan_spec.h"
-#include "kudu/common/schema.h"
-#include "kudu/util/auto_release_pool.h"
-
-namespace kudu {
-
-using std::vector;
-
-// Encodes a list of column predicates into key-range predicates.
-// Uses an AutoReleasePool to allocate EncodedKey instances,
-// which means the lifetime of RangePredicateEncoder must be >= the
-// lifetime of any classes that access the ScanSpec.
-class RangePredicateEncoder {
- public:
-  // 'key_schema' is not copied and must remain valid for the lifetime
-  // of this object.
-  //
-  // Some parts of the resulting predicates may be allocated out of 'arena'
-  // and thus 'arena' must not be reset or destructed until after any ScanSpecs
-  // modified by this encoder have been destroyed.
-  RangePredicateEncoder(const Schema* key_schema, Arena* arena);
-
-  // Encodes the predicates found in 'spec' into a key range which is
-  // then emitted back into 'spec'.
-  //
-  // If 'erase_pushed' is true, pushed predicates are removed from 'spec'.
-  void EncodeRangePredicates(ScanSpec *spec, bool erase_pushed);
-
- private:
-  friend class TestRangePredicateEncoder;
-  FRIEND_TEST(CompositeIntKeysTest, TestSimplify);
-
-  struct SimplifiedBounds {
-    SimplifiedBounds() : upper(NULL), lower(NULL) {}
-    const void* upper;
-    const void* lower;
-    vector<int> orig_predicate_indexes;
-  };
-
-  void SimplifyBounds(const ScanSpec& spec,
-                      std::vector<SimplifiedBounds>* key_bounds) const;
-
-  // Returns the number of contiguous equalities in the key prefix.
-  int CountKeyPrefixEqualities(const std::vector<SimplifiedBounds>& bounds) const;
-
-  // Erases any predicates we've encoded from the predicate list within the
-  // ScanSpec.
-  void ErasePushedPredicates(
-      ScanSpec *spec, const std::vector<bool>& should_erase) const;
-
-  const Schema* key_schema_;
-  Arena* arena_;
-  AutoReleasePool pool_;
-};
-
-} // namespace kudu
-
-#endif

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/row_key-util-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/row_key-util-test.cc b/src/kudu/common/row_key-util-test.cc
deleted file mode 100644
index 661dde4..0000000
--- a/src/kudu/common/row_key-util-test.cc
+++ /dev/null
@@ -1,135 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#include <gtest/gtest.h>
-
-#include "kudu/common/partial_row.h"
-#include "kudu/common/row.h"
-#include "kudu/common/row_key-util.h"
-#include "kudu/common/schema.h"
-#include "kudu/gutil/mathlimits.h"
-#include "kudu/util/test_util.h"
-
-namespace kudu {
-
-class RowKeyUtilTest : public KuduTest {
- public:
-  RowKeyUtilTest()
-    : arena_(1024, 4096) {}
-
- protected:
-  uint8_t* row_data(KuduPartialRow* row) {
-    return row->row_data_;
-  }
-
-  Arena arena_;
-};
-
-TEST_F(RowKeyUtilTest, TestIncrementNonCompositeKey) {
-  Schema schema({ ColumnSchema("key", INT32),
-                  ColumnSchema("other_col", INT32),
-                  ColumnSchema("other_col2", STRING, true) },
-                1);
-  KuduPartialRow p_row(&schema);
-  ContiguousRow row(&schema, row_data(&p_row));
-
-  // Normal increment.
-  EXPECT_OK(p_row.SetInt32(0, 1000));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 key=1001", p_row.ToString());
-
-  // Overflow increment.
-  EXPECT_OK(p_row.SetInt32(0, MathLimits<int32_t>::kMax));
-  EXPECT_FALSE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 key=-2147483648", p_row.ToString());
-}
-
-TEST_F(RowKeyUtilTest, TestIncrementCompositeKey) {
-  Schema schema({ ColumnSchema("k1", INT32),
-                  ColumnSchema("k2", INT32),
-                  ColumnSchema("other_col", STRING, true) },
-                2);
-
-  KuduPartialRow p_row(&schema);
-  ContiguousRow row(&schema, row_data(&p_row));
-
-  // Normal increment.
-  EXPECT_OK(p_row.SetInt32(0, 1000));
-  EXPECT_OK(p_row.SetInt32(1, 1000));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 k1=1000, int32 k2=1001", p_row.ToString());
-
-  // Overflow a later part of the key, carrying into the earlier
-  // part..
-  EXPECT_OK(p_row.SetInt32(1, MathLimits<int32_t>::kMax));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 k1=1001, int32 k2=-2147483648", p_row.ToString());
-
-  // Overflow the whole key.
-  EXPECT_OK(p_row.SetInt32(0, MathLimits<int32_t>::kMax));
-  EXPECT_OK(p_row.SetInt32(1, MathLimits<int32_t>::kMax));
-  EXPECT_FALSE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 k1=-2147483648, int32 k2=-2147483648", p_row.ToString());
-}
-
-TEST_F(RowKeyUtilTest, TestIncrementCompositeIntStringKey) {
-  Schema schema({ ColumnSchema("k1", INT32),
-                  ColumnSchema("k2", STRING),
-                  ColumnSchema("other_col", STRING, true) },
-                2);
-
-  KuduPartialRow p_row(&schema);
-  ContiguousRow row(&schema, row_data(&p_row));
-
-  // Normal increment.
-  EXPECT_OK(p_row.SetInt32(0, 1000));
-  EXPECT_OK(p_row.SetString(1, "hello"));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 k1=1000, string k2=hello\\000", p_row.ToString());
-
-  // There's no way to overflow a string key - you can always make it higher
-  // by tacking on more \x00.
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("int32 k1=1000, string k2=hello\\000\\000", p_row.ToString());
-}
-
-TEST_F(RowKeyUtilTest, TestIncrementCompositeStringIntKey) {
-  Schema schema({ ColumnSchema("k1", STRING),
-                  ColumnSchema("k2", INT32),
-                  ColumnSchema("other_col", STRING, true) },
-                2);
-
-  KuduPartialRow p_row(&schema);
-  ContiguousRow row(&schema, row_data(&p_row));
-
-  // Normal increment.
-  EXPECT_OK(p_row.SetString(0, "hello"));
-  EXPECT_OK(p_row.SetInt32(1, 1000));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("string k1=hello, int32 k2=1001", p_row.ToString());
-
-  // Overflowing the int32 portion should tack \x00 onto the
-  // string portion.
-  EXPECT_OK(p_row.SetInt32(1, MathLimits<int32_t>::kMax));
-  EXPECT_TRUE(row_key_util::IncrementKey(&row, &arena_));
-  EXPECT_EQ("string k1=hello\\000, int32 k2=-2147483648", p_row.ToString());
-}
-
-
-
-
-} // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/row_key-util.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/row_key-util.cc b/src/kudu/common/row_key-util.cc
deleted file mode 100644
index dadf74e..0000000
--- a/src/kudu/common/row_key-util.cc
+++ /dev/null
@@ -1,118 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-#include "kudu/common/row_key-util.h"
-
-#include <boost/type_traits/is_unsigned.hpp>
-
-#include "kudu/common/row.h"
-
-namespace kudu {
-namespace row_key_util {
-
-namespace {
-
-template<DataType type>
-bool IncrementIntCell(void* cell_ptr) {
-  typedef DataTypeTraits<type> traits;
-  typedef typename traits::cpp_type cpp_type;
-
-  cpp_type orig;
-  memcpy(&orig, cell_ptr, sizeof(cpp_type));
-
-  cpp_type inc;
-  if (boost::is_unsigned<cpp_type>::value) {
-    inc = orig + 1;
-  } else {
-    // Signed overflow is undefined in C. So, we'll use a branch here
-    // instead of counting on undefined behavior.
-    if (orig == MathLimits<cpp_type>::kMax) {
-      inc = MathLimits<cpp_type>::kMin;
-    } else {
-      inc = orig + 1;
-    }
-  }
-  memcpy(cell_ptr, &inc, sizeof(cpp_type));
-  return inc > orig;
-}
-
-bool IncrementStringCell(void* cell_ptr, Arena* arena) {
-  Slice orig;
-  memcpy(&orig, cell_ptr, sizeof(orig));
-  uint8_t* new_buf = CHECK_NOTNULL(
-      static_cast<uint8_t*>(arena->AllocateBytes(orig.size() + 1)));
-  memcpy(new_buf, orig.data(), orig.size());
-  new_buf[orig.size()] = '\0';
-
-  Slice inc(new_buf, orig.size() + 1);
-  memcpy(cell_ptr, &inc, sizeof(inc));
-  return true;
-}
-
-} // anonymous namespace
-
-bool IncrementCell(const ColumnSchema& col, void* cell_ptr, Arena* arena) {
-  DataType type = col.type_info()->physical_type();
-  switch (type) {
-#define HANDLE_TYPE(t) case t: return IncrementIntCell<t>(cell_ptr);
-    HANDLE_TYPE(UINT8);
-    HANDLE_TYPE(UINT16);
-    HANDLE_TYPE(UINT32);
-    HANDLE_TYPE(UINT64);
-    HANDLE_TYPE(INT8);
-    HANDLE_TYPE(INT16);
-    HANDLE_TYPE(INT32);
-    HANDLE_TYPE(TIMESTAMP);
-    HANDLE_TYPE(INT64);
-    case UNKNOWN_DATA:
-    case BOOL:
-    case FLOAT:
-    case DOUBLE:
-      LOG(FATAL) << "Unable to handle type " << type << " in row keys";
-    case STRING:
-    case BINARY:
-      return IncrementStringCell(cell_ptr, arena);
-    default: CHECK(false) << "Unknown data type: " << type;
-  }
-  return false; // unreachable
-#undef HANDLE_TYPE
-}
-
-void SetKeyToMinValues(ContiguousRow* row) {
-  for (int i = 0; i < row->schema()->num_key_columns(); i++) {
-    const ColumnSchema& col = row->schema()->column(i);
-    col.type_info()->CopyMinValue(row->mutable_cell_ptr(i));
-  }
-}
-
-bool IncrementKey(ContiguousRow* row, Arena* arena) {
-  return IncrementKeyPrefix(row, row->schema()->num_key_columns(), arena);
-}
-
-bool IncrementKeyPrefix(ContiguousRow* row, int prefix_len, Arena* arena) {
-  for (int i = prefix_len - 1; i >= 0; --i) {
-    if (IncrementCell(row->schema()->column(i),
-                                row->mutable_cell_ptr(i),
-                                arena)) {
-      return true;
-    }
-  }
-  return false;
-}
-
-} // namespace row_key_util
-} // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/row_key-util.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/row_key-util.h b/src/kudu/common/row_key-util.h
deleted file mode 100644
index 21df4ab..0000000
--- a/src/kudu/common/row_key-util.h
+++ /dev/null
@@ -1,77 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-//
-// Utility functions for working with the primary key portion of a row.
-#ifndef KUDU_COMMON_ROW_KEY_UTIL_H
-#define KUDU_COMMON_ROW_KEY_UTIL_H
-
-#include "kudu/gutil/port.h"
-
-namespace kudu {
-
-class Arena;
-class ColumnSchema;
-class ContiguousRow;
-
-namespace row_key_util {
-
-// Set all of the parts of the key in 'row' to the minimum legal values
-// for their types.
-//
-// For example:
-// - signed ints become very large negative values
-// - unsigned ints become 0
-// - strings become ""
-void SetKeyToMinValues(ContiguousRow* row);
-
-// Increment the primary key of this row to the smallest key which is greater
-// than the current key.
-//
-// For example, for a composite key with types (int8, int8), incrementing
-// the row (1, 1) will result in (1, 2). Incrementing (1, 127) will result
-// in (2, -128).
-//
-// Note that not all keys may be incremented without overflow. For example,
-// if the primary key is an int8, and the key is already set to '127',
-// incrementing would overflow. In this case, the value is incremented and
-// overflowed, but the function returns 'false' to indicate the overflow
-// condition. Otherwise, returns 'true'.
-//
-// String types are increment by appending a '\0' byte to the end. Since our
-// strings have unbounded length, this implies that if a key has a string
-// component, it will always be incremented.
-//
-// For the case of incrementing string types, we allocate a new copy of the
-// string from 'arena', which must be non-NULL.
-//
-// REQUIRES: all key columns must be valid.
-bool IncrementKey(ContiguousRow* row, Arena* arena) WARN_UNUSED_RESULT;
-
-// The same as the above function, but only acts on a prefix of the primary
-// key.
-//
-// For example, for a composite primary key (int8, int8, int8) with value
-// (1,2,3), IncrementKeyPrefix(2) will return (1,3,3).
-bool IncrementKeyPrefix(ContiguousRow* row, int prefix_len,
-                        Arena* arena) WARN_UNUSED_RESULT;
-
-// Increments the provided cell in place.
-bool IncrementCell(const ColumnSchema& col, void* cell_ptr, Arena* arena);
-
-} // namespace row_key_util
-} // namespace kudu
-#endif /* KUDU_COMMON_ROW_KEY_UTIL_H */

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/scan_spec-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/scan_spec-test.cc b/src/kudu/common/scan_spec-test.cc
new file mode 100644
index 0000000..428d9cd
--- /dev/null
+++ b/src/kudu/common/scan_spec-test.cc
@@ -0,0 +1,666 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "kudu/common/scan_spec.h"
+
+#include <glog/logging.h>
+#include <gtest/gtest.h>
+#include <vector>
+
+#include "kudu/common/column_predicate.h"
+#include "kudu/common/partial_row.h"
+#include "kudu/common/row.h"
+#include "kudu/common/schema.h"
+#include "kudu/gutil/map-util.h"
+#include "kudu/util/auto_release_pool.h"
+#include "kudu/util/memory/arena.h"
+#include "kudu/util/test_macros.h"
+#include "kudu/util/test_util.h"
+
+namespace kudu {
+
+class TestScanSpec : public KuduTest {
+ public:
+  explicit TestScanSpec(const Schema& s)
+    : arena_(1024, 256 * 1024),
+      pool_(),
+      schema_(s),
+      spec_() {}
+
+  enum ComparisonOp {
+    GE,
+    EQ,
+    LE
+  };
+
+  template<class T>
+  void AddPredicate(ScanSpec* spec, StringPiece col, ComparisonOp op, T val) {
+    int idx = schema_.find_column(col);
+    CHECK(idx != Schema::kColumnNotFound);
+
+    void* val_void = arena_.AllocateBytes(sizeof(val));
+    memcpy(val_void, &val, sizeof(val));
+
+    switch (op) {
+      case GE:
+        spec->AddPredicate(ColumnPredicate::Range(schema_.column(idx), val_void, nullptr));
+        break;
+      case EQ:
+        spec->AddPredicate(ColumnPredicate::Equality(schema_.column(idx), val_void));
+        break;
+      case LE: {
+        auto p = ColumnPredicate::InclusiveRange(schema_.column(idx), nullptr, val_void, &arena_);
+        if (p) spec->AddPredicate(*p);
+        break;
+      };
+    }
+  }
+
+  // Set the lower bound of the spec to the provided row. The row must outlive
+  // the spec.
+  void SetLowerBound(ScanSpec* spec, const KuduPartialRow& row) {
+    CHECK(row.IsKeySet());
+    ConstContiguousRow cont_row(row.schema(), row.row_data_);
+    gscoped_ptr<EncodedKey> enc_key(EncodedKey::FromContiguousRow(cont_row));
+    spec->SetLowerBoundKey(enc_key.get());
+    pool_.Add(enc_key.release());
+  }
+
+  // Set the exclusive upper bound of the spec to the provided row. The row must
+  // outlive the spec.
+  void SetExclusiveUpperBound(ScanSpec* spec, const KuduPartialRow& row) {
+    CHECK(row.IsKeySet());
+    ConstContiguousRow cont_row(row.schema(), row.row_data_);
+    gscoped_ptr<EncodedKey> enc_key(EncodedKey::FromContiguousRow(cont_row));
+    spec->SetExclusiveUpperBoundKey(enc_key.get());
+    pool_.Add(enc_key.release());
+  }
+
+ protected:
+  Arena arena_;
+  AutoReleasePool pool_;
+  Schema schema_;
+  ScanSpec spec_;
+};
+
+class CompositeIntKeysTest : public TestScanSpec {
+ public:
+  CompositeIntKeysTest() :
+    TestScanSpec(
+        Schema({ ColumnSchema("a", INT8),
+                 ColumnSchema("b", INT8),
+                 ColumnSchema("c", INT8) },
+               3)) {
+  }
+};
+
+// Test that multiple predicates on a column are collapsed.
+TEST_F(CompositeIntKeysTest, TestSimplify) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 127);
+  AddPredicate<int8_t>(&spec, "b", GE, 3);
+  AddPredicate<int8_t>(&spec, "b", LE, 127);
+  AddPredicate<int8_t>(&spec, "b", LE, 100);
+  AddPredicate<int8_t>(&spec, "c", LE, 64);
+  SCOPED_TRACE(spec.ToString(schema_));
+
+  ASSERT_EQ(3, spec.predicates().size());
+  ASSERT_EQ("`a` = 127", FindOrDie(spec.predicates(), "a").ToString());
+  ASSERT_EQ("`b` >= 3 AND `b` < 101", FindOrDie(spec.predicates(), "b").ToString());
+  ASSERT_EQ("`c` < 65", FindOrDie(spec.predicates(), "c").ToString());
+}
+
+// Predicate: a == 64
+TEST_F(CompositeIntKeysTest, TestPrefixEquality) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 64);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+
+  // Expect: key >= (64, -128, -128) AND key < (65, -128, -128)
+  EXPECT_EQ("PK >= (int8 a=64, int8 b=-128, int8 c=-128) AND "
+            "PK < (int8 a=65, int8 b=-128, int8 c=-128)",
+            spec.ToString(schema_));
+}
+
+// Predicate: a <= 126
+TEST_F(CompositeIntKeysTest, TestPrefixUpperBound) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", LE, 126);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK < (int8 a=127, int8 b=-128, int8 c=-128)", spec.ToString(schema_));
+}
+
+// Predicate: a >= 126
+TEST_F(CompositeIntKeysTest, TestPrefixLowerBound) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", GE, 126);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=126, int8 b=-128, int8 c=-128)", spec.ToString(schema_));
+}
+
+// Predicates: a >= 3 AND b >= 4 AND c >= 5
+TEST_F(CompositeIntKeysTest, TestConsecutiveLowerRangePredicates) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", GE, 3);
+  AddPredicate<int8_t>(&spec, "b", GE, 4);
+  AddPredicate<int8_t>(&spec, "c", GE, 5);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=3, int8 b=4, int8 c=5) AND `b` >= 4 AND `c` >= 5",
+            spec.ToString(schema_));
+}
+
+// Predicates: a <= 3 AND b <= 4 AND c <= 5
+TEST_F(CompositeIntKeysTest, TestConsecutiveUpperRangePredicates) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", LE, 3);
+  AddPredicate<int8_t>(&spec, "b", LE, 4);
+  AddPredicate<int8_t>(&spec, "c", LE, 5);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK < (int8 a=4, int8 b=-128, int8 c=-128) AND `b` < 5 AND `c` < 6",
+            spec.ToString(schema_));
+}
+
+// Predicates: a = 3 AND b >= 4 AND c >= 5
+TEST_F(CompositeIntKeysTest, TestEqualityAndConsecutiveLowerRangePredicates) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 3);
+  AddPredicate<int8_t>(&spec, "b", GE, 4);
+  AddPredicate<int8_t>(&spec, "c", GE, 5);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=3, int8 b=4, int8 c=5) AND "
+            "PK < (int8 a=4, int8 b=-128, int8 c=-128) AND "
+            "`c` >= 5", spec.ToString(schema_));
+}
+
+// Predicates: a = 3 AND 4 <= b <= 14 AND 15 <= c <= 15
+TEST_F(CompositeIntKeysTest, TestEqualityAndConsecutiveRangePredicates) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 3);
+  AddPredicate<int8_t>(&spec, "b", GE, 4);
+  AddPredicate<int8_t>(&spec, "b", LE, 14);
+  AddPredicate<int8_t>(&spec, "c", GE, 5);
+  AddPredicate<int8_t>(&spec, "c", LE, 15);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=3, int8 b=4, int8 c=5) AND "
+            "PK < (int8 a=3, int8 b=15, int8 c=-128) AND "
+            "`c` >= 5 AND `c` < 16", spec.ToString(schema_));
+}
+
+// Test a predicate on a non-prefix part of the key. Can't be pushed.
+//
+// Predicate: b == 64
+TEST_F(CompositeIntKeysTest, TestNonPrefix) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "b", EQ, 64);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  // Expect: nothing pushed (predicate is still on `b`, not PK)
+  EXPECT_EQ("`b` = 64", spec.ToString(schema_));
+}
+
+// Test what happens when an upper bound on a cell is equal to the maximum
+// value for the cell. In this case, the preceding cell is also at the maximum
+// value as well, so we eliminate the upper bound entirely.
+//
+// Predicate: a == 127 AND b >= 3 AND b <= 127
+TEST_F(CompositeIntKeysTest, TestRedundantUpperBound) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 127);
+  AddPredicate<int8_t>(&spec, "b", GE, 3);
+  AddPredicate<int8_t>(&spec, "b", LE, 127);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=127, int8 b=3, int8 c=-128)", spec.ToString(schema_));
+}
+
+// A similar test, but in this case we still have an equality prefix
+// that needs to be accounted for, so we can't eliminate the upper bound
+// entirely.
+//
+// Predicate: a == 1 AND b >= 3 AND b < 127
+TEST_F(CompositeIntKeysTest, TestRedundantUpperBound2) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 1);
+  AddPredicate<int8_t>(&spec, "b", GE, 3);
+  AddPredicate<int8_t>(&spec, "b", LE, 127);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=1, int8 b=3, int8 c=-128) AND "
+            "PK < (int8 a=2, int8 b=-128, int8 c=-128)",
+            spec.ToString(schema_));
+}
+
+// Test what happens with equality bounds on max value.
+//
+// Predicate: a == 127 AND b = 127
+TEST_F(CompositeIntKeysTest, TestRedundantUpperBound3) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 127);
+  AddPredicate<int8_t>(&spec, "b", EQ, 127);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=127, int8 b=127, int8 c=-128)",
+            spec.ToString(schema_));
+}
+
+// Test that, if so desired, pushed predicates are not erased.
+//
+// Predicate: a == 126
+TEST_F(CompositeIntKeysTest, TestNoErasePredicates) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 126);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, false);
+  EXPECT_EQ("PK >= (int8 a=126, int8 b=-128, int8 c=-128) AND "
+            "PK < (int8 a=127, int8 b=-128, int8 c=-128) AND "
+            "`a` = 126", spec.ToString(schema_));
+}
+
+// Test that, if pushed predicates are erased, that we don't
+// erase non-pushed predicates.
+// Because we have no predicate on column 'b', we can't push a
+// a range predicate that includes 'c'.
+//
+// Predicate: a == 126 AND c == 126
+TEST_F(CompositeIntKeysTest, TestNoErasePredicates2) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 126);
+  AddPredicate<int8_t>(&spec, "c", EQ, 126);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  // The predicate on column A should be pushed while "c" remains.
+  EXPECT_EQ("PK >= (int8 a=126, int8 b=-128, int8 c=-128) AND "
+            "PK < (int8 a=127, int8 b=-128, int8 c=-128) AND "
+            "`c` = 126", spec.ToString(schema_));
+}
+
+// Test that predicates added out of key order are OK.
+//
+// Predicate: b == 126 AND a == 126
+TEST_F(CompositeIntKeysTest, TestPredicateOrderDoesntMatter) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "b", EQ, 126);
+  AddPredicate<int8_t>(&spec, "a", EQ, 126);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=126, int8 b=126, int8 c=-128) AND "
+            "PK < (int8 a=126, int8 b=127, int8 c=-128)",
+            spec.ToString(schema_));
+}
+
+// Tests that a scan spec without primary key bounds will not have predicates
+// after optimization.
+TEST_F(CompositeIntKeysTest, TestLiftPrimaryKeyBounds_NoBounds) {
+  ScanSpec spec;
+  spec.OptimizeScan(schema_, &arena_, &pool_, false);
+  ASSERT_EQ(0, spec.predicates().size());
+}
+
+// Test that implicit constraints specified in the lower primary key bound are
+// lifted into the predicates.
+TEST_F(CompositeIntKeysTest, TestLiftPrimaryKeyBounds_LowerBound) {
+  { // key >= (10, 11, 12)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    SetLowerBound(&spec, lower_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` >= 10", FindOrDie(spec.predicates(), "a").ToString());
+  }
+  { // key >= (10, 11, min)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", INT8_MIN));
+
+    SetLowerBound(&spec, lower_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` >= 10", FindOrDie(spec.predicates(), "a").ToString());
+  }
+  { // key >= (10, min, min)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", INT8_MIN));
+    CHECK_OK(lower_bound.SetInt8("c", INT8_MIN));
+
+    SetLowerBound(&spec, lower_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` >= 10", FindOrDie(spec.predicates(), "a").ToString());
+  }
+}
+
+// Test that implicit constraints specified in the lower primary key bound are
+// lifted into the predicates.
+TEST_F(CompositeIntKeysTest, TestLiftPrimaryKeyBounds_UpperBound) {
+  {
+    // key < (10, 11, 12)
+    ScanSpec spec;
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 11));
+    CHECK_OK(upper_bound.SetInt8("c", 12));
+
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` < 11", FindOrDie(spec.predicates(), "a").ToString());
+  }
+  {
+    // key < (10, 11, min)
+    ScanSpec spec;
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 11));
+    CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` < 11", FindOrDie(spec.predicates(), "a").ToString());
+  }
+  {
+    // key < (10, min, min)
+    ScanSpec spec;
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", INT8_MIN));
+    CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` < 10", FindOrDie(spec.predicates(), "a").ToString());
+  }
+}
+
+// Test that implicit constraints specified in the primary key bounds are lifted
+// into the predicates.
+TEST_F(CompositeIntKeysTest, TestLiftPrimaryKeyBounds_BothBounds) {
+  {
+    // key >= (10, 11, 12)
+    //      < (10, 11, 13)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 11));
+    CHECK_OK(upper_bound.SetInt8("c", 13));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(3, spec.predicates().size());
+    ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+    ASSERT_EQ("`b` = 11", FindOrDie(spec.predicates(), "b").ToString());
+    ASSERT_EQ("`c` = 12", FindOrDie(spec.predicates(), "c").ToString());
+  }
+  {
+    // key >= (10, 11, 12)
+    //      < (10, 11, 14)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 11));
+    CHECK_OK(upper_bound.SetInt8("c", 14));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(3, spec.predicates().size());
+    ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+    ASSERT_EQ("`b` = 11", FindOrDie(spec.predicates(), "b").ToString());
+    ASSERT_EQ("`c` >= 12 AND `c` < 14", FindOrDie(spec.predicates(), "c").ToString());
+  }
+  {
+    // key >= (10, 11, 12)
+    //      < (10, 12, min)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 12));
+    CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(3, spec.predicates().size());
+    ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+    ASSERT_EQ("`b` = 11", FindOrDie(spec.predicates(), "b").ToString());
+    ASSERT_EQ("`c` >= 12", FindOrDie(spec.predicates(), "c").ToString());
+  }
+  {
+    // key >= (10, 11, 12)
+    //      < (10, 12, 13)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 10));
+    CHECK_OK(upper_bound.SetInt8("b", 12));
+    CHECK_OK(upper_bound.SetInt8("c", 13));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(2, spec.predicates().size());
+    ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+    ASSERT_EQ("`b` >= 11 AND `b` < 13", FindOrDie(spec.predicates(), "b").ToString());
+  }
+  {
+    // key >= (10, 11, 12)
+    //      < (11, min, min)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", 11));
+    CHECK_OK(lower_bound.SetInt8("c", 12));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 11));
+    CHECK_OK(upper_bound.SetInt8("b", INT8_MIN));
+    CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(2, spec.predicates().size());
+    ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+    ASSERT_EQ("`b` >= 11", FindOrDie(spec.predicates(), "b").ToString());
+  }
+  {
+    // key >= (10, min, min)
+    //      < (12, min, min)
+    ScanSpec spec;
+
+    KuduPartialRow lower_bound(&schema_);
+    CHECK_OK(lower_bound.SetInt8("a", 10));
+    CHECK_OK(lower_bound.SetInt8("b", INT8_MIN));
+    CHECK_OK(lower_bound.SetInt8("c", INT8_MIN));
+
+    KuduPartialRow upper_bound(&schema_);
+    CHECK_OK(upper_bound.SetInt8("a", 12));
+    CHECK_OK(upper_bound.SetInt8("b", INT8_MIN));
+    CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+    SetLowerBound(&spec, lower_bound);
+    SetExclusiveUpperBound(&spec, upper_bound);
+
+    spec.OptimizeScan(schema_, &arena_, &pool_, false);
+    ASSERT_EQ(1, spec.predicates().size());
+    ASSERT_EQ("`a` >= 10 AND `a` < 12", FindOrDie(spec.predicates(), "a").ToString());
+  }
+}
+
+// Test that implicit constraints specified in the primary key upper/lower
+// bounds are merged into the set of predicates.
+TEST_F(CompositeIntKeysTest, TestLiftPrimaryKeyBounds_WithPredicates) {
+  // b >= 15
+  // c >= 3
+  // c <= 100
+  // key >= (10, min, min)
+  //      < (10,  90, min)
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "b", GE, 15);
+  AddPredicate<int8_t>(&spec, "c", GE, 3);
+  AddPredicate<int8_t>(&spec, "c", LE, 100);
+
+  KuduPartialRow lower_bound(&schema_);
+  CHECK_OK(lower_bound.SetInt8("a", 10));
+  CHECK_OK(lower_bound.SetInt8("b", INT8_MIN));
+  CHECK_OK(lower_bound.SetInt8("c", INT8_MIN));
+
+  KuduPartialRow upper_bound(&schema_);
+  CHECK_OK(upper_bound.SetInt8("a", 10));
+  CHECK_OK(upper_bound.SetInt8("b", 90));
+  CHECK_OK(upper_bound.SetInt8("c", INT8_MIN));
+
+  SetLowerBound(&spec, lower_bound);
+  SetExclusiveUpperBound(&spec, upper_bound);
+
+  spec.OptimizeScan(schema_, &arena_, &pool_, false);
+  ASSERT_EQ(3, spec.predicates().size());
+  ASSERT_EQ("`a` = 10", FindOrDie(spec.predicates(), "a").ToString());
+  ASSERT_EQ("`b` >= 15 AND `b` < 90", FindOrDie(spec.predicates(), "b").ToString());
+  ASSERT_EQ("`c` >= 3 AND `c` < 101", FindOrDie(spec.predicates(), "c").ToString());
+}
+
+// Tests for String parts in composite keys
+//------------------------------------------------------------
+class CompositeIntStringKeysTest : public TestScanSpec {
+ public:
+  CompositeIntStringKeysTest() :
+    TestScanSpec(
+        Schema({ ColumnSchema("a", INT8),
+                 ColumnSchema("b", STRING),
+                 ColumnSchema("c", STRING) },
+               3)) {
+  }
+};
+
+// Predicate: a == 64
+TEST_F(CompositeIntStringKeysTest, TestPrefixEquality) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 64);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  // Expect: key >= (64, "", "") AND key < (65, "", "")
+  EXPECT_EQ("PK >= (int8 a=64, string b=, string c=) AND "
+            "PK < (int8 a=65, string b=, string c=)",
+            spec.ToString(schema_));
+}
+
+// Predicate: a == 64 AND b = "abc"
+TEST_F(CompositeIntStringKeysTest, TestPrefixEqualityWithString) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 64);
+  AddPredicate<Slice>(&spec, "b", EQ, Slice("abc"));
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=64, string b=abc, string c=) AND "
+            "PK < (int8 a=64, string b=abc\\000, string c=)",
+            spec.ToString(schema_));
+}
+
+// Tests for non-composite int key
+//------------------------------------------------------------
+class SingleIntKeyTest : public TestScanSpec {
+ public:
+  SingleIntKeyTest() :
+    TestScanSpec(
+        Schema({ ColumnSchema("a", INT8) }, 1)) {
+    }
+};
+
+TEST_F(SingleIntKeyTest, TestEquality) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 64);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=64) AND PK < (int8 a=65)", spec.ToString(schema_));
+}
+
+TEST_F(SingleIntKeyTest, TestRedundantUpperBound) {
+  ScanSpec spec;
+  AddPredicate<int8_t>(&spec, "a", EQ, 127);
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("PK >= (int8 a=127)",
+            spec.ToString(schema_));
+}
+
+TEST_F(SingleIntKeyTest, TestNoPredicates) {
+  ScanSpec spec;
+  SCOPED_TRACE(spec.ToString(schema_));
+  spec.OptimizeScan(schema_, &arena_, &pool_, true);
+  EXPECT_EQ("", spec.ToString(schema_));
+}
+
+} // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/scan_spec.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/scan_spec.cc b/src/kudu/common/scan_spec.cc
index 9419508..d8469e0 100644
--- a/src/kudu/common/scan_spec.cc
+++ b/src/kudu/common/scan_spec.cc
@@ -17,19 +17,54 @@
 
 #include "kudu/common/scan_spec.h"
 
+#include <algorithm>
 #include <string>
+#include <utility>
 #include <vector>
 
+#include "kudu/common/key_util.h"
+#include "kudu/common/row.h"
+#include "kudu/gutil/map-util.h"
 #include "kudu/gutil/strings/join.h"
-#include "kudu/gutil/strings/escaping.h"
+#include "kudu/util/auto_release_pool.h"
 
-using std::vector;
+using std::any_of;
+using std::max;
+using std::move;
 using std::string;
+using std::vector;
 
 namespace kudu {
 
-void ScanSpec::AddPredicate(const ColumnRangePredicate &pred) {
-  predicates_.push_back(pred);
+void ScanSpec::AddPredicate(ColumnPredicate pred) {
+  ColumnPredicate* predicate = FindOrNull(predicates_, pred.column().name());
+  if (predicate != nullptr) {
+    predicate->Merge(pred);
+  } else {
+    string column_name = pred.column().name();
+    predicates_.emplace(move(column_name), move(pred));
+  }
+}
+
+void ScanSpec::RemovePredicate(const string& column_name) {
+  predicates_.erase(column_name);
+}
+
+void ScanSpec::RemovePredicates() {
+  predicates_.clear();
+}
+
+bool ScanSpec::CanShortCircuit() const {
+  if (lower_bound_key_ &&
+      exclusive_upper_bound_key_ &&
+      lower_bound_key_->encoded_key().compare(exclusive_upper_bound_key_->encoded_key()) >= 0) {
+    return false;
+  }
+
+  return any_of(predicates_.begin(), predicates_.end(),
+                [] (const pair<string, ColumnPredicate>& predicate) {
+                  return predicate.second.predicate_type() == PredicateType::None;
+                });
 }
 
 void ScanSpec::SetLowerBoundKey(const EncodedKey* key) {
@@ -58,34 +93,157 @@ void ScanSpec::SetExclusiveUpperBoundPartitionKey(const Slice& partitionKey) {
   }
 }
 
-string ScanSpec::ToString() const {
-  return ToStringWithOptionalSchema(nullptr);
+string ScanSpec::ToString(const Schema& schema) const {
+  vector<string> preds;
+
+  if (lower_bound_key_ || exclusive_upper_bound_key_) {
+    preds.push_back(EncodedKey::RangeToStringWithSchema(lower_bound_key_,
+                                                        exclusive_upper_bound_key_,
+                                                        schema));
+  }
+
+  // List predicates in stable order.
+  for (int idx = 0; idx < schema.num_columns(); idx++) {
+    const ColumnPredicate* predicate = FindOrNull(predicates_, schema.column(idx).name());
+    if (predicate != nullptr) {
+      preds.push_back(predicate->ToString());
+    }
+  }
+
+  return JoinStrings(preds, " AND ");
 }
 
-string ScanSpec::ToStringWithSchema(const Schema& s) const {
-  return ToStringWithOptionalSchema(&s);
+void ScanSpec::OptimizeScan(const Schema& schema,
+                            Arena* arena,
+                            AutoReleasePool* pool,
+                            bool remove_pushed_predicates) {
+  // Don't bother if we can already short circuit the scan. This also lets us
+  // rely on lower_bound_key_ < exclusive_upper_bound_key_ and no None
+  // predicates in the optimization step.
+  if (!CanShortCircuit()) {
+    LiftPrimaryKeyBounds(schema, arena);
+    PushPredicatesIntoPrimaryKeyBounds(schema, arena, pool, remove_pushed_predicates);
+  }
 }
 
-string ScanSpec::ToStringWithOptionalSchema(const Schema* s) const {
-  vector<string> preds;
+void ScanSpec::PushPredicatesIntoPrimaryKeyBounds(const Schema& schema,
+                                                  Arena* arena,
+                                                  AutoReleasePool* pool,
+                                                  bool remove_pushed_predicates) {
+  // Step 1: load key column predicate values into a pair of rows.
+  uint8_t* lower_buf = static_cast<uint8_t*>(
+      CHECK_NOTNULL(arena->AllocateBytes(schema.key_byte_size())));
+  uint8_t* upper_buf = static_cast<uint8_t*>(
+      CHECK_NOTNULL(arena->AllocateBytes(schema.key_byte_size())));
+  ContiguousRow lower_key(&schema, lower_buf);
+  ContiguousRow upper_key(&schema, upper_buf);
 
-  if (lower_bound_key_ || exclusive_upper_bound_key_) {
-    if (s) {
-      preds.push_back(EncodedKey::RangeToStringWithSchema(
-                          lower_bound_key_,
-                          exclusive_upper_bound_key_,
-                          *s));
-    } else {
-      preds.push_back(EncodedKey::RangeToString(
-                          lower_bound_key_,
-                          exclusive_upper_bound_key_));
+  int lower_bound_predicates_pushed = key_util::PushLowerBoundPrimaryKeyPredicates(
+      predicates_, &lower_key, arena);
+  int upper_bound_predicates_pushed = key_util::PushUpperBoundPrimaryKeyPredicates(
+      predicates_, &upper_key, arena);
+
+  // Step 2: Erase pushed predicates
+  // Predicates through the first range predicate may be erased.
+  if (remove_pushed_predicates) {
+    for (int32_t col_idx = 0;
+         col_idx < max(lower_bound_predicates_pushed, upper_bound_predicates_pushed);
+         col_idx++) {
+      const string& column = schema.column(col_idx).name();
+      PredicateType type = FindOrDie(predicates_, schema.column(col_idx).name()).predicate_type();
+      if (type == PredicateType::Equality) {
+        RemovePredicate(column);
+      } else if (type == PredicateType::Range) {
+        RemovePredicate(column);
+        break;
+      } else {
+        LOG(FATAL) << "Can not remove unknown predicate type";
+      }
     }
   }
 
-  for (const ColumnRangePredicate& pred : predicates_) {
-    preds.push_back(pred.ToString());
+  // Step 3: set the new bounds
+  if (lower_bound_predicates_pushed > 0) {
+    EncodedKey* lower = EncodedKey::FromContiguousRow(ConstContiguousRow(lower_key)).release();
+    pool->Add(lower);
+    SetLowerBoundKey(lower);
+  }
+  if (upper_bound_predicates_pushed > 0) {
+    EncodedKey* upper = EncodedKey::FromContiguousRow(ConstContiguousRow(upper_key)).release();
+    pool->Add(upper);
+    SetExclusiveUpperBoundKey(upper);
+  }
+}
+
+void ScanSpec::LiftPrimaryKeyBounds(const Schema& schema, Arena* arena) {
+  if (lower_bound_key_ == nullptr && exclusive_upper_bound_key_ == nullptr) { return; }
+  int32_t num_key_columns = schema.num_key_columns();
+  for (int32_t col_idx = 0; col_idx < num_key_columns; col_idx++) {
+    const ColumnSchema& column = schema.column(col_idx);
+    const void* lower = lower_bound_key_ == nullptr
+      ? nullptr : lower_bound_key_->raw_keys()[col_idx];
+    const void* upper = exclusive_upper_bound_key_ == nullptr
+      ? nullptr : exclusive_upper_bound_key_->raw_keys()[col_idx];
+
+    if (lower != nullptr && upper != nullptr && column.Compare(lower, upper) == 0) {
+      // We are still in the equality prefix of the bounds
+      AddPredicate(ColumnPredicate::Equality(column, lower));
+    } else {
+
+      // Determine if the upper bound column value is exclusive or inclusive.
+      // The value is exclusive if all of the remaining column values are
+      // equal to the minimum value, otherwise it's inclusive.
+      //
+      // examples, with key columns: (int8 a, int8 b):
+      //
+      // key >= (1, 2)
+      //      < (3, min)
+      // should result in predicate 1 <= a < 3
+      //
+      // key >= (1, 2)
+      //      < (3, 5)
+      // should result in predicate 1 <= a < 4
+      bool is_exclusive = true;
+      if (upper != nullptr) {
+        uint8_t min[kLargestTypeSize];
+        for (int32_t suffix_idx = col_idx + 1;
+            is_exclusive && suffix_idx < num_key_columns;
+            suffix_idx++) {
+          const ColumnSchema& suffix_column = schema.column(suffix_idx);
+          suffix_column.type_info()->CopyMinValue(min);
+          const void* suffix_val = exclusive_upper_bound_key_->raw_keys()[suffix_idx];
+          is_exclusive &= suffix_column.type_info()->Compare(suffix_val, min) == 0;
+        }
+      }
+
+      if (is_exclusive) {
+        ColumnPredicate predicate = ColumnPredicate::Range(column, lower, upper);
+        if (predicate.predicate_type() == PredicateType::Equality &&
+            col_idx + 1 < num_key_columns) {
+          // If this turns out to be an equality predicate, then we can add one
+          // more lower bound predicate from the next component (if it exists).
+          //
+          // example, with key columns (int8 a, int8 b):
+          //
+          // key >= (2, 3)
+          // key  < (3, min)
+          //
+          // should result in the predicates:
+          //
+          // a = 2
+          // b >= 3
+          AddPredicate(ColumnPredicate::Range(schema.column(col_idx + 1),
+                                              lower_bound_key_->raw_keys()[col_idx + 1],
+                                              nullptr));
+        }
+        AddPredicate(move(predicate));
+      } else {
+        auto pred = ColumnPredicate::InclusiveRange(column, lower, upper, arena);
+        if (pred) AddPredicate(*pred);
+      }
+      break;
+    }
   }
-  return JoinStrings(preds, "\n");
 }
 
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/common/scan_spec.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/scan_spec.h b/src/kudu/common/scan_spec.h
index 415cc28..4951b0b 100644
--- a/src/kudu/common/scan_spec.h
+++ b/src/kudu/common/scan_spec.h
@@ -18,28 +18,53 @@
 #define KUDU_COMMON_SCAN_SPEC_H
 
 #include <string>
-#include <vector>
+#include <unordered_map>
 
-#include "kudu/common/scan_predicate.h"
+#include "kudu/common/schema.h"
+#include "kudu/common/column_predicate.h"
 #include "kudu/common/encoded_key.h"
 
 namespace kudu {
 
-using std::vector;
+class AutoReleasePool;
+class Arena;
 
 class ScanSpec {
  public:
   ScanSpec()
-    : lower_bound_key_(NULL),
-      exclusive_upper_bound_key_(NULL),
+    : predicates_(),
+      lower_bound_key_(nullptr),
+      exclusive_upper_bound_key_(nullptr),
       lower_bound_partition_key_(),
       exclusive_upper_bound_partition_key_(),
       cache_blocks_(true) {
   }
 
-  typedef vector<ColumnRangePredicate> PredicateList;
+  // Add a predicate on the column.
+  //
+  // The new predicate is merged into the existing predicate for the column.
+  void AddPredicate(ColumnPredicate pred);
+
+  // Remove the predicate for the column.
+  void RemovePredicate(const std::string& column_name);
+
+  // Removes all column predicates.
+  void RemovePredicates();
 
-  void AddPredicate(const ColumnRangePredicate &pred);
+  // Returns true if the result set is known to be empty.
+  bool CanShortCircuit() const;
+
+  // Optimizes the scan by unifying the lower and upper bound constraints and
+  // the column predicates.
+  //
+  // If remove_pushed_predicates is true, then column predicates that are pushed
+  // into the upper or lower primary key bounds are removed.
+  //
+  // Idempotent.
+  void OptimizeScan(const Schema& schema,
+                    Arena* arena,
+                    AutoReleasePool* pool,
+                    bool remove_pushed_predicates);
 
   // Set the lower bound (inclusive) primary key for the scan.
   // Does not take ownership of 'key', which must remain valid.
@@ -65,22 +90,15 @@ class ScanSpec {
   // Only used in the client.
   void SetExclusiveUpperBoundPartitionKey(const Slice& slice);
 
-  const vector<ColumnRangePredicate> &predicates() const {
+  // Returns the scan predicates.
+  const std::unordered_map<std::string, ColumnPredicate>& predicates() const {
     return predicates_;
   }
 
-  // Return a pointer to the list of predicates in this scan spec.
-  //
-  // Callers may use this during predicate pushdown to remove predicates
-  // from their caller if they're able to apply them lower down the
-  // iterator tree.
-  vector<ColumnRangePredicate> *mutable_predicates() {
-    return &predicates_;
-  }
-
   const EncodedKey* lower_bound_key() const {
     return lower_bound_key_;
   }
+
   const EncodedKey* exclusive_upper_bound_key() const {
     return exclusive_upper_bound_key_;
   }
@@ -100,14 +118,31 @@ class ScanSpec {
     cache_blocks_ = cache_blocks;
   }
 
-  std::string ToString() const;
-  std::string ToStringWithSchema(const Schema& s) const;
+  std::string ToString(const Schema& s) const;
 
  private:
-  // Helper for the ToString*() methods. 's' may be NULL.
-  std::string ToStringWithOptionalSchema(const Schema* s) const;
 
-  vector<ColumnRangePredicate> predicates_;
+  // Lift implicit predicates specified as part of the lower and upper bound
+  // primary key constraints into the simplified predicate bounds.
+  //
+  // When the lower and exclusive upper bound primary keys have a prefix of
+  // equal components, the components can be lifted into an equality predicate
+  // over their associated column. Optionally, a single (pair) of range
+  // predicates can be lifted from the key component following the prefix of
+  // equal components.
+  void LiftPrimaryKeyBounds(const Schema& schema, Arena* arena);
+
+  // Encode the column predicates into lower and upper primary key bounds, and
+  // replace the existing bounds if the new bounds are more constrained.
+  //
+  // If remove_pushed_predicates is true, then the predicates in the primary key
+  // bound will be removed if the bound is replaced.
+  void PushPredicatesIntoPrimaryKeyBounds(const Schema& schema,
+                                          Arena* arena,
+                                          AutoReleasePool* pool,
+                                          bool remove_pushed_predicates);
+
+  std::unordered_map<std::string, ColumnPredicate> predicates_;
   const EncodedKey* lower_bound_key_;
   const EncodedKey* exclusive_upper_bound_key_;
   std::string lower_bound_partition_key_;

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/master/sys_catalog.cc
----------------------------------------------------------------------
diff --git a/src/kudu/master/sys_catalog.cc b/src/kudu/master/sys_catalog.cc
index f25e66a..bd8f7fd 100644
--- a/src/kudu/master/sys_catalog.cc
+++ b/src/kudu/master/sys_catalog.cc
@@ -23,6 +23,7 @@
 #include "kudu/common/partial_row.h"
 #include "kudu/common/partition.h"
 #include "kudu/common/row_operations.h"
+#include "kudu/common/scan_spec.h"
 #include "kudu/common/schema.h"
 #include "kudu/common/wire_protocol.h"
 #include "kudu/consensus/consensus_meta.h"
@@ -35,8 +36,8 @@
 #include "kudu/master/master.h"
 #include "kudu/master/master.pb.h"
 #include "kudu/rpc/rpc_context.h"
-#include "kudu/tablet/tablet_bootstrap.h"
 #include "kudu/tablet/tablet.h"
+#include "kudu/tablet/tablet_bootstrap.h"
 #include "kudu/tablet/transactions/write_transaction.h"
 #include "kudu/tserver/tserver.pb.h"
 #include "kudu/util/debug/trace_event.h"
@@ -435,8 +436,7 @@ Status SysCatalogTable::VisitTables(TableVisitor* visitor) {
   const int type_col_idx = schema_.find_column(kSysCatalogTableColType);
   CHECK(type_col_idx != Schema::kColumnNotFound);
 
-  ColumnRangePredicate pred_tables(schema_.column(type_col_idx),
-                                   &tables_entry, &tables_entry);
+  auto pred_tables = ColumnPredicate::Equality(schema_.column(type_col_idx), &tables_entry);
   ScanSpec spec;
   spec.AddPredicate(pred_tables);
 
@@ -583,8 +583,7 @@ Status SysCatalogTable::VisitTablets(TabletVisitor* visitor) {
   const int type_col_idx = schema_.find_column(kSysCatalogTableColType);
   CHECK(type_col_idx != Schema::kColumnNotFound);
 
-  ColumnRangePredicate pred_tablets(schema_.column(type_col_idx),
-                                   &tablets_entry, &tablets_entry);
+  auto pred_tablets = ColumnPredicate::Equality(schema_.column(type_col_idx), &tablets_entry);
   ScanSpec spec;
   spec.AddPredicate(pred_tablets);
 

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/cfile_set-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/cfile_set-test.cc b/src/kudu/tablet/cfile_set-test.cc
index fc62d30..7ecba71 100644
--- a/src/kudu/tablet/cfile_set-test.cc
+++ b/src/kudu/tablet/cfile_set-test.cc
@@ -80,10 +80,9 @@ class TestCFileSet : public KuduRowSetTest {
 
     // Create a scan with a range predicate on the key column.
     ScanSpec spec;
-    ColumnRangePredicate pred1(
-      schema_.column(0),
-      lower != kNoBound ? &lower : nullptr,
-      upper != kNoBound ? &upper : nullptr);
+    auto pred1 = ColumnPredicate::Range(schema_.column(0),
+                                        lower != kNoBound ? &lower : nullptr,
+                                        upper != kNoBound ? &upper : nullptr);
     spec.AddPredicate(pred1);
     ASSERT_OK(iter->Init(&spec));
 
@@ -96,7 +95,7 @@ class TestCFileSet : public KuduRowSetTest {
         if (block.selection_vector()->IsRowSelected(i)) {
           RowBlockRow row = block.row(i);
           if ((lower != kNoBound && *schema_.ExtractColumnFromRow<UINT32>(row, 0) < lower) ||
-              (upper != kNoBound && *schema_.ExtractColumnFromRow<UINT32>(row, 0) > upper)) {
+              (upper != kNoBound && *schema_.ExtractColumnFromRow<UINT32>(row, 0) >= upper)) {
             FAIL() << "Row " << schema_.DebugRow(row) << " should not have "
                    << "passed predicate " << pred1.ToString();
           }
@@ -245,23 +244,22 @@ TEST_F(TestCFileSet, TestRangeScan) {
   gscoped_ptr<RowwiseIterator> iter(new MaterializingIterator(cfile_iter));
   Schema key_schema = schema_.CreateKeyProjection();
   Arena arena(1024, 256 * 1024);
-  RangePredicateEncoder encoder(&key_schema, &arena);
+  AutoReleasePool pool;
 
   // Create a scan with a range predicate on the key column.
   ScanSpec spec;
   uint32_t lower = 2000;
-  uint32_t upper = 2009;
-  ColumnRangePredicate pred1(schema_.column(0), &lower, &upper);
+  uint32_t upper = 2010;
+  auto pred1 = ColumnPredicate::Range(schema_.column(0), &lower, &upper);
   spec.AddPredicate(pred1);
-  encoder.EncodeRangePredicates(&spec, true);
+  spec.OptimizeScan(schema_, &arena, &pool, true);
   ASSERT_OK(iter->Init(&spec));
 
   // Check that the bounds got pushed as index bounds.
   // Since the key column is the rowidx * 2, we need to divide the integer bounds
   // back down.
   EXPECT_EQ(lower / 2, cfile_iter->lower_bound_idx_);
-  // + 1 because the upper bound is exclusive
-  EXPECT_EQ(upper / 2 + 1, cfile_iter->upper_bound_idx_);
+  EXPECT_EQ(upper / 2, cfile_iter->upper_bound_idx_);
 
   // Read all the results.
   vector<string> results;

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/composite-pushdown-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/composite-pushdown-test.cc b/src/kudu/tablet/composite-pushdown-test.cc
index 47d4d31..6d5a40a 100644
--- a/src/kudu/tablet/composite-pushdown-test.cc
+++ b/src/kudu/tablet/composite-pushdown-test.cc
@@ -112,10 +112,10 @@ TEST_F(CompositePushdownTest, TestPushDownExactEquality) {
   int8_t month = 9;
   int8_t day = 7;
   Slice host(kTestHostnames[0]);
-  ColumnRangePredicate pred_year(schema_.column(0), &year, &year);
-  ColumnRangePredicate pred_month(schema_.column(1), &month, &month);
-  ColumnRangePredicate pred_day(schema_.column(2), &day, &day);
-  ColumnRangePredicate pred_host(schema_.column(3), &host, &host);
+  auto pred_year = ColumnPredicate::Equality(schema_.column(0), &year);
+  auto pred_month = ColumnPredicate::Equality(schema_.column(1), &month);
+  auto pred_day = ColumnPredicate::Equality(schema_.column(2), &day);
+  auto pred_host = ColumnPredicate::Equality(schema_.column(3), &host);
   spec.AddPredicate(pred_year);
   spec.AddPredicate(pred_month);
   spec.AddPredicate(pred_day);
@@ -133,19 +133,20 @@ TEST_F(CompositePushdownTest, TestPushDownExactEquality) {
 // Test for "host <= 'foo'" which should reject 'foobaz'.
 // Regression test for a bug in an earlier implementation of predicate pushdown.
 TEST_F(CompositePushdownTest, TestPushDownStringInequality) {
+  Arena arena(256, 1024);
   ScanSpec spec;
   int16_t year = 2001;
   int8_t month = 9;
   int8_t day = 7;
   Slice host("foo");
-  ColumnRangePredicate pred_year(schema_.column(0), &year, &year);
-  ColumnRangePredicate pred_month(schema_.column(1), &month, &month);
-  ColumnRangePredicate pred_day(schema_.column(2), &day, &day);
-  ColumnRangePredicate pred_host(schema_.column(3), nullptr, &host);
+  auto pred_year = ColumnPredicate::Equality(schema_.column(0), &year);
+  auto pred_month = ColumnPredicate::Equality(schema_.column(1), &month);
+  auto pred_day = ColumnPredicate::Equality(schema_.column(2), &day);
+  auto pred_host = ColumnPredicate::InclusiveRange(schema_.column(3), nullptr, &host, &arena);
   spec.AddPredicate(pred_year);
   spec.AddPredicate(pred_month);
   spec.AddPredicate(pred_day);
-  spec.AddPredicate(pred_host);
+  spec.AddPredicate(*pred_host);
   vector<string> results;
 
   ASSERT_NO_FATAL_FAILURE(ScanTablet(&spec, &results, "Exact match using compound key"));
@@ -164,9 +165,9 @@ TEST_F(CompositePushdownTest, TestPushDownDateEquality) {
   int16_t year = 2001;
   int8_t month = 9;
   int8_t day = 7;
-  ColumnRangePredicate pred_year(schema_.column(0), &year, &year);
-  ColumnRangePredicate pred_month(schema_.column(1), &month, &month);
-  ColumnRangePredicate pred_day(schema_.column(2), &day, &day);
+  auto pred_year = ColumnPredicate::Equality(schema_.column(0), &year);
+  auto pred_month = ColumnPredicate::Equality(schema_.column(1), &month);
+  auto pred_day = ColumnPredicate::Equality(schema_.column(2), &day);
   spec.AddPredicate(pred_year);
   spec.AddPredicate(pred_month);
   spec.AddPredicate(pred_day);
@@ -188,8 +189,8 @@ TEST_F(CompositePushdownTest, TestPushDownDateEquality) {
 TEST_F(CompositePushdownTest, TestPushDownPrefixEquality) {
   int16_t year = 2001;
   int8_t month = 9;
-  ColumnRangePredicate pred_year(schema_.column(0), &year, &year);
-  ColumnRangePredicate pred_month(schema_.column(1), &month, &month);
+  ColumnPredicate pred_year = ColumnPredicate::Equality(schema_.column(0), &year);
+  ColumnPredicate pred_month = ColumnPredicate::Equality(schema_.column(1), &month);
 
   {
     ScanSpec spec;
@@ -229,26 +230,26 @@ TEST_F(CompositePushdownTest, TestPushDownPrefixEquality) {
 TEST_F(CompositePushdownTest, TestPushDownPrefixEqualitySuffixInequality) {
   int16_t year = 2001;
   int8_t month_l = 9;
-  int8_t month_u = 11;
+  int8_t month_u = 12;
   int8_t day_l = 1;
-  int8_t day_u = 15;
+  int8_t day_u = 16;
 
-  ColumnRangePredicate pred_year(schema_.column(0), &year, &year);
+  auto pred_year = ColumnPredicate::Equality(schema_.column(0), &year);
 
-  ColumnRangePredicate pred_month_eq(schema_.column(1), &month_l, &month_l);
-  ColumnRangePredicate pred_month_ge_le(schema_.column(1), &month_l, &month_u);
-  ColumnRangePredicate pred_month_le(schema_.column(1), nullptr, &month_l);
+  auto pred_month_eq = ColumnPredicate::Equality(schema_.column(1), &month_l);
+  auto pred_month_ge_lt = ColumnPredicate::Range(schema_.column(1), &month_l, &month_u);
+  auto pred_month_lt = ColumnPredicate::Range(schema_.column(1), nullptr, &month_l);
 
-  ColumnRangePredicate pred_day_ge_le(schema_.column(2), &day_l, &day_u);
-  ColumnRangePredicate pred_day_ge(schema_.column(2), &day_l, nullptr);
-  ColumnRangePredicate pred_day_le(schema_.column(2), nullptr, &day_u);
+  auto pred_day_ge_lt = ColumnPredicate::Range(schema_.column(2), &day_l, &day_u);
+  auto pred_day_ge = ColumnPredicate::Range(schema_.column(2), &day_l, nullptr);
+  auto pred_day_lt = ColumnPredicate::Range(schema_.column(2), nullptr, &day_u);
 
   {
-    // year=2001, month=9, day >= 1 && day <= 15
+    // year=2001, month=9, day >= 1 && day < 16
     ScanSpec spec;
     spec.AddPredicate(pred_year);
     spec.AddPredicate(pred_month_eq);
-    spec.AddPredicate(pred_day_ge_le);
+    spec.AddPredicate(pred_day_ge_lt);
     vector<string> results;
     ASSERT_NO_FATAL_FAILURE(ScanTablet(&spec, &results, "Prefix equality, suffix inequality"));
     ASSERT_EQ(15 * 3, results.size());
@@ -278,11 +279,11 @@ TEST_F(CompositePushdownTest, TestPushDownPrefixEqualitySuffixInequality) {
   }
 
   {
-    // year=2001, month=9, day <= 15
+    // year=2001, month=9, day < 16
     ScanSpec spec;
     spec.AddPredicate(pred_year);
     spec.AddPredicate(pred_month_eq);
-    spec.AddPredicate(pred_day_le);
+    spec.AddPredicate(pred_day_lt);
     vector<string> results;
     ASSERT_NO_FATAL_FAILURE(ScanTablet(&spec, &results, "Prefix equality, suffix inequality"));
     ASSERT_EQ(15 * 3, results.size());
@@ -295,10 +296,10 @@ TEST_F(CompositePushdownTest, TestPushDownPrefixEqualitySuffixInequality) {
   }
 
   {
-    // year=2001, month >= 9 && month <= 11
+    // year=2001, month >= 9 && month < 12
     ScanSpec spec;
     spec.AddPredicate(pred_year);
-    spec.AddPredicate(pred_month_ge_le);
+    spec.AddPredicate(pred_month_ge_lt);
     vector<string> results;
     ASSERT_NO_FATAL_FAILURE(ScanTablet(&spec, &results, "Prefix equality, suffix inequality"));
     ASSERT_EQ(3 * 28 * 3, results.size());
@@ -311,18 +312,18 @@ TEST_F(CompositePushdownTest, TestPushDownPrefixEqualitySuffixInequality) {
   }
 
   {
-    // year=2001, month <= 9
+    // year=2001, month < 9
     ScanSpec spec;
     spec.AddPredicate(pred_year);
-    spec.AddPredicate(pred_month_le);
+    spec.AddPredicate(pred_month_lt);
     vector<string> results;
     ASSERT_NO_FATAL_FAILURE(ScanTablet(&spec, &results, "Prefix equality, suffix inequality"));
-    ASSERT_EQ(9 * 28 * 3, results.size());
+    ASSERT_EQ(8 * 28 * 3, results.size());
     EXPECT_EQ("(int16 year=2001, int8 month=1, int8 day=1, "
               "string hostname=baz, string data=2001/01/01-baz)",
               results.front());
-    EXPECT_EQ("(int16 year=2001, int8 month=9, int8 day=28, "
-              "string hostname=foobar, string data=2001/09/28-foobar)",
+    EXPECT_EQ("(int16 year=2001, int8 month=8, int8 day=28, "
+              "string hostname=foobar, string data=2001/08/28-foobar)",
               results.back());
   }
 }
@@ -330,10 +331,10 @@ TEST_F(CompositePushdownTest, TestPushDownPrefixEqualitySuffixInequality) {
 TEST_F(CompositePushdownTest, TestPushdownPrefixInequality) {
 
   int16_t year_2001 = 2001;
-  int16_t year_2003 = 2003;
+  int16_t year_2004 = 2004;
   {
-    // year >= 2001 && year <= 2003
-    ColumnRangePredicate pred_year(schema_.column(0), &year_2001, &year_2003);
+    // year >= 2001 && year < 2004
+    auto pred_year = ColumnPredicate::Range(schema_.column(0), &year_2001, &year_2004);
     ScanSpec spec;
     spec.AddPredicate(pred_year);
     vector<string> results;
@@ -349,7 +350,7 @@ TEST_F(CompositePushdownTest, TestPushdownPrefixInequality) {
 
   {
     // year >= 2001
-    ColumnRangePredicate pred_year(schema_.column(0), &year_2001, nullptr);
+    auto pred_year = ColumnPredicate::Range(schema_.column(0), &year_2001, nullptr);
     ScanSpec spec;
     spec.AddPredicate(pred_year);
     vector<string> results;
@@ -366,8 +367,8 @@ TEST_F(CompositePushdownTest, TestPushdownPrefixInequality) {
   }
 
   {
-    // year <= 2003
-    ColumnRangePredicate pred_year(schema_.column(0), nullptr, &year_2003);
+    // year < 2004
+    auto pred_year = ColumnPredicate::Range(schema_.column(0), nullptr, &year_2004);
     ScanSpec spec;
     spec.AddPredicate(pred_year);
     vector<string> results;

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/diskrowset-test-base.h
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/diskrowset-test-base.h b/src/kudu/tablet/diskrowset-test-base.h
index 1ef1b80..262a21c 100644
--- a/src/kudu/tablet/diskrowset-test-base.h
+++ b/src/kudu/tablet/diskrowset-test-base.h
@@ -252,11 +252,11 @@ class TestRowSet : public KuduRowSetTest {
   void VerifyRandomRead(const DiskRowSet& rs, const Slice& row_key,
                         const string& expected_val) {
     Arena arena(256, 1024);
+    AutoReleasePool pool;
     ScanSpec spec;
-    ColumnRangePredicate pred(schema_.column(0), &row_key, &row_key);
+    auto pred = ColumnPredicate::Equality(schema_.column(0), &row_key);
     spec.AddPredicate(pred);
-    RangePredicateEncoder enc(&schema_, &arena);
-    enc.EncodeRangePredicates(&spec, true);
+    spec.OptimizeScan(schema_, &arena, &pool, true);
 
     MvccSnapshot snap = MvccSnapshot::CreateSnapshotIncludingAllTransactions();
     gscoped_ptr<RowwiseIterator> row_iter;

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/tablet-pushdown-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/tablet-pushdown-test.cc b/src/kudu/tablet/tablet-pushdown-test.cc
index b02e225..1188dbe 100644
--- a/src/kudu/tablet/tablet-pushdown-test.cc
+++ b/src/kudu/tablet/tablet-pushdown-test.cc
@@ -22,8 +22,10 @@
 #include <vector>
 
 #include "kudu/common/schema.h"
-#include "kudu/tablet/tablet.h"
 #include "kudu/tablet/tablet-test-base.h"
+#include "kudu/tablet/tablet.h"
+#include "kudu/util/auto_release_pool.h"
+#include "kudu/util/memory/arena.h"
 #include "kudu/util/test_macros.h"
 #include "kudu/util/test_util.h"
 
@@ -81,6 +83,10 @@ class TabletPushdownTest : public KuduTabletTest,
   // the same set of rows. Run the scan and verify that the
   // expected rows are returned.
   void TestScanYieldsExpectedResults(ScanSpec spec) {
+    Arena arena(128, 1028);
+    AutoReleasePool pool;
+    spec.OptimizeScan(schema_, &arena, &pool, true);
+
     gscoped_ptr<RowwiseIterator> iter;
     ASSERT_OK(tablet()->NewRowIterator(client_schema_, &iter));
     ASSERT_OK(iter->Init(&spec));
@@ -144,6 +150,10 @@ class TabletPushdownTest : public KuduTabletTest,
   // returns the expected number of rows. The rows themselves
   // should be empty.
   void TestCountOnlyScanYieldsExpectedResults(ScanSpec spec) {
+    Arena arena(128, 1028);
+    AutoReleasePool pool;
+    spec.OptimizeScan(schema_, &arena, &pool, true);
+
     Schema empty_schema(std::vector<ColumnSchema>(), 0);
     gscoped_ptr<RowwiseIterator> iter;
     ASSERT_OK(tablet()->NewRowIterator(empty_schema, &iter));
@@ -164,8 +174,8 @@ class TabletPushdownTest : public KuduTabletTest,
 TEST_P(TabletPushdownTest, TestPushdownIntKeyRange) {
   ScanSpec spec;
   int32_t lower = 200;
-  int32_t upper = 210;
-  ColumnRangePredicate pred0(schema_.column(0), &lower, &upper);
+  int32_t upper = 211;
+  auto pred0 = ColumnPredicate::Range(schema_.column(0), &lower, &upper);
   spec.AddPredicate(pred0);
 
   TestScanYieldsExpectedResults(spec);
@@ -177,8 +187,8 @@ TEST_P(TabletPushdownTest, TestPushdownIntValueRange) {
 
   ScanSpec spec;
   int32_t lower = 2000;
-  int32_t upper = 2100;
-  ColumnRangePredicate pred1(schema_.column(1), &lower, &upper);
+  int32_t upper = 2101;
+  auto pred1 = ColumnPredicate::Range(schema_.column(1), &lower, &upper);
   spec.AddPredicate(pred1);
 
   TestScanYieldsExpectedResults(spec);

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/tablet.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/tablet.cc b/src/kudu/tablet/tablet.cc
index a5b08f4..eae5bb1 100644
--- a/src/kudu/tablet/tablet.cc
+++ b/src/kudu/tablet/tablet.cc
@@ -1774,9 +1774,7 @@ Tablet::Iterator::Iterator(const Tablet* tablet, const Schema& projection,
     : tablet_(tablet),
       projection_(projection),
       snap_(std::move(snap)),
-      order_(order),
-      arena_(256, 4096),
-      encoder_(&tablet_->key_schema(), &arena_) {}
+      order_(order) {}
 
 Tablet::Iterator::~Iterator() {}
 
@@ -1785,15 +1783,9 @@ Status Tablet::Iterator::Init(ScanSpec *spec) {
 
   RETURN_NOT_OK(tablet_->GetMappedReadProjection(projection_, &projection_));
 
-  vector<shared_ptr<RowwiseIterator> > iters;
-  if (spec != nullptr) {
-    VLOG(3) << "Before encoding range preds: " << spec->ToString();
-    encoder_.EncodeRangePredicates(spec, true);
-    VLOG(3) << "After encoding range preds: " << spec->ToString();
-  }
+  vector<shared_ptr<RowwiseIterator>> iters;
 
-  RETURN_NOT_OK(tablet_->CaptureConsistentIterators(
-      &projection_, snap_, spec, &iters));
+  RETURN_NOT_OK(tablet_->CaptureConsistentIterators(&projection_, snap_, spec, &iters));
 
   switch (order_) {
     case ORDERED:

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/tablet.h
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/tablet.h b/src/kudu/tablet/tablet.h
index be5e5de..aa31b81 100644
--- a/src/kudu/tablet/tablet.h
+++ b/src/kudu/tablet/tablet.h
@@ -26,7 +26,6 @@
 #include <boost/thread/shared_mutex.hpp>
 
 #include "kudu/common/iterator.h"
-#include "kudu/common/predicate_encoder.h"
 #include "kudu/common/schema.h"
 #include "kudu/gutil/atomicops.h"
 #include "kudu/gutil/gscoped_ptr.h"
@@ -624,11 +623,6 @@ class Tablet::Iterator : public RowwiseIterator {
   const MvccSnapshot snap_;
   const OrderMode order_;
   gscoped_ptr<RowwiseIterator> iter_;
-
-  // TODO: we could probably share an arena with the Scanner object inside the
-  // tserver, but piping it in would require changing a lot of call-sites.
-  Arena arena_;
-  RangePredicateEncoder encoder_;
 };
 
 // Structure which represents the components of the tablet's storage.

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tablet/tablet_random_access-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tablet/tablet_random_access-test.cc b/src/kudu/tablet/tablet_random_access-test.cc
index 2459f9c..8295ff9 100644
--- a/src/kudu/tablet/tablet_random_access-test.cc
+++ b/src/kudu/tablet/tablet_random_access-test.cc
@@ -187,7 +187,7 @@ class TestRandomAccess : public KuduTabletTest {
     const Schema& schema = this->client_schema_;
     gscoped_ptr<RowwiseIterator> iter;
     CHECK_OK(this->tablet()->NewRowIterator(schema, &iter));
-    ColumnRangePredicate pred_one(schema.column(0), &key, &key);
+    auto pred_one = ColumnPredicate::Equality(schema.column(0), &key);
     spec.AddPredicate(pred_one);
     CHECK_OK(iter->Init(&spec));
 

http://git-wip-us.apache.org/repos/asf/incubator-kudu/blob/53e67e9e/src/kudu/tserver/tablet_server-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tserver/tablet_server-test.cc b/src/kudu/tserver/tablet_server-test.cc
index fe57f9f..a82d8c8 100644
--- a/src/kudu/tserver/tablet_server-test.cc
+++ b/src/kudu/tserver/tablet_server-test.cc
@@ -1393,11 +1393,11 @@ TEST_F(TabletServerTest, TestScanWithStringPredicates) {
   ASSERT_OK(SchemaToColumnPBs(schema_, scan->mutable_projected_columns()));
 
   // Set up a range predicate: "hello 50" < string_val <= "hello 59"
-  ColumnRangePredicatePB* pred = scan->add_range_predicates();
+  ColumnRangePredicatePB* pred = scan->add_deprecated_range_predicates();
   pred->mutable_column()->CopyFrom(scan->projected_columns(2));
 
   pred->set_lower_bound("hello 50");
-  pred->set_upper_bound("hello 59");
+  pred->set_inclusive_upper_bound("hello 59");
 
   // Send the call
   {
@@ -1434,15 +1434,15 @@ TEST_F(TabletServerTest, TestScanWithPredicates) {
   ASSERT_OK(SchemaToColumnPBs(schema_, scan->mutable_projected_columns()));
 
   // Set up a range predicate: 51 <= key <= 100
-  ColumnRangePredicatePB* pred = scan->add_range_predicates();
+  ColumnRangePredicatePB* pred = scan->add_deprecated_range_predicates();
   pred->mutable_column()->CopyFrom(scan->projected_columns(0));
 
   int32_t lower_bound_int = 51;
   int32_t upper_bound_int = 100;
   pred->mutable_lower_bound()->append(reinterpret_cast<char*>(&lower_bound_int),
                                       sizeof(lower_bound_int));
-  pred->mutable_upper_bound()->append(reinterpret_cast<char*>(&upper_bound_int),
-                                      sizeof(upper_bound_int));
+  pred->mutable_inclusive_upper_bound()->append(reinterpret_cast<char*>(&upper_bound_int),
+                                                sizeof(upper_bound_int));
 
   // Send the call
   {


Mime
View raw message