Re: [PERFORM] Index Choice Problem

[Adam Alkins]

Nevermind the reply, blonde moment on the ordering...This works :)ThanksOn 2/18/06, Adam Alkins <
[EMAIL PROTECTED]> wrote:Unfortunately I'm using 8.0.4 and this is for a government website, I only get so many maintenance windows. Is this the only workaround for this issue?
I did make a test index as you described on my test box and tried the query and it used the new index. However, ORDER BY forum_id then last_post_time is simply not the intended sorting order. (Though I'm considering just SELECTing the topic_last_post_time field and resorting the results in the script if this is the only workaround).
- AdamOn 2/18/06, Tom Lane <
[EMAIL PROTECTED]> wrote:
Adam Alkins <[EMAIL PROTECTED]> writes:> SELECT t.topic_id>   FROM phpbb_topics AS t
>   WHERE t.forum_id
 = 71>   AND t.topic_id NOT IN (205026, 29046, 144569, 59780, 187424,> 138635, 184973, 170551, 22419, 181690, 197254, 205130)>   ORDER BY 
t.topic_last_post_time DESC>   LIMIT 23 OFFSET 0If you're using 8.1, you'd probably find that an index on (forum_id,topic_last_post_time) would work nicely for this.  You could use it
in prior versions too, but you'd have to spell the ORDER BY ratherstrangely:ORDER BY forum_id desc, topic_last_post_time descThe reason for this trickery is to get the planner to realize thatthe index order matches the ORDER BY ...
regards, tom lane-- Adam Alkins
http://www.rasadam.comMobile: 868-680-4612

-- Adam Alkinshttp://www.rasadam.comMobile: 868-680-4612

Re: [PERFORM] Index Choice Problem

[Adam Alkins]

Unfortunately I'm using 8.0.4 and this is for a government website, I only get so many maintenance windows. Is this the only workaround for this issue?I did make a test index as you described on my test box and tried the query and it used the new index. However, ORDER BY forum_id then last_post_time is simply not the intended sorting order. (Though I'm considering just SELECTing the topic_last_post_time field and resorting the results in the script if this is the only workaround).
- AdamOn 2/18/06, Tom Lane <[EMAIL PROTECTED]> wrote:
Adam Alkins <[EMAIL PROTECTED]> writes:> SELECT t.topic_id>   FROM phpbb_topics AS t>   WHERE t.forum_id
 = 71>   AND t.topic_id NOT IN (205026, 29046, 144569, 59780, 187424,> 138635, 184973, 170551, 22419, 181690, 197254, 205130)>   ORDER BY 
t.topic_last_post_time DESC>   LIMIT 23 OFFSET 0If you're using 8.1, you'd probably find that an index on (forum_id,topic_last_post_time) would work nicely for this.  You could use it
in prior versions too, but you'd have to spell the ORDER BY ratherstrangely:ORDER BY forum_id desc, topic_last_post_time descThe reason for this trickery is to get the planner to realize thatthe index order matches the ORDER BY ...
regards, tom lane-- Adam Alkinshttp://www.rasadam.comMobile: 868-680-4612

Re: [PERFORM] Index Choice Problem

[Tom Lane]

Adam Alkins <[EMAIL PROTECTED]> writes:
> SELECT t.topic_id
>   FROM phpbb_topics AS t
>   WHERE t.forum_id = 71
>   AND t.topic_id NOT IN (205026, 29046, 
> 144569, 59780, 187424,
> 138635, 184973, 170551, 22419, 181690, 197254, 205130)
>   ORDER BY t.topic_last_post_time 
> DESC
>   LIMIT 23 OFFSET 0

If you're using 8.1, you'd probably find that an index on (forum_id,
topic_last_post_time) would work nicely for this.  You could use it
in prior versions too, but you'd have to spell the ORDER BY rather
strangely:
ORDER BY forum_id desc, topic_last_post_time desc
The reason for this trickery is to get the planner to realize that
the index order matches the ORDER BY ...

regards, tom lane

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Gregory Maxwell]

On 2/17/06, Ragnar <[EMAIL PROTECTED]> wrote:
> Say again ?
> Let us say you have 1 billion rows, where the
> column in question contains strings like
> baaaaaa
> baaaaab
> baaaaac
> ...
> not necessarily in this order on disc of course
>
> The minimum value would be keyed as 0001h,
> the next one as 0002h and so on.
>
> Now insert new value 'a'
>
> Not only will you have to update 1 billion records,
> but also all the values in your map.
>
> please explain

No comment on the usefulness of the idea overall.. but the solution
would be to insert with the colliding value of the existing one lesser
than it..

It will falsly claim equal, which you then must fix with a second
local sort which should be fast because you only need to sort the
duplicates/false dupes.  If you insert too much then this obviously
becomes completely useless.

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

[PERFORM] Stored proc and optimizer question

[Antal Attila]

Hi!

I have a question about the query optimizer and the function scan. See 
the next case:


CREATE TABLE a (id SERIAL PRIMARY KEY, userid INT4, col  TEXT);
CREATE TABLE b (id SERIAL PRIMARY KEY, userid INT4, a_id INT4 REFERENCES 
a (id), col  TEXT);

CREATE INDEX idx_a_uid ON a(userid);
CREATE INDEX idx_b_uid ON b(userid);
CREATE INDEX idx_a_col ON a(col);
CREATE INDEX idx_b_col ON b(col);

First solution:

   CREATE VIEW ab_view AS
   SELECT a.id AS id,
  a.userid AS userid_a, b.userid AS userid_b,
  a.col AS col_a, b.col AS col_b
   FROM a LEFT JOIN b ON (a.id = b.a_id);

   EXPLAIN ANALYSE SELECT * FROM ab_view
   WHERE userid_a = 23 AND userid_b = 23 AND col_a LIKE 's%'
   ORDER BY col_b
   LIMIT 10 OFFSET 10;

   QUERY PLAN
--
Limit  (cost=15.70..15.70 rows=1 width=76) (actual time=0.108..0.108 
rows=0 loops=1)
  ->  Sort  (cost=15.69..15.70 rows=1 width=76) (actual 
time=0.104..0.104 rows=0 loops=1)

