GIST index and ORDER BY - Mailing list pgsql-general

From Michał Kłeczek
Subject GIST index and ORDER BY
Date
Msg-id 3FA1E0A9-8393-41F6-88BD-62EEEA1EC21F@kleczek.org
Whole thread Raw
List pgsql-general
Hi All,

Maybe somebody could help come up with an idea on how to resolve this.

The situation is as follows:

1. We have a huge (10 billion rows) table with customer operations
2. It needs to be searched by several criteria at the same time - one of them is text similarity (and we decided to try pg_trgm)
3. For the purposes of this question the important columns are:
- customer account id (customer can have multiple accounts)
- operation date
- operation pk (autonumber)

4. We want to partition the table by range on operation date for easier archiving
5. The queries are always in the form of TOP N ordered by operation date DESC
(Ie. latest operations meeting search criteria)

I’ve decided to have a single “universal” index that will cover all search criteria: multicolumn GIST with btree_gist extension.
(Multiple indexes don’t work well because selectivity of subsets of columns is too low)

To workaround the lack of GIST support for ORDER BY and implement paging (ie. TOP n) I use the following trick:

SELECT

WHERE
 customer_id = $cust AND
 operation_date = $date AND operation_id < $id
 AND …other criteria
ORDER BY (‘2200-01-01' <-> operation_date), (MAX_BIGINT <-> operation_id)

UNION ALL

SELECT

WHERE
 customer_id = $cust AND
 operation_date < $date
 AND …other criteria
ORDER BY (‘2200-01-01' <-> operation_date), (MAX_BIGINT <-> operation_id)

LIMIT $limit


It all works really well for a single partition - it is a straight forward index scan with limit.
The problem is with partition pruning based on ORDER BY because
sort criteria are different than partition criteria - so the plan ends up with scanning all partitions and merge joining them.

I tried to partition by (‘2200-01-01' <-> operation_date) expression instead and it helps with partition pruning for order by
but disables partition pruning based on search criteria.
Artificially adding this expression to search criteria does not help because this criteria is not covered by index and triggers
additional filter in index scan.

I also tried to - instead of indxing operation_date - index (‘2200-01-01' <-> operation_date). But it actually does not solve the problem
because sort criteria the becomes: ( MAX_INT <-> indexed_expression )
And the issue is actually the same.

The only solution I could come up with is manual sorting by partition ranges using a series of UNION ALL:

SELECT * FROM part_100 … ORDER BY ...
UNION ALL
SELECT * FROM part_99 … ORDER BY …


Does anyone have any other idea?

The problem seems to be fundamentally caused by the fact that btree_gist requires different expressions for searching and ordering.

Possibly worth posting it to pgsql-hackers to find out if there are fundamental reasons why GIST does not support ORDER BY
_even_ for btree_gist (where you could implement the above trick internally).


Thanks for help!


Michal

pgsql-general by date:

Previous
From: Lauri Kajan
Date:
Subject: Re: Index scan is not pushed down to union all subquery
Next
From: David HJ
Date:
Subject: Proposal to Compile a 256-Byte Identifier Length Version Alongside the Current 64-Byte Version