public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v56 1/6] sequential scan for dshash
5+ messages / 5 participants
[nested] [flat]
* [PATCH v56 1/6] sequential scan for dshash
@ 2020-03-13 07:58 Kyotaro Horiguchi <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Kyotaro Horiguchi @ 2020-03-13 07:58 UTC (permalink / raw)
Dshash did not allow scan the all entries sequentially. This commit
adds the functionality. The interface is similar but a bit different
both from that of dynahash and simple dshash search functions. One of
the most significant differences is the sequential scan interface of
dshash always needs a call to dshash_seq_term when scan ends. Another
is locking. Dshash holds partition lock when returning an entry,
dshash_seq_next() also holds lock when returning an entry but callers
shouldn't release it, since the lock is essential to continue a scan.
The seqscan interface allows entry deletion while a scan is in
progress. The in-scan deletion should be performed by
dshash_delete_current().
---
src/backend/lib/dshash.c | 161 ++++++++++++++++++++++++++++++-
src/include/lib/dshash.h | 22 +++++
src/tools/pgindent/typedefs.list | 1 +
3 files changed, 183 insertions(+), 1 deletion(-)
diff --git a/src/backend/lib/dshash.c b/src/backend/lib/dshash.c
index e0c763be32..29ad767618 100644
--- a/src/backend/lib/dshash.c
+++ b/src/backend/lib/dshash.c
@@ -127,6 +127,10 @@ struct dshash_table
#define NUM_SPLITS(size_log2) \
(size_log2 - DSHASH_NUM_PARTITIONS_LOG2)
+/* How many buckets are there in a given size? */
+#define NUM_BUCKETS(size_log2) \
+ (((size_t) 1) << (size_log2))
+
/* How many buckets are there in each partition at a given size? */
#define BUCKETS_PER_PARTITION(size_log2) \
(((size_t) 1) << NUM_SPLITS(size_log2))
@@ -153,6 +157,10 @@ struct dshash_table
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2) \
((partition) << NUM_SPLITS(size_log2))
+/* Choose partition based on bucket index. */
+#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2) \
+ ((bucket_idx) >> NUM_SPLITS(size_log2))
+
/* The head of the active bucket for a given hash value (lvalue). */
#define BUCKET_FOR_HASH(hash_table, hash) \
(hash_table->buckets[ \
@@ -324,7 +332,7 @@ dshash_destroy(dshash_table *hash_table)
ensure_valid_bucket_pointers(hash_table);
/* Free all the entries. */
- size = ((size_t) 1) << hash_table->size_log2;
+ size = NUM_BUCKETS(hash_table->size_log2);
for (i = 0; i < size; ++i)
{
dsa_pointer item_pointer = hash_table->buckets[i];
@@ -592,6 +600,157 @@ dshash_memhash(const void *v, size_t size, void *arg)
return tag_hash(v, size);
}
+/*
+ * dshash_seq_init/_next/_term
+ * Sequentially scan through dshash table and return all the
+ * elements one by one, return NULL when no more.
+ *
+ * dshash_seq_term should always be called when a scan finished.
+ * The caller may delete returned elements midst of a scan by using
+ * dshash_delete_current(). exclusive must be true to delete elements.
+ */
+void
+dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table,
+ bool exclusive)
+{
+ status->hash_table = hash_table;
+ status->curbucket = 0;
+ status->nbuckets = 0;
+ status->curitem = NULL;
+ status->pnextitem = InvalidDsaPointer;
+ status->curpartition = -1;
+ status->exclusive = exclusive;
+}
+
+/*
+ * Returns the next element.
+ *
+ * Returned elements are locked and the caller must not explicitly release
+ * it. It is released at the next call to dshash_next().
+ */
+void *
+dshash_seq_next(dshash_seq_status *status)
+{
+ dsa_pointer next_item_pointer;
+
+ if (status->curitem == NULL)
+ {
+ int partition;
+
+ Assert(status->curbucket == 0);
+ Assert(!status->hash_table->find_locked);
+
+ /* first shot. grab the first item. */
+ partition =
+ PARTITION_FOR_BUCKET_INDEX(status->curbucket,
+ status->hash_table->size_log2);
+ LWLockAcquire(PARTITION_LOCK(status->hash_table, partition),
+ status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
+ status->curpartition = partition;
+
+ /* resize doesn't happen from now until seq scan ends */
+ status->nbuckets =
+ NUM_BUCKETS(status->hash_table->control->size_log2);
+ ensure_valid_bucket_pointers(status->hash_table);
+
+ next_item_pointer = status->hash_table->buckets[status->curbucket];
+ }
+ else
+ next_item_pointer = status->pnextitem;
+
+ Assert(LWLockHeldByMeInMode(PARTITION_LOCK(status->hash_table,
+ status->curpartition),
+ status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
+
+ /* Move to the next bucket if we finished the current bucket */
+ while (!DsaPointerIsValid(next_item_pointer))
+ {
+ int next_partition;
+
+ if (++status->curbucket >= status->nbuckets)
+ {
+ /* all buckets have been scanned. finish. */
+ return NULL;
+ }
+
+ /* Check if move to the next partition */
+ next_partition =
+ PARTITION_FOR_BUCKET_INDEX(status->curbucket,
+ status->hash_table->size_log2);
+
+ if (status->curpartition != next_partition)
+ {
+ /*
+ * Move to the next partition. Lock the next partition then release
+ * the current, not in the reverse order to avoid concurrent
+ * resizing. Avoid dead lock by taking lock in the same order
+ * with resize().
+ */
+ LWLockAcquire(PARTITION_LOCK(status->hash_table,
+ next_partition),
+ status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
+ LWLockRelease(PARTITION_LOCK(status->hash_table,
+ status->curpartition));
+ status->curpartition = next_partition;
+ }
+
+ next_item_pointer = status->hash_table->buckets[status->curbucket];
+ }
+
+ status->curitem =
+ dsa_get_address(status->hash_table->area, next_item_pointer);
+ status->hash_table->find_locked = true;
+ status->hash_table->find_exclusively_locked = status->exclusive;
+
+ /*
+ * The caller may delete the item. Store the next item in case of deletion.
+ */
+ status->pnextitem = status->curitem->next;
+
+ return ENTRY_FROM_ITEM(status->curitem);
+}
+
+/*
+ * Terminates the seqscan and release all locks.
+ *
+ * Should be always called when finishing or exiting a seqscan.
+ */
+void
+dshash_seq_term(dshash_seq_status *status)
+{
+ status->hash_table->find_locked = false;
+ status->hash_table->find_exclusively_locked = false;
+
+ if (status->curpartition >= 0)
+ LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
+}
+
+/* Remove the current entry while a seq scan. */
+void
+dshash_delete_current(dshash_seq_status *status)
+{
+ dshash_table *hash_table = status->hash_table;
+ dshash_table_item *item = status->curitem;
+ size_t partition PG_USED_FOR_ASSERTS_ONLY
+ = PARTITION_FOR_HASH(item->hash);
+
+ Assert(status->exclusive);
+ Assert(hash_table->control->magic == DSHASH_MAGIC);
+ Assert(hash_table->find_locked);
+ Assert(hash_table->find_exclusively_locked);
+ Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
+ LW_EXCLUSIVE));
+
+ delete_item(hash_table, item);
+}
+
+/* Get the current entry while a seq scan. */
+void *
+dshash_get_current(dshash_seq_status *status)
+{
+ return ENTRY_FROM_ITEM(status->curitem);
+}
+
/*
* Print debugging information about the internal state of the hash table to
* stderr. The caller must hold no partition locks.
diff --git a/src/include/lib/dshash.h b/src/include/lib/dshash.h
index c069ec9de7..a6ea377173 100644
--- a/src/include/lib/dshash.h
+++ b/src/include/lib/dshash.h
@@ -59,6 +59,21 @@ typedef struct dshash_parameters
struct dshash_table_item;
typedef struct dshash_table_item dshash_table_item;
+/*
+ * Sequential scan state. The detail is exposed to let users know the storage
+ * size but it should be considered as an opaque type by callers.
+ */
+typedef struct dshash_seq_status
+{
+ dshash_table *hash_table; /* dshash table working on */
+ int curbucket; /* bucket number we are at */
+ int nbuckets; /* total number of buckets in the dshash */
+ dshash_table_item *curitem; /* item we are currently at */
+ dsa_pointer pnextitem; /* dsa-pointer to the next item */
+ int curpartition; /* partition number we are at */
+ bool exclusive; /* locking mode */
+} dshash_seq_status;
+
/* Creating, sharing and destroying from hash tables. */
extern dshash_table *dshash_create(dsa_area *area,
const dshash_parameters *params,
@@ -80,6 +95,13 @@ extern bool dshash_delete_key(dshash_table *hash_table, const void *key);
extern void dshash_delete_entry(dshash_table *hash_table, void *entry);
extern void dshash_release_lock(dshash_table *hash_table, void *entry);
+/* seq scan support */
+extern void dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table,
+ bool exclusive);
+extern void *dshash_seq_next(dshash_seq_status *status);
+extern void dshash_seq_term(dshash_seq_status *status);
+extern void dshash_delete_current(dshash_seq_status *status);
+extern void *dshash_get_current(dshash_seq_status *status);
/* Convenience hash and compare functions wrapping memcmp and tag_hash. */
extern int dshash_memcmp(const void *a, const void *b, size_t size, void *arg);
extern dshash_hash dshash_memhash(const void *v, size_t size, void *arg);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 61cf4eae1f..78e852569e 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2958,6 +2958,7 @@ dshash_hash
dshash_hash_function
dshash_parameters
dshash_partition
+dshash_seq_status
dshash_table
dshash_table_control
dshash_table_handle
--
2.27.0
----Next_Part(Tue_Mar_16_10_27_55_2021_500)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v56-0002-Add-conditional-lock-feature-to-dshash.patch"
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2023-01-14 15:13 Alena Rybakina <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Alena Rybakina @ 2023-01-14 15:13 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; +Cc: pgsql-hackers; [email protected]
I agree with your idea and try to implement it and will soon attach a
patch with a solution.
I also have a really practical example confirming that such optimization
can be useful.
A query was written that consisted of 50000 conditions due to the fact
that the ORM framework couldn't work with a query having an ANY
operator. In summary, we got a better plan that contained 50000 Bitmap
Index Scan nodes with 50000 different conditions. Since approximately
27336 Bite of memory were required to initialize one BitmapOr Index Scan
node, therefore, about 1.27 GB of memory was spent at the initialization
step of the plan execution and query execution time was about 55756,053
ms (00:55,756).
|psql -U postgres -c "CREATE DATABASE test_db" pgbench -U postgres -d
test_db -i -s 10 ||SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE
%s', '(' || string_agg('int', ',') || ')', string_agg(FORMAT('aid =
$%s', g.id), ' or ') ) AS cmd FROM generate_series(1, 50000) AS g(id)
\gexec ||SELECT FORMAT('execute x %s;', '(' || string_agg(g.id::text, ',') ||
')') AS cmd FROM generate_series(1, 50000) AS g(id) \gexec |||||
||
I got the plan of this query:
|QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on pgbench_accounts a (cost=44.35..83.96 rows=10
width=97)
Recheck Cond: ((aid = 1) OR (aid = 2) OR (aid = 3) OR (aid = 4) OR
(aid = 5) OR (aid = 6) OR (aid = 7) OR (aid = 8) OR (aid = 9) OR (aid = 10))
-> BitmapOr (cost=44.35..44.35 rows=10 width=0)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 1)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 2)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 3)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 4)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 5)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 6)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 7)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 8)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 9)
-> Bitmap Index Scan on pgbench_accounts_pkey
(cost=0.00..4.43 rows=1 width=0)
Index Cond: (aid = 10)|
If I rewrite this query using ANY operator,
SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE aid = ANY(SELECT
g.id FROM generate_series(1, 50000) AS g(id))',
'(' || string_agg('int',',') ||')'
) AS cmd FROM generate_series(1, 50000) AS g(id)
\gexec
I will get a plan where the array comparison operator is used through
ANY operator at the index scan stage. It's execution time is
significantly lower as 339,764 ms.
QUERY PLAN
---------------------------------------------------------------------------------------------------
Index Scan using pgbench_accounts_pkey on pgbench_accounts a (cost=0.42..48.43 rows=10 width=97)
Index Cond: (aid = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))
(2 rows)
IN operator is also converted to ANY operator, and if I rewrite this
query as:
SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE aid IN(%s)',
'(' || string_agg('int',',') ||')',
string_agg(FORMAT('%s', g.id),', ')
) AS cmd
FROM generate_series(1, 50000) AS g(id)
\gexec
I will get the same plan as the previous one using ANY operator and his
execution time will be about the same.
QUERY PLAN
---------------------------------------------------------------------------------------------------
Index Scan using pgbench_accounts_pkey on pgbench_accounts a (cost=0.42..48.43 rows=10 width=97)
Index Cond: (aid = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))
(2 rows)
On 28.12.2022 07:19, Andrey Lepikhov wrote:
> On 12/26/15 23:04, Teodor Sigaev wrote:
>> I'd like to present OR-clause support for indexes. Although
>> OR-clauses could be supported by bitmapOR index scan it isn't very
>> effective and such scan lost any order existing in index. We (with
>> Alexander Korotkov) presented results on Vienna's conference this
>> year. In short, it provides performance improvement:
>>
>> EXPLAIN ANALYZE
>> SELECT count(*) FROM tst WHERE id = 5 OR id = 500 OR id = 5000;
>> ...
>> The problems on the way which I see for now:
>> 1 Calculating cost. Right now it's just a simple transformation of
>> costs computed for BitmapOr path. I'd like to hope that's possible
>> and so index's estimation function could be non-touched. So, they
>> could believe that all clauses are implicitly-ANDed
>> 2 I'd like to add such support to btree but it seems that it should
>> be a separated patch. Btree search algorithm doesn't use any kind of
>> stack of pages and algorithm to walk over btree doesn't clear for me
>> for now.
>> 3 I could miss some places which still assumes implicitly-ANDed list
>> of clauses although regression tests passes fine.
> I support such a cunning approach. But this specific case, you
> demonstrated above, could be optimized independently at an earlier
> stage. If to convert:
>
> (F(A) = ConstStableExpr_1) OR (F(A) = ConstStableExpr_2)
> to
> F(A) IN (ConstStableExpr_1, ConstStableExpr_2)
>
> it can be seen significant execution speedup. For example, using the
> demo.sql to estimate maximum positive effect we see about 40% of
> execution and 100% of planning speedup.
>
> To avoid unnecessary overhead, induced by the optimization, such
> transformation may be made at the stage of planning (we have
> cardinality estimations and have pruned partitions) but before
> creation of a relation scan paths. So, we can avoid planning overhead
> and non-optimal BitmapOr in the case of many OR's possibly aggravated
> by many indexes on the relation.
> For example, such operation can be executed in create_index_paths()
> before passing rel->indexlist.
>
--
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2023-01-14 15:45 Marcos Pegoraro <[email protected]>
parent: Alena Rybakina <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Marcos Pegoraro @ 2023-01-14 15:45 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
>
> I agree with your idea and try to implement it and will soon attach a
> patch with a solution.
>
Additionally, if those OR constants repeat you'll see ...
If all constants are the same value, fine
explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1));
Index Only Scan using x_id on x (cost=0.42..4.44 rows=1 width=4)
Index Cond: (id = 1)
if all values are almost the same, ops
explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1) OR (ID =
2));
Bitmap Heap Scan on x (cost=17.73..33.45 rows=4 width=4)
Recheck Cond: ((id = 1) OR (id = 1) OR (id = 1) OR (id = 2))
-> BitmapOr (cost=17.73..17.73 rows=4 width=0)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 1)
-> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
Index Cond: (id = 2)
thanks
Marcos
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2023-06-26 01:47 Alena Rybakina <[email protected]>
parent: Marcos Pegoraro <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Alena Rybakina @ 2023-06-26 01:47 UTC (permalink / raw)
To: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; +Cc: Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
Hi, all! Sorry I haven't written for a long time.
I finished writing the code patch for transformation "Or" expressions to
"Any" expressions. I didn't see any problems in regression tests, even
when I changed the constant at which the minimum or expression is
replaced by any at 0. I ran my patch on sqlancer and so far the code has
never fallen.
On 14.01.2023 18:45, Marcos Pegoraro wrote:
>
> I agree with your idea and try to implement it and will soon
> attach a patch with a solution.
>
> Additionally, if those OR constants repeat you'll see ...
> If all constants are the same value, fine
> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1));
> Index Only Scan using x_id on x (cost=0.42..4.44 rows=1 width=4)
> Index Cond: (id = 1)
>
> if all values are almost the same, ops
> explain select * from x where ((ID = 1) OR (ID = 1) OR (ID = 1) OR (ID
> = 2));
> Bitmap Heap Scan on x (cost=17.73..33.45 rows=4 width=4)
> Recheck Cond: ((id = 1) OR (id = 1) OR (id = 1) OR (id = 2))
> -> BitmapOr (cost=17.73..17.73 rows=4 width=0)
> -> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
> Index Cond: (id = 1)
> -> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
> Index Cond: (id = 1)
> -> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
> Index Cond: (id = 1)
> -> Bitmap Index Scan on x_id (cost=0.00..4.43 rows=1 width=0)
> Index Cond: (id = 2)
>
> thanks
> Marcos
>
--
Regards,
Alena Rybakina
Attachments:
[text/x-patch] 0001-Replace-clause-X-N1-OR-X-N2-.-with-X-ANY-N1-N2-on.patch (10.7K, ../../[email protected]/3-0001-Replace-clause-X-N1-OR-X-N2-.-with-X-ANY-N1-N2-on.patch)
download | inline diff:
From 56fba3befe4f6b041d097d8884815fe943fb21f9 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Mon, 26 Jun 2023 04:18:15 +0300
Subject: [PATCH] Replace clause (X=N1) OR (X=N2) ... with X = ANY(N1, N2) on
the stage of the optimiser when we are still working with a tree expression.
Firstly, we do not try to make a transformation for "non-or"
expressions or inequalities and the creation of a relation
with "or" expressions occurs according to the same scenario;
secondly, we do not make transformations if there are less
than 15 or expressions (here you can put another number, but
during testing, already starting with 3 expressions, the execution
time and planning time with transformed or were faster);
thirdly, it is worth considering that we consider "or" expressions
only at the current level.
The transformation takes place according to the following scheme:
first we define the groups on the left side, collect the constants
in a list for each group, then considering each group we make the
collected constants to one type, find a common type for array and
using the make_scalar_array_op function we form ScalarArrayOpExpr,
if possible. If it is not possible, then these constants both remain
in the same expr as before the function call. All successful attempts
(received ScalarArrayOpExpr together with unformulated Expr are combined
via OR operation).
---
src/backend/parser/parse_expr.c | 289 ++++++++++++++++++++++++++++++-
src/tools/pgindent/typedefs.list | 1 +
2 files changed, 289 insertions(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 346fd272b6d..c5f58aee9ec 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -95,6 +95,293 @@ static Expr *make_distinct_op(ParseState *pstate, List *opname,
static Node *make_nulltest_from_distinct(ParseState *pstate,
A_Expr *distincta, Node *arg);
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid scalar_type;
+ Oid opno;
+ Expr *expr;
+} OrClauseGroupEntry;
+
+int const_transform_or_limit = 15;
+
+static Node *
+transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
+{
+ List *or_list = NIL;
+ ListCell *lc_eargs,
+ *lc_args;
+ List *groups_list = NIL;
+ bool change_apply = false;
+ const char *opname;
+ Node *result;
+ bool or_statement=false;
+ BoolExpr *expr = (BoolExpr *)copyObject(expr_orig);
+
+ Assert(IsA(expr, BoolExpr));
+
+ /* If this is not expression "Or", then will do it the old way. */
+ switch (expr->boolop)
+ {
+ case AND_EXPR:
+ opname = "AND";
+ break;
+ case OR_EXPR:
+ opname = "OR";
+ or_statement = true;
+ break;
+ case NOT_EXPR:
+ opname = "NOT";
+ break;
+ default:
+ elog(ERROR, "unrecognized boolop: %d", (int) expr->boolop);
+ opname = NULL; /* keep compiler quiet */
+ break;
+ }
+
+ if (!or_statement || list_length(expr->args) < const_transform_or_limit)
+ return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+
+ /*
+ * NOTE:
+ * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
+ * a list of sub-restrictinfo args, and rinfo->clause - which is the
+ * same expression, made from bare clauses. To not break selectivity
+ * caches and other optimizations, use both:
+ * - use rinfos from orclause if no transformation needed
+ * - use bare quals from rinfo->clause in the case of transformation,
+ * to create new RestrictInfo: in this case we have no options to avoid
+ * selectivity estimation procedure.
+ */
+ foreach(lc_eargs, expr->args)
+ {
+ A_Expr *arg = (A_Expr *) lfirst(lc_eargs);
+ Node *bare_orarg;
+ Node *const_expr;
+ Node *non_const_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+ bool allow_transformation;
+
+ /*
+ * The first step: checking that the expression consists only of equality.
+ * We can only do this here, while arg is still row data type, namely A_Expr.
+ * After applying transformExprRecurce, we already know that it will be OpExr type,
+ * but checking the expression for equality is already becoming impossible for us.
+ * Sometimes we have the chance to devide expression into the groups on
+ * equality and inequality. This is possible if all list items are not at the
+ * same level of a single BoolExpr expression, otherwise all of them cannot be converted.
+ */
+
+ if (!arg)
+ break;
+
+ allow_transformation = (
+ or_statement &&
+ arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
+ list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
+ );
+
+
+ bare_orarg = transformExprRecurse(pstate, (Node *)arg);
+ bare_orarg = coerce_to_boolean(pstate, bare_orarg, opname);
+
+ /*
+ * The next step: transform all the inputs, and detect whether any contain
+ * Vars.
+ */
+ if (!allow_transformation || !bare_orarg || !IsA(bare_orarg, OpExpr) || !contain_vars_of_level(bare_orarg, 0))
+ {
+ /* Again, it's not the expr we can transform */
+ or_list = lappend(or_list, bare_orarg);
+ continue;
+ }
+
+ /*
+ * Get pointers to constant and expression sides of the clause
+ */
+ non_const_expr = get_leftop(bare_orarg);
+ const_expr = get_rightop(bare_orarg);
+
+ /*
+ * At this point we definitely have a transformable clause.
+ * Classify it and add into specific group of clauses, or create new
+ * group.
+ * TODO: to manage complexity in the case of many different clauses
+ * (X1=C1) OR (X2=C2 OR) ... (XN = CN) we could invent something
+ * like a hash table (htab key ???).
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, non_const_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ non_const_expr = NULL;
+ break;
+ }
+ }
+
+ if (non_const_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = non_const_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->opno = ((OpExpr *)bare_orarg)->opno;
+ gentry->expr = (Expr *)bare_orarg;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this rinfo, just add itself
+ * to the list and go further.
+ */
+ or_statement = false;
+ }
+ else
+ {
+ /* Let's convert each group of clauses to an IN operation. */
+
+ /*
+ * Go through the list of groups and convert each, where number of
+ * consts more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc_args, groups_list)
+ {
+ OrClauseGroupEntry *gentry = (OrClauseGroupEntry *) lfirst(lc_args);
+ List *allexprs;
+ Oid scalar_type,
+ array_type;
+
+ Assert(list_length(gentry->consts) > 0);
+
+ if (list_length(gentry->consts) == 1)
+ {
+ /*
+ * Only one element in the class. Return rinfo into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ /*
+ * Do the transformation. It's been a long way ;)
+ *
+ * First of all, try to select a common type for the array elements. Note that
+ * since the LHS' type is first in the list, it will be preferred when
+ * there is doubt (eg, when all the RHS items are unknown literals).
+ *
+ * Note: use list_concat here not lcons, to avoid damaging rnonvars.
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+ allexprs = list_concat(list_make1(gentry->node), gentry->consts);
+ scalar_type = select_common_type(NULL, allexprs, NULL, NULL);
+ if (OidIsValid(scalar_type) &&
+ !verify_common_type(scalar_type, allexprs))
+ scalar_type = InvalidOid;
+
+ if (OidIsValid(scalar_type) && scalar_type != RECORDOID)
+ array_type = get_array_type(scalar_type);
+ else
+ array_type = InvalidOid;
+ if (array_type != InvalidOid)
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common type
+ * and build an ArrayExpr for them.
+ */
+ List *aexprs;
+ ArrayExpr *newa;
+ ScalarArrayOpExpr *saopexpr;
+ ListCell *l;
+
+ aexprs = NIL;
+
+ foreach(l, gentry->consts)
+ {
+ Node *rexpr = (Node *) lfirst(l);
+
+ rexpr = coerce_to_common_type(pstate, rexpr,
+ scalar_type,
+ "IN");
+ aexprs = lappend(aexprs, rexpr);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1; /* Position of the new clause is undefined */
+
+ saopexpr = (ScalarArrayOpExpr *)make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1); /* Position of the new clause is undefined */
+
+ /*
+ * TODO: here we can try to coerce the array to a Const and find
+ * hash func instead of linear search (see 50e17ad281b).
+ * convert_saop_to_hashed_saop((Node *) saopexpr);
+ * We don't have to do this anymore, do we?
+ */
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ change_apply = true;
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+ }
+
+ if (!change_apply)
+ {
+ or_statement = false;
+ }
+ }
+
+ if (or_statement)
+ {
+ /* One more trick: assemble correct clause */
+ expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
+ result = (Node *)expr;
+ }
+ /*
+ * There was no reasons to create a new expresion, so
+ * run the original BoolExpr conversion with using
+ * transformBoolExpr function
+ */
+ else
+ {
+ result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ }
+ list_free(or_list);
+ list_free_deep(groups_list);
+
+ return result;
+}
/*
* transformExpr -
@@ -208,7 +495,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = transformBoolExpr(pstate, (BoolExpr *) expr);
+ result = (Node *)transformBoolExprOr(pstate, (Expr *)expr);
break;
case T_FuncCall:
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 260854747b4..01918e6aeac 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1630,6 +1630,7 @@ NumericSumAccum
NumericVar
OM_uint32
OP
+OrClauseGroupEntry
OSAPerGroupState
OSAPerQueryState
OSInfo
--
2.34.1
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2023-06-26 03:18 Peter Geoghegan <[email protected]>
parent: Alena Rybakina <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Peter Geoghegan @ 2023-06-26 03:18 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
On Sun, Jun 25, 2023 at 6:48 PM Alena Rybakina <[email protected]> wrote:
> I finished writing the code patch for transformation "Or" expressions to "Any" expressions.
This seems interesting to me. I'm currently working on improving
nbtree's "native execution of ScalarArrayOpExpr quals" (see commit
9e8da0f7 for background information). That is relevant to what you're
trying to do here.
Right now nbtree's handling of ScalarArrayOpExpr is rather
inefficient. The executor does pass the index scan an array of
constants, so the whole structure already allows the nbtree code to
execute the ScalarArrayOpExpr in whatever way would be most efficient.
There is only one problem: it doesn't really try to do so. It more or
less just breaks down the large ScalarArrayOpExpr into "mini" queries
-- one per constant. Internally, query execution isn't significantly
different to executing many of these "mini" queries independently. We
just sort and deduplicate the arrays. We don't intelligently decide
which pages dynamically. This is related to skip scan.
Attached is an example query that shows the problem. Right now the
query needs to access a buffer containing an index page a total of 24
times. It's actually accessing the same 2 pages 12 times. My draft
patch only requires 2 buffer accesses -- because it "coalesces the
array constants together" dynamically at run time. That is a little
extreme, but it's certainly possible.
BTW, this project is related to skip scan. It's part of the same
family of techniques -- MDAM techniques. (I suppose that that's
already true for ScalarArrayOpExpr execution by nbtree, but without
dynamic behavior it's not nearly as valuable as it could be.)
If executing ScalarArrayOpExprs was less inefficient in these cases
then the planner could be a lot more aggressive about using them.
Seems like these executor improvements might go well together with
what you're doing in the planner. Note that I have to "set
random_page_cost=0.1" to get the planner to use all of the quals from
the query as index quals. It thinks (correctly) that the query plan is
very inefficient. That happens to match reality right now, but the
underlying reality could change significantly. Something to think
about.
--
Peter Geoghegan
Attachments:
[application/octet-stream] saop_patch_test.sql (6.2K, ../../CAH2-WzmD5u5kCZG0qMtVySz8VB1_drOiX=j0buDufK-EJc3YkQ@mail.gmail.com/2-saop_patch_test.sql)
download
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2023-06-26 03:18 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-03-13 07:58 [PATCH v56 1/6] sequential scan for dshash Kyotaro Horiguchi <[email protected]>
2023-01-14 15:13 Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-01-14 15:45 ` Re: POC, WIP: OR-clause support for indexes Marcos Pegoraro <[email protected]>
2023-06-26 01:47 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-26 03:18 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox