bshuf_block: fix GetFirstKey() and GetLastKey() This fixes a bug where the bitshuffle encoding would return the wrong value for GetFirstKey() and GetLastKey(). The issue was that, in the case of UINT32s, the data_ array was being inspected after 'Finish()' had already collapsed down the elements to their minimum width.
Since this collapsing is only done on UINT32 types, this would only affect these functions on dictionary-encoded binary blocks, which use bitshuffle internally for storing the UINT32 code words. However, the "cleanup" commit prior to this one also fixed some incorrect indexing that would affect BIT_SHUFFLE blocks outside the context of UINT32. These functions are only used in the case that the column in question is a non-composite primary key, in order to build the value index as well as to determine the min/max bounds of a written CFile. The result of returning the wrong value for GetLastKey() was that the resulting index blocks would be incorrect, and seeks based on key would end up at the wrong row. This could cause spurious "row not found" errors or even crashes in some cases. Apparently real users have not made use of BITSHUFFLE or DICT_ENCODING on such columns, since we haven't seen reports of this in the wild; I instead discovered this issue while working on KUDU-1751 (changing those encodings to be the default). The patch fixes the issue and also expands test coverage to cover the GetFirstKey/GetLastKey calls. Change-Id: I83dbc01ebf7a10e69b7fff6b7973967ebf6b4580 Reviewed-on: http://gerrit.cloudera.org:8080/5192 Tested-by: Kudu Jenkins Reviewed-by: Dan Burkert <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/kudu/repo Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/3d3c6f03 Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/3d3c6f03 Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/3d3c6f03 Branch: refs/heads/master Commit: 3d3c6f03351b1b27d179229614516ed8a6513c86 Parents: 1e6d4ad Author: Todd Lipcon <[email protected]> Authored: Tue Nov 22 16:19:04 2016 -0800 Committer: Todd Lipcon <[email protected]> Committed: Wed Nov 30 00:09:23 2016 +0000 ---------------------------------------------------------------------- src/kudu/cfile/bshuf_block.cc | 1 + src/kudu/cfile/bshuf_block.h | 24 ++++++++++++++++++++---- src/kudu/cfile/encoding-test.cc | 35 ++++++++++++++++++++++++++++------- 3 files changed, 49 insertions(+), 11 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kudu/blob/3d3c6f03/src/kudu/cfile/bshuf_block.cc ---------------------------------------------------------------------- diff --git a/src/kudu/cfile/bshuf_block.cc b/src/kudu/cfile/bshuf_block.cc index dec20bf..db68d27 100644 --- a/src/kudu/cfile/bshuf_block.cc +++ b/src/kudu/cfile/bshuf_block.cc @@ -54,6 +54,7 @@ void AbortWithBitShuffleError(int64_t val) { // in the current block. template<> Slice BShufBlockBuilder<UINT32>::Finish(rowid_t ordinal_pos) { + RememberFirstAndLastKey(); uint32_t max_value = 0; for (int i = 0; i < count_; i++) { max_value = std::max(max_value, *cell_ptr(i)); http://git-wip-us.apache.org/repos/asf/kudu/blob/3d3c6f03/src/kudu/cfile/bshuf_block.h ---------------------------------------------------------------------- diff --git a/src/kudu/cfile/bshuf_block.h b/src/kudu/cfile/bshuf_block.h index 4a4b551..a9ec466 100644 --- a/src/kudu/cfile/bshuf_block.h +++ b/src/kudu/cfile/bshuf_block.h @@ -96,6 +96,7 @@ class BShufBlockBuilder : public BlockBuilder { data_.reserve(options_->storage_attributes.cfile_block_size); buffer_.clear(); buffer_.resize(kHeaderSize); + finished_ = false; } bool IsBlockFull() const override { @@ -103,6 +104,7 @@ class BShufBlockBuilder : public BlockBuilder { } int Add(const uint8_t* vals_void, size_t count) OVERRIDE { + DCHECK(!finished_); const CppType* vals = reinterpret_cast<const CppType* >(vals_void); int added = 0; // If the current block is full, stop adding more items. @@ -121,24 +123,25 @@ class BShufBlockBuilder : public BlockBuilder { } Status GetFirstKey(void* key) const OVERRIDE { + DCHECK(finished_); if (count_ == 0) { return Status::NotFound("no keys in data block"); } - memcpy(key, cell_ptr(0), size_of_type); + memcpy(key, &first_key_, size_of_type); return Status::OK(); } Status GetLastKey(void* key) const OVERRIDE { + DCHECK(finished_); if (count_ == 0) { return Status::NotFound("no keys in data block"); } - // TODO(todd): the following memcpy is incorrect. Will fix this in the - // next commit in this patch series. - memcpy(key, &data_[count_ - 1], size_of_type); + memcpy(key, &last_key_, size_of_type); return Status::OK(); } Slice Finish(rowid_t ordinal_pos) OVERRIDE { + RememberFirstAndLastKey(); return Finish(ordinal_pos, size_of_type); } @@ -154,6 +157,15 @@ class BShufBlockBuilder : public BlockBuilder { return reinterpret_cast<CppType*>(&data_[idx * size_of_type]); } + // Remember the last added key in 'last_key_'. This is done during + // Finish() because Finish() may rearrange/collapse the values in the + // data_ buffer during the encoding process. + void RememberFirstAndLastKey() { + if (count_ == 0) return; + memcpy(&first_key_, cell_ptr(0), size_of_type); + memcpy(&last_key_, cell_ptr(count_ - 1), size_of_type); + } + size_t EstimateEncodedSize() const { int num = KUDU_ALIGN_UP(count_, 8); // The result of bshuf_compress_lz4_bound(num, size_of_type, 0) @@ -196,6 +208,7 @@ class BShufBlockBuilder : public BlockBuilder { InlineEncodeFixed32(&buffer_[8], kHeaderSize + bytes); InlineEncodeFixed32(&buffer_[12], num_elems_after_padding); InlineEncodeFixed32(&buffer_[16], final_size_of_type); + finished_ = true; return Slice(buffer_.data(), kHeaderSize + bytes); } @@ -208,6 +221,9 @@ class BShufBlockBuilder : public BlockBuilder { faststring data_; faststring buffer_; uint32_t count_; + bool finished_; + CppType first_key_; + CppType last_key_; const WriterOptions* options_; }; http://git-wip-us.apache.org/repos/asf/kudu/blob/3d3c6f03/src/kudu/cfile/encoding-test.cc ---------------------------------------------------------------------- diff --git a/src/kudu/cfile/encoding-test.cc b/src/kudu/cfile/encoding-test.cc index d8e5cc3..b8ece20 100644 --- a/src/kudu/cfile/encoding-test.cc +++ b/src/kudu/cfile/encoding-test.cc @@ -245,6 +245,13 @@ class TestEncoding : public ::testing::Test { // the slice should take at least a few bytes per entry ASSERT_GT(s.size(), kCount * 2u); + // Check first/last keys + Slice key; + ASSERT_OK(sbb.GetFirstKey(&key)); + ASSERT_EQ("hello 0", key); + ASSERT_OK(sbb.GetLastKey(&key)); + ASSERT_EQ(StringPrintf("hello %d", kCount - 1), key); + DecoderType sbd(s); ASSERT_OK(sbd.ParseHeader()); ASSERT_EQ(kCount, sbd.Count()); @@ -300,8 +307,9 @@ class TestEncoding : public ::testing::Test { CHECK_EQ(num_ints, ibb->Add(reinterpret_cast<uint8_t *>(&data[0]), num_ints)); - Slice s = ibb->Finish(0); + LOG(INFO) << "Created " << TypeTraits<IntType>::name() << " block with " << num_ints << " ints" + << " (" << s.size() << " bytes)"; BlockDecoderType ibd(s); ASSERT_OK(ibd.ParseHeader()); @@ -478,6 +486,13 @@ class TestEncoding : public ::testing::Test { to_insert.size()); Slice s = ibb->Finish(kOrdinalPosBase); + // Check GetFirstKey() and GetLastKey(). + CppType key; + ASSERT_OK(ibb->GetFirstKey(&key)); + ASSERT_EQ(to_insert.front(), key); + ASSERT_OK(ibb->GetLastKey(&key)); + ASSERT_EQ(to_insert.back(), key); + DecoderType ibd(s); ASSERT_OK(ibd.ParseHeader()); @@ -862,12 +877,14 @@ class IntEncodingTest : public TestEncoding { TYPED_TEST(IntEncodingTest, TestSeekAllTypes) { - this->template DoIntSeekTest<UINT8>(32, 1000, true); - this->template DoIntSeekTest<INT8>(32, 1000, true); - this->template DoIntSeekTest<UINT16>(64, 1000, true); - this->template DoIntSeekTest<INT16>(64, 1000, true); - this->template DoIntSeekTest<UINT32>(64, 1000, true); - this->template DoIntSeekTest<INT32>(64, 1000, true); + this->template DoIntSeekTest<UINT8>(100, 1000, true); + this->template DoIntSeekTest<INT8>(100, 1000, true); + this->template DoIntSeekTest<UINT16>(10000, 1000, true); + this->template DoIntSeekTest<INT16>(10000, 1000, true); + this->template DoIntSeekTest<UINT32>(10000, 1000, true); + this->template DoIntSeekTest<INT32>(10000, 1000, true); + this->template DoIntSeekTest<UINT64>(10000, 1000, true); + this->template DoIntSeekTest<INT64>(10000, 1000, true); } TYPED_TEST(IntEncodingTest, IntSeekTestTinyBlockAllTypes) { @@ -877,6 +894,8 @@ TYPED_TEST(IntEncodingTest, IntSeekTestTinyBlockAllTypes) { this->template DoIntSeekTestTinyBlock<INT16>(); this->template DoIntSeekTestTinyBlock<UINT32>(); this->template DoIntSeekTestTinyBlock<INT32>(); + this->template DoIntSeekTestTinyBlock<UINT64>(); + this->template DoIntSeekTestTinyBlock<INT64>(); } TYPED_TEST(IntEncodingTest, TestRoundTrip) { @@ -886,6 +905,8 @@ TYPED_TEST(IntEncodingTest, TestRoundTrip) { this->template DoIntRoundTripTest<INT16>(); this->template DoIntRoundTripTest<UINT32>(); this->template DoIntRoundTripTest<INT32>(); + this->template DoIntRoundTripTest<UINT64>(); + this->template DoIntRoundTripTest<INT64>(); } #ifdef NDEBUG
