Rushmore optimisation

[AndrewMozley]

There is a report which is a listing of bank transactions. It reads its records sequentially from one table XARCB.

Each of these records can have one or more associated records in a table XARCT; this table includes a field ID_XARCB which refers to its parent record, a Line_no and a description. It has a primary index with key STR(ID_XARCB) + STR(Line_no).

So there could be between one and ten records in XARCT for a particular record in XARCB.

The report scans through XARCB, and for each record it comes across it likes to find any non-blank description (Desc) from the detail file XARCT. The program used to do this with the instructions :

CREATE CURSOR cResult  . . .
SELECT XARCB
SCAN <for range of dates>
   *  Append a record to the cursor CRESULT
   *  populate that record with relevant fields from XARCB
   SELECT XARCT
   LOCATE FOR ID_XARCB = XARCB.ID .AND. !EMPTY(Desc)
   SELECT cResult
   REPLACE cDesc WITH XARCT.Desc
   ENDSCAN

This worked pretty well, but when the user asks for a listing with hundreds of records in the final report, it runs very slowly: the reason is that each LOCATE instruction in the loop is taking nearly a second, so I have not optimised the processing !

I had vaguely hoped that Rushmore optimisation would help to speed up the processing of the LOCATE instruction. I must be wrong!

What is the simplest way that I can make use of the existence of the index on the XARCT table to retrieve a record (with a non-blank Desc field) to match the current XARCB record.

Thanks. Andrew Mozley

 

[Sng1]

*- Create cursor from XARCB using SQL query and 1 extra field as Desc cResult, then in place of scan..Endscan loop do follwing
SELECT XARCB
set Index To ID_XARCB
Select cResult
set relation to ID_XARCB into XARCB
Replace Desc with XARCB.Desc for !EMPTY(Desc)
Set Relation To

 

[Mike Lewis]

Andrew,

I note that your index is on STR(ID_XARCB) + STR(Line_no) - that is, with those two numeric fields converted to character fields - whereas the condition in you LOCATE is based in part on the original numeric field. I'm not sure about this, but I doubt that Rushmore would kick in in those circumstances.

You might do better by having separate indexes on ID_XARCB and Line_no - that is, on the numeric fields rather than converting them to strings. That way, the LOCATE would at least be partly optimisable.

Also, STR(ID_XARCB) + STR(Line_no) is probably variable length - depending on the number of digits in each of the two numbers. I'm not sure how important that is, but I've always been wary about using variable lenght keys in indexes.

Mike

__________________________________
Mike Lewis (Edinburgh, Scotland)

Visual FoxPro articles, tips and downloads

 

[Chris Miller]

VFP9 introduced BINTOC() not only to enable easier conversion of numbers to binary strings for API structs or similar use cases, but also to replace STR() in index expressions. So you may also index on BINTOC(ID_XARCB) + BINTOC(Line_no).

And Mike already said what seems not known to you, if you index on an expression instead of a single fieldname, Rushmore also only kicks in when you locate for the similar expression, so while it costs a little time to evaluate an expression like BINTOC(22322) + BINTOC(3) it's likely faster to LOATE FOR BINTOC(ID_XARCB) + BINTOC(Line_no) = BINTOC(22322) + BINTOC(3) with an index on BINTOC(ID_XARCB) + BINTOC(Line_no), than to LOCATE FOR BINTOC(ID_XARCB) = 22322 AND Line_no = 3, even if the two single field indexes on ID_XARCB and Line_no (also) exist.

The advantage of single field indexes is they can be used with conditions that make multiple simple comparisons of the fields, but a single index on an expression reduces the number of single optimization steps which finally need to be combined to the overall rushmore result.

Even though it looks more complicated to optimize, you can imagine an index on BINTOC(ID_XARCB) + BINTOC(Line_no) creates a field with the name of the index tag as the name of a persisted computed column and has an index on that field.



Which is a good segue into your EMPTY(field) searches. For reasons that would require a long explanation, I don't recommend an index on EMPTY(field), there is an easier way to make use of the simple index on the description field, which you already have, you can locate FOR NOT field==space(20) if the desc field is a char(20) field.

