Re: [HACKERS] optimizer and type question

OK, building on your high-level explanation, I am attaching a patch that
attempts to do something "better" than the current code. Note that I
have only tested this with the date type and my particular query. I
haven't run it through the regression, so consider it "proof of concept"
at best. Although hopefully it will serve my purposes.

> My thought is that what the staop column ought to be is the OID of the
> comparison function that was used to determine the sort order of the
> column. Without a sort op the lowest and highest keys in the column are
> not well defined, so it makes no sense to assert "these are the lowest
> and highest values" without providing the sort op that determined that.
>
> (For sufficiently complex data types one could reasonably have multiple
> ordering operators. A crude example is sorting on "circumference" and
> "area" for polygons.) But typically the sort op will be the "<"
> operator for the column data type.
>
I changed vacuum.c to do exactly that. oid of the lt sort op.

> So, the vacuum code is definitely broken --- it's not storing the sort
> op that it used. The code in gethilokey might be broken too, depending
> on how it is producing the operator it's trying to match against the
> tuple. For example, if the actual operator in the query is any of
> < <= > >= on int4, then int4lt ought to be used to probe the pg_statistic
> table. I'm not sure if we have adequate info in pg_operator or pg_type
> to let the optimizer code determine the right thing to probe with :-(
>
This indeed seems like a bigger problem. I thought about somehow using
type-matching from the sort op and the actual operator in the query - if
both the left and right type match, then consider them the same for
purposes of this probe. That seemed complicated, so I punted in my
example - it just does the search with relid and attnum and assumes that
only returns one tuple. This works in my case (maybe in all cases,
because of the way vacuum is currently written - ?).

> What we really want here is to be able to map datatype values into
> some sort of numeric range so that we can compute what fraction of the
> low-key-to-high-key range is on each side of the probe value (the
> constant taken from the query). This general concept will apply to
> many scalar types, so what we want is a type-specific mapping function
> and a less-specific fraction-computing-function. Offhand I'd say that
> we want intltsel() and floatltsel(), plus conversion routines that can
> produce either int4 or float8 from a data type as seems appropriate.
> Anything that couldn't map to one or the other would have to supply its
> own selectivity function.
>
This is what my example then does. Uses the stored sort op to get the
type and then uses typinput to convert from the string to an int4.

Then puts the int4 back into string format because that's what everyone
was expecting.

It seems to work for my particular query. I now get:

(selfuncs) gethilokey() obj 18663 attr 11 opid 1096 (ignored)
(selfuncs) gethilokey() found op 1087 in pg_proc
(selfuncs) gethilokey() found type 1082 in pg_type
(selfuncs) gethilokey() going to use 1084 to convert type 1082
(selfuncs) gethilokey() have low -2921 high -396
(selfuncs) intltsel() high -396 low -2921 val -486
(plancat) restriction_selectivity() for func 103 op 1096 rel 18663 attr
11 const -486 flag 3 returns 0.964356
NOTICE: QUERY PLAN:

Sort (cost=34467.88 size=0 width=0)
-> Aggregate (cost=34467.88 size=0 width=0)
-> Group (cost=34467.88 size=0 width=0)
-> Sort (cost=34467.88 size=0 width=0)
-> Seq Scan on lineitem (cost=34467.88 size=579166 width=44)

including my printfs, which exist in the patch as well.

Selectivity is now the expected 96% and the size estimate for the seq
scan is much closer to correct.

Again, not tested with anything besides date, so caveat not-tested.

Hope this helps.

Erik

----------------------[optimizer_fix.sh]------------------------

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
# selfuncs.c.diff
# vacuum.c.diff
# This archive created: Mon Mar 22 22:58:14 1999
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'selfuncs.c.diff'
then
echo shar: "will not over-write existing file 'selfuncs.c.diff'"
else
cat << \SHAR_EOF > 'selfuncs.c.diff'
***
/afs/ece.cmu.edu/project/lcs/lcs-004/er1p/postgres/611/src/backend/utils/adt
/selfuncs.c Thu Mar 11 23:59:35 1999
---
/afs/ece.cmu.edu/project/lcs/lcs-004/er1p/postgres/615/src/backend/utils/adt
/selfuncs.c Mon Mar 22 22:57:25 1999
***************
*** 32,37 ****
--- 32,40 ----
#include "utils/lsyscache.h" /* for get_oprrest() */
#include "catalog/pg_statistic.h"

+ #include "catalog/pg_proc.h" /* for Form_pg_proc */
+ #include "catalog/pg_type.h" /* for Form_pg_type */
+
/* N is not a valid var/constant or relation id */
#define NONVALUE(N) ((N) == -1)

***************
*** 103,110 ****
bottom;

result = (float64) palloc(sizeof(float64data));
! if (NONVALUE(attno) || NONVALUE(relid))
*result = 1.0 / 3;
else
{
/* XXX val = atol(value); */
--- 106,114 ----
bottom;

result = (float64) palloc(sizeof(float64data));
! if (NONVALUE(attno) || NONVALUE(relid)) {
*result = 1.0 / 3;
+ }
else
{
/* XXX val = atol(value); */
***************
*** 117,130 ****
}
high = atol(highchar);
low = atol(lowchar);
if ((flag & SEL_RIGHT && val < low) ||
(!(flag & SEL_RIGHT) && val > high))
{
float32data nvals;

nvals = getattdisbursion(relid, (int) attno);
! if (nvals == 0)
*result = 1.0 / 3.0;
else
{
*result = 3.0 * (float64data) nvals;
--- 121,136 ----
}
high = atol(highchar);
low = atol(lowchar);
+ printf("(selfuncs) intltsel() high %d low %d val %d\n",high,low,val);
if ((flag & SEL_RIGHT && val < low) ||
(!(flag & SEL_RIGHT) && val > high))
{
float32data nvals;

nvals = getattdisbursion(relid, (int) attno);
! if (nvals == 0) {
*result = 1.0 / 3.0;
+ }
else
{
*result = 3.0 * (float64data) nvals;
***************
*** 336,341 ****
--- 342,353 ----
{
Relation rel;
HeapScanDesc scan;
+ /* this assumes there is only one row in the statistics table for any
particular */
+ /* relid, attnum pair - could be more complicated if staop is also
used. */
+ /* at the moment, if there are multiple rows, this code ends up
picking the */
+ /* "first" one
- er1p */
+ /* the actual "ignoring" is done in the call to heap_beginscan()
below, where */
+ /* we only mention 2 of the 3 keys in this array
- er1p */
static ScanKeyData key[3] = {
{0, Anum_pg_statistic_starelid, F_OIDEQ, {0, 0, F_OIDEQ}},
{0, Anum_pg_statistic_staattnum, F_INT2EQ, {0, 0, F_INT2EQ}},
***************
*** 344,355 ****
bool isnull;
HeapTuple tuple;

rel = heap_openr(StatisticRelationName);

key[0].sk_argument = ObjectIdGetDatum(relid);
key[1].sk_argument = Int16GetDatum((int16) attnum);
key[2].sk_argument = ObjectIdGetDatum(opid);
! scan = heap_beginscan(rel, 0, SnapshotNow, 3, key);
tuple = heap_getnext(scan, 0);
if (!HeapTupleIsValid(tuple))
{
--- 356,377 ----
bool isnull;
HeapTuple tuple;

+ HeapTuple tup;
+ Form_pg_proc proc;
+ Form_pg_type typ;
+ Oid which_op;
+ Oid which_type;
+ int32 low_value;
+ int32 high_value;
+
rel = heap_openr(StatisticRelationName);

key[0].sk_argument = ObjectIdGetDatum(relid);
key[1].sk_argument = Int16GetDatum((int16) attnum);
key[2].sk_argument = ObjectIdGetDatum(opid);
! printf("(selfuncs) gethilokey() obj %d attr %d opid %d (ignored)\n",
! key[0].sk_argument,key[1].sk_argument,key[2].sk_argument);
! scan = heap_beginscan(rel, 0, SnapshotNow, 2, key);
tuple = heap_getnext(scan, 0);
if (!HeapTupleIsValid(tuple))
{
***************
*** 376,383 ****
--- 398,461 ----
&isnull));
if (isnull)
elog(DEBUG, "gethilokey: low key is null");
+
heap_endscan(scan);
heap_close(rel);
+
+ /* now we deal with type conversion issues
*/
+ /* when intltsel() calls this routine (who knows what other callers
might do) */
+ /* it assumes that it can call atol() on the strings and then use
integer */
+ /* comparison from there. what we are going to do here, then, is try
to use */
+ /* the type information from Anum_pg_statistic_staop to convert the
high */
+ /* and low values
- er1p */
+
+ /* WARNING: this code has only been tested with the date type and has
NOT */
+ /* been regression tested. consider it "sample" code of what might
be the */
+ /* right kind of thing to do
- er1p */
+
+ /* get the 'op' from pg_statistic and look it up in pg_proc */
+ which_op = heap_getattr(tuple,
+ Anum_pg_statistic_staop,
+ RelationGetDescr(rel),
+ &isnull);
+ if (InvalidOid == which_op) {
+ /* ignore all this stuff, try conversion only if we have a valid staop */
+ /* note that there is an accompanying change to 'vacuum analyze' that */
+ /* gets this set to something useful. */
+ } else {
+ /* staop looks valid, so let's see what we can do about conversion */
+ tup = SearchSysCacheTuple(PROOID, ObjectIdGetDatum(which_op), 0, 0, 0);
+ if (!HeapTupleIsValid(tup)) {
+ elog(ERROR, "selfuncs: unable to find op in pg_proc %d", which_op);
+ }
+ printf("(selfuncs) gethilokey() found op %d in pg_proc\n",which_op);
+
+ /* use that to determine the type of stahikey and stalokey via pg_type */
+ proc = (Form_pg_proc) GETSTRUCT(tup);
+ which_type = proc->proargtypes[0]; /* XXX - use left and right
separately? */
+ tup = SearchSysCacheTuple(TYPOID, ObjectIdGetDatum(which_type), 0, 0, 0);
+ if (!HeapTupleIsValid(tup)) {
+ elog(ERROR, "selfuncs: unable to find type in pg_type %d", which_type);
+ }
+ printf("(selfuncs) gethilokey() found type %d in pg_type\n",which_type);
+
+ /* and use that type to get the conversion function to int4 */
+ typ = (Form_pg_type) GETSTRUCT(tup);
+ printf("(selfuncs) gethilokey() going to use %d to convert type
%d\n",typ->typinput,which_type);
+
+ /* and convert the low and high strings */
+ low_value = (int32) fmgr(typ->typinput, *low, -1);
+ high_value = (int32) fmgr(typ->typinput, *high, -1);
+ printf("(selfuncs) gethilokey() have low %d high
%d\n",low_value,high_value);
+
+ /* now we have int4's, which we put back into strings because
that's what out */
+ /* callers (intltsel() at least) expect
- er1p */
+ pfree(*low); pfree(*high); /* let's not leak the old strings */
+ *low = int4out(low_value);
+ *high = int4out(high_value);
+
+ /* XXX - this probably leaks the two tups we got from
SearchSysCacheTuple() - er1p */
+ }
}

float64
SHAR_EOF
fi
if test -f 'vacuum.c.diff'
then
echo shar: "will not over-write existing file 'vacuum.c.diff'"
else
cat << \SHAR_EOF > 'vacuum.c.diff'
***
/afs/ece.cmu.edu/project/lcs/lcs-004/er1p/postgres/611/src/backend/commands/
vacuum.c Thu Mar 11 23:59:09 1999
---
/afs/ece.cmu.edu/project/lcs/lcs-004/er1p/postgres/615/src/backend/commands/
vacuum.c Mon Mar 22 21:23:15 1999
***************
*** 1842,1848 ****
i = 0;
values[i++] = (Datum) relid; /* 1 */
values[i++] = (Datum) attp->attnum; /* 2 */
! values[i++] = (Datum) InvalidOid; /* 3 */
fmgr_info(stats->outfunc, &out_function);
out_string = (*fmgr_faddr(&out_function)) (stats->min,
stats->attr->atttypid);
values[i++] = (Datum) fmgr(F_TEXTIN, out_string);
--- 1842,1848 ----
i = 0;
values[i++] = (Datum) relid; /* 1 */
values[i++] = (Datum) attp->attnum; /* 2 */
! values[i++] = (Datum) stats->f_cmplt.fn_oid; /* 3 */ /* get the
'<' oid, instead of 'invalid' - er1p */
fmgr_info(stats->outfunc, &out_function);
out_string = (*fmgr_faddr(&out_function)) (stats->min,
stats->attr->atttypid);
values[i++] = (Datum) fmgr(F_TEXTIN, out_string);
SHAR_EOF
fi
exit 0
# End of shell archive