pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
best way to fetch next/prev record based on index
34+ messages / 7 participants
[nested] [flat]

* best way to fetch next/prev record based on index
@ 2004-07-27 13:07  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 4 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 13:07 UTC (permalink / raw)
  To: pgsql-performance

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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 14:13  Markus Schaber <schabios@logi-track.com>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  3 siblings, 0 replies; 34+ messages in thread

From: Markus Schaber @ 2004-07-27 14:13 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

Hi, Merlin,

On Tue, 27 Jul 2004 09:07:02 -0400
"Merlin Moncure" <merlin.moncure@rcsonline.com> 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:schabios@logi-track.com | www.logi-track.com



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 14:21  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 14:21 UTC (permalink / raw)
  To: Markus Schaber <schabios@logi-track.com>; +Cc: pgsql-performance

> > 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?

Left that part out (oops) :).  My queries always have that at the end
(or they will give incorrect results!).  All are suffixed with order by
a,b,c limit n.  n is manipulated in some cases for progressive read
ahead (kind of like fetch 'n' in cursors)).

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.

Merlin



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 14:36  Rod Taylor <pg@rbt.ca>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  3 siblings, 0 replies; 34+ messages in thread

From: Rod Taylor @ 2004-07-27 14:36 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

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.





^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 14:50  Markus Schaber <schabios@logi-track.com>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Markus Schaber @ 2004-07-27 14:50 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

Hi, Merlin,

On Tue, 27 Jul 2004 10:21:32 -0400
"Merlin Moncure" <merlin.moncure@rcsonline.com> 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:schabios@logi-track.com | www.logi-track.com



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 15:03  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 15:03 UTC (permalink / raw)
  To: Markus Schaber <schabios@logi-track.com>; +Cc: pgsql-performance; Rod Taylor <pg@rbt.ca>

Markus 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).

It is mathematically impossible for any index except for (a,b,c) to
work.  Although, in theory, (a,b) could be used...but that wouldn't
help.  In any event, creating 1000s and 1000s of extra indices is not an
option.

Here is some log snippets illustrating my problem:

Here is a log snippet illustrating things when everything is working ok
(notice the sub-millisecond times):

prepare data3_read_next_menu_item_recent_file_0 (character varying,
numeric, numeric, numeric)
	as select xmin, xmax, *
	from data3.menu_item_recent_file
	where mir_user_id >= $1 and 
		(mir_user_id >  $1 or  mir_menu_item_id >= $2) and 
		(mir_user_id >  $1 or  mir_menu_item_id >  $2 or
mir_sequence_no >  $3)
	order by mir_user_id, mir_menu_item_id, mir_sequence_no
	limit $4 0.000849704 sec
data3_read_next_menu_item_recent_file_0 0.000435999 sec params:
$1=MERLIN $2=00057 $3=00000001 $4=1 
data3_read_next_menu_item_recent_file_0 0.0117151 sec params: $1=MERLIN
$2=00058 $3=00000002 $4=2 
data3_read_next_menu_item_recent_file_0 0.0385374 sec params: $1=MERLIN
$2=00203 $3=00000005 $4=3 
data3_read_next_menu_item_recent_file_0 0.0211677 sec params: $1=MERLIN
$2=00449 $3=00000010 $4=4 
data3_read_next_menu_item_recent_file_0 0.000818999 sec params:
$1=MERLIN $2=00813 $3=00000008 $4=5

Here is a log snippet when there is a problem:
data3_start_nl_line_file_0 37.2677 sec params: $1= $2=008768 $3=003 $4=1

prepare data3_read_next_line_file_0 (character, numeric, numeric,
numeric)
	as select xmin, xmax, *
	from data3.line_file
	where li_quote_flag >= $1 and 
		(li_quote_flag >  $1 or  li_order_no >= $2) and 
		(li_quote_flag >  $1 or  li_order_no >  $2 or  li_seq_no
>  $3)
	order by li_quote_flag, li_order_no, li_seq_no
	limit $4 0.000839501 sec
data3_read_next_line_file_0 0.313869 sec params: $1= $2=008768 $3=005
$4=1 
data3_read_next_line_file_0 0.343179 sec params: $1= $2=008768 $3=006
$4=2 
data3_read_next_line_file_0 0.308703 sec params: $1= $2=008768 $3=008
$4=3 
data3_read_next_line_file_0 0.306802 sec params: $1= $2=008768 $3=011
$4=4 
data3_read_next_line_file_0 0.311033 sec params: $1= $2=008768 $3=015
$4=5

