RBarryYoung said:
It has long been known that naive linear string concatenation is an O(n^2) operation (more specifically, it's triangular). That simple fact is one of the big reasons that .NET has the StringBuilder class (which uses the strings->array->mass_concatenate trick that peter alludes to).
As it happens, I spent quite a lot of time last month investigating this problem and potential solutions and let me just say: it's tough in SQL. Here are the problems:
1) SQL Server apparently (based on my tests) already does the "buffer-extension" trick available to mutable strings. Unfortunately, the Extension trick does NOT solve the O(n^2) problem, it just partially alleviates it at the lower end because some percentage(k) of appends can be extensions instead of creating a new string. Effectively it changes the {(n)*(n+1)/2} cost of the naive implementation to {n +(n)*(n-1)/(2*k)} where "k" is that percentage. It's better, but it's still O(n^2).
2) The "array & mass-concatenate" trick is not available to T-SQL, not because SQL doesn't have arrays (tables serve the same purpose), but because AFAIK, there is no function that can take a variable "collection" of strings (table, array, whatever) and produce an output string.
3) The "pre-allocate and Stuff" trick popular with mutable strings is not workable in T-SQL because the STUFF() function in T_SQL is NOT like the function of the same name in some general purpose languages: the T-SQL STUFF() is an RHS (right-hand side) function and NOT an LHS (left-hand side) function. AFAIK, there is no function in SQL that can (physically) write into a pre-existing string.
That all said, I did eventually find a way to do it. Not in the O(n) time (linear) achievable in most general purpose languages, but I could get it down to O(n*Log(n)) time which is still a huge improvement. Unfortunately, I do not have it together in a presentable form and it would take me some time to do so (a day or so), but I can get it to you if you want.
February 18, 2009 12:32 PM

karthikeyan (6/8/2009)

---

1) O(n) means ?
2) O(n^2) means ?
3) O(n log n) means ?

"pre-allocate and Stuff" trick popular with mutable strings

OK, since I couldn't get a copy of Moby Dick, I made my own test data. Here is your test rig Phil, with my test data and my technique, followed by your original approach. Needless to say, my method is nearly linear, but the simple approach grows geometrically:

karthikeyan (6/8/2009)

---

They used some concepts which i couldn't understand.

1) O(n) means ?
2) O(n^2) means ?
3) O(n log n) means ?
4) What is mean naive linear string concatenation?

--NOTE: This is an example.  I dont really use While loops in SQL.
Declare @i As int 
Declare @A As varchar(MAX)
Select @i = 1, @A = ''

WHILE @i <= (Select Count(*) From MyStrings)
BEGIN
    Select @A = @A + Select B From MyStrings Where ID = @i
END

RBarryyoung,

1) What do you mean by "buffer-extension"?

2) Can you explain about the formula you used?

karthikeyan (6/8/2009)

---

Yes Gail...I have studied...But i don't remember the functionality...
I have reviewed the above mentioed URL, Since there are lot of formula's are there,it is confusing...

3) What RHS (right-hand side) function denotes exactly?

4) What LHS (Left-hand side) function denotes exactly?

OK, since I couldn't get a copy of Moby Dick, I made my own test data. Here is your test rig Phil, with my test data and my technique, followed by your original approach. Needless to say, my method is nearly linear, but the simple approach grows geometrically:

5) what are all the method available apart from linear? What is mean by linear method?
how to know whether my code use linear method?

karthikeyan (6/8/2009)

---

1) What is mean by pseudo cursor?

Declare @str varchar(MAX)
Set @str = ''
Select @str = @str + ',' + [name] From sys.columns
Print @str

2) what this trick will do?

4) What LHS (Left-hand side) RHS (Right-hand side) function denotes exactly?

 Set @str = UPPER('Some text.')

3) What RLHS (rightleft-hand side) function denotes exactly?

 STUFF(@str, offset, len) = 'foo'

RBarryYoung (6/8/2009)

---

For (1-3), see the Wikipedia articles that Gail referenced. Big-O notation is simple once you understand it, but a little confusing to explain so I'm deferring to the experts.

For (4), "naive linear string concatenation" is just the normal way of concatentating many strings together by appending each one onto the end of an accumulated output string:

--NOTE: This is an example.  I dont really use While loops in SQL.
Declare @i As int 
Declare @A As varchar(MAX)
Select @i = 1, @A = ''

WHILE @i <= (Select Count(*) From MyStrings)
BEGIN
    Select @A = @A + Select B From MyStrings Where ID = @i
END

The problem with this approach is that you have to re-copy @A every time through the loop and @A is getting larger every time. So even if our strings are all 1 character, first we have to copy 1 character, then 2 characters, then 3, then 4, 5, 6, 7, ... all the way out to N where N is total number of strings we want to concatenate together.

This totals to ((N^2) + N)/2 which is complexity Order N^2 (or just O(N^2)).


The "buffer-extension trick" is referring to a low-level (Assembler or C) trick that takes advantage of that fact that in most OS's strings often have large gaps of unallocated memory after them. Thus if you want to add the string B$ onto the end of A$, then normally you would have to allocate a new buffer whose length is >= Len(A$) + Len(B$), then copy all of A$ inot it, then copy B$ in after A$ and then re-point A$ to the new buff (and deallocate the old). Besides all of the memory allocation overhead, this is an O(n) operation where n = Len(A$)+Len(B$).

However, if A$ just happens to have an unused portion of memory after it whose size is >= Len(B$) then, instead you can just copy B$ into that unused memory after A$ and extend A$'s length value to inlcude the appended characters.


Which formula? I use a lot of them.

2) Can you explain about the formula you used?

Which formula? I use a lot of them.

1) SQL Server apparently (based on my tests) already does the "buffer-extension" trick available to mutable strings. Unfortunately, the Extension trick does NOT solve the O(n^2) problem,

karthikeyan (6/9/2009)

---

Big O notation means the steps to complete a problem. Right?

RBarryYoung (6/8/2009)

---

Pusedocursor is a name that some people (including me) use for the SQL Server (and Sybase too, I believe) trick of being able to assign both to and from variables for every row of a resultset. The typical example is the simple string concatenation trick that we often use:

Declare @str varchar(MAX)
Set @str = ''
Select @str = @str + ',' + [name] From sys.columns
Print @str

We used to call this "string mapping" back in the old days. Instead of reallocating the output string with every iteration, you estimate the likely size of the output string and pre-allocate the output string with that much blank space and use a LenPtr to keep track of how much of this buffer you have used. Then for each string you "MAP" or "STUFF" the current source string into the next available space after LenPtr and then update LenPtr to the new end. This is linear time ( O(n) ) because you only have to touch each input character once.


Left-hand Functions appear left of the assignment operator ("="):

 Set @str = UPPER('Some text.')

These are normal functions, and AFAIK, in T-SQL, all functions are LHS.


Right-hand Side functions appear on the right-hand side and they usually do "special" things having to do with addressing the output property or variable. AFAIK, T-SQL does not have any, but in some languages, STUFF is a RHS:

 STUFF(@str, offset, len) = 'foo'

This example would overwrite the output string (@str) with the input string starting at 'offset' for 'len' characters. The difference between this and th LHS STUFF() function in T-SQL is that the RHS version does not return anything, it actually does write over the characters of the @str variable.