Sort Key: b.col
->  Nested Loop  (cost=3.32..15.68 rows=1 width=76) (actual 
time=0.085..0.085 rows=0 loops=1)

  Join Filter: ("outer".id = "inner".a_id)
  ->  Bitmap Heap Scan on a  (cost=2.30..6.13 rows=1 
width=40) (actual time=0.082..0.082 rows=0 loops=1)

Recheck Cond: (userid = 23)
Filter: (col ~~ 's%'::text)
->  BitmapAnd  (cost=2.30..2.30 rows=1 width=0) 
(actual time=0.077..0.077 rows=0 loops=1)
  ->  Bitmap Index Scan on idx_a_uid  
(cost=0.00..1.02 rows=6 width=0) (actual time=0.075..0.075 rows=0 loops=1)

Index Cond: (userid = 23)
  ->  Bitmap Index Scan on idx_a_col  
(cost=0.00..1.03 rows=6 width=0) (never executed)
Index Cond: ((col >= 's'::text) AND 
(col < 't'::text))
  ->  Bitmap Heap Scan on b  (cost=1.02..9.49 rows=5 
width=40) (never executed)

Recheck Cond: (userid = 23)
->  Bitmap Index Scan on idx_b_uid  
(cost=0.00..1.02 rows=5 width=0) (never executed)

  Index Cond: (userid = 23)
Total runtime: 0.311 ms


In the first solution the query optimizer can work on the view and the 
full execution of the query will be optimal. But I have to use 2 
condition for the userid fields (userid_a = 23 AND userid_b = 23 ). If I 
have to eliminate the duplication I can try to use stored function.


Second solution:
   CREATE FUNCTION ab_select(INT4)  RETURNS setof ab_view AS $$
   SELECT a.id AS id,
  a.userid AS userid_a, b.userid AS userid_b,
  a.col AS col_a, b.col AS col_b
   FROM a LEFT JOIN b ON (a.id = b.a_id AND b.userid = $1)
   WHERE a.userid = $1;
   $$ LANGUAGE SQL STABLE;

   EXPLAIN ANALYSE SELECT * FROM ab_select(23)
   WHERE col_a LIKE 's%'
   ORDER BY col_b
   LIMIT 10 OFFSET 10;

 QUERY PLAN
--
Limit  (cost=15.07..15.07 rows=1 width=76) (actual time=1.034..1.034 
rows=0 loops=1)
  ->  Sort  (cost=15.06..15.07 rows=5 width=76) (actual 
time=1.030..1.030 rows=0 loops=1)

Sort Key: col_b
->  Function Scan on ab_select  (cost=0.00..15.00 rows=5 
width=76) (actual time=1.004..1.004 rows=0 loops=1)

  Filter: (col_a ~~ 's%'::text)
Total runtime: 1.103 ms

The second solution have 2 advantage:
 1. The second query is more beautiful and shorter.
 2. You can rewrite easier the stored function without modify the query.

But I have heartache, because the optimizer give up the game. It cannot 
optimize the query globally (inside and outside the stored function) in 
spite of the STABLE keyword. It use function scan on the result of the 
stored function.


How can I eliminate the function scan while I want to keep the advantages?

In my opinion the optimizer cannot replace the function scan with a more 
optimal plan, but this feature may be implemented in the next versions 
of  PostgreSQL. I would like to suggest this.


I built this case theoretically, but I have more stored procedure which 
works with bad performance therefore.


Regards,
Antal Attila

---(end of broadcast)---
TIP 5: don't forget to increase your free space map settings

[PERFORM] Measuring Lock Performance

[Lane Van Ingen]

Does anybody know if it is possible to use the statistics collected by
PostgreSQL to do the following, and how?

- view all locks held by a particular PostgreSQL session (including how to
determine
  the session ID#)

- determine effect of lock contention on overall database performance, as
well as the
  extent to which contention varies with overall database traffic

I am using version 8.0.2 on Windows 2003.



---(end of broadcast)---
TIP 6: explain analyze is your friend

Re: [PERFORM] Optimizing performance of a like '%...%' condition

[Chris]

Indexing the t_name.name field, I can increase speed, but only if I
restrict my search to something like :

select *
from t_name
where t_name.name like 'my_search%'

(In this case it takes generally less than 1 second)


My question : Are there algorithms or tools that can speed up such a
type of queries ("like" condition begining with a "%" symbol) ?


Apart from indexing the field you could use full text indexing. See 
http://techdocs.postgresql.org/techdocs/fulltextindexing.php



What other types of queries are you running that you want to speed up ?

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [PERFORM] SQL Function Performance

[Mark Liberman]

Title: RE: [PERFORM] SQL Function Performance






> in my case; both direct query and sql function gererate same execution plan. Also, execution plan belongs to the sql function better than direct sql > query plan. But, direct sql result comes less than 1 second. sql function result comes about in 50 seconds.

How are you getting at the plan inside your function?  If you just do an EXPLAIN on the function call you get a FUNCTION SCAN line in your plan, which tells you nothing.  I remember I had to work through some process for catching the output of the Explain plan in a cursor and returning that to actually see the plan.  I saw in a previous response he suggested using a PREPARE and EXECUTE against that.  I'm not sure that's the same as what's going on in the function (although I could be wrong).

Just humor me and try creating the sql query in the fuction in a text variable and then Executing it. 

Prior to that, however, you might try just recreating the function.  The plan may be re-evaluated at that point.

- Mark

Re: [PERFORM] SQL Function Performance

[Mark Liberman]

Title: RE: [PERFORM] SQL Function Performance






I've run into this issue. It basically comes down to the plan that is being used inside the function is not the same as the plan used when you issue the query manually outside of the function.  Although I'm no expert on when plans are prepared and re-evaluated for functions, I know that they are not re-evaluated each time to execute the function.

So, what I did in such cases was to build up the sql query in a text variable inside my function, and then use the EXECUTE command inside the function.  When you use the EXECUTE command, the plan is prepared each time.  I know there is some minimal overhead of preparing the plan each time, but it seems like it's minor compared to the saving's you'll get.

- Mark

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Dann Corbit]

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:pgsql-hackers-
> [EMAIL PROTECTED] On Behalf Of Markus Schaber
> Sent: Thursday, February 16, 2006 5:45 AM
> To: pgsql-performance@postgresql.org; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create
Index
> 
> Hi, Ron,
> 
> Ron wrote:
> 
> > ...and of course if you know enough about the data to be sorted so
as to
> > constrain it appropriately, one should use a non comparison based
O(N)
> > sorting algorithm rather than any of the general comparison based
> > O(NlgN) methods.
> 
> Sounds interesting, could you give us some pointers (names, URLs,
> papers) to such algorithms?

