ceph/src/rocksdb/utilities/spatialdb/spatial_db_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5
   6 #ifndef ROCKSDB_LITE
   7
   8 #include <vector>
   9 #include <string>
  10 #include <set>
  11
  12 #include "rocksdb/utilities/spatial_db.h"
  13 #include "util/compression.h"
  14 #include "util/testharness.h"
  15 #include "util/testutil.h"
  16 #include "util/random.h"
  17
  18 namespace rocksdb {
  19 namespace spatial {
  20
  21 class SpatialDBTest : public testing::Test {
  22  public:
  23   SpatialDBTest() {
  24     dbname_ = test::PerThreadDBPath("spatial_db_test");
  25     DestroyDB(dbname_, Options());
  26   }
  27
  28   void AssertCursorResults(BoundingBox<double> bbox, const std::string& index,
  29                            const std::vector<std::string>& blobs) {
  30     Cursor* c = db_->Query(ReadOptions(), bbox, index);
  31     ASSERT_OK(c->status());
  32     std::multiset<std::string> b;
  33     for (auto x : blobs) {
  34       b.insert(x);
  35     }
  36
  37     while (c->Valid()) {
  38       auto itr = b.find(c->blob().ToString());
  39       ASSERT_TRUE(itr != b.end());
  40       b.erase(itr);
  41       c->Next();
  42     }
  43     ASSERT_EQ(b.size(), 0U);
  44     ASSERT_OK(c->status());
  45     delete c;
  46   }
  47
  48   std::string dbname_;
  49   SpatialDB* db_;
  50 };
  51
  52 TEST_F(SpatialDBTest, FeatureSetSerializeTest) {
  53   if (!LZ4_Supported()) {
  54     return;
  55   }
  56   FeatureSet fs;
  57
  58   fs.Set("a", std::string("b"));
  59   fs.Set("x", static_cast<uint64_t>(3));
  60   fs.Set("y", false);
  61   fs.Set("n", Variant());  // null
  62   fs.Set("m", 3.25);
  63
  64   ASSERT_TRUE(fs.Find("w") == fs.end());
  65   ASSERT_TRUE(fs.Find("x") != fs.end());
  66   ASSERT_TRUE((*fs.Find("x")).second == Variant(static_cast<uint64_t>(3)));
  67   ASSERT_TRUE((*fs.Find("y")).second != Variant(true));
  68   std::set<std::string> keys({"a", "x", "y", "n", "m"});
  69   for (const auto& x : fs) {
  70     ASSERT_TRUE(keys.find(x.first) != keys.end());
  71     keys.erase(x.first);
  72   }
  73   ASSERT_EQ(keys.size(), 0U);
  74
  75   std::string serialized;
  76   fs.Serialize(&serialized);
  77
  78   FeatureSet deserialized;
  79   ASSERT_TRUE(deserialized.Deserialize(serialized));
  80
  81   ASSERT_TRUE(deserialized.Contains("a"));
  82   ASSERT_EQ(deserialized.Get("a").type(), Variant::kString);
  83   ASSERT_EQ(deserialized.Get("a").get_string(), "b");
  84   ASSERT_TRUE(deserialized.Contains("x"));
  85   ASSERT_EQ(deserialized.Get("x").type(), Variant::kInt);
  86   ASSERT_EQ(deserialized.Get("x").get_int(), static_cast<uint64_t>(3));
  87   ASSERT_TRUE(deserialized.Contains("y"));
  88   ASSERT_EQ(deserialized.Get("y").type(), Variant::kBool);
  89   ASSERT_EQ(deserialized.Get("y").get_bool(), false);
  90   ASSERT_TRUE(deserialized.Contains("n"));
  91   ASSERT_EQ(deserialized.Get("n").type(), Variant::kNull);
  92   ASSERT_TRUE(deserialized.Contains("m"));
  93   ASSERT_EQ(deserialized.Get("m").type(), Variant::kDouble);
  94   ASSERT_EQ(deserialized.Get("m").get_double(), 3.25);
  95
  96   // corrupted serialization
  97   serialized = serialized.substr(0, serialized.size() - 4);
  98   deserialized.Clear();
  99   ASSERT_TRUE(!deserialized.Deserialize(serialized));
 100 }
 101
 102 TEST_F(SpatialDBTest, TestNextID) {
 103   if (!LZ4_Supported()) {
 104     return;
 105   }
 106   ASSERT_OK(SpatialDB::Create(
 107       SpatialDBOptions(), dbname_,
 108       {SpatialIndexOptions("simple", BoundingBox<double>(0, 0, 100, 100), 2)}));
 109
 110   ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 111   ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(5, 5, 10, 10),
 112                         "one", FeatureSet(), {"simple"}));
 113   ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(10, 10, 15, 15),
 114                         "two", FeatureSet(), {"simple"}));
 115   delete db_;
 116   db_ = nullptr;
 117
 118   ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 119   assert(db_ != nullptr);
 120   ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(55, 55, 65, 65),
 121                         "three", FeatureSet(), {"simple"}));
 122   delete db_;
 123
 124   ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 125   AssertCursorResults(BoundingBox<double>(0, 0, 100, 100), "simple",
 126                       {"one", "two", "three"});
 127   delete db_;
 128 }
 129
 130 TEST_F(SpatialDBTest, FeatureSetTest) {
 131   if (!LZ4_Supported()) {
 132     return;
 133   }
 134   ASSERT_OK(SpatialDB::Create(
 135       SpatialDBOptions(), dbname_,
 136       {SpatialIndexOptions("simple", BoundingBox<double>(0, 0, 100, 100), 2)}));
 137   ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 138
 139   FeatureSet fs;
 140   fs.Set("a", std::string("b"));
 141   fs.Set("c", std::string("d"));
 142
 143   ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(5, 5, 10, 10),
 144                         "one", fs, {"simple"}));
 145
 146   Cursor* c =
 147       db_->Query(ReadOptions(), BoundingBox<double>(5, 5, 10, 10), "simple");
 148
 149   ASSERT_TRUE(c->Valid());
 150   ASSERT_EQ(c->blob().compare("one"), 0);
 151   FeatureSet returned = c->feature_set();
 152   ASSERT_TRUE(returned.Contains("a"));
 153   ASSERT_TRUE(!returned.Contains("b"));
 154   ASSERT_TRUE(returned.Contains("c"));
 155   ASSERT_EQ(returned.Get("a").type(), Variant::kString);
 156   ASSERT_EQ(returned.Get("a").get_string(), "b");
 157   ASSERT_EQ(returned.Get("c").type(), Variant::kString);
 158   ASSERT_EQ(returned.Get("c").get_string(), "d");
 159
 160   c->Next();
 161   ASSERT_TRUE(!c->Valid());
 162
 163   delete c;
 164   delete db_;
 165 }
 166
 167 TEST_F(SpatialDBTest, SimpleTest) {
 168   if (!LZ4_Supported()) {
 169     return;
 170   }
 171   // iter 0 -- not read only
 172   // iter 1 -- read only
 173   for (int iter = 0; iter < 2; ++iter) {
 174     DestroyDB(dbname_, Options());
 175     ASSERT_OK(SpatialDB::Create(
 176         SpatialDBOptions(), dbname_,
 177         {SpatialIndexOptions("index", BoundingBox<double>(0, 0, 128, 128),
 178                              3)}));
 179     ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 180     assert(db_ != nullptr);
 181
 182     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(33, 17, 63, 79),
 183                           "one", FeatureSet(), {"index"}));
 184     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(65, 65, 111, 111),
 185                           "two", FeatureSet(), {"index"}));
 186     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(1, 49, 127, 63),
 187                           "three", FeatureSet(), {"index"}));
 188     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(20, 100, 21, 101),
 189                           "four", FeatureSet(), {"index"}));
 190     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(81, 33, 127, 63),
 191                           "five", FeatureSet(), {"index"}));
 192     ASSERT_OK(db_->Insert(WriteOptions(), BoundingBox<double>(1, 65, 47, 95),
 193                           "six", FeatureSet(), {"index"}));
 194
 195     if (iter == 1) {
 196       delete db_;
 197       db_ = nullptr;
 198       ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_, true));
 199     }
 200
 201     AssertCursorResults(BoundingBox<double>(33, 17, 47, 31), "index", {"one"});
 202     AssertCursorResults(BoundingBox<double>(17, 33, 79, 63), "index",
 203                         {"one", "three"});
 204     AssertCursorResults(BoundingBox<double>(17, 81, 63, 111), "index",
 205                         {"four", "six"});
 206     AssertCursorResults(BoundingBox<double>(85, 86, 85, 86), "index", {"two"});
 207     AssertCursorResults(BoundingBox<double>(33, 1, 127, 111), "index",
 208                         {"one", "two", "three", "five", "six"});
 209     // even though the bounding box doesn't intersect, we got "four" back
 210     // because
 211     // it's in the same tile
 212     AssertCursorResults(BoundingBox<double>(18, 98, 19, 99), "index", {"four"});
 213     AssertCursorResults(BoundingBox<double>(130, 130, 131, 131), "index", {});
 214     AssertCursorResults(BoundingBox<double>(81, 17, 127, 31), "index", {});
 215     AssertCursorResults(BoundingBox<double>(90, 50, 91, 51), "index",
 216                         {"three", "five"});
 217
 218     delete db_;
 219     db_ = nullptr;
 220   }
 221 }
 222
 223 namespace {
 224 std::string RandomStr(Random* rnd) {
 225   std::string r;
 226   for (int k = 0; k < 10; ++k) {
 227     r.push_back(static_cast<char>(rnd->Uniform(26)) + 'a');
 228   }
 229   return r;
 230 }
 231
 232 BoundingBox<int> RandomBoundingBox(int limit, Random* rnd, int max_size) {
 233   BoundingBox<int> r;
 234   r.min_x = rnd->Uniform(limit - 1);
 235   r.min_y = rnd->Uniform(limit - 1);
 236   r.max_x = r.min_x + rnd->Uniform(std::min(limit - 1 - r.min_x, max_size)) + 1;
 237   r.max_y = r.min_y + rnd->Uniform(std::min(limit - 1 - r.min_y, max_size)) + 1;
 238   return r;
 239 }
 240
 241 BoundingBox<double> ScaleBB(BoundingBox<int> b, double step) {
 242   return BoundingBox<double>(b.min_x * step + 1, b.min_y * step + 1,
 243                              (b.max_x + 1) * step - 1,
 244                              (b.max_y + 1) * step - 1);
 245 }
 246
 247 }  // namespace
 248
 249 TEST_F(SpatialDBTest, RandomizedTest) {
 250   if (!LZ4_Supported()) {
 251     return;
 252   }
 253   Random rnd(301);
 254   std::vector<std::pair<std::string, BoundingBox<int>>> elements;
 255
 256   BoundingBox<double> spatial_index_bounds(0, 0, (1LL << 32), (1LL << 32));
 257   ASSERT_OK(SpatialDB::Create(
 258       SpatialDBOptions(), dbname_,
 259       {SpatialIndexOptions("index", spatial_index_bounds, 7)}));
 260   ASSERT_OK(SpatialDB::Open(SpatialDBOptions(), dbname_, &db_));
 261   double step = (1LL << 32) / (1 << 7);
 262
 263   for (int i = 0; i < 1000; ++i) {
 264     std::string blob = RandomStr(&rnd);
 265     BoundingBox<int> bbox = RandomBoundingBox(128, &rnd, 10);
 266     ASSERT_OK(db_->Insert(WriteOptions(), ScaleBB(bbox, step), blob,
 267                           FeatureSet(), {"index"}));
 268     elements.push_back(make_pair(blob, bbox));
 269   }
 270
 271   // parallel
 272   db_->Compact(2);
 273   // serial
 274   db_->Compact(1);
 275
 276   for (int i = 0; i < 1000; ++i) {
 277     BoundingBox<int> int_bbox = RandomBoundingBox(128, &rnd, 10);
 278     BoundingBox<double> double_bbox = ScaleBB(int_bbox, step);
 279     std::vector<std::string> blobs;
 280     for (auto e : elements) {
 281       if (e.second.Intersects(int_bbox)) {
 282         blobs.push_back(e.first);
 283       }
 284     }
 285     AssertCursorResults(double_bbox, "index", blobs);
 286   }
 287
 288   delete db_;
 289 }
 290
 291 }  // namespace spatial
 292 }  // namespace rocksdb
 293
 294 int main(int argc, char** argv) {
 295   ::testing::InitGoogleTest(&argc, argv);
 296   return RUN_ALL_TESTS();
 297 }
 298
 299 #else
 300 #include <stdio.h>
 301
 302 int main(int /*argc*/, char** /*argv*/) {
 303   fprintf(stderr, "SKIPPED as SpatialDB is not supported in ROCKSDB_LITE\n");
 304   return 0;
 305 }
 306
 307 #endif  // !ROCKSDB_LITE