473,574 Members | 17,882 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Table partitioning for maximum speed?

I'm sure this is a concept that's been explored here. I have a table
(fairly simple, just two columns, one of which is a 32-digit checksum)
with several million rows (currently, about 7 million). About a million
times a day we do

select * from my_table where md5 = ?

to verify presence or absence of the row, and base further processing on
that information.

The idea bandied about now is to partition this table into 16 (or 256,
or ...) chunks by first digit (or 2, or ...). In the simplest case, this
would mean:

create table my_table_0 as select * from my_table where md5 like '0%';

create table my_table_1 as select * from my_table where md5 like '1%';

....

create table my_table_f as select * from my_table where md5 like 'f%';
Then change the code to examine the checksum and create a query to the
appropriate table based on the first digit.

Obviously, this is conceptually similar to what the index on the "md5"
column is supposed to do for us. However, partitioning moves just a
little of the processing load off the database server and onto the
machine running the application. That's important, because we can afford
more application machines as load increases, but we can't as easily
upgrade the database server.

Will a query against a table of 0.5 million rows beat a query against a
table of 7 million rows by a margin that makes it worth the hassle of
supporting 15 "extra" tables?

--
Jeff Boes vox 269.226.9550 ext 24
Database Engineer fax 269.349.9076
Nexcerpt, Inc. http://www.nexcerpt.com
...Nexcerpt... Extend your Expertise

Nov 12 '05 #1
18 6332
On Thu, Oct 09, 2003 at 18:37:19 +0000,
Jeff Boes <jb***@nexcerpt .com> wrote:
I'm sure this is a concept that's been explored here. I have a table
(fairly simple, just two columns, one of which is a 32-digit checksum)
with several million rows (currently, about 7 million). About a million
times a day we do

select * from my_table where md5 = ?

to verify presence or absence of the row, and base further processing on
that information.

The idea bandied about now is to partition this table into 16 (or 256,
or ...) chunks by first digit (or 2, or ...). In the simplest case, this
would mean:


If there is an index on the checksum column, then you shouldn't get
much of a speed up by partitioning the data.
If you don't have an index on the checksum, it sounds like you should.

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to ma*******@postg resql.org

Nov 12 '05 #2

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

That's important, because we can afford more application
machines as load increases, but we can't as easily
upgrade the database server.


Two ideas come to mind:

One way to speed things up is to convert the entire checksum. Consider
what a md5 checksum really is: a text string representing a hexadecimal
number. Storing it as TEXT or CHAR is not as good as storing it as a
number directly. Have your application convert it to a decimal number,
and then store the checksum as type NUMERIC in the database. This gives
an immediate speed boost. Next, use partial indexes to speed things up
even further. How many partial indexes you want to create depends on your
ratio of selects to updates, and how important each is to you. Some quick
statistical analysis I did showed that for 10 indexes, the magic number
is somewhere around 3.402 x 10 ^ 37. In other words:

CREATE TABLE md5check (id SERIAL, md5 NUMERIC);

CREATE INDEX md5_i0 ON md5check (md5) WHERE
md5 <= 340000000000000 000000000000000 00000000;
CREATE INDEX md5_i1 ON md5check (md5) WHERE
md5 > 340000000000000 000000000000000 00000000 AND
md5 <= 680000000000000 000000000000000 00000000;
CREATE INDEX md5_i2 ON md5check (md5) WHERE
md5 > 680000000000000 000000000000000 00000000 AND
md5 <= 102000000000000 000000000000000 000000000;
....
CREATE INDEX md5_i10 ON md5check (md5) WHERE
md5 > 340000000000000 000000000000000 000000000;

On my test table with 1/2 million rows, I saw a speed up from
..16 msec (using TEXT only) to .09 msec. The more partial indexes
you create, the faster things will go. Just remember to put the
upper and lower boundary indexes in place to catch everything.

Aside: if you are merely testing for the existence of the row,
you can pull back a constant instead of the whole row:

SELECT 1 FROM md5check WHERE md5 = ?
Another way to speed things up is to break the checksum up into parts
so that we can use one of the "normal" datatypes: specifically, BIGINT.
Divide the 32 character checksum into four pieces, convert each piece
to a decimal number, and store each in its own BIGINT column. The good
news with this way is that you only need an index on one of the columns.
Even at 7 million plus, the number of matches of 1/4 of the checksum
characters is small enough to not need additional indexes.

CREATE TABLE md5check
(id SERIAL, md1 BIGINT, md2 BIGINT, md3 BIGINT, md4 BIGINT);

CREATE INDEX md5_i1 ON md5check(md1);

You can also add partial indexes to this as well, for maximum speed.
- --
Greg Sabino Mullane gr**@turnstep.c om
PGP Key: 0x14964AC8 200310101135

-----BEGIN PGP SIGNATURE-----
Comment: http://www.turnstep.com/pgp.html

iD8DBQE/ht6DvJuQZxSWSsg RAjvyAJ9ndadWAg JIm84dc/kB8RABEIzIbwCg1 UJL
2VUQeQU+LMgXnum OoMT6kWk=
=PeUQ
-----END PGP SIGNATURE-----

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

Nov 12 '05 #3
Please keep discussions on the list so that others may learn from or comment
on the suggested solutions.

On Fri, Oct 10, 2003 at 11:27:50 -0400,
Jeff Boes <jb***@nexcerpt .com> wrote:
Bruno Wolff III wrote:
On Thu, Oct 09, 2003 at 18:37:19 +0000,
Jeff Boes <jb***@nexcerpt .com> wrote:


The idea bandied about now is to partition this table into 16 (or 256,
or ...) chunks by first digit (or 2, or ...). In the simplest case, this
would mean:


If there is an index on the checksum column, then you shouldn't get
much of a speed up by partitioning the data.
If you don't have an index on the checksum, it sounds like you should.

Yes, the table has:

Table "public.link_ch ecksums"
Column | Type | Modifiers
---------+---------------+-----------
md5 | character(32) | not null
link_id | integer | not null
Indexes: ix_link_checksu ms_pk primary key btree (md5)


In that event I would expect that you might only save a few disk accesses
by having a btree with fewer levels.

If the query is slow, it might be doing a sequential search because of
a type mismatch. You can use explain to double check what plan is being
used.

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

Nov 12 '05 #4
Bruno Wolff III wrote:
On Fri, Oct 10, 2003 at 11:27:50 -0400,
Jeff Boes <jb***@nexcerpt .com> wrote:

Yes, the table has:

Table "public.link_ch ecksums"
Column | Type | Modifiers
---------+---------------+-----------
md5 | character(32) | not null
link_id | integer | not null
Indexes: ix_link_checksu ms_pk primary key btree (md5)


In that event I would expect that you might only save a few disk accesses
by having a btree with fewer levels.

If the query is slow, it might be doing a sequential search because of
a type mismatch. You can use explain to double check what plan is being
used.


Actually, the query is *not* slow; but since we executing it a million
times a day, any savings we can realize will add up in a hurry. For
example, yesterday this query resulted in the following stats:

'count' => 814621,
'avg' => '0.009',
'time' => '7674.932'

That is, we executed it 814,621 times, for a total (wallclock) time
spent waiting of 7,674 seconds (obviously, we have multiple backends
executing). So, even if we can cut this by only 0.004, that would result
in a savings of almost an hour.

So, again: will front-loading the work by mapping the original query to
16 (or 256) different queries by examining the first digit save us
anything? (My colleague who came up with this idea thinks so, since the
calculation will be done on a box other than the database host, and even
one disk access saved per query would outweigh the calculation.)

Will having 15 (or 255) additional tables make the cache behave
differently? Is there overhead associated with having another 15 (or
255) tables?

--
Jeff Boes vox 269.226.9550 ext 24
Database Engineer fax 269.349.9076
Nexcerpt, Inc. http://www.nexcerpt.com
...Nexcerpt... Extend your Expertise

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to ma*******@postg resql.org

Nov 12 '05 #5
On Fri, Oct 10, 2003 at 04:30:20PM -0000, gr**@turnstep.c om wrote:
One way to speed things up is to convert the entire checksum. Consider
what a md5 checksum really is: a text string representing a hexadecimal
number. Storing it as TEXT or CHAR is not as good as storing it as a
number directly. Have your application convert it to a decimal number,
and then store the checksum as type NUMERIC in the database.


A subsequent idea is that with NUMERIC or other variable length fields
you are wasting time, space and cache hits anyway. It would be probably
faster to create a custom datatype, with fixed length for the exact size
of an MD5 sum. With suitable input and output functions and all the
operators you need, you will likely gain some additional performance
boost.

IIRC, Manfred Koizar developed a fixed-width char datatype for Shridar
Daitankhar (sp?) maybe a year ago. It is probably a good starting
point. Look for it in the pgsql-performance archives.

--
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"Endurecers e, pero jamás perder la ternura" (E. Guevara)

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

Nov 12 '05 #6
On Fri, Oct 10, 2003 at 13:40:17 -0400,
Jeff Boes <jb***@nexcerpt .com> wrote:

So, again: will front-loading the work by mapping the original query to
16 (or 256) different queries by examining the first digit save us
anything? (My colleague who came up with this idea thinks so, since the
calculation will be done on a box other than the database host, and even
one disk access saved per query would outweigh the calculation.)
This could potentially save you some disk accesses. If the index is mostly
in cache now, you might not get a noticable benefit.
Will having 15 (or 255) additional tables make the cache behave
differently? Is there overhead associated with having another 15 (or
255) tables?


I am not sure whether or not you would use significantly more space
by having multiple tables.

The data format change suggested by someone else may be worth trying
as well. In addition to their suggestions, you might experiment with
keeping the hash in either 4 ints or 2 bigints. If you use bigints,
you could probably just use an index on one of the bigints and have
only a small chance of finding more than one row that matches.

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

http://archives.postgresql.org

Nov 12 '05 #7
>>>>> "JB" == Jeff Boes <jb***@nexcerpt .com> writes:

