You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "kgyrtkirk (via GitHub)" <gi...@apache.org> on 2023/09/19 15:25:26 UTC
[PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
kgyrtkirk opened a new pull request, #15012:
URL: https://github.com/apache/druid/pull/15012
`MV_FILTER_ONLY` assumed that there are no duplicates in their input; however that may not be true - as if the values are run thru a function (like `LOOKUP`) - that property may change.
This changeset changes the preallocated output size to be assomptical with the number of inputs instead of clamping at the size of the filtering array.
<!-- Thanks for trying to help us make Apache Druid be the best it can be! Please fill out as much of the following information as is possible (where relevant, and remove it when irrelevant) to help make the intention and scope of this PR clear in order to ease review. -->
<!-- Please read the doc for contribution (https://github.com/apache/druid/blob/master/CONTRIBUTING.md) before making this PR. Also, once you open a PR, please _avoid using force pushes and rebasing_ since these make it difficult for reviewers to see what you've changed in response to their reviews. See [the 'If your pull request shows conflicts with master' section](https://github.com/apache/druid/blob/master/CONTRIBUTING.md#if-your-pull-request-shows-conflicts-with-master) for more details. -->
Fixes #XXXX.
<!-- Replace XXXX with the id of the issue fixed in this PR. Remove this section if there is no corresponding issue. Don't reference the issue in the title of this pull-request. -->
<!-- If you are a committer, follow the PR action item checklist for committers:
https://github.com/apache/druid/blob/master/dev/committer-instructions.md#pr-and-issue-action-item-checklist-for-committers. -->
### Description
<!-- Describe the goal of this PR, what problem are you fixing. If there is a corresponding issue (referenced above), it's not necessary to repeat the description here, however, you may choose to keep one summary sentence. -->
<!-- Describe your patch: what did you change in code? How did you fix the problem? -->
<!-- If there are several relatively logically separate changes in this PR, create a mini-section for each of them. For example: -->
#### Fixed the bug ...
#### Renamed the class ...
#### Added a forbidden-apis entry ...
<!--
In each section, please describe design decisions made, including:
- Choice of algorithms
- Behavioral aspects. What configuration values are acceptable? How are corner cases and error conditions handled, such as when there are insufficient resources?
- Class organization and design (how the logic is split between classes, inheritance, composition, design patterns)
- Method organization and design (how the logic is split between methods, parameters and return types)
- Naming (class, method, API, configuration, HTTP endpoint, names of emitted metrics)
-->
<!-- It's good to describe an alternative design (or mention an alternative name) for every design (or naming) decision point and compare the alternatives with the designs that you've implemented (or the names you've chosen) to highlight the advantages of the chosen designs and names. -->
<!-- If there was a discussion of the design of the feature implemented in this PR elsewhere (e. g. a "Proposal" issue, any other issue, or a thread in the development mailing list), link to that discussion from this PR description and explain what have changed in your final design compared to your original proposal or the consensus version in the end of the discussion. If something hasn't changed since the original discussion, you can omit a detailed discussion of those aspects of the design here, perhaps apart from brief mentioning for the sake of readability of this PR description. -->
<!-- Some of the aspects mentioned above may be omitted for simple and small changes. -->
#### Release note
<!-- Give your best effort to summarize your changes in a couple of sentences aimed toward Druid users.
If your change doesn't have end user impact, you can skip this section.
For tips about how to write a good release note, see [Release notes](https://github.com/apache/druid/blob/master/CONTRIBUTING.md#release-notes).
-->
<hr>
##### Key changed/added classes in this PR
* `MyFoo`
* `OurBar`
* `TheirBaz`
<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:
- [ ] been self-reviewed.
- [ ] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] a release note entry in the PR description.
- [ ] 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)
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [ ] 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.
- [ ] 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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330923205
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
for (String value : values) {
int i = idLookup.lookupId(value);
if (i >= 0) {
builder.addMapping(i);
}
}
} else {
+ builder = IdMapping.Builder.ofCardinality(cardinality);
Review Comment:
Hmm, I don't think we probably want to do this like this, rather, I think we wan to switch [`IdMapping.Builder` to use a growable collection like `IntList` instead of `int[]` for the `reverseMapping`](https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/segment/IdMapping.java#L102) to handle this case where the ids are a many to one mapping because of something like a lookup extraction fn being used. The reason is because for something like `MV_FILTER_ONLY`, the cardinality of the column might be like 1 million, while the cardinality of the values supplied to the function might just be a few values, so allocating a whole `int[]` for the complete cardinality of the column seems pretty dramatic.
We could potentially optimize this in some manner by checking for extractionFn, and [if the extractionFn extraction type is one to one, and only do this path if it is many to one, but I don't think its really needed](https://github.com/apache/druid/blob/master/processing/src/main/java/org/apache/druid/query/extraction/ExtractionFn.java#L118).
This matters a lot less for a deny list, which likely will still have a cardinality close to the base column.
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
Review Comment:
i think this could also be impacted the same way as the other branch, so I don't really think this fixes things (though it does the virtual column since it uses the 'else' branch here
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330969196
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
for (String value : values) {
int i = idLookup.lookupId(value);
if (i >= 0) {
builder.addMapping(i);
}
}
} else {
+ builder = IdMapping.Builder.ofCardinality(cardinality);
Review Comment:
ok, ignore all of this, we talked about this offline, but to capture that discussion here: I think the _real_ right thing to do here is have `ListFilteredVirtualColumn` and `ListFilteredDimensionSpec` force use of `PredicateFilteredDimensionSelector` whenever the extractionFn is present on the `delegate` `DimensionSpec`, for both allow or deny lists.
Additionally `ListFilteredVirtualColumn` also should return `NoIndexesColumnIndexSupplier.getInstance()` whenever `getIndexSupplier` is called and the `delegate` has an `extractionFn`.
The reason is that use of `IdMapping` requires a 1:1 relation between the filtered dimension and underlying dimension, and that isn't really possible to do with a many to one lookup.
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330926155
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
Review Comment:
I was thinking this might get into similar troubles - but then noticed that: this branch uses a foreach on the `values` ; so it may make at-most `|values|` calls to `addMapping` - so I think its safe to leave it like this.
...hmm...but I'm wondering if I've misunderstood your comment: what did you mean by "impacted the same way" - the exception issue; or some perf stuff?
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "kgyrtkirk (via GitHub)" <gi...@apache.org>.
kgyrtkirk commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330942408
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
for (String value : values) {
int i = idLookup.lookupId(value);
if (i >= 0) {
builder.addMapping(i);
}
}
} else {
+ builder = IdMapping.Builder.ofCardinality(cardinality);
Review Comment:
I didn't wanted to change that class - but it makes sense to do so.
with auto-growing available this second branch doesn't cause any issues; so I've undone the changes to this part.
btw: I'm wondering in case it reports 1-to-1 - wouldn't that still map unknown values to `null` ? ...so if there is a `null` in the input `values` it could still have more matches - but anyway this will work correctly with the current approach
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "rohangarg (via GitHub)" <gi...@apache.org>.
rohangarg commented on PR #15012:
URL: https://github.com/apache/druid/pull/15012#issuecomment-1737444364
The CI failures were due to the flakiness in some of the IT jobs which are unrelated - repeated rerunning of them didn't let us get pass the setup issue we were running into, hence merging this.
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "rohangarg (via GitHub)" <gi...@apache.org>.
rohangarg merged PR #15012:
URL: https://github.com/apache/druid/pull/15012
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330919799
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
Review Comment:
i think this could also be impacted the same way as the other branch, so I don't really think this fixes things (though it does the virtual column since it uses the 'else' branch here)
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1330943355
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -92,15 +92,17 @@ public static IdMapping buildAllowListIdMapping(
IndexedGetter<String> fn
)
{
- final IdMapping.Builder builder = IdMapping.Builder.ofCardinality(values.size());
+ IdMapping.Builder builder;
if (idLookup != null) {
+ builder = IdMapping.Builder.ofCardinality(values.size());
for (String value : values) {
int i = idLookup.lookupId(value);
if (i >= 0) {
builder.addMapping(i);
}
}
} else {
+ builder = IdMapping.Builder.ofCardinality(cardinality);
Review Comment:
hmm, actually is that right? Thinking a bit more about this, maybe I'm wrong and reverse mapping actually needs to be a list of ints associated with each value if there is a many to one mapping.. which introduces a lot of extra complexity in places (i've also found some bugs in the index supplier implementation of this virtual column). Let me think a bit more about this...
--
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
Re: [PR] MV_FILTER_ONLY may run into Exceptions in case duplicate values were processed (druid)
Posted by "github-code-scanning[bot] (via GitHub)" <gi...@apache.org>.
github-code-scanning[bot] commented on code in PR #15012:
URL: https://github.com/apache/druid/pull/15012#discussion_r1331012134
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -79,9 +79,9 @@
}
if (isWhitelist) {
- return filterAllowList(values, selector);
+ return filterAllowList(values, selector, delegate.getExtractionFn() != null);
Review Comment:
## Deprecated method or constructor invocation
Invoking [DimensionSpec.getExtractionFn](1) should be avoided because it has been deprecated.
[Show more details](https://github.com/apache/druid/security/code-scanning/5802)
##########
processing/src/main/java/org/apache/druid/segment/virtual/ListFilteredVirtualColumn.java:
##########
@@ -136,9 +137,9 @@
)
{
if (allowList) {
- return ListFilteredDimensionSpec.filterAllowList(values, factory.makeDimensionSelector(delegate));
+ return ListFilteredDimensionSpec.filterAllowList(values, factory.makeDimensionSelector(delegate), delegate.getExtractionFn() != null);
Review Comment:
## Deprecated method or constructor invocation
Invoking [DimensionSpec.getExtractionFn](1) should be avoided because it has been deprecated.
[Show more details](https://github.com/apache/druid/security/code-scanning/5804)
##########
processing/src/main/java/org/apache/druid/query/dimension/ListFilteredDimensionSpec.java:
##########
@@ -79,9 +79,9 @@
}
if (isWhitelist) {
- return filterAllowList(values, selector);
+ return filterAllowList(values, selector, delegate.getExtractionFn() != null);
} else {
- return filterDenyList(values, selector);
+ return filterDenyList(values, selector, delegate.getExtractionFn() != null);
Review Comment:
## Deprecated method or constructor invocation
Invoking [DimensionSpec.getExtractionFn](1) should be avoided because it has been deprecated.
[Show more details](https://github.com/apache/druid/security/code-scanning/5803)
##########
processing/src/main/java/org/apache/druid/segment/virtual/ListFilteredVirtualColumn.java:
##########
@@ -136,9 +137,9 @@
)
{
if (allowList) {
- return ListFilteredDimensionSpec.filterAllowList(values, factory.makeDimensionSelector(delegate));
+ return ListFilteredDimensionSpec.filterAllowList(values, factory.makeDimensionSelector(delegate), delegate.getExtractionFn() != null);
} else {
- return ListFilteredDimensionSpec.filterDenyList(values, factory.makeDimensionSelector(delegate));
+ return ListFilteredDimensionSpec.filterDenyList(values, factory.makeDimensionSelector(delegate), delegate.getExtractionFn() != null);
Review Comment:
## Deprecated method or constructor invocation
Invoking [DimensionSpec.getExtractionFn](1) should be avoided because it has been deprecated.
[Show more details](https://github.com/apache/druid/security/code-scanning/5805)
##########
processing/src/main/java/org/apache/druid/segment/virtual/ListFilteredVirtualColumn.java:
##########
@@ -182,6 +183,9 @@
@Override
public ColumnIndexSupplier getIndexSupplier(String columnName, ColumnSelector columnSelector)
{
+ if (delegate.getExtractionFn() != null) {
Review Comment:
## Deprecated method or constructor invocation
Invoking [DimensionSpec.getExtractionFn](1) should be avoided because it has been deprecated.
[Show more details](https://github.com/apache/druid/security/code-scanning/5806)
--
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