[
https://issues.apache.org/jira/browse/HIVE-29740?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Zhihua Deng resolved HIVE-29740.
--------------------------------
Fix Version/s: 4.3.0
Resolution: Fixed
> 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
> Fix For: 4.3.0
>
> 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)