If it's a memo field, which truly can store "" and doesn't pad with spaces, you could use FOR NOT field=="", if you could index on memo fields. In that case you could index on LEFT(field,1) but an even simpler solution is to index on LEN(field) which can be 0 for memo while it's always N for char(N) fields.

The LEN() index also allows to disregard descriptions with less than X characters as empty, if you like. So you can demand a certain minimum length below which a description is disregarded as such.

Chriss

PS: Looking at your code in detail, as you expect only up to 10 detail records, why not simply LOCATE FOR ID_XARCB = XARCB.ID without the second condition and then CONTINUE until you find non-empty descriptions? Besides look into SET KEY, if you have an index tag on the XARCT.ID_XARCB field, you can SET ORDER TO ID_XARCB and then SET KEY TO XARCB.ID works like a relation on steroids. A simple SCAN..ENDSCAN now is equal to a SCAN FOR ID_XARCB = XARCB.ID. There's less work on finding non-empty descriptions in these 10 records as aftermath than letting Rushmore find the 2 of a all records within the 10 of all records that are the final result. Because Rushmore does not look for the 2 records of the 10 records from the first condition. Rushmore doesn't work incrementally, it treats every single condition on the full table and generates as many bitmaps as atomic conditions are in the FOR or WHERE clause before determining the overall result. Which means it determines all records with non-empty description in all the table, which may be >50% of all data, then finally bitands that with the 10 records having the specific ID_XARCB value.

That's why it can be faster to only look for one very selective condition and check the other condition or conditions in a "full scan" mode, as that "full" scan is just on the few records you already cherrypicked with the major selective condition. SET KEY is quite easy to understand as it actually makes use of what you can also do manually by SEEKing to the first record with a certain foreign key id and then SCAN REST WHILE that key is staying this same value. You know its fast to SKIP 1 with an index setting the order of records, that's because an index is not only fast in finding a single/first record but also all records with the same value or even within a min/max range, for which SET KEY also offers the RANGE option.

 

[AndrewMozley]

Thank you Mike L. I am learning about Rushmore!

Slighly different scenario.

Am processing sequential records in table XARCN (nominal transactions) and trying to locate a corresponding record in table XARCB (this has all transactions).

Each record in XARCN has a date arcn.tran_date and a reference arcn.folio; these identify it uniquely
The XARCB table has corresponding fields arcb.tran_date and arcb.folio. It also has an index x1arcb with a key DTOS(tran_date) + STR(ID,6). (At present this is the only index and is fixed within the application).

Starting from a record in XARCN I want to find the corresponding record in the XARCB table. Using this existing index, I had hoped to write something like :

SELECT arcb
LOCATE FOR DTOS(tran_date) = DTOS(arcn.tran_date) .AND. ;
      arcb.folio = arcn.folio

This does indeed find the record we want, but it takes about 0.6 seconds, so I imagine it is reading all records until it finds one which matches.

So I am instead including code which says :

SELECT arcb
SEEK DTOS(tran_date)
lfound = .F.
SCAN REST WHILE tran_date = arcn.tran_date
    IF folio = arcn.folio
      lFound = .T.
      ENDIF
   ENDSCAN

This achieves the desired result; I had just hoped that (in the first sample), Rushmore would kick in and make use of the index. I realise that I could include a second index (permanent or just within this module)

Thanks again

 

[Chris Miller]

Andrew,

yes, that's a bit strange, but as you know the index on the expression DTOS(tran_date)+STR(ID,6) can be used to SEEK the partial value DTOS(tran_date). But Rushmore does not to use an index which is defined on an expression that at least starts with DTOS().

I think the reason for this is, while seeking to the first record matching the DTOS(tran_date) portion also works for at least getting near to a record with a certain folio value, the index sorts nodes within the date by str(id,6) and not by folio. It's a bit strange, as Rushmore also optimizes other comparison operators as >,<,>=,<=, etc.

Try this:

LOCATE FOR DTOS(tran_date)+STR(ID,6)>=DTOS(arcn.tran_date)+STR(0,6) AND DTOS(tran_date)+STR(ID,6)<=DTOS(arcn.tran_date)+STR(999999,6) .AND. arcb.folio = arcn.folio

