You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2021/11/24 15:29:43 UTC
[GitHub] [druid] yuanlihan opened a new pull request #11987: Add two new array functions to Druid
yuanlihan opened a new pull request #11987:
URL: https://github.com/apache/druid/pull/11987
### Description
This PR adds two new array function to Druid.
| function | description |
| --- | --- |
| array_contains_contiguous_subarray(arr,expr) | returns 1 if the array contains the element specified by expr, or contains contiguous subarray(see [substring](https://en.wikipedia.org/wiki/Substring)) specified by expr if expr is an array, else 0 |
| array_contains_subsequence(arr,expr) | returns 1 if the array contains the element specified by expr, or contains [subsequence](https://en.wikipedia.org/wiki/Subsequence) specified by expr if expr is an array, else 0 |
The two array functions can be typically used as filters on [multi-value dimensions](https://druid.apache.org/docs/latest/querying/multi-value-dimensions.html) to do funnel analysis for user behaviour analytics.
Below is a simple example of user behaviour data
```json
{"timestamp": "2011-01-12T00:00:00.000Z", "user": "id1", "events": ["login","home","search"]}
{"timestamp": "2011-01-13T00:00:00.000Z", "user": "id2", "events": ["home","search","shop"]}
{"timestamp": "2011-01-14T00:00:00.000Z", "user": "id3", "events": ["home","product","cart"]}
```
We can query how many users get through a series of steps
```sql
select APPROX_COUNT_DISTINCT(user) from ds_name where MV_CONTAINS_SUBSEQUENCE(events, ARRAY['home', 'product'])
```
##### Key changed/added classes in this PR
* `Function`
* `ArrayContainsSubsequenceOperatorConversion`
* `ArrayContainsContiguousSubarrayOperatorConversion`
* `MultiValueStringOperatorConversions`
<hr>
<!-- Check the items by putting "x" in the brackets for the done things. Not all of these items apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items from the checklist below are strictly necessary, but it would be very helpful if you at least self-review the PR. -->
This PR has:
- [X] been self-reviewed.(Remove this item if the PR doesn't have any relation to concurrency.)
- [X] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
- [X] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [X] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
- [ ] added integration tests.
- [X] been tested in a test Druid cluster.
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] LakshSingla commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
LakshSingla commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r756636906
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
The implementation seems to have complexity of O(length1 * length2), which seems suboptimal if we used something like [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). Maybe something like [Collections#indexOfSublist](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList%28java.util.List,%20java.util.List%29) can be better, but it seems that it might be using the same algorithm underneath. In any case, I think it could be optimized further, and we might not wanna go with the naive implementation [String searching](https://en.wikipedia.org/wiki/String-searching_algorithm#Examples_of_search_algorithms)
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r760735640
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
Hi @LakshSingla, thanks for the comment.
> The implementation seems to have complexity of O(length1 * (length1-length2)), which seems suboptimal if we used something like KMP. Maybe something like Collections#indexOfSublist can be better, but it seems that it might be using the same algorithm underneath. In any case, I think it could be optimized further, and we might not wanna go with the naive implementation if the operands we expect have can have a decent length. String searching
I got your point that you're concerned about the performance of the array function here. Actually, during SQL function translation, it'll try to void unnecessary array comparing by leveraging a serial of dimension filters which can use Druid's bitmap index to speed up filtering.
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] LakshSingla commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
LakshSingla commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r756636906
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
The implementation seems to have complexity of `O(length1 * (length1-length2))`, which seems suboptimal if we used something like [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). Maybe something like [Collections#indexOfSublist](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList%28java.util.List,%20java.util.List%29) can be better, but it seems that it might be using the same algorithm underneath. In any case, I think it could be optimized further, and we might not wanna go with the naive implementation if the operands we expect have can have a decent length. [String searching](https://en.wikipedia.org/wiki/String-searching_algorithm#Examples_of_search_algorithms)
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] LakshSingla commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
LakshSingla commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r756636906
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
The implementation seems to have complexity of `O(length1 * length2)`, which seems suboptimal if we used something like [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). Maybe something like [Collections#indexOfSublist](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList%28java.util.List,%20java.util.List%29) can be better, but it seems that it might be using the same algorithm underneath. In any case, I think it could be optimized further, and we might not wanna go with the naive implementation [String searching](https://en.wikipedia.org/wiki/String-searching_algorithm#Examples_of_search_algorithms)
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] LakshSingla commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
LakshSingla commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r756636906
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
The implementation seems to have complexity of O(length1 * length2), which seems suboptimal if we used something like [KMP](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). Maybe something like [Collections#indexOfSublist](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#indexOfSubList%28java.util.List,%20java.util.List%29) can be better.
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] yuanlihan commented on a change in pull request #11987: Add two new array functions to Druid
Posted by GitBox <gi...@apache.org>.
yuanlihan commented on a change in pull request #11987:
URL: https://github.com/apache/druid/pull/11987#discussion_r760735640
##########
File path: core/src/main/java/org/apache/druid/math/expr/Function.java
##########
@@ -3422,6 +3422,100 @@ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
}
}
+ class ArrayContainsContiguousSubarrayFunction extends ArraysFunction
+ {
+ @Override
+ public String name()
+ {
+ return "array_contains_contiguous_subarray";
+ }
+
+ @Override
+ public boolean hasArrayOutput()
+ {
+ return true;
+ }
+
+ @Nullable
+ @Override
+ public ExpressionType getOutputType(Expr.InputBindingInspector inputTypes, List<Expr> args)
+ {
+ return ExpressionType.LONG;
+ }
+
+ @Override
+ ExprEval doApply(ExprEval lhsExpr, ExprEval rhsExpr)
Review comment:
Hi @LakshSingla, thanks for the comment.
> The implementation seems to have complexity of O(length1 * (length1-length2)), which seems suboptimal if we used something like KMP. Maybe something like Collections#indexOfSublist can be better, but it seems that it might be using the same algorithm underneath. In any case, I think it could be optimized further, and we might not wanna go with the naive implementation if the operands we expect have can have a decent length. String searching
I got your point that you're concerned about the performance of the array function here. Actually, during SQL function translation, it'll try to void necessary array comparing by leveraging a serial of dimension filters which can use Druid's bitmap index to speed up filtering.
--
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.
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org