Runtime of SORT

[former_member479347]

Is there (in)official information on the worst and average case runtime of SORT?

I'd like to determine the values for x and n for which the following code segment:

SELECT fields FROM db_table UP TO n ROWS
  INTO TABLE itab.
SORT itab BY whatever.
DO x TIMES.
  READ TABLE itab WITH KEY key BINARY SEARCH
ENDDO.

outperforms this code segment:

SELECT fields FROM db_table UP TO n ROWS
  INTO TABLE itab.
DO x TIMES.
  READ TABLE itab WITH KEY key.
ENDDO.

(Assuming that exactly n rows are transferred to the internal table.)

Binary search has a worst case runtime of log n. But I need to know if SORT guarantees a runtime boundary like n log n.

--Florian

[former_member479347]

Is there (in)official information on the worst and average case runtime of SORT?

I'd like to determine the values for x and n for which the following code segment:

SELECT fields FROM db_table UP TO n ROWS
  INTO TABLE itab.
SORT itab BY whatever.
DO x TIMES.
  READ TABLE itab WITH KEY key BINARY SEARCH
ENDDO.

outperforms this code segment:

SELECT fields FROM db_table UP TO n ROWS
  INTO TABLE itab.
DO x TIMES.
  READ TABLE itab WITH KEY key.
ENDDO.

(Assuming that exactly n rows are transferred to the internal table.)

Binary search has a worst case runtime of log n. But I need to know if SORT guarantees a runtime boundary like n log n.

--Florian

[Former Member]

the answer is somewhere in the area of 50!

sort + x binary search read < x standard read

a n logn + x b log n < x c n

x > a n logn / ( cn - b log n ) ~ a/c log n

The last time I measured it a/c was about 50.

Siegfried

[Former Member]

Hi,

I'm not sure if i can answer your question mathematically.

Reading an internal table with BInary Search, and that too without sorting is going to take lot of time. Because, Binary Search will divide the table into half( virtually) search in the first half..n then the next half, n so on....

so , if u dont sort...its going to search the record for a long time....

u can find the runtime of each and every statement using :

GET RUN TIME FIELD t1.
sort itab by f1.
GET RUN TIME FIELD t2.

now u get the runtime t = t2-t1.

regards,

madhu

[Former Member]

> if u dont sort...its going to search the record for a long time....

This is a misunderstanding, binary search on a unsorted standard table is not slower than on a sorted standard table. It will simply miss some entries !

I.e. the results are uncorrect !!!!

Good measurements should be done differently see here:

How to Measure Operations on Internal Tables

/people/siegfried.boes/blog/2007/11/09/how-to-measure-operations-on-internal-tables

Siegfried

[Former Member]

yeah. I made a mistake there!!! Thanks for pointing out.

regards,

madhumitha

[former_member479347]

Asymptotically, your estimation of

x > a/c log n

is correct. However, since we're dealing with business data, we must not neglect small values of n, which keeps the math more complex. My simple, unrealiable measurement series yielded the following result:

n=1 ==> x --> infinity

n=10 ==> x > 88

n=100 ==> x > 15

n=1,000 ==> x > 9

n=10,000 ==> x > 14

n=100,000 ==> x > 18

n=1,000,000 ==> x > 19

Anyway, I understand your comment such that SORT indeed guarantees a worst case runtime of O(n log n), which was what I originally asked for.

--Florian

[Former Member]

you should not calculate with the small n, because all scaling assumptions are not fulfilled

for small n. I would trust them not before n = 20 or 50.

It might be that a and c changed not in the same ratio since I have measured them.

Anyway, the principle should be clear. Sort the table and use binary search if the read is inside a loop.

But do not sort it, if you read only once or a few times, you will not the time spent on the sort back.

Actually, I am wondering, how you come to this question.

Siegfried

[former_member479347]

Oh, we have plenty of this lying around here. The question came up in a performance review. Since recently I was announced "performance specialist" I wanted to get a precise idea of what I was talking about when I said "get that thing sorted".

Thanks for your contribution, I gave you the rating you earned. By the way, I checked some of your blog entries: great stuff!

--Florian