Re: Highly Efficient Custom Sorting

On Fri, Jul 2, 2010 at 11:17 PM, Eliot Gable
<egable+pgsql-performance(at)gmail(dot)com> wrote:
> Well, I re-wrote the algorithm in Perl. However, it did not solve the speed
> issue. Running time now is a whopping 240+ ms instead of the 31.8ms I was
> getting before (15.2 of which is sorting). Here is the Perl code on the
> sorting. I won't post the pl/pgsql code, because this is far more clear (in
> my opinion) on what the algorithm does:
> DROP TYPE IF EXISTS glbtype CASCADE;
> CREATE TYPE glbtype AS (
> id INTEGER,
> "group" TEXT,
> priority INTEGER,
> weight INTEGER
> );
> DROP TYPE IF EXISTS glbtype_result CASCADE;
> CREATE TYPE glbtype_result AS (
> id INTEGER,
> priority INTEGER,
> weight INTEGER,
> "order" BIGINT
> );
> CREATE OR REPLACE FUNCTION GroupedRandomWeightedLB(glbtype[]) RETURNS SETOF
> glbtype_result AS

ok, I didn't take the time to read your implementation and completely
understand it, but it looks like you're looking at a N^2 sorting at
best.

You probably want to do something like this (it might not be quite
right, you need to explain what each of your input array fields is
supposed to represent):
CREATE OR REPLACE FUNCTION GroupedRandomWeightedLB(glbtype[]) RETURNS SETOF
glbtype_result AS
$$
with g as (select unnest(glbtype) as t)
select array(select ((t).id, (t).priority) (t).weight), 0)::glbtype_result
from g order by (t).group, (t).priority, random() * (t).weight);
$$ language sql;

(not sure what "order" is, is that the rownum, can't that just be
inferred from the array position?)

merlin