Re: Select Performance Using Order By on Index

Where angels fear to tread... >From: theo@rasdev.rascal.co.za (T. Kramer 794-1472) >Date: Sun, 19 Nov 1995 12:42:19 +0200 (RSA) >X-Informix-List-Id: <list.8021> > >I have a peformance problem when using select and order by on a multi field >index that, hopefully, some of you SQL gurus can help me with. > >The problem is as follows: > >I need to select and fetch forwards in the natural index order where the index >contains multiple segments on a single data table. To illustrate the point >and for the sake of simplicity I will use numeric fields as follows: > > field1 field2 field3 > ----------------------------- > 1 5 1 > 1 5 2 > 1 6 0 > 1 6 1 > 1 6 2 > 1 6 3 > 2 4 3 > >The index I have created is unique and consists of all three fields in order. > >The query that I use is as follows: > >SELECT * FROM find WHERE > find_field1 = 1 AND find_field2 = 5 AND find_field3 >= 1 OR > find_field1 = 1 AND find_field2 > 5 OR > find_field1 > 1 >ORDER BY find_field1, find_field2, find_field3> >Doing this query on small tables gives reasonable performance, however, if I >do the query on large tables (approx 30000 records) and the required record >is towards the end of the index the select becomes unacceptably slow. Note that >the extent sizes on the table are correctly set up. > >Changing the query to the following: > >SELECT * FROM find WHERE > find_field1 >= AND find_field2 >= 5 AND find_field3 >= 1 >ORDER BY find_field1, find_field2, find_field3 Fixing the typo (find_field1 >= 1), this is a completely different query from your previous one, and must supply a completely different set of answers. This query can never return a row where find_field2 is 4 (or less), because the query criteria rule that out. Likewise, any row where find_field3 is zero (or less) is not returned because the query criteria explicitly rule it out... This much is non-controversial; it is not performance related, but simply a definition of what the query is supposed to do. >provides intantaneous response (so I do know that informix can do it) yet provides >an incorrect result set when scrolling forwards ie. the third and last record >are no longer part of the result set. Comparing the cost using 'explain' also >gives an entire different picture for the two queries ie. the first query is >much more expensive than the second, yet I feel that the second should be more >expensive as records in the natural index sequence have to be skipped. Note that >in both cases informix reports that it does use the index. > >The questions I have are as follows: > >1. Why is this the case on a naturally ordered index? > >2. What can I do to improve the select performance with the result set > being what I require? You don't specify which version of which engine you are using, which could be significant -- please include this information when asking a question, even if you think it isn't relevant. I did some testing with your sample data set, which is not big enough to allow conclusive testing (as you know, and I know you know). I shortened all your names -- the table to ff and the columns to f1, f2, f3. Using a 6.00.UE1 OnLine on Sun Sparc 10 running Solaris 2.4, I got the SET EXPLAIN output for three queries (with the owner removed, and with spaces before close parentheses removed): QUERY: ------ SELECT * FROM ff WHERE f1 = 1 AND f2 = 5 AND f3 >= 1 OR f1 = 1 AND f2 > 5 OR f1 > 1 ORDER BY f1, f2, f3; Estimated Cost: 2 Estimated # of Rows Returned: 3 1) ff: INDEX PATH Filters: ((((ff.f1 = 1 AND ff.f2 = 5) AND ff.f3 >= 1) OR (ff.f1 = 1 AND ff.f2 > 5)) OR ff.f1 > 1) (1) Index Keys: f1 f2 f3 (Key-Only) QUERY: ------ SELECT * FROM ff WHERE f1 >= 1 AND f2 >= 5 AND f3 >= 1 ORDER BY f1, f2, f3; Estimated Cost: 1 Estimated # of Rows Returned: 1 1) ff: INDEX PATH Filters: (ff.f2 >= 5 AND ff.f3 >= 1) (1) Index Keys: f1 f2 f3 (Key-Only) Lower Index Filter: ff.f1 >= 1 QUERY: ------ SELECT * FROM ff WHERE f1 = 1 AND f2 = 5 AND f3 >= 1 UNION SELECT * FROM ff WHERE f1 = 1 AND f2 > 5 UNION SELECT * FROM ff WHERE f1 > 1 ORDER BY 1, 2, 3; Estimated Cost: 5 Estimated # of Rows Returned: 3 Temporary Files Required For: Order By 1) ff: INDEX PATH (1) Index Keys: f1 f2 f3 (Key-Only) Lower Index Filter: (ff.f1 = 1 AND (ff.f2 = 5 AND ff.f3 >= 1)) Union Query: ------------ 1) ff: INDEX PATH (1) Index Keys: f1 f2 f3 (Key-Only) Lower Index Filter: (ff.f1 = 1 AND ff.f2 > 5) Union Query: ------------ 1) ff: INDEX PATH (1) Index Keys: f1 f2 f3 (Key-Only) Lower Index Filter: ff.f1 > 1 The first two are the queries you supplied. Comment: I would have used parentheses around the OR'd clauses, simply to make sure that the optimizer wouldn't misunderstand the query. It does work correctly without them because of the relative precedence of AND and OR, but I had to think twice to be reasonably sure of that. The first of those queries has a more complex condition, but makes full use of the index. The second query only uses the first component of the index -- the filter condition is then applied to each row selected. It is useful that it does it with the key-only search; that reduces the amount of i/o required. If the table had a 4th (non-indexed) column and it had to be retrieved too, things might alter. The third query is an alternative to the first and it produces the same results. Its advantage is that the queries are better bounded -- the first part only works with the rows where f1 = 1 and f2 = 5, the second part only works with the rows where f1 = 1 and f2 > 5, and the third part works with the rows where f1 > 1. These sets are disjoint. Unfortunately, it does use a temporary file for the ordering (and duplicate elimination, even though that is a no-op given the disjoint criteria and the unique index), because it hasn't figured out the disjointness and that each part can be ordered and if the parts are taken in order, the result is in order. Whether this would help at the tail of a giant size table is debatable until the test is done, and thereafter is quantifiable. I think it may work well, but I am by no means certain. It may not work as well in the middle of the range because of that temporary table. Also notice how the ORDER BY syntax had to be changed to use numeric sort column designators. Nothing very conclusive about how to get better performance. Yours, Jonathan Leffler (johnl@informix.com) #include <disclaimer.h> PS: One thought which should make no difference, but which might do so... Have you tried reversing the order of the OR'd clauses in the WHERE clause of the first SELECT?