Skip to content

Commit 186cbbd

Browse files
tglsfdctglsfdc
committed
Provide hashing support for arrays.
The core of this patch is hash_array() and associated typcache infrastructure, which works just about exactly like the existing support for array comparison. In addition I did some work to ensure that the planner won't think that an array type is hashable unless its element type is hashable, and similarly for sorting. This includes adding a datatype parameter to op_hashjoinable and op_mergejoinable, and adding an explicit "hashable" flag to SortGroupClause. The lack of a cross-check on the element type was a pre-existing bug in mergejoin support --- but it didn't matter so much before, because if you couldn't sort the element type there wasn't any good alternative to failing anyhow. Now that we have the alternative of hashing the array type, there are cases where we can avoid a failure by being picky at the planner stage, so it's time to be picky. The issue of exactly how to combine the per-element hash values to produce an array hash is still open for discussion, but the rest of this is pretty solid, so I'll commit it as-is.
1 parent bd1ff97 commit 186cbbd

30 files changed

+375
-88
lines changed

‎src/backend/commands/analyze.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1794,7 +1794,8 @@ std_typanalyze(VacAttrStats *stats)
17941794
/* Look for default "<" and "=" operators for column's type */
17951795
get_sort_group_operators(stats->attrtypid,
17961796
false, false, false,
1797-
&ltopr, &eqopr, NULL);
1797+
&ltopr, &eqopr, NULL,
1798+
NULL);
17981799

17991800
/* If column has no "=" operator, we can't do much of anything */
18001801
if (!OidIsValid(eqopr))

‎src/backend/nodes/copyfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1882,6 +1882,7 @@ _copySortGroupClause(SortGroupClause *from)
18821882
COPY_SCALAR_FIELD(eqop);
18831883
COPY_SCALAR_FIELD(sortop);
18841884
COPY_SCALAR_FIELD(nulls_first);
1885+
COPY_SCALAR_FIELD(hashable);
18851886

18861887
return newnode;
18871888
}

‎src/backend/nodes/equalfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2227,6 +2227,7 @@ _equalSortGroupClause(SortGroupClause *a, SortGroupClause *b)
22272227
COMPARE_SCALAR_FIELD(eqop);
22282228
COMPARE_SCALAR_FIELD(sortop);
22292229
COMPARE_SCALAR_FIELD(nulls_first);
2230+
COMPARE_SCALAR_FIELD(hashable);
22302231

22312232
return true;
22322233
}

‎src/backend/nodes/outfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2073,6 +2073,7 @@ _outSortGroupClause(StringInfo str, SortGroupClause *node)
20732073
WRITE_OID_FIELD(eqop);
20742074
WRITE_OID_FIELD(sortop);
20752075
WRITE_BOOL_FIELD(nulls_first);
2076+
WRITE_BOOL_FIELD(hashable);
20762077
}
20772078

20782079
static void

‎src/backend/nodes/readfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -264,6 +264,7 @@ _readSortGroupClause(void)
264264
READ_OID_FIELD(eqop);
265265
READ_OID_FIELD(sortop);
266266
READ_BOOL_FIELD(nulls_first);
267+
READ_BOOL_FIELD(hashable);
267268

268269
READ_DONE();
269270
}

