Runtimes of Reads and Loops on Internal Tables

In ABAP coding many performance problems are related to the handling of internal tables. Especially in the case of nested loops on two large tables, it is important for the runtime of the inner operation to scale faster than linear, otherwise the complete nested loop would show a quadratic scaling. Therefore, it is essential to know the runtime behavior of internal table operations. In this web log we will present precise measurement results of read statements on internal tables.

1. Nested Loop Processing

Assume your program contains a nested loop on two internal tables itab1 and itab2. The most commonly used ones are the following three,

`LOOP AT itab1 INTO wa1.`
`  LOOP AT itab2 INTO wa2.`
`    If ( wa2-key = wa1-key ).`
`      .. processing ..`
`    ENDIF.   `
`  ENDLOOP. `
`ENDLOOP.`
` `
`Or`
` `
`LOOP AT itab1 INTO wa1.`
`  LOOP AT itab2 INTO wa2 WHERE key = wa1-key.`
`    .. processing ..  `
`  ENDLOOP. `
`ENDLOOP.`
` `
`Or`
` `
`LOOP AT itab1 INTO wa1.`
`  READ TABLE itab2 INTO wa2 WITH key = wa1-key.`
`  IF ( sy-subrc = 0 ).`
`    .. processing .. `
`  ENDIF. `
`ENDLOOP.`

The loop at table itab1 must process all lines. There is nothing to improve, as it will scale linearly with the number of lines in table 1, i.e. with N1. It is obvious that the first example loops over all lines in table itab2, i.e. N2. Altogether the nested loop scales with N1 * N2. If both N1 and N2 grow with the amount of processed data N, which can be the number of positions, contract lines etc., then the nested loop scales proportional to N*N, i.e. it scales quadratically or nonlinearly.

It is often overseen that also examples 2 and 3 scale quadratically, as the ‘LOOP AT WHERE’ and the READ without BINARY SEARCH on a standard table also scan the whole table, i.e. itab2.
This, however, is not necessary, as only one or a few lines of itab2 correspond to one line in itab1. These lines must be found efficiently to get a scaling behavior on N2 which is faster than linear.

`LOOP AT itab1 INTO wa1.`
` `
`   Efficient Operation to find the line    or lines on table itab2 which correspond to wa1 ENDLOOP.`

The following sections present measurements on different table types. How the measurements must be done in order to get reliable results will be explained in my next web log (coming soon).

2. Reads with Runtimes Independent of Table Size

The fastest access type is when the searched line can be accessed directly, which makes this read type independent of the size of the internal table. This is achieved by

• ‘READ itab WITH index’ (red)
• ‘READ sort_tab’ WITH index’ (blue)
• ‘READ hash_tab WITH TABLE KEY …’ (green)

Figure 1: Averaged runtimes (in microseconds) for different fast reads on internal tables as a function of the table sizes N. Red indicates the read with index on a standard table, blue the read with index on a sorted table, and green the read on a hashed table with a complete table key.

3. Reads with Runtimes with a Logarithmic Dependence on the Table Size

The binary search splits the search area into two halves in every step, and checks in which half it must continue to search. Therefore the runtime must have a logarithmic dependence on the table size N. It is realized by

• ‘READ itab WITH KEY … BINARY SEARCH’ on standard tables (red) or
• ‘READ sort_tab WITH TABLE KEY …’ (blue)

Figure 2: Averaged runtimes (in microseconds) for different read with logarithmic dependences on table size N. Red indicates the read with binary search on a standard table, and blue the read on a sorted table with a table key.

Reads with keys which are only incomplete table keys can exploit the binary search and the sorted search for the leading fields of the table key. The rest of the processing is a linear scan.

4. Loops in Internal Tables

For completeness on nested loop processing a remark on loops as inner operation is necessary. A loop is required if several lines of the inner table 2 can fulfill the key condition. The loop can be realized by

• ‘LOOP AT itab WHERE …’
• ‘LOOP AT sort_tab WHERE
• READ itab WITH KEY … BINARY SEARCH, Save index, LOOP AT itab FROM index, Exit if condition is not fulfilled anymore.

To be more precise the coding is added

It is important that the SORT on table 2 is outside of the LOOP on table 2, so that it is executed only once. The BINARY SEARCH efficiently finds the starting point of the loop, but it is equally important to leave the LOOP as soon as the condition is no longer fulfilled.

For the LOOP AT WHERE on standard table we expect a linear dependence on the size of table 2, as it must scan the whole table. The other two methods should show logarithmic dependencies. Especially the – not so widely known – workaround on standard tables can help to improve existing programs where a change of the table type is no longer possible.

Figure 3: Averaged runtime (in microseconds) for ‘LOOP AT … WHERE’ with different table sizes N.  Black is the very expensive loop at where on standard table, whichis already for small values outside of the displayed scale. Blue indicates the loop at where on a sorted table, and red the workaround on a standard using read binary search plus loop from index.

