Improve DbListCommand operation from O(n^2) to O(n)

Right now the DbListCommand retrieves the uuid's of all the elements
passed in as argument. This is an O(n^2) operation so when the number
of elements in a grows it's likely that we get Timeout Exceptions.

Instead of doing this, whenever possible, we'll retrieve all the
elements (from the in-memory replica) and only fetch those who were
passed as arguments avoiding the O(n^2) operation.

(cherry picked from 476b174f7d)
Change-Id: I71411e5dd68753eb3825f8b0e91009f87de1b260
Closes-Bug: #1769897
This commit is contained in:
Daniel Alvarez 2018-05-08 16:02:56 +02:00 committed by Miguel Angel Ajo
parent f971e5d1a4
commit fd64d41ea6
2 changed files with 40 additions and 2 deletions

View File

@ -202,8 +202,12 @@ class DbListCommand(BaseCommand):
def run_idl(self, txn):
table_schema = self.api._tables[self.table]
idx = idlutils.get_index_column(table_schema)
columns = self.columns or list(table_schema.columns.keys()) + ['_uuid']
if self.records:
# If there's an index for this table, we'll fetch all columns and
# remove the unwanted ones based on self.records. Otherwise, let's try
# to get the uuid of the wanted ones which is an O(n^2) operation.
if not idx and self.records:
rows = []
for record in self.records:
try:
@ -216,14 +220,41 @@ class DbListCommand(BaseCommand):
raise
else:
rows = table_schema.rows.values()
def _match(row):
elem = getattr(row, idx)
found = elem in self.records
if found:
records_found.remove(elem)
return found
records_found = []
if idx and self.records:
if self.if_exists:
match = lambda row: getattr(row, idx) in self.records
else:
# If we're using the approach of removing the unwanted
# elements, we'll use a helper list to remove elements as we
# find them in the DB contents. This will help us identify
# quickly if there's some record missing to raise a RowNotFound
# exception later.
records_found = list(self.records)
match = _match
else:
match = lambda row: True
self.result = [
rowview.RowView(row) if self.row else {
c: idlutils.get_column_value(row, c)
for c in columns
}
for row in rows
for row in rows if match(row)
]
if records_found:
raise idlutils.RowNotFound(table=self.table, col=idx,
match=records_found[0])
class DbFindCommand(BaseCommand):
def __init__(self, api, table, *conditions, **kwargs):

View File

@ -79,6 +79,13 @@ class TestBackendDb(base.FunctionalTestCase):
cmd = self.api.db_list('Bridge', ['unpossible'])
self.assertRaises(idlutils.RowNotFound, cmd.execute, check_error=True)
def test_db_list_multiple_records_no_exist(self):
# Check the case where some records are found and some are not. We
# should still be getting the RowNotFound exception in this case.
cmd = self.api.db_list('Bridge',
[self.bridges[0]['name'], 'unpossible'])
self.assertRaises(idlutils.RowNotFound, cmd.execute, check_error=True)
def test_db_list_record_if_exsists(self):
self.api.db_list('Bridge', ['unpossible'])