He refers to counting sort and radix sort (which comes in most
significant digit and least significant digit format).  These are also
called distribution (as opposed to comparison) sorts.

These sorts are O(n) as a function of the data size, but really they are
O(M*n) where M is the average key length and n is the data set size.
(In the case of MSD radix sort M is the average length to completely
differentiate strings)

So if you have an 80 character key, then 80*log(n) will only be faster
than n*log(n) when you have 2^80th elements -- in other words -- never.

If you have short keys, on the other hand, distribution sorts will be
dramatically faster.  On an unsigned integer, for instance, it requires
4 passes with 8 bit buckets and so 16 elements is the crossover to radix
is faster than an O(n*log(n)) sort.  Of course, there is a fixed
constant of proportionality and so it will really be higher than that,
but for large data sets distribution sorting is the best thing that
there is for small keys.

You could easily have an introspective MSD radix sort.  The nice thing
about MSD radix sort is that you can retain the ordering that has
occurred so far and switch to another algorithm.

An introspective MSD radix sort could call an introspective quick sort
algorithm once it processed a crossover point of buckets of key data.

In order to have distribution sorts that will work with a database
system, for each and every data type you will need a function to return
the bucket of bits of significance for the kth bucket of bits.  For a
character string, you could return key[bucket].  For an unsigned integer
it is the byte of the integer to return will be a function of the
endianness of the CPU.  And for each other distinct data type a bucket
function would be needed or a sort could not be generated for that type
using the distribution method.

---(end of broadcast)---
TIP 6: explain analyze is your friend

[PERFORM] Index Choice Problem

[Adam Alkins]

Hi List,

I would like some insight from the experts here as to how I can alter
which index PostgreSQL is choosing to run a query.

First off, I'm running an active web forum (phpBB) with sometimes
hundreds of concurrent users. The query in question is one which pulls
the lists of topics in the forum. The table in question is here:

--

forums=> \d phpbb_topics;
 Table "public.phpbb_topics"
Column| Type  |  
Modifiers
--+---+---
 topic_id | integer   | not null default
nextval('phpbb_topics_id_seq'::text)
 forum_id | integer   | not null default 0
 topic_title  | character varying(60) | not null default
''::character varying
 topic_poster | integer   | not null default 0
 topic_time   | integer   | not null default 0
 topic_views  | integer   | not null default 0
 topic_replies| integer   | not null default 0
 topic_status | smallint  | not null default (0)::smallint
 topic_vote   | smallint  | not null default (0)::smallint
 topic_type   | smallint  | not null default (0)::smallint
 topic_first_post_id  | integer   | not null default 0
 topic_last_post_id   | integer   | not null default 0
 topic_moved_id   | integer   | not null default 0
 topic_last_post_time | integer   | not null default 0
Indexes:
"forum_id_phpbb_topics_index" btree (forum_id)
"topic_id_phpbb_topics_index" btree (topic_id)
"topic_last_post_id_phpbb_topics_index" btree (topic_last_post_id)
"topic_last_post_time_phpbb_topics_index" btree (topic_last_post_time)
"topic_moved_id_phpbb_topics_index" btree (topic_moved_id)

--

To layout the contents of the table, here are some relevant queries
showing the number of entries

forums=# SELECT COUNT(*) FROM phpbb_topics; SELECT COUNT(*) FROM
phpbb_topics WHERE forum_id = 71; SELECT COUNT(*) FROM phpbb_topics
WHERE forum_id = 55;
 count

 190588
(1 row)

 count
---
  1013
(1 row)

 count
---
 35035
(1 row)

--

Ok. Now, here's the problem. I run a query to pull the list of topics
for the forum. There pagination, so the first page query looks like
this:

SELECT t.topic_id
FROM phpbb_topics AS t
WHERE t.forum_id = 71
AND t.topic_id NOT IN (205026, 29046, 
144569, 59780, 187424,
138635, 184973, 170551, 22419, 181690, 197254, 205130)
ORDER BY t.topic_last_post_time 
DESC
LIMIT 23 OFFSET 0

  
  
  
 QUERY PLAN
-
 Limit  (cost=3487.78..3487.87 rows=34 width=8) (actual
time=1112.921..1113.005 rows=34 loops=1)
   ->  Sort  (cost=3486.15..3489.10 rows=1181 width=8) (actual
time=1112.087..1112.535 rows=687 loops=1)
 Sort Key: topic_last_post_time
 ->  Index Scan using forum_id_phpbb_topics_index on
phpbb_topics t  (cost=0.00..3425.89 rows=1181 width=8) (actual
time=54.650..1109.877 rows=1012 loops=1)
   Index Cond: (forum_id = 71)
   Filter: (topic_id <> 205026)
 Total runtime: 1113.268 ms
(7 rows)

--

This is the query on one of the lesser active forums (forum_id = 71)
which as list earlier only has 1013 rows. This query slow because
PostgreSQL is not using the index on the "forum_id" column, but
instead scanning through the topics via the topic_last_post_time and
filtering through the posts. This would be good for the forum_id = 55
where the most recent topics would be quickly found. Now here's the
stranger part, going deeper into the results (ie selecting pages
further down), the planner does this:

--

SELECT t.topic_id
FROM phpbb_topics AS t
WHERE t.forum_id = 71
AND t.topic_id NOT IN (205026)
ORDER BY t.topic_last_post_time 
DESC
LIMIT 34 OFFSET 653

  
QUERY PLAN
-
 Limit  (cost=3487.78..3487.87 r

[PERFORM] Future of Table Partitioning

[Patrick Carriere]

Title: Future of Table Partitioning






Hi,


I was wondering what the plan is for the future of table partitioning in PostgresQL. It is pretty hard for me to implement partitioning right now with its current limitation, specifically the fact that unique constraints cannot be enforced across partitions and that Constraint Exclusion cannot be used on non-constant values like CURRENT_DATE. It is also quite cumbersome to do all the maintenance work to create the new child table, do the triggers, drop the old one, etc,etc using the table inheritance every week since I would need to do weekly and monthly table partitioning.

So, my question in short, Is there any plan to at least do Global unique check constraints (or at least a global unique index) and is there a thread/documentation somewhere about what are the future planned changes to table partitioning?


Thanks


Patrick Carriere

Software Architect

Nexus Telecom (Americas)

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Jonah H. Harris]