Then Rushmore will use the index to limit the result to all records with the same tran_date.

Your solution with a scan rest does the same. I would check which runs faster.

Just remember complicating the FOR condition to guide Rushmore into using the index looks worse than the straight forward simple conditions but the DTOS(tran_date)+STR(ID,6) expressions are not computed. They were once computed when the record entered the table and the index tree was expanded.

So when you want Rushmore to use an index for at least partial optimization because the first part of the index already is very selective, you just have to provide the extreme values for the rest of the index expression. The range does not need to start at STR(-999999,6) when you know the IDs are only positive, you could even shrink the range to STR(10000,6) when you know no id is larger than that, but a smaller range will not make it faster anyway, just like checking IF 42>0 and 42<999999 is not becoming faster when you instead check IF 42>0 and 42<1000.

Chriss

 

[Chris Miller]

Another way of optimising this without Rushmoe but using the index would (again in severeal forum threads now) by SET KEY, this time with the RANGE option:

...
SELECT arcb
SET ORDER TO x1arcb
SET KEY TO RANGE DTOS(arcn.tran_date)+STR(0,6), DTOS(arcn.tran_date)+STR(999999,6)
SCAN for folio = arcn.folio
    ? arb.id
    EXIT
ENDSCAN

Depending on the number of records with the same date, this may outperform Rushmore, because you know you only seek one record and can EXIT Rushmore will examine the whole range for records with same folio, albeit LOCATE will then only go to the first of them anyway.

Chriss

 

[AndrewMozley]

Thank you Chris (replying to your 11.44 posting). That does indeed work. It takes (in a typical case) 0.002 seconds on my machine.

So it seems that Rushmore is prepared to optimise a LOCATE instruction making use of any active index; but it likes the index expression to be complete - in the way you expressed it - by making use of it (twice) in the range expression you provided.

But I take your point that if I really want to maximize performance it is worth considering the simpler form of SEEK , followed by a SCAN.

Thanks again.

 

[Chris Miller]

Hi Andrew,

I see, you haven't yet considered my last post, but even also considering the SET KEY to solution - I'd simply test whether LOCATE (Rushmore) works better than SEEK or SET KEY with a SCAN. The advantage of a single command over a script obviously always is only needing to interpret one line of code instead of multiple lines. The LOCATE is just one entry point into the C++ implementation of the LOCATE command, branching off into Rushmore, but only coming back to the VFP code interpreter with the final result.

It's very obvious you can have loads of code to run within 0.6 seconds, so you have much room to write something working faster and then anything that reduces the overall time works, doesn't it? The main rule I have in mind is only rarely letting users wait for more than 3 seconds. Show progress for longer running tasks and ideally at least keep the system responsive so users can spend their waiting time on something else. Think about expectance of users, too. A progress wouldn't calm users for something they expect to have immediate results.


What will work fastest? I don't really know without having your data. The Rushmore preparation step may look at all index tags on a table, but there are only a few. So the work Rushmore has to do to identify an index for optimization isn't that bad.

It's not easy to measure what's really fastest. Usually you'd do a multitude of searches but this is a case where only the first LOCATE or SEEK or SET KEY matters in the real application and caching always helps to make further calls faster. So ideally measure with high performance counters.

I guess any solution that solves the 0.6 seconds is good and you may also choose what seems most easy to understand from the code maintenance point of view. You can always pick the fastest way and add a comment to explain it to your future self or another developer, but we're unfortunately living in a world of people wasting time with try & error expecting to need less time to figure something out than needing to find the manual page and read it. And that's even more true for software, no matter if it has a help or not. People rather look for someone showing work processes on youtube.

This is not much of a rant, as I also do often enough and this is a driving factor for creating intuitively usable solutions.

I just remember a discussion whether the finger gestures for zooming in and out of a touch display are actually intuitive. It's easy enough to learn that I guess some people already unwarily used it on paper. I don't remember doing that, but I am very aware of disappointment when the zooming gestures doesn't work on a touch display because it depends on context.

Okay, that's far off. The point is reducing your working time also is good for your customer, it's often forgotten this isn't just a one time cost, because most often you implement and maintain and extend features.