Remarks: The measurements were executed in July 2007 on a pretty fast new machine. Older servers will give larger absolute times; however, the relations should hold on all systems.

Here, reliable measurements of reads and loops on internal tables have been shown. The results are summarized in the table below. Only operations scaling faster than linear should be used inside a nested loop, otherwise quadratic coding is produced.

Recommendations for nested loops:

• Use sorted tables as inner tables, if possible, because the usage is simple and fault tolerant. You do not have to track the number of sorts. Sorted tables can be used with reads and also with loops if the access is not unique.
• In cases where the key is either one field only or always completely known, hashed tables can be even better.
• In practise index accesses are in practise quite rare, because the index is usually not known.
• Standard tables should be used as inner tables only in optimized ways where the binary search can be exploited, either in the read or in the loop. But the table must be sorted, and the number of sorts must be kept very small. Optimally, there is only one sort and all later table changes keep the sort order.
• Standard tables without optimization should not be used in a nested loop.
• The order of the tables must be checked, the outer table itab1 should be the smaller one as it must be processed completely. There is no optimization potential for the outer table, it can be standard table. A sort will have no effect, and should therefore be avoided.
• There are more sophisticated ways of programming nested loops using nested indexes which are even a bit more performance-efficient. These are, however, more difficult to program and to test and are only recommended in highly performance critical tasks.

Further Reading: Performance-Optimierung von ABAP-Programmen (in German!)

More information on performance topics can be found in my new textbook on performance (published Nov 2009). However please note, that it is right now only available in German.

Chapter Overview:

1. Introduction
2. Performance Tools
3. Database Know-How
4. Optimal Database Programming
5. Buffers
6. ABAP – Internal Tables
7. Analysis and Optimization
8. Programs and Processes
9. Further Topics
10. Appendix

In the book you will find detailed descriptions of all relevant performance tools. An introduction to database processing, indexes, optimizers etc. is also given. Many database statements are discussed and different alternatives are compared. The resulting recommendations are supported by ABAP test programs which you can download from the publishers webpage (see below). The importance of the buffers in the SAP system are discussed in chaptr five. Of all ABAP statements mainly the usage of internal tables is important for a good performance. With all the presented knowledge you will able to analyse your programs and optimize them. The performance implications of further topics, such as modularisation, workprocesses, remote function calls (RFCs), locks & enqueues, update tasks and prallelization are explained in the eight chapter.

Even more information – including the test programs – can be found on the webpage of the publisher.

I would recommend you especially the examples for the different database statements. The file with the test program (K4a) and necessary overview with the input numbers (K4b) can even be used, if you do not speak German!

Assigned Tags

You must be Logged on to comment or reply to a post.
Thanks for the blog...Performance tips are always welcome -;)

Greetings,

Blag.

Many programs I have seen in assorted systems do not use loops in an effecient manner, and it makes me weep.
The reason this is so sad is that SAP have gone to the trouble of providing many examples of how to speed up programs - go to transaction SE30 and then press the "tips and tricks" button - and there are dozens of performance tips. There is even one on nested loops.
I can only presume that this is not widely known as there are constant streams of questions on the internet about performance problems.
Very clear blog on this issue.
Just a small remark regarding the sample proposed for the workaround  wiht loops in interan tables.
Should the second loop will be instead:
Very clear blog on this issue.
Just a small remark regarding the sample proposed for the workaround  wiht loops in interan tables.
Should the second loop will be instead:
just to finish...
loop at itab2 into wa2 from tabix1

and not
loop at itab2 into wa2 from tabix2

A you see it is a very small mistake.

Regards,
Pascal

Siegfried Boes
Blog Post Author
your comment is not complete ... but you are right ðŸ™‚

it should be behind the read: tabix2 = sy-tabix.

I will update it.

Siegfried

The last line of your blog caught my attention. Can you please come up with details of how to write more sophisticated nested loops. ðŸ™‚
Siegfried Boes
Blog Post Author
You can check other sources for parallel index or parallel cursor, but I have changed my mind. I am not recommending these methods anymore.

They require that both tables are ordered in the same way. The cost for the sort of the outer table is similar to the runtime advantage. Any LOOP with READ or LOOP inside requires no sorted outer table.

The methods are complicated and hard to update, so not really recommended.

Siegfried

I have been using this method from quite a long time and it is very effetive (As execution time for loop in loop get multiplied)..

This is really good analysis.

I remember we had debated once - for use of parallel cursor and sorted table in one of the forums ðŸ™‚ ...

Regards,
Mohaiyuddin

Great analysis and after so many years, still useful. Many thanks to the author!

A remark to "INTO".

In case, the tables have large lines, the performance will decrease significantly.

Using "REFERENCE INTO ref" or "ASSIGNING <fs>" will improve performance.