Last night I implemented a non-recursive introsort in C... let me test it a bit more and then I'll post it here for everyone else to try out.On 2/16/06, Markus Schaber
 <[EMAIL PROTECTED]> wrote:Hi, Ron,
Ron wrote:> ...and of course if you know enough about the data to be sorted so as to> constrain it appropriately, one should use a non comparison based O(N)> sorting algorithm rather than any of the general comparison based
> O(NlgN) methods.Sounds interesting, could you give us some pointers (names, URLs,papers) to such algorithms?Thanks a lot,Markus--Markus Schaber | Logical Tracking&Tracing International AG
Dipl. Inf. | Software Development GISFight against software patents in EU! www.ffii.org www.nosoftwarepatents.org---(end of broadcast)---
TIP 4: Have you searched our list archives?   http://archives.postgresql.org-- Jonah H. Harris, Database Internals Architect
EnterpriseDB Corporation732.331.1324

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index behaviour)

[Dann Corbit]

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:pgsql-hackers-
> [EMAIL PROTECTED] On Behalf Of Tom Lane
> Sent: Wednesday, February 15, 2006 5:22 PM
> To: Ron
> Cc: pgsql-performance@postgresql.org; pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create
Index
> behaviour)
> 
> Ron <[EMAIL PROTECTED]> writes:
> > How are we choosing our pivots?
> 
> See qsort.c: it looks like median of nine equally spaced inputs (ie,
> the 1/8th points of the initial input array, plus the end points),
> implemented as two rounds of median-of-three choices.  With half of
the
> data inputs zero, it's not too improbable for two out of the three
> samples to be zeroes in which case I think the med3 result will be
zero
> --- so choosing a pivot of zero is much more probable than one would
> like, and doing so in many levels of recursion causes the problem.

Adding some randomness to the selection of the pivot is a known
technique to fix the oddball partitions problem.  However, Bentley and
Sedgewick proved that every quick sort algorithm has some input set that
makes it go quadratic (hence the recent popularity of introspective
sort, which switches to heapsort if quadratic behavior is detected.  The
C++ template I submitted was an example of introspective sort, but
PostgreSQL does not use C++ so it was not helpful).

> I think.  I'm not too sure if the code isn't just being sloppy about
the
> case where many data values are equal to the pivot --- there's a
special
> case there to switch to insertion sort, and maybe that's getting
invoked
> too soon.  

Here are some cases known to make qsort go quadratic:
1. Data already sorted
2. Data reverse sorted
3. Data organ-pipe sorted or ramp
4. Almost all data of the same value

There are probably other cases.  Randomizing the pivot helps some, as
does check for in-order or reverse order partitions.

Imagine if 1/3 of the partitions fall into a category that causes
quadratic behavior (have one of the above formats and have more than
CUTOFF elements in them).

It is doubtful that the switch to insertion sort is causing any sort of
problems.  It is only going to be invoked on tiny sets, for which it has
a fixed cost that is probably less that qsort() function calls on sets
of the same size.

>It'd be useful to get a line-level profile of the behavior of
> this code in the slow cases...

I guess that my in-order or presorted tests [which often arise when
there are very few distinct values] may solve the bad partition
problems.  Don't forget that the algorithm is called recursively.

>   regards, tom lane
> 
> ---(end of
broadcast)---
> TIP 3: Have you checked our extensive FAQ?
> 
>http://www.postgresql.org/docs/faq

---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [PERFORM] out of memory

[martial . bizel]

Good morning,

I've increased sort_mem until 2Go !!
and the error "out of memory" appears again.

Here the request I try to pass with her explain plan,

 Nested Loop  (cost=2451676.23..2454714.73 rows=1001 width=34)
   ->  Subquery Scan "day"  (cost=2451676.23..2451688.73 rows=1000 width=16)
 ->  Limit  (cost=2451676.23..2451678.73 rows=1000 width=12)
   ->  Sort  (cost=2451676.23..2451684.63 rows=3357 width=12)
 Sort Key: sum(occurence)
 ->  HashAggregate  (cost=2451471.24..2451479.63 rows=3357
width=12)
   ->  Index Scan using test_date on
queries_detail_statistics  (cost=0.00..2449570.55 rows=380138 width=12)
 Index Cond: ((date >= '2006-01-01'::date) AND
(date <= '2006-01-30'::date))
 Filter: (((portal)::text = '1'::text) OR
((portal)::text = '2'::text))
   ->  Index Scan using query_string_pkey on query_string  (cost=0.00..3.01
rows=1 width=34)
 Index Cond: ("outer".query = query_string.id)
(11 rows)

Any new ideas ?,
thanks

MB.




> On Tue, 2006-02-14 at 10:32, [EMAIL PROTECTED] wrote:
> > command explain analyze crash with the "out of memory" error
> >
> > I precise that I've tried a lot of values from parameters shared_buffer and
> > sort_mem
> >
> > now, in config file, values are :
> > sort_mem=32768
> > and shared_buffer=3
>
> OK, on the command line, try increasing the sort_mem until hash_agg can
> work.  With a 4 gig machine, you should be able to go as high as needed
> here, I'd think.  Try as high as 50 or so or more.  Then when
> explain analyze works, compare the actual versus estimated number of
> rows.
>



---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Tom Lane]

Mark Lewis <[EMAIL PROTECTED]> writes:
> I think we're actually on the same page here; you're right that the
> constraint above ( f(a)==f(b) iff a==b ) can't be extended to data types
> with more than 32 bits of value space.  But the constraint I listed was
> actually:

> if a==b then f(a)==f(b)

I believe Martijn had it right: the important constraint is

f(a) > f(b) implies a > b

which implies by commutativity

f(a) < f(b) implies a < b

and these two together imply

a == b implies f(a) == f(b)

Now you can't do any sorting if you only have the equality rule, you
need the inequality rule.

regards, tom lane

---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Ragnar]

