Re: [PERFORM] best way to fetch next/prev record based on index
Just an update on this: queries in the 'next key' form on fields(a,b,c) only ever use the index for the first field (a). I just never noticed that before...in most cases this is selective enough. In most logical cases in multi part keys the most important stuff comes first. Curiously, queries in the Boolean reversed form (switching and with or, etc.) find the index but do not apply any condition, kind of like an indexed sequential scan... Well, if and when the rowtype comparison can be made to work over multi part keys (and the optimizer is made to do tricks there), postgres can be made to give much better generalized ISAM access. In the meantime, I'll just troubleshoot specific cases via application specific behavior as they come up. In any case, many thanks to Greg and Tom for taking the time to pick this apart. Merlin ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: Well, if and when the rowtype comparison can be made to work over multi part keys (and the optimizer is made to do tricks there), postgres can be made to give much better generalized ISAM access. In the meantime, I'll just troubleshoot specific cases via application specific behavior as they come up. In any case, many thanks to Greg and Tom for taking the time to pick this apart. Well I'm not sure whether you caught it, but Tom did come up with a work-around that works with the current infrastructure if all the columns involved are the same datatype. You can create a regular btree index on the expression array[a,b,c] and then do your lookup using array[a,b,c] array[a1,b1,c1]. This will only work in 7.4, not previous releases, for several reasons. -- greg ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark wrote: Well I'm not sure whether you caught it, but Tom did come up with a work-around that works with the current infrastructure if all the columns involved are the same datatype. You can create a regular btree index on the expression array[a,b,c] and then do your lookup using array[a,b,c] array[a1,b1,c1]. Unfortunately, ISAM files allow keys based on combinations of fields on any type. So this is not an option. (I have spent over 6 months researching this problem). However, this would work: Create index on t(stackparam(array[a::text,b::text,c::text), array['char(2)', 'int', 'date')]; With the 'type strings' queried out in advance. stackparam(text[], text[]) is a C function with uses the types and cats the strings together in such a way that preserves sorting. In any case, this is an ugly and inefficient mess, and I have no desire to do this unless there is no other way. I would much rather see postgres 'get' (a,b,c) (a1, b1, c1)...if there is even a chance this is possible, I'll direct my efforts there. IMNSHO, this form was invented by the SQL folks for dealing with data in an ISAM manner, postgres should be able do it and do it well. Merlin ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: I would much rather see postgres 'get' (a,b,c) (a1, b1, c1)...if there is even a chance this is possible, I'll direct my efforts there. For the ISAM context this whole discussion is kinda moot, because you really don't want to have to plan and execute a fairly expensive query for every record fetch. If we had all the improvements discussed, it would be a reasonably cheap operation by the standards of execute an independent query, but by the standards of fetch next record in my query it'll still suck. (Using PREPARE might help, but only somewhat.) It strikes me that what you really want for ISAM is to improve the cursor mechanism so it will do the things you need. I'm not sure what's involved, but let's talk about that angle for a bit. regards, tom lane ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: I would much rather see postgres 'get' (a,b,c) (a1, b1, c1)...if there is even a chance this is possible, I'll direct my efforts there. For the ISAM context this whole discussion is kinda moot, because you really don't want to have to plan and execute a fairly expensive query for every record fetch. If we had all the improvements discussed, it would be a reasonably cheap operation by the standards of execute an independent query, but by the standards of fetch next record in my query it'll still suck. (Using PREPARE might help, but only somewhat.) It strikes me that what you really want for ISAM is to improve the cursor mechanism so it will do the things you need. I'm not sure what's involved, but let's talk about that angle for a bit. Sorry for the long post, but here's an explanation of why I think things are better off where they are. I've created a middleware that translates ISAM file I/O on the fly to SQL and uses prepared statements over parse/bind to execute them. This is why I was so insistent against scoping prepared statement lifetime to transaction level. Cursors seem attractive at first but they are a decidedly mixed bag. First of all, PostgreSQL cursors are insensitive, which absolutely precludes their use. Supposing they weren't though, I'm not so sure I'd use them if it was possible to do the same things via vanilla queries. It turns out that prepared statements get the job done. Moving them to parse/bind got me a 30% drop in server cpu time and statement execution times run between .1 and .5 ms for random reads. Sequential reads go from that fast to slower depending on index performance. So, I don't have performance issues except where the index doesn't deliver. 2000-1 reads/sec is competitive with commercial ISAM filesystems on the pc (assuming application is not running on the server), and it is far better than any other commercial ISAM emulation I've played with up to this point. Don't have concrete #s, but the server can deliver 2-3 times that in concurrency situations, in many cases the application performance is actually network bound...this is all on pc hardware. Of course, mainframes can do much, much better than this but that's really outside the scope of what I'm trying to do. So, things run pretty fast as they are, and keeping things running through queries keeps things generic and flexible. Also, queries consume zero resources on the server except for the time it takes to process and deal with them. Cursors, OTOH, have to be opened up for every table for every user. Cursors are read-only always, whereas views can be updated with rules. It's worth noting that other commercial ISAM emulation systems (for example Acu4GL by AcuCorp) cut queries on the fly as well, even when cursor options are available. If cursors became sensitive, they would be worth consideration. I've never really had 1000 large ones open at once, be interesting to see how that worked. In ideal object would be a 'pseudo cursor', an insensitive cursor shared by multiple users with each having their own record pointer. This might be better handled via middleware though (this might also give better options handling different locking scenarios). Merlin ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [PERFORM] best way to fetch next/prev record based on index
Stephan Szabo [EMAIL PROTECTED] writes:
Given the comment on make_row_op,
/*
* XXX it's really wrong to generate a simple AND combination for =
* =. We probably need to invent a new runtime node type to handle
* those correctly. For the moment, though, keep on doing this ...
*/
I'd expect it'd be accepted.
Hm, this code is new. As of version 1.169 2004/04/18 it only accepted = and
operators:
/* Combining operators other than =/ is dubious... */
if (row_length != 1
strcmp(opname, =) != 0
strcmp(opname, ) != 0)
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg(row comparison cannot use operator %s,
opname)));
I think perhaps it's a bad idea to be introducing support for standard syntax
until we can support the correct semantics. It will only mislead people and
create backwards-compatibility headaches when we fix it to work properly.
Removing ,=,,= would be trivial. Patch (untested):
--- parse_expr.c.~1.174.~ 2004-07-28 01:01:12.0 -0400
+++ parse_expr.c2004-07-28 01:52:29.0 -0400
@@ -1695,11 +1695,7 @@
*/
oprname = strVal(llast(opname));
- if ((strcmp(oprname, =) == 0) ||
- (strcmp(oprname, ) == 0) ||
- (strcmp(oprname, =) == 0) ||
- (strcmp(oprname, ) == 0) ||
- (strcmp(oprname, =) == 0))
+ if (strcmp(oprname, =) == 0)
{
boolop = AND_EXPR;
}
Fixing it to write out complex boolean expressions wouldn't be too hard, but
I'm not clear it would be worth it, since I suspect the end result would be as
the comment indicates, to introduce a new runtime node.
--
greg
---(end of broadcast)---
TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark [EMAIL PROTECTED] writes:
Fixing it to write out complex boolean expressions wouldn't be too hard, but
I'm not clear it would be worth it, since I suspect the end result would be as
the comment indicates, to introduce a new runtime node.
Just to prove that it isn't really all that hard, I took a stab at doing this.
This is basically only my second attempt to write even trivial bits of server
backend code so I certainly don't suggest anyone try using this code.
In fact it doesn't quite compile, because I have a bit of confusion between
the char *oprname and List *opname variables. Now I could clear that up, but
I'm missing one piece of the puzzle. To make it work I do need a way to
construct a List *opname from or = and I don't know how to do that.
I think that's all I'm missing, but perhaps in the morning I'll look at this
code and wonder what was I thinking?!
This approach won't get the optimizer to actually use an index for these
comparisons, but it will fix the semantics to match the spec. Later we can
either improve the optimizer to detect expressions like this (which I think
would be cooler since some users may write them by hand and not use the
row-expression approach, but I don't see how to do it), or introduce a new
run-time node and have the optimizer handle it. But at least we won't have to
worry about backwards-compatibility issues with the semantics changing.
Oh, I tried to stick to the style, but sometimes I couldn't help myself. I
suppose I would have to fix up the style the rest of the way if I got it
working and you wanted a patch to apply.
/*
* Transform a row op row construct
*/
static Node *
make_row_op(ParseState *pstate, List *opname, Node *ltree, Node *rtree)
{
Node *result = NULL;
RowExpr*lrow,
*rrow;
List *largs,
*rargs;
char *oprname;
/* Inputs are untransformed RowExprs */
lrow = (RowExpr *) transformExpr(pstate, ltree);
rrow = (RowExpr *) transformExpr(pstate, rtree);
Assert(IsA(lrow, RowExpr));
Assert(IsA(rrow, RowExpr));
largs = lrow-args;
rargs = rrow-args;
if (list_length(largs) != list_length(rargs))
ereport(ERROR,
(errcode(ERRCODE_SYNTAX_ERROR),
errmsg(unequal number of entries in row expression)));
oprname = strVal(llast(opname));
if (strcmp(oprname, =) == 0)
{
result = make_row_op_simple(pstate, =, largs, rargs);
}
else if (strcmp(oprname, ) == 0)
{
result = make_row_op_simple(pstate, , largs, rargs);
}
else if ((strcmp(oprname, ) == 0) ||
(strcmp(oprname, ) == 0))
{
result = make_row_op_complex(pstate, oprname, largs, rargs);
}
/* alternatively these last two could just create negated and
* expressions. Which is better depends on whether the extra clause
* confuses the optimizer more or less than having to push the NOTs down
*/
else if (strcmp(oprname, =) == 0)
{
Node *branch = make_row_op_simple(pstate, =, largs, rargs);
result = make_row_op_complex(pstate, , largs, rargs);
result = (Node *) makeBoolExpr(OR_EXPR, list_make2(result, branch));
}
else if (strcmp(oprname, =) == 0)
{
Node *branch = make_row_op_simple(pstate, =, largs, rargs);
result = make_row_op_complex(pstate, , largs, rargs);
result = (Node *) makeBoolExpr(OR_EXPR, list_make2(result, branch));
}
else
{
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg(operator %s is not supported for row expressions,
oprname)));
}
return result;
}
/*
* Handle something like
* (A,B,C) = (X,Y,Z)
* By constructing
* (A=X) AND (B=Y) AND (C=Z)
*
*/
static Node *
make_row_op_simple(ParseState *pstate, char *oprname,
List *largs, List *rargs)
{
ListCell *l, *r;
BoolExprType boolop;
Node *result;
boolop = strcmp(oprname, )==0 ? OR_EXPR : AND_EXPR;
forboth(l, largs, r, rargs)
{
Node*larg = (Node *) lfirst(l);
Node*rarg = (Node *) lfirst(r);
Node*cmp;
cmp = (Node *) make_op(pstate, opname, larg, rarg);
cmp = coerce_to_boolean(pstate, cmp, row comparison);
if (result == NULL)
result = cmp;
else
result = (Node *) makeBoolExpr(boolop,
list_make2(result, cmp));
}
if (result == NULL)
{
/* zero-length rows? Generate constant TRUE or FALSE */
if (boolop == AND_EXPR)
result = makeBoolConst(true, false);
else
result = makeBoolConst(false, false);
}
return result;
}
/*
* Handles something like:
* (A,B,C) (X,Y,Z)
*
* By constructing something like:
* ( ( A X) OR (A=X AND BY) OR (A=X AND B=Y AND CZ) )
*
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark [EMAIL PROTECTED] writes: This approach won't get the optimizer to actually use an index for these comparisons, but it will fix the semantics to match the spec. Later we can either improve the optimizer to detect expressions like this (which I think would be cooler since some users may write them by hand and not use the row-expression approach, but I don't see how to do it), or introduce a new run-time node and have the optimizer handle it. But at least we won't have to worry about backwards-compatibility issues with the semantics changing. Oh, I tried to stick to the style, but sometimes I couldn't help myself. I suppose I would have to fix up the style the rest of the way if I got it working and you wanted a patch to apply. Regarding the = and = operators: can you apply them in the complex pass? If you can, this might be more efficient. /* * Handles something like: * (A,B,C) (X,Y,Z) * * By constructing something like: * ( ( A X) OR (A=X AND BY) OR (A=X AND B=Y AND CZ) ) * ^ */ | the last comparison of the last major clause (or the only comparison for a single field row construct) is a special case. In cases use , in = cases use =, etc.; this is logical equivalent to doing or of simple = intersected with complex . Is this step of the transformation visible to the optimizer/planner? For purely selfish reasons, it would be really nice if a field by field row construction could get a fast path to the index if the fields match the index fields. Merlin ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark [EMAIL PROTECTED] writes: Removing ,=,,= would be trivial. ... and not backwards-compatible. If we did that then cases involving unlabeled row expressions would no longer work as they did in prior releases. For example select (1,2,3) (4,5,6); is accepted by all releases back to 7.0, and probably much further (but 7.0 is the oldest I have handy to test). The only reason the code in parse_expr.c appears new is that the functionality used to be in gram.y. I'd like to see this fixed to comply with the spec, but given the lack of complaints about the existing behavior over so many years, ripping it out meanwhile doesn't seem appropriate. regards, tom lane ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark [EMAIL PROTECTED] writes: Removing ,=,,= would be trivial. ... and not backwards-compatible. If we did that then cases involving unlabeled row expressions would no longer work as they did in prior releases. For example select (1,2,3) (4,5,6); is accepted by all releases back to 7.0, and probably much further (but 7.0 is the oldest I have handy to test). The only reason the code in parse_expr.c appears new is that the functionality used to be in gram.y. I'd like to see this fixed to comply with the spec, but given the lack of complaints about the existing behavior over so many years, ripping it out meanwhile doesn't seem appropriate. Just to clarify: I think Greg is arguing to bring pg to SQL 92 spec and not remove anything. ISTM the SQL standard was designed with exactly my problem in mind: how to get the next key in a table. IMHO, relying on select (1,2,3) (4,5,6); to give a result which is neither standard nor documented seems to be bad style. The current methodology could cause pg to give incorrect results in TPC benchmarks...not good. Also, it's trivial to rewrite that comparison with the old behavior using 'and'. OTOH, it is not trivial to rewrite the comparison to do it the correct way...it's kind of an SQL 'trick question'. Most likely, a very small minority of pg users are even away of the above syntax anyways. To be fair, I'm a big fan of deprecating features for at least one release for compatibility reasons. It's no big deal to me, because I'm already writing the queries out the long way anyways. My interests are in the optimizer. If there is a way to enhance it so that it multi-column comparisons in a logical way, that would be great. Is this theoretically possible (probable)? Merlin ---(end of broadcast)--- TIP 2: you can get off all lists at once with the unregister command (send unregister YourEmailAddressHere to [EMAIL PROTECTED])
Re: [PERFORM] best way to fetch next/prev record based on index
Tom Lane [EMAIL PROTECTED] writes: The only reason the code in parse_expr.c appears new is that the functionality used to be in gram.y. Ah, that was what I was missing. Though it's odd since it seems there was code in parse_expr.c to handle the = case specially. I'd like to see this fixed to comply with the spec, but given the lack of complaints about the existing behavior over so many years, ripping it out meanwhile doesn't seem appropriate. I tried my hand at this last night and think I did an ok first pass. But I'm missing one piece of the puzzle to get it to compile. What do I need to know to be able to construct a List* suitable for passing as the second arg to make_op() knowing only that I want to create a List* to represent = or or so on? I also had another question I didn't ask in the other email. In the midst of a forboth() loop, how would I tell if I'm at the last element of the lists? Would lnext(l)==NULL do it? -- greg ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark [EMAIL PROTECTED] writes: Tom Lane [EMAIL PROTECTED] writes: The only reason the code in parse_expr.c appears new is that the functionality used to be in gram.y. Ah, that was what I was missing. Though it's odd since it seems there was code in parse_expr.c to handle the = case specially. IIRC, the case involving a subselect, eg ... WHERE (1,2) = ANY (SELECT a, b FROM foo) ... has always been handled in parse_expr.c, but cases involving simple rows were previously expanded in gram.y. One of the reasons I moved the logic over to parse_expr.c was the thought that it would be easier to do it right in parse_expr.c --- gram.y would not be allowed to look up related operators, which seems necessary to handle the construct per spec. I tried my hand at this last night and think I did an ok first pass. The main issue in my mind is whether to invent a separate node type for row comparisons. This is probably a good idea for a number of reasons, the most obvious being that there's no way to avoid multiple evaluations of the subexpressions if you try to expand it into simple comparisons. Also it seems likely that the planner would find it easier to recognize the relationship to a multicolumn index than if the thing is expanded. (But teaching the planner and the index mechanisms themselves about this is going to be a major project in any case.) One thing I did not like about your first pass is that it makes unsupportable assumptions about there being a semantic relationship between operators named, say, '' and '='. Postgres used to have such bogosity in a number of places but we've managed to get rid of most of it. (Offhand I think the only remaining hard-wired assumption about operators of particular names having particular semantics is that the foreign key mechanisms assume '=' must be the right operator to compare keys with. Eventually we need to get rid of that too.) IMHO the right way to do this is to look up a suitable btree operator class and use the appropriate member operators of that class. (In a separate-node-type implementation, we'd probably ignore the operators as such altogether, and just call the btree comparison function of the opclass.) It's not entirely clear to me how to select the opclass when the initially given inputs are of different types, though. In the present code we leave it to oper() to do the right thing, including possibly coercing the inputs to matching types. Possibly we should still apply oper(), but then insist that the selected operator appear as a btree opclass member, comparable to the way we handle sort operators now. regards, tom lane ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [PERFORM] best way to fetch next/prev record based on index
Tom Lane [EMAIL PROTECTED] writes: One thing I did not like about your first pass is that it makes unsupportable assumptions about there being a semantic relationship between operators named, say, '' and '='. Hm, I think I even had caught that issue on the mailing list previously. In that case though, it seems even the existing code is insufficient. Instead of testing whether the operator with strcmp against = and it should perhaps be looking for an operator class and the strategy number for the operator and its negator. -- greg ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
[PERFORM] best way to fetch next/prev record based on index
I am in a situation where I have to treat a table as logically ordered based on an index. Right now I'm doing this via queries, and a I need a better way to do it. Cursors do not meet my requirements, because they are always insensitive. Also, my performance requirements are extreme...I need 100% index usage. Currently, I use queries to do this. Unfortunately, the queries can get kind of complex because many if the indexes (keys, really) are over 3 or more columns in a table. So, for a table t with a three part key over columns a,b,c, the query to read the next value from t for given values a1, b1, c1 is select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) In about 95% of cases, the planner correctly selects the index t(a,b,c) and uses it. However, the 5% remaining cases usually come at the worst time, when large tables and 3 or 4 part keys are involved. In those cases sometimes the planner applies the filter to a, but not b or c with a large performance hit. Manipulating statistics on the table does not seem to help. Interestingly, it is possible to rewrite the above query by switching and with or and = with . However when written that way, the planner almost never gets it right. My problem is deceptively simple: how you read the next record from a table based on a given set of values? In practice, this is difficult to implement. If anybody can suggest a alternative/better way to this, I'm all ears. Merlin ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: So, for a table t with a three part key over columns a,b,c, the query to read the next value from t for given values a1, b1, c1 is select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) In about 95% of cases, the planner correctly selects the index t(a,b,c) and uses it. I'm surprised it's that good. Why not do select * from t where a = a1 and b = b1 and c = c1 order by a,b,c limit 1 offset 1; which has a much more obvious translation to an indexscan. regards, tom lane ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [PERFORM] best way to fetch next/prev record based on index
Greg Stark wrote: do it for multi-column keys. It seems it would be nice if some syntax similar to (a,b,c) (a1,b1,c1) worked for this. Hum. It would seem my intuition matches the SQL92 spec and Postgres gets this wrong. [...] Even if Postgres did this right I'm not sure that would solve your index woes. I imagine the first thing Postgres would do is rewrite it into regular scalar expressions. Ideally the optimizer should be capable of then deducing from the scalar expressions that an index scan would be useful. Wow. For once, the standard is my friend. Well, what has to be done? :) Does pg do it the way it does for a reason? From the outside it seems like the planner would have an easier job if it can make a field by field comparison. Would a patch introducing the correct behavior (per the standard) be accepted? It seems pretty complicated (not to mention the planner issues). Merlin ---(end of broadcast)--- TIP 8: explain analyze is your friend
[PERFORM] best way to fetch next/prev record based on index
SELECT * FROM t WHERE (a = a1 AND b=b1 AND c=c1) ORDER BY a,b,c LIMIT 1 OFFSET 1; using the way LIMIT cuts down on sort time (I've never tried it with both LIMIT and OFFSET, though; you could always use LIMIT 2 and skip a record client-side if that works better). Don't want to further clutter the list (answered this question several times already), but your query does not work. What I meant to write was: select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) order by a, b, c limit 1 The problem with your query is it excludes all values of c = c1 regardless of values of a and b. Merlin ---(end of broadcast)--- TIP 7: don't forget to increase your free space map settings
Re: [PERFORM] best way to fetch next/prev record based on index
Interestingly, it is possible to rewrite the above query by switching and with or and = with . However when written that way, the planner almost never gets it right. Well, note it's still not really getting it right even in your case. It's doing an index scan on a=a1 but if you have lots of values in your table where a=a1 and bb1 then it's going to unnecessarily read through all of those. One thing that can help is to add ORDER BY a,b,c LIMIT 1 to your query. That will virtually guarantee that it uses an index scan, which will at least avoid making it scan all the records *after* finding the match. However it still doesn't seem to make Postgres use an Index Cond to allow it to do an instant lookup. I expected WHERE (a,b,c) (a1,b1,c1) to work however it doesn't. It appears to mean aa1 AND bb1 AND cc1 which isn't at all what you want. I imagine the standard dictates this meaning. My problem is deceptively simple: how you read the next record from a table based on a given set of values? In practice, this is difficult to implement. If anybody can suggest a alternative/better way to this, I'm all ears. I've done this a million times for simple integer keys, but I've never had to do it for multi-column keys. It seems it would be nice if some syntax similar to (a,b,c) (a1,b1,c1) worked for this. -- greg ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] wrote .. [snip] select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) I don't see why this is guaranteed to work without an ORDER BY clause, even if TABLE t is clustered on the correct index. Am I missing something? I have two suggestions: (1) I think I would have written SELECT * FROM t WHERE (a = a1 AND b=b1 AND c=c1) ORDER BY a,b,c LIMIT 1 OFFSET 1; using the way LIMIT cuts down on sort time (I've never tried it with both LIMIT and OFFSET, though; you could always use LIMIT 2 and skip a record client-side if that works better). (2) I've seen code where depending on the types and values of the fields, it was possible to construct a string from a, b, c by some sort of concatenation where the index now agreed with the lexicographic (dictionary) ordering on the string. Postgres could do that with a functional index, if your values can be used with this trick. ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html
Correction of [PERFORM] best way to fetch next/prev record based on index
Hi, Merlin, On Tue, 27 Jul 2004 16:13:25 +0200, I myself wrote: You mut not Should be must, not mut :-) My problem is deceptively simple: how you read the next record from a table based on a given set of values? In practice, this is difficult to implement. If anybody can suggest a alternative/better way to this, I'm all ears. So you really want something like 'SELECT * FROM t WHERE a=a1 AND b=b1 AND c=c1 ORDER BY a,b,c ASC LIMIT 1' Sorry, as you want the _next_, and I assume that a1, b1 and c1 are the current row's values, you should rather use something like: 'SELECT * FROM t WHERE a=a1 AND b=b1 AND c=c1 ORDER BY a,b,c ASC LIMIT 1 OFFSET 1' HTH, Markus -- markus schaber | dipl. informatiker logi-track ag | rennweg 14-16 | ch 8001 zürich phone +41-43-888 62 52 | fax +41-43-888 62 53 mailto:[EMAIL PROTECTED] | www.logi-track.com ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [PERFORM] best way to fetch next/prev record based on index
Hi, Merlin, On Tue, 27 Jul 2004 09:07:02 -0400 Merlin Moncure [EMAIL PROTECTED] wrote: So, for a table t with a three part key over columns a,b,c, the query to read the next value from t for given values a1, b1, c1 is select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) You mut not rely on such trickery to get any ordering, as the SQL data model contains no ordering, and a query optimizer is free to deliver you the tuples in any order it feels like. Why don't you add a 'ORDER BY a,b,c ASC' to your query? Interestingly, it is possible to rewrite the above query by switching and with or and = with . However when written that way, the planner almost never gets it right. That's the reason why you cannot rely on any implicit ordering, the planner is free to rewrite a query as it likes as long as it delivers the same tuples, but in any order it wants. My problem is deceptively simple: how you read the next record from a table based on a given set of values? In practice, this is difficult to implement. If anybody can suggest a alternative/better way to this, I'm all ears. So you really want something like 'SELECT * FROM t WHERE a=a1 AND b=b1 AND c=c1 ORDER BY a,b,c ASC LIMIT 1' HTH, Markus -- markus schaber | dipl. informatiker logi-track ag | rennweg 14-16 | ch 8001 zürich phone +41-43-888 62 52 | fax +41-43-888 62 53 mailto:[EMAIL PROTECTED] | www.logi-track.com ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html
Re: [PERFORM] best way to fetch next/prev record based on index
You only want one record to be returned? Tack a LIMIT 1 onto the end of the query. My problem is deceptively simple: how you read the next record from a table based on a given set of values? In practice, this is difficult to implement. If anybody can suggest a alternative/better way to this, I'm all ears. ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [PERFORM] best way to fetch next/prev record based on index
I said: Oh, wait, you're right --- I'm mis-visualizing the situation. Hmm, it sure seems like there ought to be an easy way to do this... The problem is that a multi-column index doesn't actually have the semantics you want. If you are willing to consider adding another index (or replacing the existing 3-column guy), how about create index ti on t((array[a,b,c])); select * from t where array[a,b,c] = array[a1,b1,c1] order by array[a,b,c] limit 1 offset 1; This seems to do the right thing in 7.4 and later. It does require that all three columns have the same datatype though; you weren't specific about the data model ... regards, tom lane ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [PERFORM] best way to fetch next/prev record based on index
Hi, Merlin, On Tue, 27 Jul 2004 10:21:32 -0400 Merlin Moncure [EMAIL PROTECTED] wrote: The basic problem is the planner can't always match the query to the index. So, either the planner has to be helped/fixed or I have to explore another solution. This seems to happen most when the 'a' column has very poor selectivity. In this case, the planner will only examine the 'a' part of the key. So it may help to add some more indices so you have an index for all permutations, Create an index on (a,b,c), (a,c,b), (b,c,a), (b,a,c), (c,a,b) and (c,b,a). So as long as one of the rows has enough selectivity, the planner should be able to select the correct index. Maybe increasing the number of random samples for the rows is useful. HTH, Markus -- markus schaber | dipl. informatiker logi-track ag | rennweg 14-16 | ch 8001 zürich phone +41-43-888 62 52 | fax +41-43-888 62 53 mailto:[EMAIL PROTECTED] | www.logi-track.com ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html
Re: [PERFORM] best way to fetch next/prev record based on index
Greg wrote: One thing that can help is to add ORDER BY a,b,c LIMIT 1 to your query. That will virtually guarantee that it uses an index scan, which will at least avoid making it scan all the records *after* finding the match. However it still doesn't seem to make Postgres use an Index Cond to allow it to do an instant lookup. Yes, order by/limit was accidentally left of my original example. My problem is with the word 'virtually'. do it for multi-column keys. It seems it would be nice if some syntax similar to (a,b,c) (a1,b1,c1) worked for this. 'nice' would be an understatement... if the above syntax is not defined in the standard, I would humbly suggest, well, beg for it to work as you thought it did. That would be GREAT! ISMT it may be that that is in fact standard...(I don't have it, so I don't know). Merlin ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: Plus, your where clause does not guarantee results. No, but in combination with the ORDER BY it does. Please note also that the offset would *always* be one, so your gripe about it not scaling seems misguided to me. regards, tom lane ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [PERFORM] best way to fetch next/prev record based on index
Merlin Moncure [EMAIL PROTECTED] writes: do it for multi-column keys. It seems it would be nice if some syntax similar to (a,b,c) (a1,b1,c1) worked for this. 'nice' would be an understatement... if the above syntax is not defined in the standard, I would humbly suggest, well, beg for it to work as you thought it did. That would be GREAT! ISMT it may be that that is in fact standard...(I don't have it, so I don't know). Hum. It would seem my intuition matches the SQL92 spec and Postgres gets this wrong. From page 208 (Section 8.2.7) of http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt 7) Let Rx and Ry be the two row value constructors of the com- parison predicate and let RXi and RYi be the i-th row value constructor elements of Rx and Ry, respectively. Rx comp op Ry is true, false, or unknown as follows: a) x = Ry is true if and only if RXi = RYi for all i. b) x Ry is true if and only if RXi RYi for some i. c) x Ry is true if and only if RXi = RYi for all i n and RXn RYn for some n. d) x Ry is true if and only if RXi = RYi for all i n and RXn RYn for some n. ... (This is A July 10, 1992 Proposed revision, I don't know how far it differs from the final. I imagine they mean Rx in all the places they use x alone) That fairly clearly specifies (a,b,c) (a1,b1,c1) to work the way you want it to. Less-than-or-equal is then defined based on the above definition. Even if Postgres did this right I'm not sure that would solve your index woes. I imagine the first thing Postgres would do is rewrite it into regular scalar expressions. Ideally the optimizer should be capable of then deducing from the scalar expressions that an index scan would be useful. -- greg ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [PERFORM] best way to fetch next/prev record based on index
Tom Lane [EMAIL PROTECTED] writes: Merlin Moncure [EMAIL PROTECTED] writes: Plus, your where clause does not guarantee results. No, but in combination with the ORDER BY it does. Oh, wait, you're right --- I'm mis-visualizing the situation. Hmm, it sure seems like there ought to be an easy way to do this... regards, tom lane ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [PERFORM] best way to fetch next/prev record based on index
select * from t where a = a1 and (a a1 or b = b1) and (a a1 or b b1 or c c1) In about 95% of cases, the planner correctly selects the index t(a,b,c) and uses it. I'm surprised it's that good. Why not do It is. In fact, it's so good, I mistakenly assumed it would get it right all the time. That led me directly to my current situation. select * from t where a = a1 and b = b1 and c = c1 order by a,b,c limit 1 offset 1; Note: I left off the limit/order part of the query in my original example. My previous experience with offset was that it's not practical for this type of use. Query time degrades when offset gets large...it's basically n^2/2 for a scan of a table. If offset was pumped up to O(1) for any sized offset, the problem would be trivial. Plus, your where clause does not guarantee results. Imagine: a b c 2 3 4 4 2 1 c ! c1 The only other way to rewrite the query is thus (pg has much more trouble with this form): select * from t where aa1 or (a = a1 and b b1) or (a = a1 and b = b1 and c c1) Merlin ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faqs/FAQ.html
Re: [PERFORM] best way to fetch next/prev record based on index
Hmm, it sure seems like there ought to be an easy way to do this... Here is the only alternative that I see: create function column_stacker(text[] columns, text[] types) returns text [...] language 'C' immutable; the above function stacks the columns together in a single string for easy range indexing. create index on t_idx(array[t.a::text, t.b::text, t.c::text], array['int', 'int', 'char(2)']); This is a lot more complicated then it sounds but it can be done. The use of arrays is forced because of limitations in the way pg handles parameters (no big deal). The real disadvantage here is that it these indexes don't help with normal queries so every key gets two indexes :(. I'm just looking for a nudge in the right direction here...if the answer is GIST, I'll start researching that, etc. The ideal solution for me would be a smarter planner or a simple C function to get the next record out of the index (exposed through a UDF). Everything has to stay generic...the ultimate goal is an ISAM driver for pg. Merlin ---(end of broadcast)--- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [PERFORM] best way to fetch next/prev record based on index
On Tue, 27 Jul 2004, Merlin Moncure wrote: Greg Stark wrote: do it for multi-column keys. It seems it would be nice if some syntax similar to (a,b,c) (a1,b1,c1) worked for this. Hum. It would seem my intuition matches the SQL92 spec and Postgres gets this wrong. [...] Even if Postgres did this right I'm not sure that would solve your index woes. I imagine the first thing Postgres would do is rewrite it into regular scalar expressions. Ideally the optimizer should be capable of then deducing from the scalar expressions that an index scan would be useful. Wow. For once, the standard is my friend. Well, what has to be done? :) Does pg do it the way it does for a reason? From the outside it seems like the planner would have an easier job if it can make a field by field comparison. Would a patch introducing the correct behavior (per the standard) be accepted? It seems pretty complicated (not to mention the planner issues). Given the comment on make_row_op, /* * XXX it's really wrong to generate a simple AND combination for = * =. We probably need to invent a new runtime node type to handle * those correctly. For the moment, though, keep on doing this ... */ I'd expect it'd be accepted. ---(end of broadcast)--- TIP 8: explain analyze is your friend