‎src/backend/optimizer/path/equivclass.c

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -925,7 +925,9 @@ generate_join_implied_equalities_normal(PlannerInfo *root,
925925
(IsA(inner_em->em_expr, RelabelType) &&
926926
IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
927927
score++;
928-
if (!enable_hashjoin || op_hashjoinable(eq_op))
928+
if (!enable_hashjoin ||
929+
op_hashjoinable(eq_op,
930+
exprType((Node *) outer_em->em_expr)))
929931
score++;
930932
if (score > best_score)
931933
{

‎src/backend/optimizer/plan/createplan.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -958,6 +958,7 @@ create_unique_plan(PlannerInfo *root, UniquePath *best_path)
958958
sortcl->eqop = eqop;
959959
sortcl->sortop = sortop;
960960
sortcl->nulls_first = false;
961+
sortcl->hashable = false; /* no need to make this accurate */
961962
sortList = lappend(sortList, sortcl);
962963
groupColPos++;
963964
}

‎src/backend/optimizer/plan/initsplan.c

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616

1717
#include "catalog/pg_operator.h"
1818
#include "catalog/pg_type.h"
19+
#include "nodes/nodeFuncs.h"
1920
#include "optimizer/clauses.h"
2021
#include "optimizer/cost.h"
2122
#include "optimizer/joininfo.h"
@@ -1486,6 +1487,7 @@ check_mergejoinable(RestrictInfo *restrictinfo)
14861487
{
14871488
Expr *clause = restrictinfo->clause;
14881489
Oid opno;
1490+
Node *leftarg;
14891491

14901492
if (restrictinfo->pseudoconstant)
14911493
return;
@@ -1495,8 +1497,9 @@ check_mergejoinable(RestrictInfo *restrictinfo)
14951497
return;
14961498

14971499
opno = ((OpExpr *) clause)->opno;
1500+
leftarg = linitial(((OpExpr *) clause)->args);
14981501

1499-
if (op_mergejoinable(opno) &&
1502+
if (op_mergejoinable(opno, exprType(leftarg)) &&
15001503
!contain_volatile_functions((Node *) clause))
15011504
restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
15021505

@@ -1521,6 +1524,7 @@ check_hashjoinable(RestrictInfo *restrictinfo)
15211524
{
15221525
Expr *clause = restrictinfo->clause;
15231526
Oid opno;
1527+
Node *leftarg;
15241528

15251529
if (restrictinfo->pseudoconstant)
15261530
return;
@@ -1530,8 +1534,9 @@ check_hashjoinable(RestrictInfo *restrictinfo)
15301534
return;
15311535

15321536
opno = ((OpExpr *) clause)->opno;
1537+
leftarg = linitial(((OpExpr *) clause)->args);
15331538

1534-
if (op_hashjoinable(opno) &&
1539+
if (op_hashjoinable(opno, exprType(leftarg)) &&
15351540
!contain_volatile_functions((Node *) clause))
15361541
restrictinfo->hashjoinoperator = opno;
15371542
}

‎src/backend/optimizer/plan/planagg.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -518,6 +518,7 @@ make_agg_subplan(PlannerInfo *root, MinMaxAggInfo *info)
518518
info->aggsortop);
519519
sortcl->sortop = info->aggsortop;
520520
sortcl->nulls_first = info->nulls_first;
521+
sortcl->hashable = false; /* no need to make this accurate */
521522
subparse->sortClause = list_make1(sortcl);
522523

523524
/* set up LIMIT 1 */

‎src/backend/optimizer/plan/subselect.c

Lines changed: 28 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -861,28 +861,45 @@ testexpr_is_hashable(Node *testexpr)
861861
return false;
862862
}
863863

864+
/*
865+
* Check expression is hashable + strict
866+
*
867+
* We could use op_hashjoinable() and op_strict(), but do it like this to
868+
* avoid a redundant cache lookup.
869+
*/
864870
static bool
865871
hash_ok_operator(OpExpr *expr)
866872
{
867873
Oid opid = expr->opno;
868-
HeapTuple tup;
869-
Form_pg_operator optup;
870874

871875
/* quick out if not a binary operator */
872876
if (list_length(expr->args) != 2)
873877
return false;
874-
/* else must look up the operator properties */
875-
tup = SearchSysCache1(OPEROID, ObjectIdGetDatum(opid));
876-
if (!HeapTupleIsValid(tup))
877-
elog(ERROR, "cache lookup failed for operator %u", opid);
878-
optup = (Form_pg_operator) GETSTRUCT(tup);
879-
if (!optup->oprcanhash || !func_strict(optup->oprcode))
878+
if (opid == ARRAY_EQ_OP)
879+
{
880+
/* array_eq is strict, but must check input type to ensure hashable */
881+
Node *leftarg = linitial(expr->args);
882+
883+
return op_hashjoinable(opid, exprType(leftarg));
884+
}
885+
else
880886
{
887+
/* else must look up the operator properties */
888+
HeapTuple tup;
889+
Form_pg_operator optup;
890+
891+
tup = SearchSysCache1(OPEROID, ObjectIdGetDatum(opid));
892+
if (!HeapTupleIsValid(tup))
893+
elog(ERROR, "cache lookup failed for operator %u", opid);
894+
optup = (Form_pg_operator) GETSTRUCT(tup);
895+
if (!optup->oprcanhash || !func_strict(optup->oprcode))
896+
{
897+
ReleaseSysCache(tup);
898+
return false;
899+
}
881900
ReleaseSysCache(tup);
882-
return false;
901+
return true;
883902
}
884-
ReleaseSysCache(tup);
885-
return true;
886903
}
887904

888905

‎src/backend/optimizer/util/pathnode.c

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818

1919
#include "catalog/pg_operator.h"
2020
#include "miscadmin.h"
21+
#include "nodes/nodeFuncs.h"
2122
#include "optimizer/clauses.h"
2223
#include "optimizer/cost.h"
2324
#include "optimizer/pathnode.h"
@@ -878,6 +879,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
878879
Relids left_varnos;
879880
Relids right_varnos;
880881
Relids all_varnos;
882+
Oid opinputtype;
881883

882884
/* Is it a binary opclause? */
883885
if (!IsA(op, OpExpr) ||
@@ -908,6 +910,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
908910
left_varnos = pull_varnos(left_expr);
909911
right_varnos = pull_varnos(right_expr);
910912
all_varnos = bms_union(left_varnos, right_varnos);
913+
opinputtype = exprType(left_expr);
911914

912915
/* Does it reference both sides? */
913916
if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
@@ -946,14 +949,14 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
946949
if (all_btree)
947950
{
948951
/* oprcanmerge is considered a hint... */
949-
if (!op_mergejoinable(opno) ||
952+
if (!op_mergejoinable(opno, opinputtype) ||
950953
get_mergejoin_opfamilies(opno) == NIL)
951954
all_btree = false;
952955
}
953956
if (all_hash)
954957
{
955958
/* ... but oprcanhash had better be correct */
956-
if (!op_hashjoinable(opno))
959+
if (!op_hashjoinable(opno, opinputtype))
957960
all_hash = false;
958961
}
959962
if (!(all_btree || all_hash))

‎src/backend/optimizer/util/tlist.c

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,6 @@
1818
#include "nodes/nodeFuncs.h"
1919
#include "optimizer/tlist.h"
2020
#include "optimizer/var.h"
21-
#include "utils/lsyscache.h"
2221

2322

2423
/*****************************************************************************
@@ -348,10 +347,7 @@ grouping_is_sortable(List *groupClause)
348347
/*
349348
* grouping_is_hashable - is it possible to implement grouping list by hashing?
350349
*
351-
* We assume hashing is OK if the equality operators are marked oprcanhash.
352-
* (If there isn't actually a supporting hash function, the executor will
353-
* complain at runtime; but this is a misdeclaration of the operator, not
354-
* a system bug.)
350+
* We rely on the parser to have set the hashable flag correctly.
355351
*/
356352
bool
357353
grouping_is_hashable(List *groupClause)
@@ -362,7 +358,7 @@ grouping_is_hashable(List *groupClause)
362358
{
363359
SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
364360

365-
if (!op_hashjoinable(groupcl->eqop))
361+
if (!groupcl->hashable)
366362
return false;
367363
}
368364
return true;

‎src/backend/parser/analyze.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1659,6 +1659,7 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
16591659
SortGroupClause *grpcl = makeNode(SortGroupClause);
16601660
Oid sortop;
16611661
Oid eqop;
1662+
bool hashable;
16621663
ParseCallbackState pcbstate;
16631664

16641665
setup_parser_errposition_callback(&pcbstate, pstate,
@@ -1667,7 +1668,8 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
16671668
/* determine the eqop and optional sortop */
16681669
get_sort_group_operators(rescoltype,
16691670
false, true, false,
1670-
&sortop, &eqop, NULL);
1671+
&sortop, &eqop, NULL,
1672+
&hashable);
16711673

16721674
cancel_parser_errposition_callback(&pcbstate);
16731675

@@ -1676,6 +1678,7 @@ transformSetOperationTree(ParseState *pstate, SelectStmt *stmt,
16761678
grpcl->eqop = eqop;
16771679
grpcl->sortop = sortop;
16781680
grpcl->nulls_first = false; /* OK with or without sortop */
1681+
grpcl->hashable = hashable;
16791682

16801683
op->groupClauses = lappend(op->groupClauses, grpcl);
16811684
}

‎src/backend/parser/parse_clause.c

Lines changed: 18 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1937,6 +1937,7 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
19371937
Oid restype = exprType((Node *) tle->expr);
19381938
Oid sortop;
19391939
Oid eqop;
1940+
bool hashable;
19401941
bool reverse;
19411942
int location;
19421943
ParseCallbackState pcbstate;
@@ -1972,13 +1973,15 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
19721973
case SORTBY_ASC:
19731974
get_sort_group_operators(restype,
19741975
true, true, false,
1975-
&sortop, &eqop, NULL);
1976+
&sortop, &eqop, NULL,
1977+
&hashable);
19761978
reverse = false;
19771979
break;
19781980
case SORTBY_DESC:
19791981
get_sort_group_operators(restype,
19801982
false, true, true,
1981-
NULL, &eqop, &sortop);
1983+
NULL, &eqop, &sortop,
1984+
&hashable);
19821985
reverse = true;
19831986
break;
19841987
case SORTBY_USING:
@@ -2000,11 +2003,17 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
20002003
errmsg("operator %s is not a valid ordering operator",
20012004
strVal(llast(sortby->useOp))),
20022005
errhint("Ordering operators must be \"<\" or \">\" members of btree operator families.")));
2006+
2007+
/*
2008+
* Also see if the equality operator is hashable.
2009+
*/
2010+
hashable = op_hashjoinable(eqop, restype);
20032011
break;
20042012
default:
20052013
elog(ERROR, "unrecognized sortby_dir: %d", sortby->sortby_dir);
20062014
sortop = InvalidOid; /* keep compiler quiet */
20072015
eqop = InvalidOid;
2016+
hashable = false;
20082017
reverse = false;
20092018
break;
20102019
}
@@ -2020,6 +2029,7 @@ addTargetToSortList(ParseState *pstate, TargetEntry *tle,
20202029

20212030
sortcl->eqop = eqop;
20222031
sortcl->sortop = sortop;
2032+
sortcl->hashable = hashable;
20232033

20242034
switch (sortby->sortby_nulls)
20252035
{
@@ -2074,8 +2084,6 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
20742084
bool resolveUnknown)
20752085
{
20762086
Oid restype = exprType((Node *) tle->expr);
2077-
Oid sortop;
2078-
Oid eqop;
20792087

20802088
/* if tlist item is an UNKNOWN literal, change it to TEXT */
20812089
if (restype == UNKNOWNOID && resolveUnknown)
@@ -2092,21 +2100,26 @@ addTargetToGroupList(ParseState *pstate, TargetEntry *tle,
20922100
if (!targetIsInSortList(tle, InvalidOid, grouplist))
20932101
{
20942102
SortGroupClause *grpcl = makeNode(SortGroupClause);
2103+
Oid sortop;
2104+
Oid eqop;
2105+
bool hashable;
20952106
ParseCallbackState pcbstate;
20962107

20972108
setup_parser_errposition_callback(&pcbstate, pstate, location);
20982109

20992110
/* determine the eqop and optional sortop */
21002111
get_sort_group_operators(restype,
21012112
false, true, false,
2102-
&sortop, &eqop, NULL);
2113+
&sortop, &eqop, NULL,
2114+
&hashable);
21032115

21042116
cancel_parser_errposition_callback(&pcbstate);
21052117

21062118
grpcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
21072119
grpcl->eqop = eqop;
21082120
grpcl->sortop = sortop;
21092121
grpcl->nulls_first = false; /* OK with or without sortop */
2122+
grpcl->hashable = hashable;
21102123

21112124
grouplist = lappend(grouplist, grpcl);
21122125
}

0 commit comments

Comments
 (0)