JB> Will a query against a table of 0.5 million rows beat a query against
JB> a table of 7 million rows by a margin that makes it worth the hassle
JB> of supporting 15 "extra" tables?

I think you'll be better off with a single table, as you won't have
contention for the index pages in the cache.

One thing to do is to reindex reasonably often (for PG < 7.4) to avoid
index bloat, which will make them not fit in cache. Just check the
size of your index in the pg_class table, and when it gets big,
reindex (assuming you do lots of updates/inserts to the table).

Your table splitting solution sounds like something I'd do if I were
forced to use mysql ;-)
--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Vivek Khera, Ph.D. Khera Communications, Inc.
Internet: kh***@kciLink.c om Rockville, MD +1-240-453-8497
AIM: vivekkhera Y!: vivek_khera http://www.khera.org/~vivek/

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

Nov 12 '05 #8

Bruno Wolff III <br***@wolff.to > writes:
The data format change suggested by someone else may be worth trying
as well. In addition to their suggestions, you might experiment with
keeping the hash in either 4 ints or 2 bigints. If you use bigints,
you could probably just use an index on one of the bigints and have
only a small chance of finding more than one row that matches.


This sounds good to me too.

You would have to experiment to see if the 4x int format is faster than the 2x
bigint or vice versa. I suspect the 4x int format is way faster, if you have
few enough collisions (like single digit) it would probably be the best.

Using native fixed-size datatypes that fit in a Datum and have assembly
instructions for comparison should be a big win over a variable sized datatype
that has to be dereferenced from a pointer and then put through complex
functions to handle comparison.

--
greg
---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to ma*******@postg resql.org

Nov 12 '05 #9
Bruno Wolff III wrote:
The data format change suggested by someone else may be worth trying
as well. In addition to their suggestions, you might experiment with
keeping the hash in either 4 ints or 2 bigints. If you use bigints,
you could probably just use an index on one of the bigints and have
only a small chance of finding more than one row that matches.


This is an interesting idea. Alternatively just use bytea and store the
16 bytes directly (i.e. no hex or base64 encoding). There is b-tree
index support for bytea.

Joe

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

http://archives.postgresql.org

Nov 12 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
6062
by: Jay | last post by:
Hi I have a huge table with over 100million records and on regular basis ineed to delete nearly a million records and insert a million records. Currently I delete indexes before going through the process and recreate the indexes which takes a very very long time. IS there a way to disable indexes and re enable them after doing insert and...
7
11937
by: Warren Wright | last post by:
Hello, We maintain a 175 million record database table for our customer. This is an extract of some data collected for them by a third party vendor, who sends us regular updates to that data (monthly). The original data for the table came in the form of a single, large text file, which we imported. This table contains name and address...
10
9888
by: Bing Wu | last post by:
Hi Folks, I have a problem while creating a big table space. It reports error: SQL1139N The total size of the table space is too big Explanation: The size of the current table space is too big. The size of a REGULAR table space is limited to 0xFFFFFF (16777215) pages while the size of a TEMPORARY/LONG table space is limited to 2 tera...
1
2043
by: Mats Kling | last post by:
Hi all, We are logging approx. 3 million records every day into a history table. Last week we ran into the 64 GB limit in UDB 8 so we recreated the table with 8 k pagesize to get some breathingroom before we hit the 128 GB limit. We are considering partitioning and I just wanted to check with you that our proposal is the best one:
10
2374
by: Sumanth | last post by:
Hi, I have a table that I would like to partition. It has a column c1 which has 100 distinct values. I was planning to partition the table on column c1 using a partioned index, and then apply data partitioned secondary indexes on the table. I then read about partioned table spaces, How do I get the same behaviour as above by creating a...
10
3541
by: shsandeep | last post by:
DB2 V8.2 (not Viper yet and no range partitioning!!) I have created a table T1 (col1, col2) with col1 as the primary key. When I try to create a partitioning key on col2, it gives me error that it should have all primary keys included. So, I created table T1 again with col2 as the partitioning key. Now, I do not have col1 as the primary...
9
17541
by: Veeru71 | last post by:
Can someone point me to good documentation on 'WITH clause" ? (I couldn't get much out of Queries section from SQL Reference manual). We are getting better performance when we explicity use global temp tables to store intermediate results than using "WITH cluase" in our queries. Where does DB2 store the intermediate results if the query uses...
15
3666
by: Piero 'Giops' Giorgi | last post by:
Hi! I have a question: I already have a DB that uses partitions to divide data in US Counties, partitioned by state. Can I use TWO levels of partitioning? I mean... 3077 filegroups and 50 partition functions that address
2
2010
by: mandor | last post by:
Hello, I need some advise in table design, and more specifically about table partitioning. I read some papers and there was mentioned that if a table is expected to hold millions of rows, it's a good idea to partition it. Vertical partitioning, as I understood it, is separating data that differs in some way in a separate table, adding a key...
0
7820
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
1
7835
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8121
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6486
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5635
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3777
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2255
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1360
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1084
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.