Обсуждение: Threaded Records in SQL: Advice Needed
Hi Everyone, I'm planning to implement a project using a php/postgres 6.5.3 combination. Part of what I need to do is develop a model in SQL to keep track of "threaded records." What I mean by this, is that I need to keep track of parent-child relationships in exactly the same way that a threaded-discussion group does. The design should be able to support approximately 100 users, mostly readers, and be able to handle approximately 1 insert per minute. So far, I've found two methods/algorithms for implenting this in SQL, but there's a problem with each. The first one is extremely efficient and inexpensive for selecting and ordering all of the records in a thread (taking only one select to get all of the records and in order), but requires that ALL records be updated on insert, which is very expensive. Because I'm expecting about 120000 records a year, or ca. 450 new records every business day, the prospect of each insert updating each record in the database is not appealing. At first it would be ok, but as the record count increased, the inserts would become extremely slow. This method works by modeling the records as "nested sets" and was explained by Joe Celko in one of his articles. The second method is simply adding fields to keep track of an id, parent_id, and root_id. Its benefit is that it is inexpensive on inserts, requiring only one insert and no updates, but it is costly to select and order all the records in a thread. Essentially, the only way I have found to do this is to implement a recursive function that selects one record at a time, checks for children, ad infinitum. Not very efficient. My concern with method 1 is that the great expense of inserting new records will slow the database down to unacceptable levels. This is based on my past experience with postgres when updating a database of 1.5 million rows (which took an hour and a half with syncing turned off.) Method 2 is problematic because it uses recursion first of all (which I understand to be heavy in resource usage) and because it makes a select for each and every record in a thread to be displayed. What I'd like to find is either a better way that I'm not aware of, or some kind of middle ground. Also, what do you make of these methods. Are they as inefficient as I want to believe? Thanks! Bryan Ingram Database Programmer S!XTYFOOTSP!DER 972-492-5676 bingram@sixtyfootspider.com <mailto:bingram@sixtyfootspider.com> <http://www.sixtyfootspider.com/> www.sixtyfootspider.com
> Hi Everyone, > > I'm planning to implement a project using a php/postgres 6.5.3 combination. > > Part of what I need to do is develop a model in SQL to keep track of > "threaded records." What I mean by this, is that I need to keep track of > parent-child relationships in exactly the same way that a > threaded-discussion group does. Hi Bryan check out the PDF files at http://ourworld.compuserve.com/homepages/Graeme_Birchall/HTM_COOK.HTM The "SQL Cookbook" that this guy writes is oriented towards IBM's DB2 database, however, he does talk about a number of different ways of handling parent-child relationships in an SQL table; his versions are able to be nested as well. Actually, this guy seems to know his stuff when it comes to SQL, so it is probably worth having a look at anyways...thus I have also posted this response to the list. Cordially Patrick Giagnocavo a222@redrose.net
In order to simplify the regular expressions, I propose to change the
"." as "field separator" in the ids: "." has a special meaning in
regular expressions, let us avoid escaping all over the place. So,
take for instance "/" as separator, so that the message in my previous
example is now "25/7/19/2".
In order to compute the correct id at insert time, I would suggest
keeping a sequence root_seq for the root messages (see CREATE SEQUENCE
in the postgres manual), and just "select nextval(root_seq)"
each time you insert a new root message. Alternatively, if you write
root message ids as e.g. "/25" and keep the previous structure, you
can use the method described below also for root messages. In this
case, you just would be interpreting the root messages as "replies to
the (fictitious) message with an empty index".
Now assume you want to insert a new reply to message with id X (which
could be at any level, e.g. X = 25/7/19). You can get the number of
the next response to X = 25/7/19 using the regular expression
capabilities of postgres "select count(id)+1 as Y from your_table where id ~ '25/7/19/[^/]*$' "
and then compute the index to be inserted as "X/Y"
In the regexp you are requesting something that matches 25/7/19/(any number of symbols different from "/")
so that all direct replies are selected, but NOT the replies to them -
as they would have a "/" somewhere before the end.
You can automatize this with the sql functions create function next_reply_num(text) returns int4 as 'select
count(*)+1from ids where id ~ ($1|| ''/[^/]*$'') ' language 'sql';
create function next_reply_id(text) returns text as 'select ($1 || ''/'' || next_reply_num($1)::text)'
language'sql';
You could then insert the next reply to message "25/19/2" using
insert into messages(id, ...) values(next_reply_id('25/19/2'), ...);
I do not know how to do this within a single call to an sql function;
it would be easy to do if you use either PL/tcl or PL/pgsql procedural
languages.
Thanks for the "challenge": this IS fun.
Miguel
Thanks for the ideas on the functions, that'll work nicely. The only other problem I see in actually implementing this, is that the id column i.e. /25/10/2/ will not be ordered correctly because it relies on ascii values. You get alphabetic orderings, rather than numerical. Such as: 1 10 11 12 14 2 20 25 3 4 5 instead of 1 2 3 4 5 10 11 12 14 20 25 Any ideas how to get around this? I'm working on the problem right now, but haven't found anything yet. Bryan
In reference to the ascii/numeric ordering problem .. But first let me say ..if someone knows of a way to get ascii values to order as if they were numerics ..please let me in on the secret .. Instead of using numbers, if letters were used the ordering would be correct. The id string would become something like: A/A/A for the 1st reply to the 1st reply of the 1st root message. This will work fine for threads with relatively few replies on the same level. For instance, the number 100 would take only 4 characters to encode, however, the number 1000 would need 39 characters to encode. For my purpose 100-200 replies on any given level will suffice nicely. Even though text fields are limited to 4096 characters, even if each level needed 40 characters for encoding, I would still have room for approximately 100 levels (plenty) .. Adding a step to the procedure you developed, we could convert the returned "next reply number" into its alphabetic equivalent. e.g. 1 = A2 = B26 = Z27 = ZA28 = ZB52 = ZZ53 = ZZA The procedure is this: next_id/26 = number of Z's mod of next_id/26 = numeric position within alphabet So .. if you wanted to add the 100th reply to the 2nd root topic ... 100/26 = 3 (ZZZ) (drop everything but the integer) mod of 100/26 = 12 (L) So we'd have 3 Z's and an L for the second root topic. The fully assembled ID would be /B/ZZZL Then a reply to this would become /B/ZZZL/A So on, and so forth .. This is verging on getting kludgey, but it still looks like it meets all of the criteria: 1) Fast inserts 2) Fast selects of a thread or part of a thread Actually this criterion hinges on the quality of the indexing 3) Rows are returned in order, with only one select. So ..I really wish there was a better way ..but this isn't too big of a price to pay. Thanks, Bryan -----Original Message----- From: Ingram, Bryan Sent: Tuesday, April 11, 2000 3:05 PM To: 'mig@utdt.edu' Cc: pgsql-sql@postgresql.org Subject: RE: [SQL] Threaded Records in SQL: Advice Needed Thanks for the ideas on the functions, that'll work nicely. The only other problem I see in actually implementing this, is that the id column i.e. /25/10/2/ will not be ordered correctly because it relies on ascii values. You get alphabetic orderings, rather than numerical. Such as: 1 10 11 12 14 2 20 25 3 4 5 instead of 1 2 3 4 5 10 11 12 14 20 25 Any ideas how to get around this? I'm working on the problem right now, but haven't found anything yet. Bryan
lexicographic ordering is what you want ...
So, new proposal (described from the start) which solves all this and
should (I think) be rather fast. On the other hand, the id fields get
larger and larger ...
(1) Ids of messages are of the form /(field_0)/(field_1)/.../(field_n) where each field counts the number of message
atthat level: field_0 counts the root messages, field_1 the replies to the root message at field_0, etc ...
(2) The field counters are numbers where (a) the first digit gives the count of digits in the index (if youthink that
youwill have more than nine digits in any field,make it a two-digit counter: 01, 02, ... 99 (b) the rest is the index
Same example as before: the second reply to the nineteenth reply to the seventh reply to root message 25 has id
/225/17/219/12 (field_0=225 means: two digits in the counter, the counter is 25) This does solve the issue of
correctordering: lexicographic ordering of THESE indexes is what you want ... shorter numbers do come before the
longerones
(3) The issuing of new indexes can be implemented in three sql functions as follows: create function
next_reply_num(text)returns text as 'select (count(*)+1)::text from ids where id ~ ($1|| ''/[^/]*$'') ' language
'sql'; create function add_ct(text) returns text as 'select (char_length($1)::text || $1)' language 'sql';
create function next_reply_id(text) returns text as 'select ($1 || ''/'' || add_ct(next_reply_num($1)))'
language'sql'; The function next_reply_num gets the next counter; add_ct prepends the digit count; next_reply_id
assemblesthe lot.
Again, maybe this can be implemented with fewer sql function calls; it
can definitely be implemented in a single tcl or pgSQL function ...
Another remark on these functions: if you EVER delete a message from
the list, the procedure next_reply_num will wreak havoc in your
numbering! If that is a possibility, you should probably select
the largest reply number to that message, parse it, add one to the
counter, prepend the byte count and then compute the index for the new
reply.
PS: I just received your e-mail which solves these issues; here is an alternative ... It is of course compatible with
usingletters instead of numbers, as you propose - the new idea is adding a "byte count" to each field, which can of
coursealso be encoded in a letter
--text follows this line--
>From: "Ingram, Bryan" <BIngram@sixtyfootspider.com>
>Cc: pgsql-sql@postgresql.org
>Date: Tue, 11 Apr 2000 14:57:00 -0500
>Content-Type: text/plain;
> charset="iso-8859-1"
>
>Thanks for the ideas on the functions, that'll work nicely.
>
>The only other problem I see in actually implementing this, is that the id
>column i.e. /25/10/2/ will not be ordered correctly because it relies on
>ascii values. You get alphabetic orderings, rather than numerical.
>
>Such as:
>
>1
>10
>11
>12
>14
>2
>20
>25
>3
>4
>5
>
>instead of
>
>1
>2
>3
>4
>5
>10
>11
>12
>14
>20
>25
>
>Any ideas how to get around this? I'm working on the problem right now, but
>haven't found anything yet.
>
>Bryan
>
Would it be too obvious to mention that leading zeroes would give you what you need? //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ Michael McCarthy TCSI Corporation michael@tcsi.com 1080 Marina Village Parkway (510) 749-8739 Alameda, CA 94501 > The only other problem I see in actually implementing this, is that the id > column i.e. /25/10/2/ will not be ordered correctly because it relies on > ascii values. You get alphabetic orderings, rather than numerical.
Bryan, You can numerically, even if the field is a text field, if all fields have a number. Just cst to an int4. E.g. create table testtable (num text, num2 text); select num from testtable order by num::int4; Troy > > Thanks for the ideas on the functions, that'll work nicely. > > The only other problem I see in actually implementing this, is that the id > column i.e. /25/10/2/ will not be ordered correctly because it relies on > ascii values. You get alphabetic orderings, rather than numerical. > > Such as: > > 1 > 10 > 11 > 12 > 14 > 2 > 20 > 25 > 3 > 4 > 5 > > instead of > > 1 > 2 > 3 > 4 > 5 > 10 > 11 > 12 > 14 > 20 > 25 > > Any ideas how to get around this? I'm working on the problem right now, but > haven't found anything yet. > > Bryan > > >
----- Original Message ----- From: "Ingram, Bryan" <BIngram@sixtyfootspider.com> To: "Ingram, Bryan" <BIngram@sixtyfootspider.com>; <mig@utdt.edu> Cc: <pgsql-sql@postgresql.org> Sent: Tuesday, April 11, 2000 9:57 PM Subject: RE: [SQL] Threaded Records in SQL: Advice Needed > In reference to the ascii/numeric ordering problem .. > > But first let me say ..if someone knows of a way to get ascii values to > order as if they were numerics ..please let me in on the secret .. > > Instead of using numbers, if letters were used the ordering would be > correct. > > The id string would become something like: A/A/A for the 1st reply to the > 1st reply of the 1st root message. > > This will work fine for threads with relatively few replies on the same > level. For instance, the number 100 would take only 4 characters to encode, > however, the number 1000 would need 39 characters to encode. More efficient to use letters as numbers in base 26? Then for up to 676 replies per level you need only 2 letters. If you allowed 3, you'd have some headroom. ---------------------------------------------------------------- Moray.McConnachie@computing-services.oxford.ac.uk
Hello, I don't know if it has been answered yet (bit late I know). I solved the ascii numeric ordering as followed: - concatenate a lot of zeroes in front (at least the length of the result value) - cut the the result length. snlsor=> select * from asciinum order by number; number ------ 1 10 111 1211 2 20 211 22 (8 rows) snlsor=> select * from asciinum order by lpad(number, 4, '0'); number ------ 1 2 10 20 22 111 211 1211 (8 rows) Best regards, Roelof > -----Original Message----- > From: Ingram, Bryan [SMTP:BIngram@sixtyfootspider.com] > Sent: dinsdag 11 april 2000 22:58 > To: Ingram, Bryan; mig@utdt.edu > Cc: pgsql-sql@postgresql.org > Subject: RE: [SQL] Threaded Records in SQL: Advice Needed > > In reference to the ascii/numeric ordering problem .. > > But first let me say ..if someone knows of a way to get ascii values to > order as if they were numerics ..please let me in on the secret .. > > Instead of using numbers, if letters were used the ordering would be > correct. > > The id string would become something like: A/A/A for the 1st reply to the > 1st reply of the 1st root message. > > This will work fine for threads with relatively few replies on the same > level. For instance, the number 100 would take only 4 characters to > encode, > however, the number 1000 would need 39 characters to encode. > > For my purpose 100-200 replies on any given level will suffice nicely. > > Even though text fields are limited to 4096 characters, even if each level > needed 40 characters for encoding, I would still have room for > approximately > 100 levels (plenty) .. > > Adding a step to the procedure you developed, we could convert the > returned > "next reply number" into its alphabetic equivalent. > > e.g. 1 = A > 2 = B > 26 = Z > 27 = ZA > 28 = ZB > 52 = ZZ > 53 = ZZA > > The procedure is this: > > next_id/26 = number of Z's > mod of next_id/26 = numeric position within alphabet > > So .. if you wanted to add the 100th reply to the 2nd root topic ... > > 100/26 = 3 (ZZZ) (drop everything but the integer) > mod of 100/26 = 12 (L) > > So we'd have 3 Z's and an L for the second root topic. > > The fully assembled ID would be /B/ZZZL > > Then a reply to this would become /B/ZZZL/A > > So on, and so forth .. > > This is verging on getting kludgey, but it still looks like it meets all > of > the criteria: > > 1) Fast inserts > 2) Fast selects of a thread or part of a thread > Actually this criterion hinges on the quality of the indexing > 3) Rows are returned in order, with only one select. > > So ..I really wish there was a better way ..but this isn't too big of a > price to pay. > > Thanks, > Bryan > > > > > > > -----Original Message----- > From: Ingram, Bryan > Sent: Tuesday, April 11, 2000 3:05 PM > To: 'mig@utdt.edu' > Cc: pgsql-sql@postgresql.org > Subject: RE: [SQL] Threaded Records in SQL: Advice Needed > > > Thanks for the ideas on the functions, that'll work nicely. > > The only other problem I see in actually implementing this, is that the id > column i.e. /25/10/2/ will not be ordered correctly because it relies on > ascii values. You get alphabetic orderings, rather than numerical. > > Such as: > > 1 > 10 > 11 > 12 > 14 > 2 > 20 > 25 > 3 > 4 > 5 > > instead of > > 1 > 2 > 3 > 4 > 5 > 10 > 11 > 12 > 14 > 20 > 25 > > Any ideas how to get around this? I'm working on the problem right now, > but > haven't found anything yet. > > Bryan >