Chriss

 

[Chris Miller]

Mike,

your code improvement is noted. Andrew understood very well, because the problem is solved, as far as I see.


Chriss

 

[AndrewMozley]

Thanks for your offer of help, Mike W. As Chriss pointed out, I didn’t understand exactly how Rushmore worked (that was why I raised this thread.). So I have created a table of 490,000 records and measured the time it takes to retrieve each record using a variety of LOCATE and SEEK commands.

This table is created by these commands

   CREATE TABLE xSearch (tFld1 C(4), tFld2 C(4), tValue N(8))
   USE C:\Stage2\NewCMS\xSearch ALIAS Src EXCL
   SELECT Src
   INDEX ON tFld1 + tFld2 TAG x1Search
   INDEX ON tFld2 TAG x2Search

Values of tFld1 range from A00 to G99 (700 records) as do the values of tFld2. The values of tValue are calculated to be unique in this table. Records were then added into the table xSearch in a fairly random order.

I then tried various ways of reading these records and adding them into a cursor to be browsed, measuring the average time it took to retrieve each record and to add it into a new cursor, cResult

1. LOCATE FOR tValue = <value1>

This is retrieving a record using a field which is not part of any key. So (I imagine) about half of the 490,000 records need to be retrieved for each record to be discovered.
Average retrieve (and insertion into the new cursor) : 105 milliseconds

2. LOCATE FOR tFld1 = <value1> .AND. tValue = <value2>

(Value 1 and Value2 have been calculated, to be sure of finding just one unique match)

Average retrieve (and insertion into the new cursor) : 117 milliseconds : It appears that Rushmore has not chosen to take advantage of the index tag x1Search - which could have speeded up the process.

3. LOCATE FOR tFld2 = <value1> .AND. tValue = <value2>
Average retrieve (and insertion into the new cursor) : 25.4 milliseconds : Rushmore has probably made use of the index tag x2Search - even though that does not lead us to a unique record.

4. LOCATE FOR tFld1 = <value1> .AND. tFld2 = <value2>
Average retrieve (and insertion into the new cursor) : 6.6 milliseconds. Rushmore has made use of index x1Search

5. SET ORDER TO TAG x1Search
. . . . .
SEEK lKey1 + lKey2
Average retrieve (and insertion into the new cursor) : 0.003 milliseconds. In this case the SEEK facility within Foxpro is used – not depending on Rushmore optimisation (much faster than method 4).

Thank you again all who have helped.

 

[Chris Miller]

Hi Andrew, thanks for the feedback.

Your first result of a LOCATE on a field NOT indexed only taking 105 ms makes me wonder how you ever got to nearly a whole second (10x as long) for a LOCATE. Maybe because the real world table has many more fields and a bigger RECSIZE()? If not it could point out to have a reason in network (SMB3?).

Anyway, its no wonder a SEEK is fastest when you have the index for it.

As the real world table had no index on folio and even less so including folio with the tran_date field, you could only get near to the record. Whenever you can add an index a SEEK on it wins, but you can't always do what you want, for example working with a third party database. Of course modifications are not always illegal, but a legacy software working with the same dbfs might be affected, If only because a new index uses bintoc and the legacy runtime doesn't have that, and last not least each new index adds to the insert and update times. So it's also not good to index on every expression used but balance the number of indexes and pick the most necessary ones.

I merely tried to get fastest with the given index only and in the end wasn't sure about the code scanning from the near almost match to one with the right folio. And that's not covered by your tests, but never mind.

LOCATE FOR DTOS(tran_date)+STR(ID,6)>=DTOS(arcn.tran_date)+STR(0,6) AND DTOS(tran_date)+STR(ID,6)<=DTOS(arcn.tran_date)+STR(999999,6) .AND. arcb.folio = arcn.folio

makes use of the index x1arcb and still goes direct to the right folio. And the other solutions seek or set key to thetran_date part of the index and then skip to the correct folio.

Chriss

 

[TamarGranor]

I've written about how Rushmore works. This is probably the most relevant:

http://www.tomorrowssolutionsllc.com/Articles/Speed Up Your SQL Code.pdf