On fös, 2006-02-17 at 08:01 -0500, Ron wrote:
> At 04:24 AM 2/17/2006, Ragnar wrote:
> >On fös, 2006-02-17 at 01:20 -0500, Ron wrote:
> > >
> > > OK, so here's _a_ way (there are others) to obtain a mapping such that
> > >   if a < b then f(a) < f (b) and
> > >   if a == b then f(a) == f(b)
> >
> > > By scanning the table once, we can map say 001h (Hex used to ease
> > > typing) to the row with the minimum value and 111h to the row
> > > with the maximum value as well as mapping everything in between to
> > > their appropriate keys.  That same scan can be used to assign a
> > > pointer to each record's location.
> >
> >This step is just as expensive as the original 
> >sort you want to replace/improve.
> 
> Why do you think that?  External sorts involve 
> the equivalent of multiple scans of the table to 
> be sorted, sometimes more than lgN (where N is 
> the number of items in the table to be 
> sorted).  Since this is physical IO we are 
> talking about, each scan is very expensive, and 
> therefore 1 scan is going to take considerably 
> less time than >= lgN scans will be.

Call me dim, but please explain exactly how you are going
to build this mapping in one scan. Are you assuming
the map will fit in memory? 

> 
> 
> >If you want to keep this mapping saved as a sort 
> >of an index, or as part ot each row data, this 
> >will make the cost of inserts and updates enormous.
> 
> Not sure you've got this right either.  Looks to 
> me like we are adding a <= 32b quantity to each 
> row.  Once we know the mapping, incrementally 
> updating it upon insert or update would seem to 
> be simple matter of a fast search for the correct 
> ranking [Interpolation search, which we have all 
> the needed data for, is O(lglgN).  Hash based 
> search is O(1)]; plus an increment/decrement of 
> the key values greater/less than the key value of 
> the row being inserted / updated.  Given than we 
> are updating all the keys in a specific range 
> within a tree structure, that update can be done 
> in O(lgm) (where m is the number of records affected).

Say again ?
Let us say you have 1 billion rows, where the
column in question contains strings like 
baaaaaa
baaaaab
baaaaac
...
not necessarily in this order on disc of course

The minimum value would be keyed as 0001h,
the next one as 0002h and so on.

Now insert new value 'a'

Not only will you have to update 1 billion records,
but also all the values in your map.

please explain

gnari



---(end of broadcast)---
TIP 9: In versions below 8.0, the planner will ignore your desire to
   choose an index scan if your joining column's datatypes do not
   match

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Mark Lewis]

On Thu, 2006-02-16 at 21:33 -0800, David Lang wrote:
> > In SQL_ASCII, just take the first 4 characters (or 8, if using a 64-bit
> > sortKey as elsewhere suggested).  The sorting key doesn't need to be a
> > one-to-one mapping.
> 
> that would violate your second contraint ( f(a)==f(b) iff (a==b) )
> 
> if you could drop that constraint (the cost of which would be extra 'real' 
> compares within a bucket) then a helper function per datatype could work 
> as you are talking.

I think we're actually on the same page here; you're right that the
constraint above ( f(a)==f(b) iff a==b ) can't be extended to data types
with more than 32 bits of value space.  But the constraint I listed was
actually:

if a==b then f(a)==f(b)

Which doesn't imply 'if and only if'.  It's a similar constraint to
hashcodes; the same value will always have the same hash, but you're not
guaranteed that the hashcodes for two distinct values will be unique.

-- Mark

---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

Re: [PERFORM] [HACKERS] Need pointers to "standard" pg database(s) for testing

[Michael Paesold]

Ron wrote:

I assume we have such?


You could look at the Sample Databases project on pgfoundry:
http://pgfoundry.org/projects/dbsamples/

Best Regards,
Michael Paesold


---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
  subscribe-nomail command to [EMAIL PROTECTED] so that your
  message can get through to the mailing list cleanly

Re: [PERFORM] Need pointers to "standard" pg database(s) for

[Scott Marlowe]

On Fri, 2006-02-17 at 10:51, Ron wrote:
> I assume we have such?

Depends on what you wanna do.
For transactional systems, look at some of the stuff OSDL has done.

For large geospatial type stuff, the government is a good source, like
www.usgs.gov or the fcc transmitter database.

There are other ones out there.  Really depends on what you wanna test.

---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

[PERFORM] Need pointers to "standard" pg database(s) for testing

[Ron]

I assume we have such?

Ron



---(end of broadcast)---
TIP 5: don't forget to increase your free space map settings

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Ron]

At 10:53 AM 2/17/2006, Martijn van Oosterhout wrote:

On Fri, Feb 17, 2006 at 08:23:40AM -0500, Ron wrote:
> >For this mapping, you need a full table sort.
> One physical IO pass should be all that's needed.  However, let's
> pretend you are correct and that we do need to sort the table to get
> the key mapping.  Even so, we would only need to do it =once= and
> then we would be able to use and incrementally update the results
> forever afterward.  Even under this assumption, one external sort to
> save all subsequent such sorts seems well worth it.
>
> IOW, even if I'm wrong about the initial cost to do this; it is still
> worth doing ;-)

I think you're talking about something different here. You're thinking
of having the whole table sorted and when you add a new value you add
it in such a way to keep it sorted. The problem is, what do you sort it
by? If you've sorted the table by col1, then when the user does ORDER
BY col2 it's useless.

No, I'm thinking about how to represent DB row data in such a way that
a= we use a compact enough representation that we can sort internally 
rather than externally.
b= we do the sort once and avoid most of the overhead upon subsequent 
similar requests.


I used the example of sorting on the entire row to show that the 
approach works even when the original record being sorted by is very large.
All my previous comments on this topic hold for the case where we are 
sorting on only part of a row as well.


If all you are doing is sorting on a column or a few columns, what 
I'm discussing is even easier since treating the columns actually 
being used a sort criteria as integers rather than the whole row as 
an atomic unit eats less resources during the key creation and 
mapping process.  If the row is 2-4KB in size, but we only care about 
some combination of columns that only takes on <= 2^8 or <= 2^16 
different values, then what I've described will be even better than 
the original example I gave.


Basically, the range of a key is going to be restricted by how
a= big the field is that represents the key (columns and such are 
usually kept narrow for performance reasons) or
b= big each row is (the more space each row takes, the fewer rows fit 
into any given amount of storage)

c= many rows there are in the table
Between the conditions, the range of a key tends to be severely 
restricted and therefore use much less space than sorting the actual 
DB records would.  ...and that gives us something we can take advantage of.




