CODEWITHSUNDEEP
androidsqlitestring-concatenation
Kaidul
Kaidul

Reputation: 15915

Database Insertion vs. String concatenation

I have a SQlite table in which I need to insert 6 items in a row. And there are 4000 such rows. So 4000 * 6 insertion operations are needed. To reduce it, I concatenate those six items and insert them as one column and thus there is only 4000 operations.

But I came to know the complexity of string concatenation operation is O(n^2) where n is the no of string. And when I fetch the item, I need to split the string into 6 parts. On the contray, any database manipulation like insertion/query has complexity of M * O(log(n)) where M is the no of rows and n is the column as it maintains B-tree structure.

So what should I do now? Should I concatenate the 6 items in one and insert it and later split it or should I insert them in 6 columns and query them in 6 attempts ? Which will be time efficient?

Upvotes: 2

Views: 125

Answers (2)

CL.
CL.

Reputation: 180270

All your algorithmic complexity estimates are wrong.

Only the most trivial way of implementing string concatenations is O(n²). When SQLite constructs a record, it already knows how many strings there are and how big they are, so it never needs to reallocate or move around partial strings. The actual time needed to construct one record is O(n). (This ignores the size of the strings, but if we assume that all strings have the same size, this does not matter.)

Even when SQLite inserts multiple strings, it constructs the record before it is inserted in the table's B-tree.

Inserting one record at an arbitrary position in a B-tree is O(log M); if you just append a record, it's O(1).

Please note that your numbers n and M do not become infinitely large but are bounded, so you have only constants, so all your times are actually O(1). What matters for you are the constant factors hidden by the O notation; the only way to find them out is to actually measure your operations.

Upvotes: 2

JJ86
JJ86

Reputation: 5113

I prefer SQLite, because you can filter your query and manage your data more easily.

What about if you have to modify or delete one columns of your String concatenation? With String this will be more complicated, because you have to split data, find the one you want to modify/delete, then re-insert it on your database.

I didn't understand why you have to "query them in 6 attempts" (did you mean to query one by one?): with a simple query you can have a Cursor wich contains all data you need.

Upvotes: 1

Related Questions