in the above statements, .3 sec to return a single row is very poor.
Explain only matches li_quote_flag to the index which offers very poor
selectivity.  li_quote_flag is a char(1) and there is an index on
line_file on the three where columns in the proper order.

Merlin



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 15:14  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  3 siblings, 0 replies; 34+ messages in thread

From: Tom Lane @ 2004-07-27 15:14 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

"Merlin Moncure" <merlin.moncure@rcsonline.com> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 15:29  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 15:29 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance

> > 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
	a >   a1 or
     (a >=  a1 and b > b1) or
     (a >=  a1 and b >= b1 and c > c1)

Merlin



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 15:33  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Tom Lane @ 2004-07-27 15:33 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

"Merlin Moncure" <merlin.moncure@rcsonline.com> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 15:40  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 1 reply; 34+ messages in thread

From: Tom Lane @ 2004-07-27 15:40 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

Tom Lane <tgl@sss.pgh.pa.us> writes:
> "Merlin Moncure" <merlin.moncure@rcsonline.com> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 16:00  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 34+ messages in thread

From: Tom Lane @ 2004-07-27 16:00 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 16:02  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 16:02 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance

> 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





^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 17:12  Greg Stark <gsstark@mit.edu>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  3 siblings, 0 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-27 17:12 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance



> 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 b<b1 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 a>a1 AND b>b1 AND c>c1 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




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 17:28  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 17:28 UTC (permalink / raw)
  To: gsstark@mit.edu; +Cc: pgsql-performance

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





^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 17:37  andrew@pillette.com
  0 siblings, 0 replies; 34+ messages in thread

From: andrew@pillette.com @ 2004-07-27 17:37 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance

"Merlin Moncure" <merlin.moncure@rcsonline.com> 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.



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* best way to fetch next/prev record based on index
@ 2004-07-27 18:17  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 18:17 UTC (permalink / raw)
  To: andrew@pillette.com; +Cc: pgsql-performance

> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 18:38  Greg Stark <gsstark@mit.edu>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-27 18:38 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: gsstark@mit.edu; pgsql-performance


"Merlin Moncure" <merlin.moncure@rcsonline.com> 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.



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-27 19:20  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Merlin Moncure @ 2004-07-27 19:20 UTC (permalink / raw)
  To: gsstark@mit.edu; +Cc: pgsql-performance; Tom Lane <tgl@sss.pgh.pa.us>

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





^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 03:45  Stephan Szabo <sszabo@megazone.bigpanda.com>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Stephan Szabo @ 2004-07-28 03:45 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: gsstark@mit.edu, pgsql-performance@postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>


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.




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 05:53  Greg Stark <gsstark@mit.edu>
  parent: Stephan Szabo <sszabo@megazone.bigpanda.com>
  0 siblings, 2 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-28 05:53 UTC (permalink / raw)
  To: Stephan Szabo <sszabo@megazone.bigpanda.com>; +Cc: Merlin Moncure <merlin.moncure@rcsonline.com>; gsstark@mit.edu, pgsql-performance@postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>


Stephan Szabo <sszabo@megazone.bigpanda.com> 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):

inline patch 1: parse_expr.c (+1/-5 lines) download inline-1.patch--- parse_expr.c.~1.174.~ 2004-07-28 01:01:12.000000000 -0400 +++ parse_expr.c 2004-07-28 01:52:29.000000000 -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 ^ permalink raw reply [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 07:14  Greg Stark <gsstark@mit.edu>
  parent: Greg Stark <gsstark@mit.edu>
  1 sibling, 0 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-28 07:14 UTC (permalink / raw)
  To: Greg Stark <gsstark@MIT.EDU>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; gsstark@mit.edu, pgsql-performance@postgresql.org, Tom Lane <tgl@sss.pgh.pa.us>


Greg Stark <gsstark@MIT.EDU> 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 B>Y) OR (A=X AND B=Y AND C>Z) )
 *
 */