In your examples:

Case 2 doesn't use the existing tag because there's no left-hand side that exactly matches a key. Try:

[pre] LOCATE FOR tFld1 + tFld2 = <value1> .AND. tValue = <value2>[/pre]

Case 4 will probably faster if you combine the two fields to match the tag that uses them both:

[pre]LOCATE FOR tFld1 + tFld2 = <value1> + <value2>[/pre]

All that said, when you're looking for a single specific value that matches a tag, SEEK is always going to be faster than LOCATE.

I've also written a whole paper about speeding things up:

http://tomorrowssolutionsllc.com/ConferenceSessions/Cant this application go any faster.PDF

Tamar

 

[AndrewMozley]

Thank you, Tamar; the article to which you refer to is useful.

My option 4 had said :

 LOCATE FOR tFld1 = <value1> .AND. tFld2 = <value2>

The key to index tag x1search is “tfld1 + tfld2”. So changing option 4 to use that explicit key (as I believe you suggest) :

 LOCATE FOR tFld1 + tFld2 = <value1>

. . . improves performance slightly (from 6.6 ms to 6.5 ms).

Still rather surprised that the performance using SEEK (my option 5 : 0.003 ms) is so much better than this Rushmore-aided LOCATE. However we do usually use SEEK where we know the exact key to one of the indexes of the table which we are working with.


Chriss : The tests that I have been running to measure performance in my recent email used a new dbf file of 490,000 records with different fields to my original question in this thread. So the time comparison with the original posting are not applicable. Sorry for the confusion.

Mike Y:
I have created this table of 490,000 records rather laboriously to make records which are created consecutively have non-consecutive keys (in case that matters to the LOCATE logic ! ) :

   LOCAL I, J, K, L, I2, J2, K2, L2
   CREATE TABLE xSearch (tFld1 C(4), tFld2 C(4), tValue N(8))
   USE C:\Stage2\NewCMS\xSearch ALIAS Src EXCL
   SELECT Src
   INDEX ON tFld1 + tFld2 TAG x1Search
   INDEX ON tFld2 TAG x2Search
   *  Now create entries in the table
   FOR I = 1 TO 7
      *  Get the numbers 1 to 7, but not in a consecutive order.
      I2 = MOD(I * 4,7) + 1
      FOR J = 0 TO 99
         *  and the numbers 0 to 99, but not consecutively.
         J2 = MOD(J * 43, 100)
         lFld1 = CHR(64 + I2) + RIGHT(STR(J2 + 100,3),2) + " "
         FOR K = 1 TO 7
            *  Get the numbers 1 to 7, but not in a consecutive order.
            K2 = MOD(K * 4,7) + 1
            FOR L = 0 TO 99
               L2 = MOD(L * 43, 100)
               lFld2 = CHR(64 + K) + RIGHT(STR(L2 + 100,3),2) + " "
               INSERT INTO Src (tFld1, tFld2, tValue) VALUES ;
                     (lFld1, lFld2, I2*100000 + J2*1000 + K2*100 + L2)
               NEXT L
            NEXT K
         NEXT J
      NEXT I

And a typical search to determine the time a LOCATE takes is a loop to retrieve 80 such records. As mentioned, there is the overhead of putting each record into the cResult cursor - but that code is present in each of the tests. This code is my (revised) option 4, where the Rushmore technology comes into play.

*  cmdSearch5()  Seek 80 records using LOCATE with an exact key
   LOCAL lChar1, lChar2, lKey1, lKey2, lSeconds
   CREATE CURSOR cResult (tFld1 C(4), tFld2 C(4), tValue N(8))
   *  Read 80 records starting at X01 Y10,
   *  where X and Y are (ideally) specified by the user.
   lChar1 = "G"
   lChar2 = "B"
   
   *  This shouldn’t be being used explicitly by LOCATE, but set it anyway.
   SELECT Src
   SET ORDER TO TAG x2Search
   
   lSeconds = SECONDS()
   FOR I = 1 TO 80
      lKey1 = lChar1 + "01 "
      lKey2 = lChar2 + RIGHT(STR(110 + I,3), 2) + " "
      SELECT Src
      LOCATE FOR tFld1 + tFld2 = (lKey1 + lKey2)
      INSERT INTO cResult (tFld1, tFld2, tValue) ;
            VALUES (Src.tFld1, Src.tFld2, Src.tValue)
      NEXT I
   lSeconds = SECONDS() - lSeconds
   MESSAGEBOX ("That took " + STR(lSeconds, 7,3) + " seconds.")
   SELECT cResult
   BROWSE
