You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ignite.apache.org by GitBox <gi...@apache.org> on 2021/07/06 17:09:47 UTC
[GitHub] [ignite] xtern opened a new pull request #9234: IGNITE-14816 Replace map to list in RuntimeIndex.
xtern opened a new pull request #9234:
URL: https://github.com/apache/ignite/pull/9234
Thank you for submitting the pull request to the Apache Ignite.
In order to streamline the review of the contribution
we ask you to ensure the following steps have been taken:
### The Contribution Checklist
- [ ] There is a single JIRA ticket related to the pull request.
- [ ] The web-link to the pull request is attached to the JIRA ticket.
- [ ] The JIRA ticket has the _Patch Available_ state.
- [ ] The pull request body describes changes that have been made.
The description explains _WHAT_ and _WHY_ was made instead of _HOW_.
- [ ] The pull request title is treated as the final commit message.
The following pattern must be used: `IGNITE-XXXX Change summary` where `XXXX` - number of JIRA issue.
- [ ] A reviewer has been mentioned through the JIRA comments
(see [the Maintainers list](https://cwiki.apache.org/confluence/display/IGNITE/How+to+Contribute#HowtoContribute-ReviewProcessandMaintainers))
- [ ] The pull request has been checked by the Teamcity Bot and
the `green visa` attached to the JIRA ticket (see [TC.Bot: Check PR](https://mtcga.gridgain.com/prs.html))
### Notes
- [How to Contribute](https://cwiki.apache.org/confluence/display/IGNITE/How+to+Contribute)
- [Coding abbreviation rules](https://cwiki.apache.org/confluence/display/IGNITE/Abbreviation+Rules)
- [Coding Guidelines](https://cwiki.apache.org/confluence/display/IGNITE/Coding+Guidelines)
- [Apache Ignite Teamcity Bot](https://cwiki.apache.org/confluence/display/IGNITE/Apache+Ignite+Teamcity+Bot)
If you need any help, please email dev@ignite.apache.org or ask anу advice on http://asf.slack.com _#ignite_ channel.
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [ignite] alex-plekhanov commented on a change in pull request #9234: IGNITE-14816
Posted by GitBox <gi...@apache.org>.
alex-plekhanov commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r673033919
##########
File path: modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -113,49 +104,65 @@ else if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get
}
/**
- *
+ * Cursor to navigate through a sorted list with duplicates.
*/
private class Cursor implements GridCursor<Row> {
- /** Sub map iterator. */
- private final Iterator<Map.Entry<Row, List<Row>>> mapIt;
+ /** List of rows. */
+ private final List<Row> rows;
- /** Iterator over rows with equal index keys. */
- private Iterator<Row> listIt;
+ /** Upper bound. */
+ private final Row upper;
- /** */
+ /** Current row. */
private Row row;
- /** */
- Cursor(SortedMap<Row, List<Row>> subMap) {
- mapIt = subMap.entrySet().iterator();
- listIt = null;
- }
+ /** Current index of list element. */
+ private int idx;
- /** {@inheritDoc} */
- @Override public boolean next() throws IgniteCheckedException {
- if (!hasNext())
- return false;
-
- next0();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound (inclusive).
+ * @param upper Upper bound (inclusive).
+ */
+ Cursor(List<Row> rows, @Nullable Row lower, @Nullable Row upper) {
+ this.rows = rows;
+ this.upper = upper;
- return true;
+ idx = computeStartIdx(rows, lower) - 1;
}
- /** */
- private boolean hasNext() {
- return listIt != null && listIt.hasNext() || mapIt.hasNext();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound.
+ * @return Lower bound position in the list.
+ */
+ private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
+ int fromIdx = lower == null ? -1 : Collections.binarySearch(rows, lower, comp);
+
+ if (fromIdx < 0)
+ fromIdx = -fromIdx - 1;
+ else {
+ // Skip duplcates.
+ while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1), rows.get(fromIdx)) == 0)
Review comment:
What if there is only one distinct value? In this case algorithm downgrade to O(n) instead of O(ln(n))
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [ignite] alex-plekhanov commented on a change in pull request #9234: IGNITE-14816
Posted by GitBox <gi...@apache.org>.
alex-plekhanov commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r679241290
##########
File path: modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -128,35 +127,41 @@ else if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get
this.rows = rows;
this.upper = upper;
- idx = computeStartIdx(rows, lower) - 1;
+ idx = lower == null ? 0 : lowerBound(rows, lower);
}
/**
+ * Searches the lower bound (skipping duplicates) using a binary search.
+ *
* @param rows List of rows.
- * @param lower Lower bound.
+ * @param target Lower bound.
* @return Lower bound position in the list.
*/
- private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
- int fromIdx = lower == null ? -1 : Collections.binarySearch(rows, lower, comp);
-
- if (fromIdx < 0)
- fromIdx = -fromIdx - 1;
- else {
- // Skip duplcates.
- while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1), rows.get(fromIdx)) == 0)
- --fromIdx;
+ private int lowerBound(List<Row> rows, Row target) {
+ int low = 0, high = rows.size() - 1, idx = -1;
+
+ while (low <= high) {
+ int mid = (high - low) / 2 + low;
+
+ if (comp.compare(rows.get(mid), target) > 0)
+ high = mid - 1;
+ else if (comp.compare(rows.get(mid), target) == 0) {
Review comment:
Let's store the comparison result and check only the result here (avoid double `compare` call)
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [ignite] alex-plekhanov commented on a change in pull request #9234: IGNITE-14816
Posted by GitBox <gi...@apache.org>.
alex-plekhanov commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r673033919
##########
File path: modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -113,49 +104,65 @@ else if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get
}
/**
- *
+ * Cursor to navigate through a sorted list with duplicates.
*/
private class Cursor implements GridCursor<Row> {
- /** Sub map iterator. */
- private final Iterator<Map.Entry<Row, List<Row>>> mapIt;
+ /** List of rows. */
+ private final List<Row> rows;
- /** Iterator over rows with equal index keys. */
- private Iterator<Row> listIt;
+ /** Upper bound. */
+ private final Row upper;
- /** */
+ /** Current row. */
private Row row;
- /** */
- Cursor(SortedMap<Row, List<Row>> subMap) {
- mapIt = subMap.entrySet().iterator();
- listIt = null;
- }
+ /** Current index of list element. */
+ private int idx;
- /** {@inheritDoc} */
- @Override public boolean next() throws IgniteCheckedException {
- if (!hasNext())
- return false;
-
- next0();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound (inclusive).
+ * @param upper Upper bound (inclusive).
+ */
+ Cursor(List<Row> rows, @Nullable Row lower, @Nullable Row upper) {
+ this.rows = rows;
+ this.upper = upper;
- return true;
+ idx = computeStartIdx(rows, lower) - 1;
}
- /** */
- private boolean hasNext() {
- return listIt != null && listIt.hasNext() || mapIt.hasNext();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound.
+ * @return Lower bound position in the list.
+ */
+ private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
+ int fromIdx = lower == null ? -1 : Collections.binarySearch(rows, lower, comp);
+
+ if (fromIdx < 0)
+ fromIdx = -fromIdx - 1;
+ else {
+ // Skip duplcates.
+ while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1), rows.get(fromIdx)) == 0)
Review comment:
What if there is only one distinct value? In this case algorithm downgrade to O(n) instead of O(ln(n))
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [ignite] xtern commented on a change in pull request #9234: IGNITE-14816
Posted by GitBox <gi...@apache.org>.
xtern commented on a change in pull request #9234:
URL: https://github.com/apache/ignite/pull/9234#discussion_r674337529
##########
File path: modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/exec/RuntimeSortedIndex.java
##########
@@ -113,49 +104,65 @@ else if (ectx.rowHandler().get(firstCol, lower) != null && ectx.rowHandler().get
}
/**
- *
+ * Cursor to navigate through a sorted list with duplicates.
*/
private class Cursor implements GridCursor<Row> {
- /** Sub map iterator. */
- private final Iterator<Map.Entry<Row, List<Row>>> mapIt;
+ /** List of rows. */
+ private final List<Row> rows;
- /** Iterator over rows with equal index keys. */
- private Iterator<Row> listIt;
+ /** Upper bound. */
+ private final Row upper;
- /** */
+ /** Current row. */
private Row row;
- /** */
- Cursor(SortedMap<Row, List<Row>> subMap) {
- mapIt = subMap.entrySet().iterator();
- listIt = null;
- }
+ /** Current index of list element. */
+ private int idx;
- /** {@inheritDoc} */
- @Override public boolean next() throws IgniteCheckedException {
- if (!hasNext())
- return false;
-
- next0();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound (inclusive).
+ * @param upper Upper bound (inclusive).
+ */
+ Cursor(List<Row> rows, @Nullable Row lower, @Nullable Row upper) {
+ this.rows = rows;
+ this.upper = upper;
- return true;
+ idx = computeStartIdx(rows, lower) - 1;
}
- /** */
- private boolean hasNext() {
- return listIt != null && listIt.hasNext() || mapIt.hasNext();
+ /**
+ * @param rows List of rows.
+ * @param lower Lower bound.
+ * @return Lower bound position in the list.
+ */
+ private int computeStartIdx(List<Row> rows, @Nullable Row lower) {
+ int fromIdx = lower == null ? -1 : Collections.binarySearch(rows, lower, comp);
+
+ if (fromIdx < 0)
+ fromIdx = -fromIdx - 1;
+ else {
+ // Skip duplcates.
+ while (fromIdx > 0 && comp.compare(rows.get(fromIdx - 1), rows.get(fromIdx)) == 0)
Review comment:
Skipping duplicates updated.
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org