static Node *
make_row_op_complex(ParseState *pstate, char *oprname, 
                    List *largs, List *rargs)
{
    ListCell   *l, *outer_l,
               *r, *outer_r;
    Node *result;
    
    forboth(outer_l, largs, outer_r, rargs) 
    {
        Node *outer_larg = (Node *) lfirst(outer_l);
        Node *outer_rarg = (Node *) lfirst(outer_r);
        Node *branch = NULL;
        Node *cmp;
        
        /* all leading elements have to be equal */
        forboth(l, largs, r, rargs)
        {
            Node    *larg = (Node *) lfirst(l);
            Node    *rarg = (Node *) lfirst(r);
            Node    *cmp;
            
            if (larg == outer_larg) {
                break;
            }
            
            cmp = (Node *) make_op(pstate, "=", larg, rarg);
            cmp = coerce_to_boolean(pstate, cmp, "row comparison");
            if (branch == NULL)
                branch = cmp;
            else
                branch = (Node *) makeBoolExpr(AND_EXPR,
                                               list_make2(branch, cmp));
        }
        
        /* trailing element has to be strictly greater or less than */
        
        cmp = (Node *) make_op(pstate, oprname, outer_larg, outer_rarg);
        cmp = coerce_to_boolean(pstate, cmp, "row comparison");
        branch = branch==NULL ? cmp : (Node *) makeBoolExpr(AND_EXPR, list_make2(branch, cmp));
        
        result = result==NULL ? branch : (Node *) makeBoolExpr(OR_EXPR, list_make2(result, branch));
    }
    
    if (result == NULL)
    {
        /* zero-length rows?  Generate constant FALSE */
        result = makeBoolConst(true, false);
    }
    
    return result;
}

-- 
greg




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 12:47  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-28 12:47 UTC (permalink / raw)
  To: gsstark@mit.edu; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; gsstark@mit.edu; pgsql-performance; Tom Lane <tgl@sss.pgh.pa.us>

> Greg Stark <gsstark@MIT.EDU> 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 B>Y) OR (A=X AND B=Y AND C>Z) )
>  *                                                  ^
>  */                                                 |

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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 14:07  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Greg Stark <gsstark@mit.edu>
  1 sibling, 1 reply; 34+ messages in thread

From: Tom Lane @ 2004-07-28 14:07 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; pgsql-performance

Greg Stark <gsstark@mit.edu> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 15:38  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-28 15:38 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Greg Stark <gsstark@mit.edu>; pgsql-performance

> Greg Stark <gsstark@mit.edu> 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




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 16:00  Greg Stark <gsstark@mit.edu>
  parent: Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 1 reply; 34+ messages in thread

From: Greg Stark @ 2004-07-28 16:00 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Greg Stark <gsstark@mit.edu>; Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; pgsql-performance


Tom Lane <tgl@sss.pgh.pa.us> 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




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 16:56  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Greg Stark <gsstark@mit.edu>
  0 siblings, 1 reply; 34+ messages in thread

From: Tom Lane @ 2004-07-28 16:56 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; pgsql-performance

Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.us> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 22:54  Greg Stark <gsstark@mit.edu>
  parent: Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 1 reply; 34+ messages in thread

From: Greg Stark @ 2004-07-28 22:54 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Greg Stark <gsstark@mit.edu>; Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; pgsql-performance


Tom Lane <tgl@sss.pgh.pa.us> 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




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-28 23:11  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Greg Stark <gsstark@mit.edu>
  0 siblings, 0 replies; 34+ messages in thread

From: Tom Lane @ 2004-07-28 23:11 UTC (permalink / raw)
  To: Greg Stark <gsstark@mit.edu>; +Cc: Stephan Szabo <sszabo@megazone.bigpanda.com>; Merlin Moncure <merlin.moncure@rcsonline.com>; pgsql-performance

Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.us> 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 '<='.  

> In that case though, it seems even the existing code is insufficient.

Well, yeah, we know the existing code is broken ;-)

> 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.

Probably.  You can find some relevant code in indxpath.c in the stuff
that tries to determine whether partial indexes are relevant.

I think that the ideal behavior is that we not look directly at the
operator name at all.  For example it's not too unreasonable to want
to write (a,b) ~<~ (c,d) if you have an index that uses those
non-locale-aware operators.  We should find the operator that matches
the name and input arguments, and then try to make sense of the operator
semantics by matching it to btree opclasses.

