A VERY SCHOLARLY DISCUSSION OF THE EFFECT OF SYNONYMS ON PERFORMANCE by Eugene Volokh, VESOFT Presented at 1982 HPIUG Conference, Copenhagen, DANMARK Published in "Thoughts & Discourses on HP3000 Software", 1st ed.
This paper will discuss the effect of synonyms on IMAGE/3000 performance, in particular the average number of I/Os necessary to perform a DBGET mode 7 (also known as a hashed, calculated, or keyed read).
As is well known, IMAGE/3000 master datasets use an access method called HASHING to implement keyed I/O against them. The essence of this method is that when a DBPUT is performed against a master dataset, the key is translated through a special HASHING FUNCTION (which is explained in Robelle Consulting's SMUG II micro-proceedings) to a record number within the dataset. Then the entry to be added is inserted into the dataset at the resulting record number. Now, when a DBGET mode 7 is performed with the same key, the key is translated through the same hashing function to the same record number; then, the entry we are looking for is just the record with that number. Thus, we should ideally be able to add or retrieve any entry in just one I/O (as opposed to considerably more I/Os needed for other access methods, such as KSAM).
However, a problem arises: what if two keys map to the same record number (this condition is known as a COLLISION)? We can't very well put both entries into the same record number, so we will have to put one of these entries (known as the SECONDARY) somewhere else, and put a pointer to it into the other entry (known as the PRIMARY). Now, if we want to retrieve the secondary, we will have to perform two I/Os: one to retrieve the primary, and then when we see that the primary is not the entry we want, a second to retrieve the secondary. A similar situation arises when a key maps to a record number that already has a primary and a secondary attached to it; then the entry is added to the so-called SYNONYM CHAIN for that record number (the primary and all its secondaries), and we now need three I/Os to get to it. Similar things occur when a key maps to a record number that has two synonyms, three synonyms, etc.
In short, access to primaries requires only one I/O; however, access to secondaries requires two or more I/Os (unless the blocking factor is greater than one).
It is also well known that the more full a dataset is, the more secondaries there are in that dataset; and, the more secondaries there are, the more I/Os are needed (on the average) to retrieve an entry. However, how many more I/Os are needed, nobody knows.
This brings up an interesting question: what is the relationship of the average number of I/Os needed to retrieve an entry to how full the dataset is (THE FILL FACTOR), measured from 0=empty, to 1=full.
In this paper, I will attempt to solve the above question theoretically, i.e. derive a general formula that, given the fill factor, will return the average number of I/Os. In order to do this, however, some simplifying assumptions must be made:
First of all, I will assume that our hashing function is "good", i.e. regardless of the data fed to it, it will return each record number with roughly equal frequency. Thus, for instance, a hashing function that returns record number 17 half of the time, or returns odd record numbers more often than even record numbers is not "good". Fortunately, IMAGE's hashing function is a relatively good one. (Note: If the dataset's key is numeric, e.g. I2, a not-so-good hashing function is used by IMAGE; thus, these results may not be correct for datasets with numeric keys).
Secondly, I will assume that the master dataset in question has blocking factor 1. This will permit me to ignore the possibility of a synonym being in the same block as the primary, thus requiring no additional I/Os when it is retrieved. I must confess that this may be a quite fallacious assumption in that synonyms very often are in the same blocks as their primaries; however, although this fact may be decrease the average number of I/Os for a given fill factor, it should not influence the overall nature of the function we are seeking.
Now, we can get down to business. Let us define N = number of entries in the dataset, C = capacity of the dataset, F = fill factor = N/C, An X-ary = an entry that is the Xth in a synonym chain, and thus takes X I/Os to retrieve. Thus, a 1-ary is a primary, and 2-arys, 3-arys, 4-arys, etc. are all secondaries, E (X, I) = the expected number of X-aries in a dataset after I entries have been added.
Let us thus ask the following question:
How many primaries can we expect in the dataset after I entries have been added to it, i.e. what is E(1,I)?
Well, we can expect as many primaries as are expected after I-1 entries have been added (i.e. E(1,I-1)) plus either 0 or 1 more primaries (depending on whether the Ith entry becomes a primary or not), i.e.
E(1,I) = E(1,I-1)+ [1]
1*(probability that the Ith entry becomes a primary).
What is the probability that the Ith entry becomes a primary? An entry becomes a primary if it hashes to any slot in the dataset that is NOT OCCUPIED BY ANOTHER PRIMARY, i.e. that is empty or is occupied by a secondary! The probability that the Ith entry becomes a primary is thus equal to
(the number of slots that are not occupied by another primary) -------------------------------------------------------------- (the total number of slots that it could possibly hash to)
The total number of slots that it could possibly hash to is, of course, C. The number of slots that are not occupied by another primary is C - (the number of slots that are occupied by a primary). When the Ith entry is being added, the expected number of slots that are occupied by a primary is by definition E(1,I-1).
Thus, the probability that the Ith entry will become a primary is
Therefore, substituting [2] into [1],
Moreover, we know that E(1,0) = expected number of primaries when the dataset has 0 entries, i.e. when the dataset is empty = 0. Thus, we have a recursive formula for E(1,I). From it we can, for instance, determine that E(1,1) = E(1,0)*(1-1/C)+1=0*(1-1/C)+1=1, that E(1,2) = E(1,1)*(1-1/C)+1=1*(1-1/C)+1=2-1/C, etc.
But, we want a non-recursive, straightforward formula. We can obtain it by further substituting [3] into itself:
E(1,I) = E(1,I-1)*(1-1/C)+1 = [4]
= (E(1,I-2)*(1-1/C)+1)*(1-1/C)+1 =
= E(1,I-2)*(1-1/C)^2+(1-1/C)+1 =
...
= (1-1/C)^(I-1)+(1-1/C)^(I-2)+ ... +(1-1/C)^2+(1-1/C)+1
The above is what is known in mathematical circles as a geometric progression, i.e. a sum of terms each one of which is (1-1/C) times less than the previous one. It is also known that the sum of the above progression is
(1-1/C)^I-1 (1-1/C)^I-1 ----------- = ----------- = -C*((1-1/C)^I-1) = C*(1-(1-1/C)^I) [5] (1-1/C)-1 -1/C
Thus, E(1,I) = C*(1-(1-1/C)^I). If what we are looking for is the percentage of the dataset's entries that are primaries, we should consider E(1,I)/I = (C/I)*(1-(1-1/C)^I).
Now, let us take a closer look at (1-1/C)^I. Clearly,
Also, we know that when C is sufficiently large (say, in excess of 100), (1-1/C)^C is close to (and in fact gets closer as C increases) the constant 1/e = 1/2.71828... = 0.367879....
Thus, for large C, we have (substituting [6] into [5])
E(1,I)/I = (C/I)*(1-(1-1/C)^I) = (C/I)*(1-(1/e)^(I/C)) = [7]
= (C/I)*(1-e^(-I/C)) = (1-e^(-I/C))/(I/C).
So, the expected fraction of primaries in our dataset, which contains N entries, is E(1,N)/N = (1-e^(-N/C))/(N/C). But, N/C = F! Therefore,
-F
E (1,N) 1-e
------- = ----- [8]
N F
Ugh.
At last, we have a solid result -- we have determined the expected number of primaries in a dataset given its fill factor. An interesting corollary to the above is that when the dataset is full, i.e. N=C or F=1, E(1,N)/N = (1-e^(-1))/1 = .632121.... Thus, even when a dataset is full, 63% of all entries in it should be primaries.
However, the battle is far from over yet. What we are trying to do is to determine the average number of I/Os needed to retrieve a given entry. Before doing the actual derivations, let me explain the method that we are going to use:
The average number of I/Os needed to retrieve a given entry is equal to the total number of I/Os needed to retrieve all entries in the dataset divided by the total number of entries.
The total number of I/Os needed to retrieve all entries in the dataset is the total number of I/Os needed to retrieve all primaries + the total number of I/Os needed to retrieve all 2-aries + .... But, the total number of I/Os needed to retrieve all X-aries = the expected number of X-aries * the number of I/Os needed to retrieve an X-ary. Clearly, to retrieve an X-ary we would need X I/Os; thus, the total number of I/Os needed to retrive all X-aries = X*E(X,N).
Therefore, the total number of I/Os needed to retrieve all entries in the dataset is 1*E(1,N)+2*E(2,N)+3*E(3,N)+.... And, the average number of I/Os needed to retrieve a given entry = the number of I/Os needed to retrieve all entries / number of entries =
1*E(1,N)+2*E(2,N)+3*E(3,N)+...
------------------------------ [9]
N
We have already determined E(1,N). Now, if we can only determine E(2,N), E(3,N), ..., we will be almost done. So, this is what we will attempt to do below.
How are we going to determine E(X,I) for X>1?
Well, reasoning similar to the one we used for E(1,I) indicates that
E(X,I) = E(X,I-1)+ [10]
(probability that the Ith entry becomes an X-ary)
Now, what is the probability that the Ith entry becomes an X-ary? To answer this, we must ask: under what conditions would an entry become an X-ary? The answer to this is: if and only if it hashes to a slot that is currently occupied by a primary which has a synonym chain of length exactly X-1. How many entries like this are there? Well, the distinguishing feature of this kind of entry is that it has in its synonym chain an (X-1)-ary but no X-aries. Thus, the number of such primary entries = number of (X-1)-aries - number of X-aries = E(X-1,I-1) - E(X,I-1). Thus, the probability that the Ith entry becomes an X-ary is
E(X-1,I-1)-E(X,I-1)
------------------- [11]
C
and thus
To obtain a non-recursive formula, we expand the above into
I
---
\ E(X-1,J-1)
E(X,I) = - ---------- * (1-1/C)^(I-J) [13]
/ C
---
J=1
In particular, let us try to determine E(2,I) = the expected number of 2-aries after I entries have been added.
E(2,I) = sum(J=1:I | E(1,J-1)/C * (1-1/C)^(I-J)) ~ [14]
~ sum(J=1:I | E(1,J)/C * (1-1/C)^(I-J)) =
= sum(J=1:I | C*(1-e^(-J/C))/C * (1-1/C)^(I-J)) ~
= sum(J=1:I | (1-1/C)^(I-J)) -
sum(J=1:I | e^(-J/C) * (1-1/C)^(I-J)) =
= sum(J=0:I-1 | (1-1/C)^J) -
sum(J=1:I | e^(-J/C) * (1-1/C)^(I-J))
Now, we can observe that sum(J=0:I-1 | (1-1/C)^J) is just E(1,I); moreover, (1-1/C)^(I-J) = ((1-1/C)^C)^((I-J)/C) ~ e^(-(I-J)/C). Thus,
E(2,I) = E(1,I) - sum(J=1:I | e^(-J/C) * e^(-(I-J)/C)) = [15]
= E(1,I) - sum(J=1:I | e^(-I/C)) =
= E(1,I) - I*e^(-I/C).
So, E(2,N) = E(1,N)-N*e^(-N/C); furthermore,
E (2,N) E (1,N) -N/C E (1,N) -F
------- = ------- - e = ------- - e [16]
N N N
Now, we can proceed to the general question: what is E(X,I) (or, what is E(X,I)/I)?
I claim that for X>=2,
E (X,I) E (X-1,I) (I/C)^(X-2) -I/C
------- = --------- - ----------- * e [17]
I I (X-1)!
where X! = X factorial = 1*2*3*...*X.
I will prove this claim via a device known as mathematical induction; i.e. I will demonstrate that the claim is valid for X=2, and if it is valid for X=A, then it is also valid for X=A+1. Clearly, this will demonstrate that the claim is valid for X=2, and therefore for X=2+1=3, and therefore also for X=3+1=4, etc.
First of all, I must prove that the claim is valid for X=2. In the case of X=2, the claim says that
E (2,I) E (1,I) (I/C)^0 -I/C E (1,I) -I/C
------- = ------- - ------- * e = ------- - e [18]
I I 0! I
But, this was proven above in the derivation of E(2,I). Thus, we know that our claim is valid for X=2.
Now let us assume that the claim is valid for X=A, i.e.
E (X,A) E (X-1,A) (A/C)^(X-2) -A/C
------- = --------- - ----------- * e [19]
A A X!
We must show that it is also valid for X=A+1.
E(A+1,I) = SUM(J=1:I | E(A,J-1)/C * (1-1/C)^(I-J)) = [20]
= SUM(J=1:I | (E(A-1,J-1)-J*(J/C)^(A-2)/(A-1)!*e^(-J/C))*
(1-1/C)^(I-J)/C) =
= SUM(J=1:I | E(A-1,J-1)*(1-1/C)^(I-J)/C) -
SUM(J=1:I | (J/C)^(A-1)/(A-1)!*e^(-J/C)*
(1-1/C)^(I-J)/C) =
= E(A,I) -
SUM(J=1:I | (J/C)^(A-1)/(A-1)!*e^(-J/C)*e^(-(I-J)/C)) =
= E(A,I) -
SUM(J=1:I | (J/C)^(A-1)/(A-1)!*e^(-I/C)) =
= E(A,I) - e^(-I/C)/(A-1)!*SUM(J=1:I | J^(A-1))/C^(A-1) =
We know that SUM(J=1:I | J^(A-1)) = I^A/A + smaller powers of I, and is thus approximately equal to I^A/A; so,
E(A+1,I) = E(A,I) - e^(-I/C)/(A-1)!* [21]
SUM(J=1:I | J^(A-1))/C^(A-1) =
= E(A,I) - e^(-I/C)/(A-1)!*(I^A/A)/C^(A-1) =
= E(A,I) - e^(-I/C)/A!*I*(I/C)^(A-1)
Thus,
E (A+1,I) E (A,I) (I/C)^(A-1) -I/C
--------- = ------- - ----------- * e [22]
I I X!
This is indeed is the result predicted by our claim for X=A+1. Thus, we know that if the claim is valid for X=A, it is valid for X=A+1.
Thus, we are justified in saying that our claim is true. Finally, we have obtained a general (albeit recursive) formula for E (X,I).
Now comes the final phase of our proof -- the derivation of the average number of I/Os needed to retrieve a record. For the remainder of this discussion, let us for convenience use the fill factor F = N/C.
The average number of I/Os needed to retrieve a record is equal to the total number of I/Os needed to retrieve all records divided by the number of records.
The total number of I/Os needed to retrieve all records is equal to (the expected number of 1-arys)*(I/Os needed to retrieve a 1-ary)+ (the expected number of 2-arys)*(I/Os needed to retrieve a 2-ary)+...
But, we know that the expected number of X-arys is simply E(X,N); the number of I/Os needed to retrieve a X-ary is simply X; and, the number of records is N.
Thus, the average number of I/Os needed to retrieve a record is
1*E(1,N)+2*E(2,N)+... E (1,N) E (2,N)
--------------------- = 1*------- + 2*------- + ... [23]
N N N
We have found that
E (X,N) E (X-1,N) F^(X-2) -F
------- = --------- - ------- * e [24]
N N (X-1)!
Thus,
E (X,N) E (1,N) F^0 -F F^1 -F F^(X-2) -F
------- = ------- - ---*e - ---*e - ... - -------*e [25]
N N 1! 2! (X-1)!
Now,
E(1,N)/N = (1-e^(-F))/F = [26]
= e^(-F)*(e^F-1)/F =
= e^(-F)*(1+(F^1)/1!+(F^2)/2!+(F^3)/3!+...-1)/F =
= e^(-F)*((F^1)/1!+(F^2)/2!+(F^3)/3!+...)/F =
= e^(-F)*((F^0)/1!+(F^1)/2!+(F^2)/3!+...)
So,
E(X,N)/N = E(1,N)/N - [27]
((F^0)/1!+(F^1)/2!+...+(F^(X-2))/(X-1)!)*e^(-F) =
= ((F^0)/1!+(F^1)/2!+...)*e^(-F) -
((F^0)/1!+(F^1)/2!+...+(F^(X-2))/(X-1)!)*e^(-F) =
= (F^(X-1)/X!+F^X/(X+1)!+...)*e^(-F) =
= sum(Y=X-1:infinity | F^Y/(Y+1)!)*e^(-F)
We are trying to calculate
E (1,N) E (2,N) E (3,N)
1*------- + 2*------- + 3*------- + ... = [28]
N N N
= 1*(F^0/1!+F^1/2!+F^2/3!+...)*e^(-F) +
2* (F^1/2!+F^2/3!+...)*e^(-F) +
3* (F^2/3!+...)*e^(-F) + ...
How many times will F^(Y-1)/Y! be included in the above sum for any given Y? Well, it will be included once in the first row, with a factor of 1; once in the second row, with a factor of 2; and so on until the Yth row, in which it will occur with a factor of Y. In the (Y+1)st row, it will no longer occur, because the (Y+1)st row contains only terms starting with (F^Y)/(Y+1)! Thus, in total, F^(Y-1)/Y! will occur in the resulting sum with a factor of (1+2+3+...+Y) = (Y+1)*Y/2. Thus, the average number of I/Os will be
= sum(Y=1:infinity | F^(Y-1)/Y!*(Y+1)*Y/2) * e^(-F) = [29]
= sum(Y=1:infinity | F^(Y-1)/(Y-1)!*(Y+1)/2) * e^(-F) =
= sum(Y=1:infinity | F^(Y-1)/(Y-1)!*(Y-1)/2+
F^(Y-1)/(Y-1)!*2/2) * e^(-F) =
= sum(Y=0:infinity | F^Y/Y!*Y/2) * e^(-F) +
sum(Y=0:infinity | F^Y/Y!) * e^(-F) =
= sum(Y=1:infinity | F^Y/(Y-1)!)/2 * e^(-F) +
sum(Y=0:infinity | F^Y/Y!) * e^(-F) =
= (F/2+1) * sum(Y=0:infinity | F^Y/Y!) * e^(-F)
Here we can again observe that sum(Y=0:infinity | F^Y/Y!) = e^F. Thus, the average number of I/Os is
= (F/2+1) * sum(Y=0:infinity | F^Y/Y!) * e^(-F) = [30] = (F/2+1) * e^F * e^(-F) = = 1+F/2
Eureka! So,
THE AVERAGE NUMBER OF I/OS REQUIRED FOR A DBGET MODE 7 AGAINST AN IMAGE/3000 MASTER DATASET WITH BLOCKING FACTOR 1 AND FILL FACTOR F IS 1+F/2.
At last.
Now that all of you have been dazzled by the above display of Incredibly Incomprehensible Mathematical Formulae, an important question comes up:
As an amateur mathematician (i.e. someone who is crazy enough to actually LIKE the above mumbo-jumbo), I can answer the above with "Why not?" or "Because it's there" or "But aren't you just overwhelmed by the incredible beauty of the result?".
However, as a computer programmer who works on what is essentially a business computer, I feel that I ought to show some applications of the above mess. Well, here they come.
For one, note that the formula generated depends only on how full the dataset is as a percentage, not on the actual number of entries in the datasets. Thus, if we compare the efficiency of IMAGE mode 7 DBGETs and KSAM FREADBYKEYs, we find that IMAGE should theoretically require only 1 to 1.5 I/Os, whereas KSAM requires on the order of log N I/Os.
Another point that this proves is that increasing the capacity of a dataset will not necessarily greatly improve the efficiency of master dataset access (as is commonly believed). For instance, if the capacity of a dataset that is 80% full is doubled, the average number of I/Os required for a DBGET mode 7 against this dataset will decrease from 1.4 to 1.2, which may not be significant enough to offset the two-fold increase in disc space usage.
On the other hand, if you see that the fraction of secondaries is much larger than 1-(1-e^(-F))/F and/or the average number of I/Os is much greater than 1+F/2, you may have come across a case in which IMAGE's hashing algorithm behaves poorly. In this case, changing the capacity very slightly may cut the number of secondaries and the average number of I/Os dramatically. In one case which I ran across, changing the capacity by 1 cut the average number of I/Os in half! The actual number of secondaries and the actual average number of I/Os may be obtained from various database utilities such as DBLOADNG, DBSTAT2, or Robelle Consulting's HowMessy.
The two major results that were derived in this paper are:
If a dataset has fill factor (number of entries/capacity) F,
the expected fraction of primaries in that dataset is:
-F
1-e
P(F)=----- [8]
F
and the expected average number of I/Os needed to retrieve an entry (if the dataset has blocking factor 1) is:
The following is a table of the results that were expected and the results that were obtained for several test datasets:
--------Actual-------- -------Expected------- --C-- --N-- --F-- %Primaries Avg num IOs %Primaries Avg num IOs 650 525 80.8% 67.2% 1.411 68.6% 1.404 331 193 58.3% 75.1% 1.337 75.8% 1.291 331 193 58.3% 75.6% 1.275 75.8% 1.291 15000 10582 70.5% 71.0% 1.387 71.8% 1.352 331 118 35.6% 80.5% 1.203 84.1% 1.178 250 206 82.4% 66.0% 1.456 68.1% 1.412
Of the following, some datasets (the one marked +) have primary percentages that are significantly less than expected and average numbers of I/Os that are significantly more than expected. The datasets marked - are exact copies of those datasets with slightly changed capacities -- their primary percentages and average numbers of I/Os are quite close to those expected:
--------Actual-------- -------Expected------- --C-- --N-- --F-- %Primaries Avg num IOs %Primaries Avg num IOs + 128 123 96.1% 7.3% 13.008 64.3% 1.480 + 127 123 96.8% 52.0% 1.667 64.0% 1.484 - 126 123 97.6% 70.7% 1.407 63.9% 1.488 + 320 284 88.9% 37.3% 2.810 66.3% 1.444 - 319 284 89.0% 65.5% 1.444 66.2% 1.445 + 400 158 39.5% 69.6% 1.456 82.6% 1.198 - 399 158 39.6% 86.1% 1.158 82.6% 1.198
These datasets are good examples of instances in which slightly altering the dataset capacity (even decreasing it!) can significantly improve performance.
Go to Adager's index of technical papers ⮂ View original 1980s typography