You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by da...@apache.org on 2017/10/10 17:32:59 UTC
kudu git commit: KUDU-2173: Partitions are incorrectly pruned when
range-partitioned on a PK prefix
Repository: kudu
Updated Branches:
refs/heads/branch-1.2.x 7b6755d3a -> da6ded64d
KUDU-2173: Partitions are incorrectly pruned when range-partitioned on a PK prefix
The partition pruner mistakenly treated a range partition which is a
proper prefix of a primary key as an exclusive bound, when in fact it's
an inclusive bound if the remaining PK column constraints are greater
than the min value.
This is a C++-only bug; the Java client only attempts to use the PK as
the range partition bound when the primary key columns match the range
partition columns exactly (see KUDU-2178).
Change-Id: I38752f50c0910cd157a912eaa272c76a1a0d9b59
Reviewed-on: http://gerrit.cloudera.org:8080/8222
Tested-by: Kudu Jenkins
Reviewed-by: Todd Lipcon <to...@apache.org>
Reviewed-on: http://gerrit.cloudera.org:8080/8246
Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/da6ded64
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/da6ded64
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/da6ded64
Branch: refs/heads/branch-1.2.x
Commit: da6ded64d6c13b8ea799888a1225a7def1e71bfa
Parents: 7b6755d
Author: Dan Burkert <da...@apache.org>
Authored: Thu Oct 5 19:21:43 2017 -0700
Committer: Todd Lipcon <to...@apache.org>
Committed: Tue Oct 10 05:59:35 2017 +0000
----------------------------------------------------------------------
src/kudu/common/key_util.cc | 7 +-
src/kudu/common/key_util.h | 4 +
src/kudu/common/partial_row.h | 1 +
src/kudu/common/partition_pruner-test.cc | 229 ++++++++++++++++++++++----
src/kudu/common/partition_pruner.cc | 27 ++-
5 files changed, 228 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/kudu/blob/da6ded64/src/kudu/common/key_util.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/key_util.cc b/src/kudu/common/key_util.cc
index 8ee6eb3..a73fd0e 100644
--- a/src/kudu/common/key_util.cc
+++ b/src/kudu/common/key_util.cc
@@ -259,9 +259,12 @@ int PushLowerBoundKeyPredicates(ColIdxIter first,
} // anonymous namespace
bool IncrementPrimaryKey(ContiguousRow* row, Arena* arena) {
- int32_t num_pk_cols = row->schema()->num_key_columns();
+ return IncrementPrimaryKey(row, row->schema()->num_key_columns(), arena);
+}
+
+bool IncrementPrimaryKey(ContiguousRow* row, int32_t num_columns, Arena* arena) {
return IncrementKey(boost::make_counting_iterator(0),
- boost::make_counting_iterator(num_pk_cols),
+ boost::make_counting_iterator(num_columns),
row,
arena);
}
http://git-wip-us.apache.org/repos/asf/kudu/blob/da6ded64/src/kudu/common/key_util.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/key_util.h b/src/kudu/common/key_util.h
index 8dc60f4..4b62004 100644
--- a/src/kudu/common/key_util.h
+++ b/src/kudu/common/key_util.h
@@ -57,6 +57,10 @@ namespace key_util {
// REQUIRES: all primary key columns must be initialized.
bool IncrementPrimaryKey(ContiguousRow* row, Arena* arena) WARN_UNUSED_RESULT;
+// Like 'IncrementPrimaryKey(ContiguousRow*, Arena*)', but only increments up to
+// 'num_columns' columns of the primary key prefix.
+bool IncrementPrimaryKey(ContiguousRow* row, int32_t num_columns, Arena* arena) WARN_UNUSED_RESULT;
+
// Increments the provided cell in place.
bool IncrementCell(const ColumnSchema& col, void* cell_ptr, Arena* arena);
http://git-wip-us.apache.org/repos/asf/kudu/blob/da6ded64/src/kudu/common/partial_row.h
----------------------------------------------------------------------
diff --git a/src/kudu/common/partial_row.h b/src/kudu/common/partial_row.h
index c252fce..a0eff6b 100644
--- a/src/kudu/common/partial_row.h
+++ b/src/kudu/common/partial_row.h
@@ -485,6 +485,7 @@ class KUDU_EXPORT KuduPartialRow {
template<typename KeyTypeWrapper> friend struct client::IntKeysTestSetup;
template<typename KeyTypeWrapper> friend struct tablet::SliceTypeRowOps;
template<typename KeyTypeWarpper> friend struct tablet::NumTypeRowOps;
+ FRIEND_TEST(TestPartitionPruner, TestIntPartialPrimaryKeyRangePruning);
FRIEND_TEST(TestPartitionPruner, TestPrimaryKeyRangePruning);
FRIEND_TEST(TestPartitionPruner, TestPartialPrimaryKeyRangePruning);
http://git-wip-us.apache.org/repos/asf/kudu/blob/da6ded64/src/kudu/common/partition_pruner-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/partition_pruner-test.cc b/src/kudu/common/partition_pruner-test.cc
index 701d4a1..9ab5bc8 100644
--- a/src/kudu/common/partition_pruner-test.cc
+++ b/src/kudu/common/partition_pruner-test.cc
@@ -29,6 +29,8 @@
#include "kudu/common/row.h"
#include "kudu/common/scan_spec.h"
#include "kudu/common/schema.h"
+#include "kudu/util/auto_release_pool.h"
+#include "kudu/util/memory/arena.h"
#include "kudu/util/test_util.h"
using boost::optional;
@@ -49,14 +51,20 @@ void CheckPrunedPartitions(const Schema& schema,
const ScanSpec& spec,
size_t remaining_tablets) {
+ ScanSpec opt_spec(spec);
+ AutoReleasePool p;
+ Arena arena(256, 1024 * 1024);
+ opt_spec.OptimizeScan(schema, &arena, &p, false);
+
PartitionPruner pruner;
- pruner.Init(schema, partition_schema, spec);
+ pruner.Init(schema, partition_schema, opt_spec);
SCOPED_TRACE(strings::Substitute("schema: $0", schema.ToString()));
SCOPED_TRACE(strings::Substitute("partition schema: $0", partition_schema.DebugString(schema)));
SCOPED_TRACE(strings::Substitute("partition pruner: $0",
pruner.ToString(schema, partition_schema)));
- SCOPED_TRACE(strings::Substitute("scan spec: $0", spec.ToString(schema)));
+ SCOPED_TRACE(strings::Substitute("optimized scan spec: $0", opt_spec.ToString(schema)));
+ SCOPED_TRACE(strings::Substitute("original scan spec: $0", spec.ToString(schema)));
int pruned_partitions = count_if(partitions.begin(), partitions.end(),
[&] (const Partition& partition) {
@@ -207,8 +215,8 @@ TEST(TestPartitionPruner, TestPartialPrimaryKeyRangePruning) {
// Applies the specified lower and upper bound primary keys against the
// schema, and checks that the expected number of partitions are pruned.
- auto Check = [&] (optional<tuple<int8_t, string>> lower,
- optional<tuple<int8_t, string>> upper,
+ auto Check = [&] (optional<tuple<int8_t, string, string>> lower,
+ optional<tuple<int8_t, string, string>> upper,
size_t remaining_tablets ) {
ScanSpec spec;
KuduPartialRow lower_bound(&schema);
@@ -219,7 +227,7 @@ TEST(TestPartitionPruner, TestPartialPrimaryKeyRangePruning) {
if (lower) {
CHECK_OK(lower_bound.SetInt8("a", get<0>(*lower)));
CHECK_OK(lower_bound.SetStringCopy("b", get<1>(*lower)));
- CHECK_OK(lower_bound.SetStringCopy("c", "fuzz"));
+ CHECK_OK(lower_bound.SetStringCopy("c", get<2>(*lower)));
ConstContiguousRow row(lower_bound.schema(), lower_bound.row_data_);
enc_lower_bound = EncodedKey::FromContiguousRow(row);
spec.SetLowerBoundKey(enc_lower_bound.get());
@@ -227,7 +235,7 @@ TEST(TestPartitionPruner, TestPartialPrimaryKeyRangePruning) {
if (upper) {
CHECK_OK(upper_bound.SetInt8("a", get<0>(*upper)));
CHECK_OK(upper_bound.SetStringCopy("b", get<1>(*upper)));
- CHECK_OK(upper_bound.SetStringCopy("c", "fuzzy"));
+ CHECK_OK(upper_bound.SetStringCopy("c", get<2>(*upper)));
ConstContiguousRow row(upper_bound.schema(), upper_bound.row_data_);
enc_upper_bound = EncodedKey::FromContiguousRow(row);
spec.SetExclusiveUpperBoundKey(enc_upper_bound.get());
@@ -238,46 +246,140 @@ TEST(TestPartitionPruner, TestPartialPrimaryKeyRangePruning) {
// No bounds
Check(boost::none, boost::none, 3);
- // PK < (-1, min, _)
- Check(boost::none, make_tuple<int8_t, string>(-1, ""), 1);
+ // PK < (-1, min, "")
+ Check(boost::none, make_tuple<int8_t, string, string>(-1, "", ""), 1);
+
+ // PK < (10, "r", "")
+ Check(boost::none, make_tuple<int8_t, string, string>(10, "r", ""), 2);
- // PK < (10, "r", _)
- Check(boost::none, make_tuple<int8_t, string>(10, "r"), 2);
+ // PK < (10, "r", "z")
+ Check(boost::none, make_tuple<int8_t, string, string>(10, "r", "z"), 3);
- // PK < (100, min)
- Check(boost::none, make_tuple<int8_t, string>(100, ""), 3);
+ // PK < (100, min, "")
+ Check(boost::none, make_tuple<int8_t, string, string>(100, "", ""), 3);
- // PK >= (-10, "m")
- Check(make_tuple<int8_t, string>(-10, "m"), boost::none, 3);
+ // PK >= (-10, "m", "")
+ Check(make_tuple<int8_t, string, string>(-10, "m", ""), boost::none, 3);
- // PK >= (0, "")
- Check(make_tuple<int8_t, string>(0, ""), boost::none, 3);
+ // PK >= (0, "", "")
+ Check(make_tuple<int8_t, string, string>(0, "", ""), boost::none, 3);
- // PK >= (0, "m")
- Check(make_tuple<int8_t, string>(0, "m"), boost::none, 2);
+ // PK >= (0, "m", "")
+ Check(make_tuple<int8_t, string, string>(0, "m", ""), boost::none, 2);
- // PK >= (100, "")
- Check(make_tuple<int8_t, string>(100, ""), boost::none, 1);
+ // PK >= (100, "", "")
+ Check(make_tuple<int8_t, string, string>(100, "", ""), boost::none, 1);
- // PK >= (-10, 0)
- // PK < (100, 0)
- Check(make_tuple<int8_t, string>(-10, ""),
- make_tuple<int8_t, string>(100, ""), 3);
+ // PK >= (-10, 0, "")
+ // PK < (100, 0, "")
+ Check(make_tuple<int8_t, string, string>(-10, "", ""),
+ make_tuple<int8_t, string, string>(100, "", ""), 3);
- // PK >= (0, "m")
- // PK < (10, "r")
- Check(make_tuple<int8_t, string>(0, "m"),
- make_tuple<int8_t, string>(10, "r"), 1);
+ // PK >= (0, "m", "")
+ // PK < (10, "r", "")
+ Check(make_tuple<int8_t, string, string>(0, "m", ""),
+ make_tuple<int8_t, string, string>(10, "r", ""), 1);
- // PK >= (0, "")
- // PK < (10, "m")
- Check(make_tuple<int8_t, string>(0, ""),
- make_tuple<int8_t, string>(10, "m"), 2);
+ // PK >= (0, "m", "")
+ // PK < (10, "r", "z")
+ Check(make_tuple<int8_t, string, string>(0, "m", ""),
+ make_tuple<int8_t, string, string>(10, "r", "z"), 2);
- // PK >= (10, "m")
- // PK < (10, "m")
- Check(make_tuple<int8_t, string>(10, "m"),
- make_tuple<int8_t, string>(10, "m"), 1);
+ // PK >= (0, "", "")
+ // PK < (10, "m", "z")
+ Check(make_tuple<int8_t, string, string>(0, "", ""),
+ make_tuple<int8_t, string, string>(10, "m", "z"), 2);
+
+ // PK >= (10, "m", "")
+ // PK < (10, "m", "z")
+ Check(make_tuple<int8_t, string, string>(10, "m", ""),
+ make_tuple<int8_t, string, string>(10, "m", "z"), 1);
+}
+
+TEST(TestPartitionPruner, TestIntPartialPrimaryKeyRangePruning) {
+ // CREATE TABLE t
+ // (a INT8, b INT8, c INT8, PRIMARY KEY (a, b, c))
+ // DISTRIBUTE BY RANGE(a, b)
+ // SPLIT ROWS [(0, 0)];
+
+ // Setup the Schema
+ Schema schema({ ColumnSchema("a", INT8),
+ ColumnSchema("b", INT8),
+ ColumnSchema("c", INT8) },
+ { ColumnId(0), ColumnId(1), ColumnId(2) },
+ 3);
+
+ PartitionSchema partition_schema;
+ auto pb = PartitionSchemaPB();
+ auto range_schema = pb.mutable_range_schema();
+ range_schema->add_columns()->set_name("a");
+ range_schema->add_columns()->set_name("b");
+ ASSERT_OK(PartitionSchema::FromPB(pb, schema, &partition_schema));
+
+ KuduPartialRow split(&schema);
+ ASSERT_OK(split.SetInt8("a", 0));
+ ASSERT_OK(split.SetInt8("b", 0));
+
+ vector<Partition> partitions;
+ ASSERT_OK(partition_schema.CreatePartitions({ split }, {}, schema, &partitions));
+
+ // Applies the specified lower and upper bound primary keys against the
+ // schema, and checks that the expected number of partitions are pruned.
+ auto Check = [&] (optional<tuple<int8_t, int8_t, int8_t>> lower,
+ optional<tuple<int8_t, int8_t, int8_t>> upper,
+ size_t remaining_tablets ) {
+ ScanSpec spec;
+ KuduPartialRow lower_bound(&schema);
+ KuduPartialRow upper_bound(&schema);
+ gscoped_ptr<EncodedKey> enc_lower_bound;
+ gscoped_ptr<EncodedKey> enc_upper_bound;
+
+ if (lower) {
+ CHECK_OK(lower_bound.SetInt8("a", get<0>(*lower)));
+ CHECK_OK(lower_bound.SetInt8("b", get<1>(*lower)));
+ CHECK_OK(lower_bound.SetInt8("c", get<2>(*lower)));
+ ConstContiguousRow row(lower_bound.schema(), lower_bound.row_data_);
+ enc_lower_bound = EncodedKey::FromContiguousRow(row);
+ spec.SetLowerBoundKey(enc_lower_bound.get());
+ }
+ if (upper) {
+ CHECK_OK(upper_bound.SetInt8("a", get<0>(*upper)));
+ CHECK_OK(upper_bound.SetInt8("b", get<1>(*upper)));
+ CHECK_OK(upper_bound.SetInt8("c", get<2>(*upper)));
+ ConstContiguousRow row(upper_bound.schema(), upper_bound.row_data_);
+ enc_upper_bound = EncodedKey::FromContiguousRow(row);
+ spec.SetExclusiveUpperBoundKey(enc_upper_bound.get());
+ }
+ CheckPrunedPartitions(schema, partition_schema, partitions, spec,
+ remaining_tablets);
+ };
+
+ // No bounds
+ Check(boost::none, boost::none, 2);
+
+ // PK < (0, 0, min)
+ Check(boost::none, make_tuple<int8_t, int8_t, int8_t>(0, INT8_MIN, INT8_MIN), 1);
+
+ // PK < (0, 0, 0);
+ Check(boost::none, make_tuple<int8_t, int8_t, int8_t>(0, 0, 0), 2);
+
+ // PK < (0, max, 0);
+ Check(boost::none, make_tuple<int8_t, int8_t, int8_t>(INT8_MAX, INT8_MAX, 0), 2);
+
+ // PK < (max, max, min);
+ Check(boost::none, make_tuple<int8_t, int8_t, int8_t>(INT8_MAX, INT8_MAX, INT8_MIN), 2);
+
+ // PK < (max, max, 0);
+ Check(boost::none, make_tuple<int8_t, int8_t, int8_t>(INT8_MAX, INT8_MAX, 0), 2);
+
+ // PK >= (0, 0, 0);
+ Check(make_tuple<int8_t, int8_t, int8_t>(0, 0, 0), boost::none, 1);
+
+ // PK >= (0, 0, -1);
+ Check(make_tuple<int8_t, int8_t, int8_t>(0, 0, -1), boost::none, 1);
+
+ // PK >= (0, 0, min);
+ Check(make_tuple<int8_t, int8_t, int8_t>(0, 0, INT8_MIN), boost::none, 1);
}
TEST(TestPartitionPruner, TestRangePruning) {
@@ -655,4 +757,59 @@ TEST(TestPartitionPruner, TestPruning) {
Check({ ColumnPredicate::Equality(schema.column(2), &ten) },
string("\0\0\0\1", 4), "", 1);
}
+
+TEST(TestPartitionPruner, TestKudu2173) {
+ // CREATE TABLE t
+ // (a INT8, b INT8, PRIMARY KEY (a, b))
+ // DISTRIBUTE BY RANGE(a)
+ // SPLIT ROWS [(10)]
+
+ // Setup the Schema
+ Schema schema({ ColumnSchema("a", INT8),
+ ColumnSchema("b", INT8)},
+ { ColumnId(0), ColumnId(1) },
+ 2);
+
+ PartitionSchema partition_schema;
+ auto pb = PartitionSchemaPB();
+ auto range_schema = pb.mutable_range_schema();
+ range_schema->add_columns()->set_name("a");
+ ASSERT_OK(PartitionSchema::FromPB(pb, schema, &partition_schema));
+
+ KuduPartialRow split1(&schema);
+ ASSERT_OK(split1.SetInt8("a", 10));
+ vector<Partition> partitions;
+ ASSERT_OK(partition_schema.CreatePartitions({ split1 }, {}, schema, &partitions));
+
+ // Applies the specified predicates to a scan and checks that the expected
+ // number of partitions are pruned.
+ auto Check = [&] (const vector<ColumnPredicate>& predicates, size_t remaining_tablets) {
+ ScanSpec spec;
+
+ for (const auto& pred : predicates) {
+ spec.AddPredicate(pred);
+ }
+ CheckPrunedPartitions(schema, partition_schema, partitions, spec,
+ remaining_tablets);
+ };
+
+ int8_t eleven = 11;
+ int8_t max = INT8_MAX;
+
+ // a < 11
+ Check({ ColumnPredicate::Range(schema.column(0), nullptr, &eleven) }, 2);
+
+ // a < 11 AND b < 11
+ Check({ ColumnPredicate::Range(schema.column(0), nullptr, &eleven),
+ ColumnPredicate::Range(schema.column(1), nullptr, &eleven) },
+ 2);
+
+ // a < max
+ Check({ ColumnPredicate::Range(schema.column(0), nullptr, &max) }, 2);
+
+ // a < max AND b < 11
+ Check({ ColumnPredicate::Range(schema.column(0), nullptr, &max),
+ ColumnPredicate::Range(schema.column(1), nullptr, &eleven) },
+ 2);
+}
} // namespace kudu
http://git-wip-us.apache.org/repos/asf/kudu/blob/da6ded64/src/kudu/common/partition_pruner.cc
----------------------------------------------------------------------
diff --git a/src/kudu/common/partition_pruner.cc b/src/kudu/common/partition_pruner.cc
index 0836637..c53c4a7 100644
--- a/src/kudu/common/partition_pruner.cc
+++ b/src/kudu/common/partition_pruner.cc
@@ -90,8 +90,9 @@ void EncodeRangeKeysFromPrimaryKeyBounds(const Schema& schema,
*range_key_end = scan_spec.exclusive_upper_bound_key()->encoded_key().ToString();
}
} else {
- // The range columns are a prefix of the primary key columns. Copy
- // the column values over to a row, and then encode the row as a range key.
+ // The range-partition key columns are a prefix of the primary key columns.
+ // Copy the column values over to a row, and then encode the row as a range
+ // key.
vector<int32_t> col_idxs(num_range_columns);
iota(col_idxs.begin(), col_idxs.end(), 0);
@@ -114,6 +115,28 @@ void EncodeRangeKeysFromPrimaryKeyBounds(const Schema& schema,
scan_spec.exclusive_upper_bound_key()->raw_keys()[idx],
schema.column(idx).type_info()->size());
}
+
+ // Determine if the upper bound primary key columns which aren't in the
+ // range-partition key are all set to the minimum value. If so, the
+ // range-partition key prefix of the primary key is already effectively an
+ // exclusive bound. If not, then we increment the range-key prefix in
+ // order to transform it from inclusive to exclusive.
+ bool min_suffix = true;
+ for (int32_t idx = num_range_columns; idx < schema.num_key_columns(); idx++) {
+ min_suffix &= schema.column(idx)
+ .type_info()
+ ->IsMinValue(scan_spec.exclusive_upper_bound_key()->raw_keys()[idx]);
+ }
+ Arena arena(std::max<size_t>(Arena::kMinimumChunkSize, schema.key_byte_size()), 4096);
+ if (!min_suffix) {
+ if (!key_util::IncrementPrimaryKey(&row, num_range_columns, &arena)) {
+ // The range-partition key upper bound can't be incremented, which
+ // means it's an inclusive bound on the maximum possible value, so
+ // skip it.
+ return;
+ }
+ }
+
key_util::EncodeKey(col_idxs, row, range_key_end);
}
}