Vikram Ahuja created HIVE-29740:
-----------------------------------
Summary: 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
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.
// 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;
}
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
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
