[
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 table object returned, 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) {
String catName = hivePrivilegeObject.getCatName();
String dbName = hivePrivilegeObject.getDbname();
String tblName = hivePrivilegeObject.getObjectName();
Table table = getFilteredTable(catName, dbName, tblName, tableList); //
← full scan here
if (table != null) {
ret.add(table);
}
}
return ret;
}
private Table getFilteredTable(String catName, String dbName, String tblName,
List<Table> tableList) {
Table ret = null;
for (Table table: tableList) { // ← inner scan: O(N) per call
// do not check catalog name if catName is null
if (catName != null && table.getCatName() != null &&
!catName.equals(table.getCatName())) {
continue;
}
String databaseName = table.getDbName();
String tableName = table.getTableName();
if (dbName.equals(databaseName) && tblName.equals(tableName)) {
ret = table;
break;
}
}
return ret;
}
{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 sort and binary-search based lookup.
Performance Impact(100,000 tables):
|| ||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 table object returned, 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 sort and binary-search based lookup.
Performance Impact(100,000 tables):
|| ||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
> 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
> Labels: pull-request-available
> Attachments:
> 0001-HIVE-29740-Fix-SHOW-TABLES-operation-taking-300-seco.patch
>
>
> 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 table object returned, 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) {
> String catName = hivePrivilegeObject.getCatName();
> String dbName = hivePrivilegeObject.getDbname();
> String tblName = hivePrivilegeObject.getObjectName();
> Table table = getFilteredTable(catName, dbName, tblName, tableList);
> // ← full scan here
> if (table != null) {
> ret.add(table);
> }
> }
> return ret;
> }
> private Table getFilteredTable(String catName, String dbName, String tblName,
> List<Table> tableList) {
> Table ret = null;
> for (Table table: tableList) { // ← inner scan: O(N) per call
> // do not check catalog name if catName is null
> if (catName != null && table.getCatName() != null &&
> !catName.equals(table.getCatName())) {
> continue;
> }
> String databaseName = table.getDbName();
> String tableName = table.getTableName();
> if (dbName.equals(databaseName) && tblName.equals(tableName)) {
> ret = table;
> break;
> }
> }
> return ret;
> }
> {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 sort and binary-search based lookup.
>
> Performance Impact(100,000 tables):
> || ||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)
