Skip to content

Creating a SQLServerDataTable is O(n^2) #497

@alexnixon

Description

@alexnixon

This is true as of the latest commit on the dev branch (e6f66e9).

The API of SQLServerDataTable prevents it from being reused between calls - the only way to clear it is by calling clear(), which throws away column metadata in addition to row data.

So you have to construct it afresh each time, and the only way to do so is by repeatedly calling addColumnMetaData. But each invocation calls Util.checkDuplicateColumnName, which iterates over all added columns so far, resulting in the SQLServerDataTable construction being O(n^2).

Possible fixes are:

  1. Store a Set of column names in SQLServerDataTable and check against that when adding columns, so the n^2 behavior goes away
  2. Provide a method to clear the rows in a SQLServerDataTable, so it's possible to write code in a way that incurs this cost less often.

Personally I wouldn't be averse to both (1) and (2). Thoughts?

Thanks,
Alex

(I haven't benchmarked this to prove it's an issue for me - it's probably not - but I thought this behavior surprising so worth noting).

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions