You are viewing a plain text version of this content. The canonical link for it is here.
Posted to gitbox@hive.apache.org by "henrib (via GitHub)" <gi...@apache.org> on 2023/08/14 10:36:28 UTC
[GitHub] [hive] henrib opened a new pull request, #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
henrib opened a new pull request, #4601:
URL: https://github.com/apache/hive/pull/4601
### What changes were proposed in this pull request?
When filtering tables (or table names) through applicable privileges, the current code uses a cartesian product (table to verify * accessible tables). When the number of tables is important (200k) and all (or most) tables are accessible, calling these filters takes a very (very) long time.
This PR improves the current filtering algorithm by first sorting the list of accessible tables (through a TableIndex derived class) and then looping around the tables to filter using a binary-search lookup in that index. Complexity goes from m*n to (m+n)*log(n) improving the performance to acceptable levels.
### Why are the changes needed?
Unacceptable performance for large sets
### Does this PR introduce _any_ user-facing change?
No
### Is the change a dependency upgrade?
No
### How was this patch tested?
Unit tests
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] nrg4878 commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "nrg4878 (via GitHub)" <gi...@apache.org>.
nrg4878 commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1293477967
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
+ return cmp != 0
+ ? cmp
+ : getTableName(left).compareTo(getTableName(right));
+ });
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by Name, tblName
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public T lookup(String dbName, String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = getDbName(item).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(item).compareTo(tableName);
+ }
+ if (cmp < 0)
+ low = mid + 1;
+ else if (cmp > 0)
+ high = mid - 1;
+ else
+ return item; // key found
+ }
+ return null; // key not found.
+ }
}
+ /**
+ * Specialized index for HivePrivilegeObject.
+ */
+ public static class PrivilegeIndex extends TableIndex<HivePrivilegeObject> {
Review Comment:
nit: the name PrivilegeIndex may cause some confusion as we have table/column privileges stored in HMS, and we we have a PrivilegeSynchronizer class that periodically refreshes these. So just a suggestion that we use something like HivePrivilegeObjectIndex or something like that.
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
Review Comment:
nit: Can you please add a bit more context to this and what it is used for. git history can always point back to the jira but better if the class had comments on its purpose.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1297355354
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
@@ -411,4 +418,93 @@ public void testU_DropDataConnector_authorizedUser() {
fail("testU_DropDataConnector_authorizedUser() failed with " + e);
}
}
+
+ /**
+ * Fake tables to test.
+ */
+ private static class TestTable {
+ private final String dbName;
+ private final String tableName;
+
+ private TestTable(String dbName, String tableName) {
+ this.dbName = dbName;
+ this.tableName = tableName;
+ }
+
+ @Override
+ public String toString() {
+ return dbName + "." + tableName;
+ }
+
+ public String getDbName() {
+ return dbName;
+ }
+
+ public String getTableName() {
+ return tableName;
+ }
+ }
+
+
+ private static List<TestTable> createTables(int dbs, int tbls) {
+ List<TestTable> tables = new ArrayList<>(dbs * tbls);
+ for(int d = 0; d < dbs; ++d) {
+ for(int t = 0; t < tbls; ++t) {
+ String dbname = String.format("db%05x", d);
+ String tblName = String.format("tbl%05x", t);
+ tables.add(new TestTable(dbname, tblName));
+ }
+ }
+ return tables;
+ }
+
+ private static final int NUM_DB = 2;
+ private static final int NUM_TBL = 50;
+ @Ignore
+ public void testIndexedTableLookup0() {
Review Comment:
Removed.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1300512829
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
Review Comment:
Indeed, import cleaned.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1303249769
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
@@ -411,4 +411,5 @@ public void testU_DropDataConnector_authorizedUser() {
fail("testU_DropDataConnector_authorizedUser() failed with " + e);
}
}
+
Review Comment:
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.
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1297353143
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
Review Comment:
Javadoc 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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1300512639
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestTablePermissionFilterAlgos.java:
##########
@@ -0,0 +1,274 @@
+/*
+ * 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.
+ */
+
+package org.apache.hadoop.hive.ql.security.authorization.plugin.metastore;
+
+import org.apache.commons.lang3.tuple.ImmutablePair;
+import org.apache.hadoop.hive.ql.security.authorization.plugin.HivePrivilegeObjectUtils;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * This test tries different methods of lookup to try and determine the most efficient in
+ * the particular usage case related to checking tables against permissions.
+ * Note that a meaningful performance test requires at least 20 dbs, 10000 tables per db and 40 loops
+ * on a 2022 laptop.
+ */
+public class TestTablePermissionFilterAlgos {
+ private static final Logger LOGGER = LogManager.getLogger(TestHiveMetaStoreAuthorizer.class);
+ // reduce constants to speed up tests when true, set to false for benchmarking
+ private static final boolean TEST = true;
+ private static final int NUM_DB = TEST? 2 : 20;
+ private static final int NUM_TBL = TEST? 100 : 10000;
+ private static final int NLOOPS = TEST? 1 : 40;
+
+ private final List<TestTable> tables = createTables(NUM_DB, NUM_TBL);
+ // lookup some
+ private final List<TestTable> filtered = tables.stream()
+ .filter(t -> t.getTableName().endsWith("0"))
+ .collect(Collectors.toList());
+
+ /**
+ * Fake tables to test.
+ */
+ private static class TestTable {
+ private int hashCode = -1;
+ private final String dbName;
+ private final String tableName;
+
+ private TestTable(String dbName, String tableName) {
+ this.dbName = dbName;
+ this.tableName = tableName;
+ }
+
+ @Override
+ public String toString() {
+ return tableFullName(this);
+ }
+
+ public String getDbName() {
+ return dbName;
+ }
+
+ public String getTableName() {
+ return tableName;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o instanceof TestTable) {
+ TestTable tt = (TestTable) o;
+ return dbName.equals(tt.dbName) && tableName.equals(tt.tableName);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ int h = hashCode;
+ if (h < 0) {
+ hashCode = h = Math.abs((31 * dbName.hashCode()) + tableName.hashCode());
+ }
+ return h;
+ }
+ }
+
+ /**
+ * Creates a list of tables.
+ * @param dbs number of databases
+ * @param tbls number of tables per database
+ * @return a list of tables
+ */
+ private static List<TestTable> createTables(int dbs, int tbls) {
+ Random rnd = new Random(20230815L);
+ List<Integer> dbis = new ArrayList<>(dbs);
+ for(int i = 0; i < dbs; ++i) {
+ dbis.add(i);
+ }
+ Collections.shuffle(dbis, rnd);
+ List<Integer> tblis = new ArrayList<>(tbls);
+ for(int i = 0; i < tbls; ++i) {
+ tblis.add(i);
+ }
+ //Collections.shuffle(tblis, rnd);
Review Comment:
Added comments and test/benchmark option.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] saihemanth-cloudera commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "saihemanth-cloudera (via GitHub)" <gi...@apache.org>.
saihemanth-cloudera commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1303113256
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +57,127 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+ /**
+ * A helper enabling efficient lookup of a table in a list by database name, table name.
+ * <p>When filtering a source list of tables by checking their presence in another permission list
+ * using the database name, table name, we need to avoid performing a cartesian product. This
+ * product stems from checking each table from the source (n tables) by comparing it to each
+ * table in the permission list (m permissions), thus an n * m complexity.</p>
+ * <p>This class reduces the complexity of the lookup in the permission by sorting them and
+ * using a binary search; the sort cost is m*log(m) and each lookup is log(m), the overall
+ * complexity of a check for all tables is in the order of m*log(m) + n*log(m) = (m + n)*log(n),
+ * close to m * log(n).</p>
+ *
+ */
+ public abstract static class TableLookup<T> {
+ /** The container. */
+ private final T[] index;
+
+ /**
+ * @param table the table
+ * @return the database name of the table
+ */
+ protected abstract String getDbName(T table);
+
+ /**
+ * @param table the table
+ * @return the table name of the table
+ */
+ protected abstract String getTableName(T table);
+
+ /**
+ * Compares a table to another by names.
+ * @param table the table
+ * @param arg the argument table
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final T arg) {
+ int cmp = getDbName(table).compareTo(getDbName(arg));
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(getTableName(arg));
+ }
+ return cmp;
+ }
+
+ /**
+ * Compares a table to names.
+ * @param table the table
+ * @param dbName the argument database name
+ * @param dbName the argument table name
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final String dbName, final String tableName) {
+ int cmp = getDbName(table).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(tableName);
+ }
+ return cmp;
+ }
+
+ /**
+ * Creates a ByName
+ * @param tables the tables to consider as a clique
+ */
+ protected TableLookup(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by names
+ Arrays.sort(index, this::compareNames);
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by database name, table name.
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public final T lookup(final String dbName, final String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = compareNames(item, dbName, tableName);
+ if (cmp < 0) {
+ low = mid + 1;
+ } else if (cmp > 0) {
+ high = mid - 1;
+ } else {
+ return item; // key found
+ }
+ }
+ return null; // key not found.
+ }
+
+ /**
+ * Checks whether a given table is present in this set.
+ * @param tt the table to check
+ * @return true if the set contains an item having the same database and table name
+ */
+ public final boolean contains(T tt) {
+ return lookup(getDbName(tt), getTableName(tt)) != null;
+ }
}
+ /**
+ * Specialized lookup for HivePrivilegeObject.
+ */
+ public static class PrivilegeLookup extends TableLookup<HivePrivilegeObject> {
Review Comment:
nit: 'PrivilegeLookup', should this be 'PrivilegeTableLookup'?
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] nrg4878 commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "nrg4878 (via GitHub)" <gi...@apache.org>.
nrg4878 commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1677456110
@jfsii Could you please review as this modifies some of the code you have changed recently. Thank yo
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] saihemanth-cloudera commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "saihemanth-cloudera (via GitHub)" <gi...@apache.org>.
saihemanth-cloudera commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1294041436
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/AuthorizationMetaStoreFilterHook.java:
##########
@@ -162,20 +159,18 @@ private List<HivePrivilegeObject> tableMetasToPrivilegeObjs(List<TableMeta> tabl
return objs;
}
- private ImmutablePair<String, String> tableMetaKey(String dbName, String tableName) {
- return new ImmutablePair(dbName, tableName);
- }
-
@Override
public List<TableMeta> filterTableMetas(List<TableMeta> tableMetas) throws MetaException {
List<HivePrivilegeObject> listObjs = tableMetasToPrivilegeObjs(tableMetas);
List<HivePrivilegeObject> filteredList = getFilteredObjects(listObjs);
- Set<ImmutablePair<String, String>> filteredNames = filteredList.stream()
- .map(e -> tableMetaKey(e.getDbname(), e.getObjectName()))
- .collect(Collectors.toSet());
- return tableMetas.stream()
- .filter(e -> filteredNames.contains(tableMetaKey(e.getDbName(), e.getTableName())))
Review Comment:
The existing implementation's run time complexity is O(N) whereas the suggested implementation's complexity is O(NlogN). So, I'm against changing this part of the code.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1297353725
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
+ return cmp != 0
+ ? cmp
+ : getTableName(left).compareTo(getTableName(right));
+ });
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by Name, tblName
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public T lookup(String dbName, String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = getDbName(item).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(item).compareTo(tableName);
+ }
+ if (cmp < 0)
+ low = mid + 1;
+ else if (cmp > 0)
+ high = mid - 1;
+ else
+ return item; // key found
+ }
+ return null; // key not found.
+ }
}
+ /**
+ * Specialized index for HivePrivilegeObject.
+ */
+ public static class PrivilegeIndex extends TableIndex<HivePrivilegeObject> {
Review Comment:
Renamed to PrivilegeLookup.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] jfsii commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "jfsii (via GitHub)" <gi...@apache.org>.
jfsii commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1298570610
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
Review Comment:
Are the changes in this file needed?
It looks maybe you had tests here and moved them and the imports are left over.
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestTablePermissionFilterAlgos.java:
##########
@@ -0,0 +1,274 @@
+/*
+ * 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.
+ */
+
+package org.apache.hadoop.hive.ql.security.authorization.plugin.metastore;
+
+import org.apache.commons.lang3.tuple.ImmutablePair;
+import org.apache.hadoop.hive.ql.security.authorization.plugin.HivePrivilegeObjectUtils;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * This test tries different methods of lookup to try and determine the most efficient in
+ * the particular usage case related to checking tables against permissions.
+ * Note that a meaningful performance test requires at least 20 dbs, 10000 tables per db and 40 loops
+ * on a 2022 laptop.
+ */
+public class TestTablePermissionFilterAlgos {
+ private static final Logger LOGGER = LogManager.getLogger(TestHiveMetaStoreAuthorizer.class);
+ // reduce constants to speed up tests when true, set to false for benchmarking
+ private static final boolean TEST = true;
+ private static final int NUM_DB = TEST? 2 : 20;
+ private static final int NUM_TBL = TEST? 100 : 10000;
+ private static final int NLOOPS = TEST? 1 : 40;
+
+ private final List<TestTable> tables = createTables(NUM_DB, NUM_TBL);
+ // lookup some
+ private final List<TestTable> filtered = tables.stream()
+ .filter(t -> t.getTableName().endsWith("0"))
+ .collect(Collectors.toList());
+
+ /**
+ * Fake tables to test.
+ */
+ private static class TestTable {
+ private int hashCode = -1;
+ private final String dbName;
+ private final String tableName;
+
+ private TestTable(String dbName, String tableName) {
+ this.dbName = dbName;
+ this.tableName = tableName;
+ }
+
+ @Override
+ public String toString() {
+ return tableFullName(this);
+ }
+
+ public String getDbName() {
+ return dbName;
+ }
+
+ public String getTableName() {
+ return tableName;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o instanceof TestTable) {
+ TestTable tt = (TestTable) o;
+ return dbName.equals(tt.dbName) && tableName.equals(tt.tableName);
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ int h = hashCode;
+ if (h < 0) {
+ hashCode = h = Math.abs((31 * dbName.hashCode()) + tableName.hashCode());
+ }
+ return h;
+ }
+ }
+
+ /**
+ * Creates a list of tables.
+ * @param dbs number of databases
+ * @param tbls number of tables per database
+ * @return a list of tables
+ */
+ private static List<TestTable> createTables(int dbs, int tbls) {
+ Random rnd = new Random(20230815L);
+ List<Integer> dbis = new ArrayList<>(dbs);
+ for(int i = 0; i < dbs; ++i) {
+ dbis.add(i);
+ }
+ Collections.shuffle(dbis, rnd);
+ List<Integer> tblis = new ArrayList<>(tbls);
+ for(int i = 0; i < tbls; ++i) {
+ tblis.add(i);
+ }
+ //Collections.shuffle(tblis, rnd);
Review Comment:
nit - might as well remove if it is not used
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1687295628
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [1 Code Smell](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1303246488
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +57,127 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+ /**
+ * A helper enabling efficient lookup of a table in a list by database name, table name.
+ * <p>When filtering a source list of tables by checking their presence in another permission list
+ * using the database name, table name, we need to avoid performing a cartesian product. This
+ * product stems from checking each table from the source (n tables) by comparing it to each
+ * table in the permission list (m permissions), thus an n * m complexity.</p>
+ * <p>This class reduces the complexity of the lookup in the permission by sorting them and
+ * using a binary search; the sort cost is m*log(m) and each lookup is log(m), the overall
+ * complexity of a check for all tables is in the order of m*log(m) + n*log(m) = (m + n)*log(n),
+ * close to m * log(n).</p>
+ *
+ */
+ public abstract static class TableLookup<T> {
+ /** The container. */
+ private final T[] index;
+
+ /**
+ * @param table the table
+ * @return the database name of the table
+ */
+ protected abstract String getDbName(T table);
+
+ /**
+ * @param table the table
+ * @return the table name of the table
+ */
+ protected abstract String getTableName(T table);
+
+ /**
+ * Compares a table to another by names.
+ * @param table the table
+ * @param arg the argument table
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final T arg) {
+ int cmp = getDbName(table).compareTo(getDbName(arg));
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(getTableName(arg));
+ }
+ return cmp;
+ }
+
+ /**
+ * Compares a table to names.
+ * @param table the table
+ * @param dbName the argument database name
+ * @param dbName the argument table name
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final String dbName, final String tableName) {
+ int cmp = getDbName(table).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(tableName);
+ }
+ return cmp;
+ }
+
+ /**
+ * Creates a ByName
+ * @param tables the tables to consider as a clique
+ */
+ protected TableLookup(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by names
+ Arrays.sort(index, this::compareNames);
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by database name, table name.
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public final T lookup(final String dbName, final String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = compareNames(item, dbName, tableName);
+ if (cmp < 0) {
+ low = mid + 1;
+ } else if (cmp > 0) {
+ high = mid - 1;
+ } else {
+ return item; // key found
+ }
+ }
+ return null; // key not found.
+ }
+
+ /**
+ * Checks whether a given table is present in this set.
+ * @param tt the table to check
+ * @return true if the set contains an item having the same database and table name
+ */
+ public final boolean contains(T tt) {
+ return lookup(getDbName(tt), getTableName(tt)) != null;
+ }
}
+ /**
+ * Specialized lookup for HivePrivilegeObject.
+ */
+ public static class PrivilegeLookup extends TableLookup<HivePrivilegeObject> {
Review Comment:
TablePrivilegeLookup it is.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1690713489
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [1 Code Smell](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] saihemanth-cloudera commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "saihemanth-cloudera (via GitHub)" <gi...@apache.org>.
saihemanth-cloudera commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1303120186
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
@@ -411,4 +411,5 @@ public void testU_DropDataConnector_authorizedUser() {
fail("testU_DropDataConnector_authorizedUser() failed with " + e);
}
}
+
Review Comment:
Nit: Can you please remove this blank line?
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] nrg4878 merged pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "nrg4878 (via GitHub)" <gi...@apache.org>.
nrg4878 merged PR #4601:
URL: https://github.com/apache/hive/pull/4601
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1682788959
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [5 Code Smells](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1681055872
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [5 Code Smells](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] jfsii commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "jfsii (via GitHub)" <gi...@apache.org>.
jfsii commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1293657388
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
+ return cmp != 0
+ ? cmp
+ : getTableName(left).compareTo(getTableName(right));
+ });
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by Name, tblName
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public T lookup(String dbName, String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = getDbName(item).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(item).compareTo(tableName);
+ }
+ if (cmp < 0)
Review Comment:
I do not know the exact Hive code style here - but I usually prefer always using { }'s unless it is single line.
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
Review Comment:
It might be a little more easy to read if there was a helper function that had a signature like:
int compare(T item, String dbName, String tableName) or
int compare(String compareDbName, String compareTableName, String compareToDbName, String compareToTableName)
which does the composite key compare and returns the cmp value and use it in TableIndex constructor and lookup method.
The argument names were hard, if you take this suggestion, I'm sure you could come up with better.
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/HiveMetaStoreAuthorizer.java:
##########
@@ -396,32 +383,16 @@ private List<String> filterTableNames(HiveMetaStoreAuthzInfo hiveMetaStoreAuthzI
}
return ret;
}
-
- private List<String> getFilteredTableNames(List<HivePrivilegeObject> hivePrivilegeObjects, String databaseName,
- List<String> tableNames) {
+ private List<String> getFilteredTableNames(List<HivePrivilegeObject> hivePrivilegeObjects, String databaseName, List<String> tableNames) {
List<String> ret = new ArrayList<>();
- for (HivePrivilegeObject hivePrivilegeObject : hivePrivilegeObjects) {
- String dbName = hivePrivilegeObject.getDbname();
- String tblName = hivePrivilegeObject.getObjectName();
- String table = getFilteredTableNames(dbName, tblName, databaseName, tableNames);
- if (table != null) {
- ret.add(table);
- }
- }
- return ret;
- }
-
- private String getFilteredTableNames(String dbName, String tblName, String databaseName, List<String> tableNames) {
- String ret = null;
- for (String tableName : tableNames) {
- if (dbName.equals(databaseName) && tblName.equals(tableName)) {
- ret = tableName;
- break;
+ final PrivilegeIndex index = new PrivilegeIndex(hivePrivilegeObjects);
+ for(String tableName : tableNames) {
+ if (index.lookup(databaseName, tableName) != null) {
+ ret.add(tableName);
}
}
return ret;
}
-
Review Comment:
I think this blank line was accidentally removed.
##########
ql/src/test/org/apache/hadoop/hive/ql/security/authorization/plugin/metastore/TestHiveMetaStoreAuthorizer.java:
##########
@@ -411,4 +418,93 @@ public void testU_DropDataConnector_authorizedUser() {
fail("testU_DropDataConnector_authorizedUser() failed with " + e);
}
}
+
+ /**
+ * Fake tables to test.
+ */
+ private static class TestTable {
+ private final String dbName;
+ private final String tableName;
+
+ private TestTable(String dbName, String tableName) {
+ this.dbName = dbName;
+ this.tableName = tableName;
+ }
+
+ @Override
+ public String toString() {
+ return dbName + "." + tableName;
+ }
+
+ public String getDbName() {
+ return dbName;
+ }
+
+ public String getTableName() {
+ return tableName;
+ }
+ }
+
+
+ private static List<TestTable> createTables(int dbs, int tbls) {
+ List<TestTable> tables = new ArrayList<>(dbs * tbls);
+ for(int d = 0; d < dbs; ++d) {
+ for(int t = 0; t < tbls; ++t) {
+ String dbname = String.format("db%05x", d);
+ String tblName = String.format("tbl%05x", t);
+ tables.add(new TestTable(dbname, tblName));
+ }
+ }
+ return tables;
+ }
+
+ private static final int NUM_DB = 2;
+ private static final int NUM_TBL = 50;
+ @Ignore
+ public void testIndexedTableLookup0() {
Review Comment:
Not sure of the purpose of this test, could you clarify or remove?
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1678065929
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [5 Code Smells](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] sonarcloud[bot] commented on pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "sonarcloud[bot] (via GitHub)" <gi...@apache.org>.
sonarcloud[bot] commented on PR #4601:
URL: https://github.com/apache/hive/pull/4601#issuecomment-1688351470
Kudos, SonarCloud Quality Gate passed! [](https://sonarcloud.io/dashboard?id=apache_hive&pullRequest=4601)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG) [0 Bugs](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=BUG)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY) [0 Vulnerabilities](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=VULNERABILITY)
[](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT) [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_hive&pullRequest=4601&resolved=false&types=SECURITY_HOTSPOT)
[](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL) [1 Code Smell](https://sonarcloud.io/project/issues?id=apache_hive&pullRequest=4601&resolved=false&types=CODE_SMELL)
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=coverage&view=list) No Coverage information
[](https://sonarcloud.io/component_measures?id=apache_hive&pullRequest=4601&metric=duplicated_lines_density&view=list) No Duplication information
 The version of Java (11.0.8) you have used to run this analysis is deprecated and we will stop accepting it soon. Please update to at least Java 17.
Read more [here](https://docs.sonarcloud.io/appendices/scanner-environment/)
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] saihemanth-cloudera commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "saihemanth-cloudera (via GitHub)" <gi...@apache.org>.
saihemanth-cloudera commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1294040144
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
+ return cmp != 0
+ ? cmp
+ : getTableName(left).compareTo(getTableName(right));
+ });
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by Name, tblName
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public T lookup(String dbName, String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = getDbName(item).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(item).compareTo(tableName);
+ }
+ if (cmp < 0)
+ low = mid + 1;
+ else if (cmp > 0)
+ high = mid - 1;
+ else
+ return item; // key found
+ }
+ return null; // key not found.
+ }
}
+ /**
+ * Specialized index for HivePrivilegeObject.
+ */
+ public static class PrivilegeIndex extends TableIndex<HivePrivilegeObject> {
Review Comment:
I have another suggestion regarding the implementation. I would like to use a Java HashMap for it,
Key: <String> - 'DbName'.'TableName'
Value: <Table> - Store the unfiltered table.
So we store the unfiltered tables list(before converting it into HivePrivilegeObject and sending them for authorization) in the form of a map like the above. Once we get the filtered list, we simply look up the 'dbName'.'tableName' in the map and return the table.
Space complexity: O(N) -- N is the size of the table list
Run time complexity: O(1) -- HashMap lookup is constant order.
I'm suggesting this because, theoretically even with the current implementation we are using up O(N) space. In practice, the space requirements of the current implementation is more efficient than what I suggested. For runtime complexity, we avoid NlogN look-up time if we go with the above suggestion.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org
[GitHub] [hive] henrib commented on a diff in pull request #4601: HIVE-27595: replaced cartesian-product table filtering by sort + binary search
Posted by "henrib (via GitHub)" <gi...@apache.org>.
henrib commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1297355025
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +59,74 @@ public static List<HivePrivilegeObject> getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR, null, dcname));
}
return objs;
+ }
+
+
+ /**
+ * An index on a table list by dbName, tableName.
+ */
+ public abstract static class TableIndex<T> {
+ private final T[] index;
+ protected abstract String getDbName(T item);
+ protected abstract String getTableName(T item);
+ protected TableIndex(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by dbname, tblname
+ Arrays.sort(index, (left, right)->{
+ int cmp = getDbName(left).compareTo(getDbName(right));
Review Comment:
Created helper functions, refactored that part.
--
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: gitbox-unsubscribe@hive.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscribe@hive.apache.org
For additional commands, e-mail: gitbox-help@hive.apache.org