RETURN DODEFAULT()

 

[Chris Miller]

Hi Andrew,

*  This shouldn’t be being used explicitly by LOCATE, but set it anyway.
   SELECT Src
   SET ORDER TO TAG x2Search

It's true LOCATE will use whatever index Rushmore works best with, but the difference in locating while an order is set vs no order is set is, locate wants to find the record from top in index sort order. That's a burden, not a help, because the Rushmore bitmaps are always created with bits set in recono order, so after having the bitmap locate still will need to find which recno is the first in index sort order.

To illustrate that:
1. Instead of SET ORDER TO
SET ORDER TO x2Search set no order or, just as Mike Yearwood said.

2. See how set order affects the locate result in a very easy to follow data example of just 2 records, each of which qualifies to the LOCATE condition:

Create Cursor testdata (num I, bool L)
Insert Into testdata Values (2,.t.)
Insert Into testdata Values (1,.t.)
Index on num tag num

Set order To
Locate For bool
? FOUND(), num

Set Order To num
Locate For bool
? FOUND(), num

Same Locate, different result record (and if you don't trust this add GO TOP before each LOCATE)

So Locate can't simply jump to the record number represented by the first set bit in a Rushmore bitmap. That makes it much slower.

If you now go back to your measurement code and do it once for
LOCATE FOR tFld1 = lKey1 .AND. tFld2 = lKey2
and once for
LOCATE FOR tFld1 + tFld2 = lKey1 + lKey2

The variant using the index expression tFld1 + tFld2 is 3-4 times faster (at least here, for me)

The second thing you can do is only measure what you really want to measure. As fine the argument is, that all other code is executed by anyy variation of the LOCATE (or SEEK), and so you knnow whih oe is fastest, you don't know by which factor, unless you also measure the mere loop doing neither LOCATE or SEEK.

I earlier said you could use HighPerfomance counters. Serch the forum with the Keyword QueryPerformanceCounter. It's quite complicated, though. I suggested it earlier, as only the first search time really counts, VFP can always make use of caching, but in the real world situation coming to the search code for the first time already should be the fastest possible.

But take that aside, to see which runs faster multiple searches are good enough. You can also (very selectively) use coverage profiling:

...
SET COVERAGE TO timing.log ADDITIVE && will not be logged
LOCATE or SEEK && will be logged
SET COVERAGE TO && will also be logged, unfortunately

...

And for determining the time all 80 LOCATEs or SEEKs took do this with the log:

CREATE CURSOR durations (duration B)
SET DECIMALS TO 18
APPEND FROM timing.log TYPE CSV 
SUM duration FOR RECNO()%2=1
ERASE locatesingle.log

You only sum each odd row of the log file as unsetting coverage logging by the 2nd SET COVERAGE TO nothing command will be in the log (as the comment says). If your code for searching has multiple lines, this will need to be adjusted to exclude the measured time for the SET COVERAGE TO line, all other log file lines are relevant to the measurement. Also, convince yourself which lines are logged, the number in the 4th CSV column of the log file is the line number. That also can be used in the FOR condition of the final SUM command.

I've done that and here are screenshots of the tests with no SET ORDER for the Src table:

So you see LOCATE can do much better when you also use the index expression.

Finally something we can all agree on, can't we?

And for sake of completeness here's the timing for the case of an added index on tFld1 with INDEX ON tFld1 TAG x3Search.

You see the timing gets close to that using the index on tFld1+tFld2, but a specialized index is faster than two separate ones.



Chriss

 

[Chris Miller]

And for sake of complete completeness the timing with SEEK:

All measurements on the same data and with 80 iterations, like in your code, Andrew.


Chriss

 

[Chris Miller]

Okay, I took that back.

Chriss