Indeed, this is what btrees do, you store the order of the table
seperate from the data. And you can store multiple orders. But even
then, when someone does ORDER BY lower(col1), it's still useless.

And you're right, we still need to do the single mass sort in the
beginning, which is precisely what we're trying to optimise here.

Sigh.  My points were:
1= we have information available to us that allows us to map the rows 
in such a way as to turn most external sorts into internal sorts, 
thereby avoiding the entire external sorting problem in those 
cases.  This is a huge performance improvement.


2= that an external sort is =NOT= required for initial key 
assignment, but even if it was it would be worth it.


3= that this is a variation of a well known technique so I'm not 
suggesting heresy here.



Ron 




---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Martijn van Oosterhout]

On Fri, Feb 17, 2006 at 08:18:41AM -0800, Scott Lamb wrote:
> On Feb 16, 2006, at 2:17 PM, Mark Lewis wrote:
> >Data types which could probably provide a useful function for f  
> >would be
> >int2, int4, oid, and possibly int8 and text (at least for SQL_ASCII).
> 
> ...and with some work, floats (I think just the exponent would work,  
> if nothing else). bytea. Probably just about anything.
> 
> Interesting. If you abandon the idea that collisions should be  
> impossible (they're not indexes) or extremely rare (they're not  
> hashes), it's pretty easy to come up with a decent hint to avoid a  
> lot of dereferences.

Yep, pretty much for any datatype you create a mapping function to map
it to a signed int32. All you have to guarentee is that f(a) > f(b)
implies that a > b. Only if f(a) == f(b) do you need to compare a and
b.

You then change the sorting code to have an array of (Datum,int32)
(ouch, double the storage) where the int32 is the f(Datum). And in the
comparison routines you first check the int32. If they give an order
you're done. On match you do the full comparison.

For integer types (int2,int4,int8,oid) the conversion is straight
forward. For float you'd use the exponent and the first few bits of the
mantissa. For strings you'd have to bail, or use a strxfrm equivalent.
NULL would be INT_MAX pr INT_MIN depending on where you want it. Thing
is, even if you don't have such a function and always return zero, the
results will still be right.

Not a new idea, but it would be very nice to implement. If would
produce nice speedups for type where comparisons are expensive. And
more importantly, the bulk of the comparisons can be moved inline and
make the whole cache-friendlyness discussed here much more meaningful.

Have a nice day,
-- 
Martijn van Oosterhout  http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.


signature.asc
Description: Digital signature

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Scott Lamb]

On Feb 16, 2006, at 2:17 PM, Mark Lewis wrote:Data types which could probably provide a useful function for f would be int2, int4, oid, and possibly int8 and text (at least for SQL_ASCII). ...and with some work, floats (I think just the exponent would work, if nothing else). bytea. Probably just about anything.Interesting. If you abandon the idea that collisions should be impossible (they're not indexes) or extremely rare (they're not hashes), it's pretty easy to come up with a decent hint to avoid a lot of dereferences. --Scott Lamb  

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Martijn van Oosterhout]

On Fri, Feb 17, 2006 at 08:23:40AM -0500, Ron wrote:
> >For this mapping, you need a full table sort.
> One physical IO pass should be all that's needed.  However, let's 
> pretend you are correct and that we do need to sort the table to get 
> the key mapping.  Even so, we would only need to do it =once= and 
> then we would be able to use and incrementally update the results 
> forever afterward.  Even under this assumption, one external sort to 
> save all subsequent such sorts seems well worth it.
> 
> IOW, even if I'm wrong about the initial cost to do this; it is still 
> worth doing ;-)

I think you're talking about something different here. You're thinking
of having the whole table sorted and when you add a new value you add
it in such a way to keep it sorted. The problem is, what do you sort it
by? If you've sorted the table by col1, then when the user does ORDER
BY col2 it's useless.

Indeed, this is what btrees do, you store the order of the table
seperate from the data. And you can store multiple orders. But even
then, when someone does ORDER BY lower(col1), it's still useless.

And you're right, we still need to do the single mass sort in the
beginning, which is precisely what we're trying to optimise here.

> ??? You do not need to resort already ordered data to insert a new 
> element into it such that the data stays ordered!  Once we have done 
> the key ordering operation once, we should not ever need to do it 
> again on the original data.  Else most sorting algorithms wouldn't work ;-)

We already do this with btree indexes. I'm not sure what you are
proposing that improves on that.

Have a nice day,
-- 
Martijn van Oosterhout  http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.


signature.asc
Description: Digital signature

Re: [PERFORM] split partitioned table across several postgres servers

[martial . bizel]

Selon Tom Lane <[EMAIL PROTECTED]>:

> [EMAIL PROTECTED] writes:
> > In fact, I don't know how to have explain plan of remote node.
>
> You send it an EXPLAIN.


Please, Could you send me what to put at end of request :

 select * from dblink('my_connexion', 'EXPLAIN select * from test where
number='1' ') as 

I want to be sure that remote test is seen as partitioned object.

thanks a lot.


>
> You can *not* use a view defined as you suggest if you want decent
> performance --- the dblink functions will fetch the entire table
> contents and the filtering will be done locally.  You'll need to
> pass the WHERE conditions over to the remote servers, which more
> or less means that you have to give them to the dblink functions
> as text.
>
> regards, tom lane
>

---(end of broadcast)---
TIP 4: Have you searched our list archives?

   http://archives.postgresql.org

Re: [PERFORM] split partitioned table across several postgres servers

[Tom Lane]

[EMAIL PROTECTED] writes:
> In fact, I don't know how to have explain plan of remote node.

You send it an EXPLAIN.

You can *not* use a view defined as you suggest if you want decent
performance --- the dblink functions will fetch the entire table
contents and the filtering will be done locally.  You'll need to
pass the WHERE conditions over to the remote servers, which more
or less means that you have to give them to the dblink functions
as text.

regards, tom lane

---(end of broadcast)---
TIP 4: Have you searched our list archives?

   http://archives.postgresql.org

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Ron]

At 05:19 AM 2/17/2006, Markus Schaber wrote:

Hi, Ron,

Ron schrieb:

> OK, so here's _a_ way (there are others) to obtain a mapping such that
>  if a < b then f(a) < f (b) and
>  if a == b then f(a) == f(b)
>
> Pretend each row is a integer of row size (so a 2KB row becomes a 16Kb
> integer; a 4KB row becomes a 32Kb integer; etc)
> Since even a 1TB table made of such rows can only have 256M - 512M
> possible values even if each row is unique, a 28b or 29b key is large
> enough to represent each row's value and relative rank compared to all
> of the others even if all row values are unique.
>
> By scanning the table once, we can map say 001h (Hex used to ease
> typing) to the row with the minimum value and 111h to the row with
> the maximum value as well as mapping everything in between to their
> appropriate keys.  That same scan can be used to assign a pointer to
> each record's location.

But with a single linear scan, this cannot be accomplished, as the table
contents are neither sorted nor distributed linearly between the minimum
and the maximum.
So what?  We are talking about key assignment here, not anything that 
requires physically manipulating the actual DB rows.

One physical IO pass should be all that's needed.



For this mapping, you need a full table sort.
One physical IO pass should be all that's needed.  However, let's 
pretend you are correct and that we do need to sort the table to get 
the key mapping.  Even so, we would only need to do it =once= and 
then we would be able to use and incrementally update the results 
forever afterward.  Even under this assumption, one external sort to 
save all subsequent such sorts seems well worth it.


IOW, even if I'm wrong about the initial cost to do this; it is still 
worth doing ;-)




> That initial scan to set up the keys is expensive, but if we wish that
> cost can be amortized over the life of the table so we don't have to pay
> it all at once.  In addition, once we have created those keys, then can
> be saved for later searches and sorts.

But for every update or insert, you have to resort the keys, which is
_very_ expensive as it basically needs to update a huge part of the table.


??? You do not need to resort already ordered data to insert a new 
element into it such that the data stays ordered!  Once we have done 
the key ordering operation once, we should not ever need to do it 
again on the original data.  Else most sorting algorithms wouldn't work ;-)



Ron 




---(end of broadcast)---
TIP 6: explain analyze is your friend

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Ron]

At 04:24 AM 2/17/2006, Ragnar wrote:

On fös, 2006-02-17 at 01:20 -0500, Ron wrote:
>
> OK, so here's _a_ way (there are others) to obtain a mapping such that
>   if a < b then f(a) < f (b) and
>   if a == b then f(a) == f(b)

> By scanning the table once, we can map say 001h (Hex used to ease
> typing) to the row with the minimum value and 111h to the row
> with the maximum value as well as mapping everything in between to
> their appropriate keys.  That same scan can be used to assign a
> pointer to each record's location.

This step is just as expensive as the original 
sort you want to replace/improve.


Why do you think that?  External sorts involve 
the equivalent of multiple scans of the table to 
be sorted, sometimes more than lgN (where N is 
the number of items in the table to be 
sorted).  Since this is physical IO we are 
talking about, each scan is very expensive, and 
therefore 1 scan is going to take considerably 
less time than >= lgN scans will be.



If you want to keep this mapping saved as a sort 
of an index, or as part ot each row data, this 
will make the cost of inserts and updates enormous.


Not sure you've got this right either.  Looks to 
me like we are adding a <= 32b quantity to each 
row.  Once we know the mapping, incrementally 
updating it upon insert or update would seem to 
be simple matter of a fast search for the correct 
ranking [Interpolation search, which we have all 
the needed data for, is O(lglgN).  Hash based 
search is O(1)]; plus an increment/decrement of 
the key values greater/less than the key value of 
the row being inserted / updated.  Given than we 
are updating all the keys in a specific range 
within a tree structure, that update can be done 
in O(lgm) (where m is the number of records affected).



>  We can now sort the key+pointer pairs instead of the actual data and
> use an optional final pass to rearrange the actual rows if we wish.

How are you suggesting this mapping be accessed? 
If the mapping is kept separate from the tuple 
data, as in an index, then how will you look up the key?
???  We've effectively created a data set where 
each record is a pointer to a DB row plus its 
key.  We can now sort the data set by key and 
then do an optional final pass to rearrange the 
actual DB rows if we so wish.  Since that final 
pass is very expensive, it is good that not all 
use scenarios will need that final pass.


The amount of storage required to sort this 
representation of the table rather than the 
actual table is so much less that it turns an 
external sorting problem into a internal sorting 
problem with an optional final pass that is =1= 
scan (albeit one scan with a lot of seeks and 
data movement).  This is a big win.  It is a 
variation of a well known technique.  See Sedgewick, Knuth, etc.




> That initial scan to set up the keys is expensive, but if we wish
> that cost can be amortized over the life of the table so we don't
> have to pay it all at once.  In addition, once we have created those
> keys, then can be saved for later searches and sorts.

What is the use case where this would work better than a
regular btree index ?
Again, ???  btree indexes address different 
issues.  They do not in any way help create a 
compact data representation of the original data 
that saves enough space so as to turn an external 
ranking or sorting problem into an internal one.



Ron 




---(end of broadcast)---
TIP 5: don't forget to increase your free space map settings

[PERFORM] split partitioned table across several postgres servers

[martial . bizel]

Hello,

I want to split table partitioned across two servers postgres (two hosts).
To query this remote object, I want to make view with union on two servers with
two dblink.

But, How to be sure that optimizer plan on remote node is same than local node
(ie : optimizer scan only the selected partitions and not make full scan  of
the remote object) ?

