pg.ddx.io pgsql-performance@postgresql.org mailing list archivehelp / color / mirror / Atom feed
Re: [HACKERS] qsort again (was Re: Strange Create 2+ messages / 2 participants [nested] [flat]
* Re: [HACKERS] qsort again (was Re: Strange Create @ 2006-02-17 09:24 Ragnar <gnari@hive.is> 1 sibling, 0 replies; 2+ messages in thread From: Ragnar @ 2006-02-17 09:24 UTC (permalink / raw) To: Ron <rjpeace@earthlink.net>; +Cc: pgsql-performance 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 0000001h (Hex used to ease > typing) to the row with the minimum value and 1111111h 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 ^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: [HACKERS] qsort again (was Re: Strange Create @ 2006-02-17 10:55 PFC <lists@peufeu.com> 1 sibling, 0 replies; 2+ messages in thread From: PFC @ 2006-02-17 10:55 UTC (permalink / raw) To: pgsql-performance 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. ^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2006-02-17 10:55 UTC | newest] Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2006-02-17 09:24 ` Ragnar <gnari@hive.is> 2006-02-17 10:55 ` PFC <lists@peufeu.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions for how to clone and mirror all data and code used for this inbox