Note that it's possible to find multiple matches, for example if someone
has installed a "reverse sort" opclass.  I think we would want to prefer
a match in the datatype's default opclass, if there is one, but
otherwise we can probably follow the lead of the existing code and
assume that any match is equally good.

			regards, tom lane



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 16:48  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 1 reply; 34+ messages in thread

From: Merlin Moncure @ 2004-07-29 16:48 UTC (permalink / raw)
  To: pgsql-performance; +Cc: Greg Stark <gsstark@mit.edu>; Tom Lane <tgl@sss.pgh.pa.us>

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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 17:57  Greg Stark <gsstark@mit.edu>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-29 17:57 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: pgsql-performance; Greg Stark <gsstark@mit.edu>; Tom Lane <tgl@sss.pgh.pa.us>


"Merlin Moncure" <merlin.moncure@rcsonline.com> 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




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 18:23  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 2 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-29 18:23 UTC (permalink / raw)
  To: gsstark@mit.edu; +Cc: pgsql-performance

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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 18:41  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  1 sibling, 0 replies; 34+ messages in thread

From: Tom Lane @ 2004-07-29 18:41 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: gsstark@mit.edu; pgsql-performance

"Merlin Moncure" <merlin.moncure@rcsonline.com> 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 18:49  Greg Stark <gsstark@mit.edu>
  parent: Merlin Moncure <merlin.moncure@rcsonline.com>
  1 sibling, 0 replies; 34+ messages in thread

From: Greg Stark @ 2004-07-29 18:49 UTC (permalink / raw)
  To: Merlin Moncure <merlin.moncure@rcsonline.com>; +Cc: gsstark@mit.edu; pgsql-performance


"Merlin Moncure" <merlin.moncure@rcsonline.com> writes:

> However, this would work:
> Create index on t(stackparam(array[a::text,b::text,c::text),
> array['char(2)', 'int', 'date')];

Well, I fear not all datatypes sort properly when treated as text. Notably
integers don't. "10" sorts before "2" for example. You could probably deal
with this with careful attention to each datatype you're converting if you're
interested in going to that length.

-- 
greg




^ permalink  raw  reply  [nested|flat] 34+ messages in thread

* Re: best way to fetch next/prev record based on index
@ 2004-07-29 20:11  Merlin Moncure <merlin.moncure@rcsonline.com>
  0 siblings, 0 replies; 34+ messages in thread

From: Merlin Moncure @ 2004-07-29 20:11 UTC (permalink / raw)
  To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance; gsstark@mit.edu

> "Merlin Moncure" <merlin.moncure@rcsonline.com> 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-10000 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



^ permalink  raw  reply  [nested|flat] 34+ messages in thread


end of thread, other threads:[~2004-07-29 20:11 UTC | newest]

Thread overview: 34+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2004-07-27 13:07 best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 14:13 ` Markus Schaber <schabios@logi-track.com>
2004-07-27 14:36 ` Rod Taylor <pg@rbt.ca>
2004-07-27 15:14 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-27 17:12 ` Greg Stark <gsstark@mit.edu>
2004-07-27 14:21 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 14:50 ` Markus Schaber <schabios@logi-track.com>
2004-07-27 15:03 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 15:29 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 15:33 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-27 15:40   ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-27 16:00     ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-27 16:02 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 17:28 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 18:38 ` Greg Stark <gsstark@mit.edu>
2004-07-27 17:37 Re: best way to fetch next/prev record based on index andrew@pillette.com
2004-07-27 18:17 best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-27 19:20 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-28 03:45 ` Stephan Szabo <sszabo@megazone.bigpanda.com>
2004-07-28 05:53   ` Greg Stark <gsstark@mit.edu>
2004-07-28 07:14     ` Greg Stark <gsstark@mit.edu>
2004-07-28 14:07     ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-28 16:00       ` Greg Stark <gsstark@mit.edu>
2004-07-28 16:56         ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-28 22:54           ` Greg Stark <gsstark@mit.edu>
2004-07-28 23:11             ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-28 12:47 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-28 15:38 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-29 16:48 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-29 17:57 ` Greg Stark <gsstark@mit.edu>
2004-07-29 18:23 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>
2004-07-29 18:41 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-07-29 18:49 ` Greg Stark <gsstark@mit.edu>
2004-07-29 20:11 Re: best way to fetch next/prev record based on index Merlin Moncure <merlin.moncure@rcsonline.com>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox