You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by GitBox <gi...@apache.org> on 2020/10/27 07:29:57 UTC
[GitHub] [incubator-doris] Youngwb opened a new pull request #4803: [Feature] Add Topn udaf
Youngwb opened a new pull request #4803:
URL: https://github.com/apache/incubator-doris/pull/4803
## Proposed changes
For #4674
This is a udaf for approximate topn using Space-Saving algorithm. At present, we can only calculate the frequent items and their frequencies in a certain column, based on which we can implement similar topN functions supported by Kylin in the future.
I have also added a test to calculate the accuracy of this algorithm. The following is a rough running result. The total amount of data is 1 million lines and follows the Zipfian distribution, where Element Cardinality represents the data cardinality, 20X, 50X.. The value representing space_expand_rate is 20,50, which is used to set the counter number in the space-saving algorithm
```
zf exponent = 0.5
Element cardinality 20X 50X 100X
1000 100% 100% 100%
10000 100% 100% 100%
100000 100% 100% 100%
500000 94% 98% 99%
zf exponent = 0.6，1
Element cardinality 20X 50X 100X
1000 100% 100% 100%
10000 100% 100% 100%
100000 100% 100% 100%
500000 100% 100% 100%
```
## Types of changes
What types of changes does your code introduce to Doris?
_Put an `x` in the boxes that apply_
- [] Bugfix (non-breaking change which fixes an issue)
- [x] New feature (non-breaking change which adds functionality)
- [] Breaking change (fix or feature that would cause existing functionality to not work as expected)
- [] Documentation Update (if none of the other choices apply)
- [] Code refactor (Modify the code structure, format the code, etc...)
## Checklist
_Put an `x` in the boxes that apply. You can also fill these out after creating the PR. If you're unsure about any of them, don't hesitate to ask. We're here to help! This is simply a reminder of what we are going to look for before merging your code._
- [x] I have create an issue on (Fix #ISSUE), and have described the bug/feature there in detail
- [x] Compiling and unit tests pass locally with my changes
- [x] I have added tests that prove my fix is effective or that my feature works
- [x] If this change need a document change, I have updated the document
- [] Any dependent changes have been merged
## Further comments
If this is a relatively large or complex change, kick off the discussion at dev@doris.apache.org by explaining why you chose the solution you did and what alternatives you considered, etc...
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [incubator-doris] morningman commented on a change in pull request #4803: [Feature] Add Topn udaf
Posted by GitBox <gi...@apache.org>.
morningman commented on a change in pull request #4803:
URL: https://github.com/apache/incubator-doris/pull/4803#discussion_r528203668
##########
File path: gensrc/proto/olap_common.proto
##########
@@ -48,3 +48,14 @@ enum CompressKind {
COMPRESS_LZ4 = 2;
}
+message PCounter {
+ required string item = 1;
+ required uint64 count = 2;
Review comment:
```suggestion
required uint64 count = 2;
```
##########
File path: be/src/util/topn_counter.cpp
##########
@@ -0,0 +1,138 @@
+// 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 <algorithm>
+#include "gen_cpp/olap_common.pb.h"
+#include "topn_counter.h"
+#include "slice.h"
+
+namespace doris {
+
+void TopNCounter::add_item(const std::string& item, uint64_t incrementCount) {
+ auto iter = _counter_map->find(item);
+ if (iter != _counter_map->end()) {
+ iter->second.add_count(incrementCount);
+ } else {
+ _counter_map->insert(std::make_pair(item, Counter(item, incrementCount)));
+ }
+ _ordered = false;
+}
+
+void TopNCounter::serialize(std::string* buffer) {
+ sort_retain(_capacity);
+ PTopNCounter topn_counter;
+ topn_counter.set_top_num(_top_num);
+ topn_counter.set_space_expand_rate(_space_expand_rate);
+ for(std::vector<Counter>::const_iterator it = _counter_vec->begin(); it != _counter_vec->end(); ++it)
+ {
+ PCounter* counter = topn_counter.add_counter();
+ counter->set_item(it->get_item());
+ counter->set_count(it->get_count());
+ }
+ topn_counter.SerializeToString(buffer);
+}
+
+bool TopNCounter::deserialize(const doris::Slice &src) {
+ PTopNCounter topn_counter;
+ if (!topn_counter.ParseFromArray(src.data, src.size)) {
+ LOG(WARNING) << "topn counter deserialize failed";
+ return false;
+ }
+
+ _space_expand_rate = topn_counter.space_expand_rate();
+ set_top_num(topn_counter.top_num());
+ for (int i = 0; i < topn_counter.counter_size(); ++i) {
+ const PCounter& counter = topn_counter.counter(i);
+ _counter_map->insert(std::make_pair(counter.item(), Counter(counter.item(), counter.count())));
+ _counter_vec->emplace_back(counter.item(), counter.count());
+ }
+ _ordered = true;
+ return true;
+}
+
+void TopNCounter::sort_retain(uint32_t capacity) {
+ _counter_vec->clear();
+ sort_retain(capacity, _counter_vec);
+ _ordered = true;
+}
+
+void TopNCounter::sort_retain(uint32_t capacity, std::vector<Counter>* sort_vec) {
+ for(std::unordered_map<std::string, Counter>::const_iterator it = _counter_map->begin(); it != _counter_map->end(); ++it) {
+ sort_vec->emplace_back(it->second.get_item(), it->second.get_count());
+ }
+
+ std::sort(sort_vec->begin(), sort_vec->end(), TopNComparator());
+ if (sort_vec->size() > capacity) {
+ for (uint32_t i = 0, n = sort_vec->size() - capacity; i < n; ++i) {
+ auto &counter = sort_vec->back();
+ _counter_map->erase(counter.get_item());
+ sort_vec->pop_back();
+ }
+ }
+}
+
+// Based on the parallel version of the Space Saving algorithm as described in:
+// A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution by Massimo Cafaro, et al.
+void TopNCounter::merge(doris::TopNCounter &&other) {
+ if (other._counter_map->size() == 0) {
+ return;
+ }
+
+ _space_expand_rate = other._space_expand_rate;
+ set_top_num(other._top_num);
+ bool this_full = _counter_map->size() >= _capacity;
+ bool another_full = other._counter_map->size() >= other._capacity;
+
+ uint64_t m1 = this_full ? _counter_vec->back().get_count() : 0;
+ uint64_t m2 = another_full ? other._counter_vec->back().get_count() : 0;
+
+ if (another_full == true) {
+ for (auto &entry : *(this->_counter_map)) {
+ entry.second.add_count(m2);
+ }
+ }
+
+ for (auto &other_entry : *(other._counter_map)) {
+ auto itr = this->_counter_map->find(other_entry.first);
+ if (itr != _counter_map->end()) {
+ itr->second.add_count(other_entry.second.get_count() - m2);
+ } else {
+ this->_counter_map->insert(std::make_pair(other_entry.first,
+ Counter(other_entry.first,other_entry.second.get_count() + m1)));
+ }
+ }
+ _ordered = false;
+ sort_retain(_capacity);
+}
+
+void TopNCounter::finalize(std::string& finalize_str) {
Review comment:
How about using JSON format output?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [incubator-doris] Youngwb commented on a change in pull request #4803: [Feature] Add Topn udaf
Posted by GitBox <gi...@apache.org>.
Youngwb commented on a change in pull request #4803:
URL: https://github.com/apache/incubator-doris/pull/4803#discussion_r543102074
##########
File path: be/src/util/topn_counter.cpp
##########
@@ -0,0 +1,138 @@
+// 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 <algorithm>
+#include "gen_cpp/olap_common.pb.h"
+#include "topn_counter.h"
+#include "slice.h"
+
+namespace doris {
+
+void TopNCounter::add_item(const std::string& item, uint64_t incrementCount) {
+ auto iter = _counter_map->find(item);
+ if (iter != _counter_map->end()) {
+ iter->second.add_count(incrementCount);
+ } else {
+ _counter_map->insert(std::make_pair(item, Counter(item, incrementCount)));
+ }
+ _ordered = false;
+}
+
+void TopNCounter::serialize(std::string* buffer) {
+ sort_retain(_capacity);
+ PTopNCounter topn_counter;
+ topn_counter.set_top_num(_top_num);
+ topn_counter.set_space_expand_rate(_space_expand_rate);
+ for(std::vector<Counter>::const_iterator it = _counter_vec->begin(); it != _counter_vec->end(); ++it)
+ {
+ PCounter* counter = topn_counter.add_counter();
+ counter->set_item(it->get_item());
+ counter->set_count(it->get_count());
+ }
+ topn_counter.SerializeToString(buffer);
+}
+
+bool TopNCounter::deserialize(const doris::Slice &src) {
+ PTopNCounter topn_counter;
+ if (!topn_counter.ParseFromArray(src.data, src.size)) {
+ LOG(WARNING) << "topn counter deserialize failed";
+ return false;
+ }
+
+ _space_expand_rate = topn_counter.space_expand_rate();
+ set_top_num(topn_counter.top_num());
+ for (int i = 0; i < topn_counter.counter_size(); ++i) {
+ const PCounter& counter = topn_counter.counter(i);
+ _counter_map->insert(std::make_pair(counter.item(), Counter(counter.item(), counter.count())));
+ _counter_vec->emplace_back(counter.item(), counter.count());
+ }
+ _ordered = true;
+ return true;
+}
+
+void TopNCounter::sort_retain(uint32_t capacity) {
+ _counter_vec->clear();
+ sort_retain(capacity, _counter_vec);
+ _ordered = true;
+}
+
+void TopNCounter::sort_retain(uint32_t capacity, std::vector<Counter>* sort_vec) {
+ for(std::unordered_map<std::string, Counter>::const_iterator it = _counter_map->begin(); it != _counter_map->end(); ++it) {
+ sort_vec->emplace_back(it->second.get_item(), it->second.get_count());
+ }
+
+ std::sort(sort_vec->begin(), sort_vec->end(), TopNComparator());
+ if (sort_vec->size() > capacity) {
+ for (uint32_t i = 0, n = sort_vec->size() - capacity; i < n; ++i) {
+ auto &counter = sort_vec->back();
+ _counter_map->erase(counter.get_item());
+ sort_vec->pop_back();
+ }
+ }
+}
+
+// Based on the parallel version of the Space Saving algorithm as described in:
+// A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution by Massimo Cafaro, et al.
+void TopNCounter::merge(doris::TopNCounter &&other) {
+ if (other._counter_map->size() == 0) {
+ return;
+ }
+
+ _space_expand_rate = other._space_expand_rate;
+ set_top_num(other._top_num);
+ bool this_full = _counter_map->size() >= _capacity;
+ bool another_full = other._counter_map->size() >= other._capacity;
+
+ uint64_t m1 = this_full ? _counter_vec->back().get_count() : 0;
+ uint64_t m2 = another_full ? other._counter_vec->back().get_count() : 0;
+
+ if (another_full == true) {
+ for (auto &entry : *(this->_counter_map)) {
+ entry.second.add_count(m2);
+ }
+ }
+
+ for (auto &other_entry : *(other._counter_map)) {
+ auto itr = this->_counter_map->find(other_entry.first);
+ if (itr != _counter_map->end()) {
+ itr->second.add_count(other_entry.second.get_count() - m2);
+ } else {
+ this->_counter_map->insert(std::make_pair(other_entry.first,
+ Counter(other_entry.first,other_entry.second.get_count() + m1)));
+ }
+ }
+ _ordered = false;
+ sort_retain(_capacity);
+}
+
+void TopNCounter::finalize(std::string& finalize_str) {
Review comment:
ok,done
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [incubator-doris] morningman merged pull request #4803: [Feature] Add Topn udaf
Posted by GitBox <gi...@apache.org>.
morningman merged pull request #4803:
URL: https://github.com/apache/incubator-doris/pull/4803
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org