[
https://issues.apache.org/jira/browse/HIVE-29740?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Vikram Ahuja updated HIVE-29740:
--------------------------------
Description:
Problem
SHOW TABLES operations which involves table listing is experiencing severe
performance degradation and is taking 300+ seconds on databases with ~1 lakh
(100,000) tables in our production cases.
Root Cause
The method filterTables in AuthorizationMetaStoreFilterHook.java contains an
O(n²) nested loop where for every authorized table object returned by the
authorization plugin, the code performs a full linear scan of the original
table list to find the matching Table object.
{code:java}
// O(n²): for each of n hivePrivilegeObjects, scans the full tableList of n
Tables
private List<Table> getFilteredTableList(List<HivePrivilegeObject>
hivePrivilegeObjects,
List<Table> tableList) {
List<Table> ret = new ArrayList<>();
for (HivePrivilegeObject hivePrivilegeObject : hivePrivilegeObjects) {
Table table = getFilteredTable(dbName, tblName, tableList); // ← full
scan here
if (table != null){
ret.add(table);
}
}
return ret;
}
private Table getFilteredTable(String dbName, String tblName, List<Table>
tableList) {
for (Table table : tableList) { // ← inner scan: O(N) per call
if (dbName.equals(table.getDbName()) &&
tblName.equals(table.getTableName())) {
return table;
}
}
return null;
}
{code}
For 1 lakh tables: n × n = 100,000 × 100,000 = 10,000,000,000 iterations per
filterTables() call
Fix: Replace the nested loop with HashMap-based O(N) lookup. Build a lookup
map from the table list, then resolve each authorized object in O(1)
Performance Impact:
|| ||Operations ||Observed Time||
|Before fix|10,000,000,000|300+ seconds|
|After fix|~100,000|~5 seconds|
|Improvement|100,000×|~60× faster|
How to Reproduce
# On a database with ~1 lakh tables
# SHOW TABLES;
# Observe: query takes 300+ seconds
# After fix: query takes ~5 seconds
was:
Problem
SHOW TABLES operations which involves table listing is experiencing severe
performance degradation and is taking 300+ seconds on databases with ~1 lakh
(100,000) tables in our production cases.
Root Cause
The method filterTables in AuthorizationMetaStoreFilterHook.java contains an
O(n²) nested loop where for every authorized table object returned by the
authorization plugin, the code performs a full linear scan of the original
table list to find the matching Table object.
{code:java}
// O(n²): for each of n hivePrivilegeObjects, scans the full tableList of n
Tables
private List<Table> getFilteredTableList(List<HivePrivilegeObject>
hivePrivilegeObjects,
List<Table> tableList) {
List<Table> ret = new ArrayList<>();
for (HivePrivilegeObject hivePrivilegeObject : hivePrivilegeObjects) {
Table table = getFilteredTable(dbName, tblName, tableList); // ← full
scan here
if (table != null){
ret.add(table);
}
}
return ret;
}
private Table getFilteredTable(String dbName, String tblName, List<Table>
tableList) {
for (Table table : tableList) { // ← inner scan: O(N) per call
if (dbName.equals(table.getDbName()) &&
tblName.equals(table.getTableName())) {
return table;
}
}
return null;
}
{code}
For 1 lakh tables: n × n = 100,000 × 100,000 = 10,000,000,000 iterations per
filterTables() call
Fix: Replace the nested loop with HashMap-based O(N) lookup. Build a lookup
map from the table list, then resolve each authorized object in O(1)
How to Reproduce
# On a database with ~1 lakh tables
# SHOW TABLES;
# Observe: query takes 300+ seconds
# After fix: query takes ~5 seconds
> SHOW TABLES operation taking 300 seconds+ on very large databases.
> ------------------------------------------------------------------
>
> Key: HIVE-29740
> URL: https://issues.apache.org/jira/browse/HIVE-29740
> Project: Hive
> Issue Type: Improvement
> Reporter: Vikram Ahuja
> Assignee: Vikram Ahuja
> Priority: Major
>
> Problem
> SHOW TABLES operations which involves table listing is experiencing severe
> performance degradation and is taking 300+ seconds on databases with ~1 lakh
> (100,000) tables in our production cases.
>
> Root Cause
> The method filterTables in AuthorizationMetaStoreFilterHook.java contains an
> O(n²) nested loop where for every authorized table object returned by the
> authorization plugin, the code performs a full linear scan of the original
> table list to find the matching Table object.
>
> {code:java}
> // O(n²): for each of n hivePrivilegeObjects, scans the full tableList of n
> Tables
> private List<Table> getFilteredTableList(List<HivePrivilegeObject>
> hivePrivilegeObjects,
> List<Table> tableList) {
> List<Table> ret = new ArrayList<>();
> for (HivePrivilegeObject hivePrivilegeObject : hivePrivilegeObjects) {
> Table table = getFilteredTable(dbName, tblName, tableList); // ← full
> scan here
> if (table != null){
> ret.add(table);
> }
> }
> return ret;
> }
> private Table getFilteredTable(String dbName, String tblName, List<Table>
> tableList) {
> for (Table table : tableList) { // ← inner scan: O(N) per call
> if (dbName.equals(table.getDbName()) &&
> tblName.equals(table.getTableName())) {
> return table;
> }
> }
> return null;
> }
> {code}
>
> For 1 lakh tables: n × n = 100,000 × 100,000 = 10,000,000,000 iterations
> per filterTables() call
>
> Fix: Replace the nested loop with HashMap-based O(N) lookup. Build a lookup
> map from the table list, then resolve each authorized object in O(1)
>
>
>
> Performance Impact:
>
> || ||Operations ||Observed Time||
> |Before fix|10,000,000,000|300+ seconds|
> |After fix|~100,000|~5 seconds|
> |Improvement|100,000×|~60× faster|
>
>
>
> How to Reproduce
> # On a database with ~1 lakh tables
> # SHOW TABLES;
> # Observe: query takes 300+ seconds
> # After fix: query takes ~5 seconds
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