example : server 1 (table test partionned on field number and 1 < number <10)
  server 2 (table test partitioned on field number 10 15.

optimizer made full scan of all partitions on all servers or
scan only partition 1 to partition 4 on server1
and scan partiton 16 to partition 19 on server2
and union  ?

In fact, I don't know how to have explain plan of remote node.

Thanks a lot.

MB



---(end of broadcast)---
TIP 6: explain analyze is your friend

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[PFC]

	Has anybody got some profiler data on the amount of time spent in  
comparisons during a sort ? Say, the proposals here would give the most  
gains on simple types like INTEGER ; so it would be interesting to know  
how much time is now spent in comparisons for sorting a column of ints. If  
it's like, 10% of the total time, well...


More hand-waving :

What are the usage case for sorts ?

	- potentially huge data sets : create index, big joins, reporting queries  
etc.
	- small data sets : typically, a query with an ORDER BY which will return  
a small amount of rows (website stuff), or joins not small enough to use a  
HashAggregate, but not big enough to create an index just for them.


	The cost of a comparison vs. moving stuff around and fetching stuff is  
probably very different in these two cases. If it all neatly fits in  
sort_mem, you can do fancy stuff (like sorting on SortKeys) which will  
need to access the data in almost random order when time comes to hand the  
sorted data back. So, I guess the SortKey idea would rather apply to the  
latter case only, which is CPU limited.


	Anyway, I was wondering about queries with multipart keys, like ORDER BY  
zipcode, client_name, date and the like. Using just an int64 as the key  
isn't going to help a lot here. Why not use a binary string of limited  
length ? I'd tend to think it would not be that slower than comparing  
ints, and it would be faster than calling each comparison function for  
each column. Each key part would get assigned to a byte range in the  
string.
	It would waste some memory, but for instance, using 2x the memory for  
half the time would be a good tradeoff if the amount of memory involved is  
in the order of megabytes.
	Also, it would solve the problem of locales. Comparisons involving  
locales are slow, but strings can be converted to a canonical form  
(removing accents and stuff), and then binary sorted.


	Also I'll insert a plug for the idea that the Sort needs to know if there  
will be a LIMIT afterwards ; this way it could reduce its working set by  
simply discarding the rows which would have been discarded anyway by the  
LIMIT. Say you want the 100 first rows out of a million ordered rows. If  
the sort knows this, it can be performed in the amount of memory for a 100  
rows sort.



---(end of broadcast)---
TIP 4: Have you searched our list archives?

  http://archives.postgresql.org

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Markus Schaber]

Hi, Ron,

Ron schrieb:

> OK, so here's _a_ way (there are others) to obtain a mapping such that
>  if a < b then f(a) < f (b) and
>  if a == b then f(a) == f(b)
> 
> Pretend each row is a integer of row size (so a 2KB row becomes a 16Kb
> integer; a 4KB row becomes a 32Kb integer; etc)
> Since even a 1TB table made of such rows can only have 256M - 512M
> possible values even if each row is unique, a 28b or 29b key is large
> enough to represent each row's value and relative rank compared to all
> of the others even if all row values are unique.
> 
> By scanning the table once, we can map say 001h (Hex used to ease
> typing) to the row with the minimum value and 111h to the row with
> the maximum value as well as mapping everything in between to their
> appropriate keys.  That same scan can be used to assign a pointer to
> each record's location.

But with a single linear scan, this cannot be accomplished, as the table
contents are neither sorted nor distributed linearly between the minimum
and the maximum.

For this mapping, you need a full table sort.

> That initial scan to set up the keys is expensive, but if we wish that
> cost can be amortized over the life of the table so we don't have to pay
> it all at once.  In addition, once we have created those keys, then can
> be saved for later searches and sorts.

But for every update or insert, you have to resort the keys, which is
_very_ expensive as it basically needs to update a huge part of the table.

Markus

---(end of broadcast)---
TIP 3: Have you checked our extensive FAQ?

   http://www.postgresql.org/docs/faq

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create Index

[Markus Schaber]

Hi, David,

David Lang schrieb:

>> In SQL_ASCII, just take the first 4 characters (or 8, if using a 64-bit
>> sortKey as elsewhere suggested).  The sorting key doesn't need to be a
>> one-to-one mapping.

> that would violate your second contraint ( f(a)==f(b) iff (a==b) )

no, it doesn't.

When both strings are equal, then the first characters are equal, too.

If they are not equal, the constraint condition does not match.

The first characters of the strings may be equal as f(a) may be equal to
f(b) as to the other constraint.

Markus

---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly

Re: [HACKERS] qsort again (was Re: [PERFORM] Strange Create

[Ragnar]

On fös, 2006-02-17 at 01:20 -0500, Ron wrote:
> At 01:47 PM 2/16/2006, Ron wrote:
> >At 12:19 PM 2/16/2006, Scott Lamb wrote:
> >>On Feb 16, 2006, at 8:32 AM, Ron wrote:
> >>>Let's pretend that we have the typical DB table where rows are
> >>>~2-4KB apiece.  1TB of storage will let us have 256M-512M rows in
> >>>such a table.
> >>>
> >>>A 32b hash code can be assigned to each row value such that only
> >>>exactly equal rows will have the same hash code.
> >>>A 32b pointer can locate any of the 256M-512M rows.
> >>>
> >>>Now instead of sorting 1TB of data we can sort 2^28 to 2^29 32b 
> >>>+32b= 64b*(2^28 to 2^29)=  2-4GB of pointers+keys followed by an
> >>>optional pass to rearrange the actual rows if we so wish.
> >>
> >>I don't understand this.
> >>
> >>This is a true statement: (H(x) != H(y)) => (x != y)
> >>This is not: (H(x) < H(y)) => (x < y)
> >>
> >>Hash keys can tell you there's an inequality, but they can't tell you
> >>how the values compare. If you want 32-bit keys that compare in the
> >>same order as the original values, here's how you have to get them:
> >For most hash codes, you are correct.  There is a class of hash or 
> >hash-like codes that maintains the mapping to support that second statement.
> >
> >More later when I can get more time.
> >Ron
> 
> OK, so here's _a_ way (there are others) to obtain a mapping such that
>   if a < b then f(a) < f (b) and
>   if a == b then f(a) == f(b)

> By scanning the table once, we can map say 001h (Hex used to ease 
> typing) to the row with the minimum value and 111h to the row 
> with the maximum value as well as mapping everything in between to 
> their appropriate keys.  That same scan can be used to assign a 
> pointer to each record's location.

This step is just as expensive as the original sort you
want to replace/improve. If you want to keep this mapping
saved as a sort of an index, or as part ot each row data, this will make
the cost of inserts and updates enormous.

> 
> We can now sort the key+pointer pairs instead of the actual data and 
> use an optional final pass to rearrange the actual rows if we wish.

How are you suggesting this mapping be accessed? If the 
mapping is kept separate from the tuple data, as in an index, then how
will you look up the key?

> That initial scan to set up the keys is expensive, but if we wish 
> that cost can be amortized over the life of the table so we don't 
> have to pay it all at once.  In addition, once we have created those 
> keys, then can be saved for later searches and sorts.

What is the use case where this would work better than a 
regular btree index ?

gnari



---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
   subscribe-nomail command to [EMAIL PROTECTED] so that your
   message can get through to the mailing list cleanly