Opinions on Fastest Token Reference Strategy
Greetings All, I am hoping for some suggestions on the fastest way to cross reference a set of tokens for quick look-up. The current reference has a sample token set of ~ 10 million unique entries that are the basis for the look-up. On a regular schedule (multiple times daily), our application parses an input stream, extracting tokens from that input stream, verifying existance in the token_reference table. If the token is not found, the token is inserted with the next token id. In all cases, the appropriate token id is returned and stored. I can not sort the input stream to only do a single look-up on the distinct set of tokens (~700K) in the input stream. The standard input stream decomposes into about 50 million tokens. Each of these 50 million tokens are referenced against the already identified 10 million tokens by a char(20) field, token_txt. The reference to these records are accumlated by the 4 byte serial, token_id, instead of the char (20) token_txt for faster subsequent reference. The table fragments are all in a single extent and statstics have been updated. I have tried the following, alone and in combination with one another, in an attempt to speed this token reference build process: - Create a hash function for a direct int8/int reference value. I have not found a hash function that is collision free where the overhead of the hash (time and space) does not overwhelm the original cost of the direct look-up. - Multiple fragmentation strategies w/PDQ. The data is poorly distributed and does not lend itself well to be fragmented by expression (distributions below). - Adding the serial key as a part of a composite index with the token_txt to have a key-only scan. - Created a reverse key look-up. Currently, this look-up consumes 90% of the resources / clock time of the application. Any improvements to this subsystem will make a big impact on throughput. I'm very willing to trade space for speed if possible. The environment is: IDS 10.00.FC5, Solaris 2.10, V880 - 4 Way, 8 GB Memory - OLTP configuration, MAX_PDQPRIORITY=50. Am I better off trying to store the data local to the application and reference it with an internal data structure of some sort? The schema is: create table "appdba".token_reference ( token_id serial not null , token_txt char(20) not null ); create unique index "appdba".token_reference_u01 on "appdba".token_reference (token_id) using btree ; -- To enforce uniqueness on the sequence create unique index "appdba".token_reference_u02 on "appdba".token_reference (token_txt) using btree ; -- To enforce uniqueness on the token text create unique index "appdba".token_reference_u03 on "appdba".token_reference (token_txt,token_id) using btree ; -- To allow key only scan alter table "appdba".token_reference add constraint primary key (token_id) constraint "appdba".token_reference_p01 ; All insight appreciated, --------------------------------------------------------------------------- Most of the tokens are numeric, but not all. A sample of the data distribuition is below: Distribution for appdba.token_reference.token_txt Constructed on 04/15/2008 High Mode, 0.500000 Resolution 000 DISTRIBUTION 000 179: ( 50280, 50280, 9168457413 ) 180: ( 50280, 50280, 925027502149 ) 181: ( 50280, 50280, 925043204211 ) 182: ( 50280, 50280, 925060608120 ) 183: ( 50280, 50280, 925076806650 ) 184: ( 50280, 50280, 925093505721 ) 185: ( 50280, 50280, 937054800664 ) 186: ( 50280, 50280, 949036208508 ) 187: ( 50280, 50280, 949056604185 ) 188: ( 50280, 50280, 949079006803 ) 189: ( 50280, 50280, 951024008902 ) 190: ( 50280, 50280, 951032002166 ) 191: ( 50280, 50280, 951049003788 ) 192: ( 50280, 50280, 951065902107 ) 193: ( 50280, 50280, 951073607200 ) 194: ( 50280, 50280, 951084504511 ) 195: ( 50280, 50280, 9517829313 ) 196: ( 50280, 50280, BLT7920 ) 197: ( 50280, 50280, IA046 ) 198: ( 50280, 50280, R11500144 ) 199: ( 50280, 50280, R42367341 ) 200: ( 50280, 50280, ZTL1036 ) 201: ( 64, 64, Ã )
the_omegamon@yahoo.com said: > Greetings All, > > I am hoping for some suggestions on the fastest way to > cross reference a set of tokens for quick look-up. The > current reference has a sample token set of ~ 10 million > unique entries that are the basis for the look-up. On a > regular schedule (multiple times daily), our application > parses an input stream, extracting tokens from that input > stream, verifying existance in the token_reference table. > If the token is not found, the token is inserted with the > next token id. In all cases, the appropriate token id is > returned and stored. I can not sort the input stream to > only do a single look-up on the distinct set of tokens > (~700K) in the input stream. What is the percentage split of found vs not found likely to be and does it change over time? > The standard input stream decomposes into about 50 million > tokens. Each of these 50 million tokens are referenced > against the already identified 10 million tokens by a > char(20) field, token_txt. The reference to these records > are accumlated by the 4 byte serial, token_id, instead of > the char (20) token_txt for faster subsequent reference. > The table fragments are all in a single extent and statstics > have been updated. > > I have tried the following, alone and in combination with one > another, in an attempt to speed this token reference build > process: > > - Create a hash function for a direct int8/int reference value. > I have not found a hash function that is collision free where > the overhead of the hash (time and space) does not overwhelm > the original cost of the direct look-up. > > - Multiple fragmentation strategies w/PDQ. The data is poorly > distributed and does not lend itself well to be fragmented > by expression (distributions below). > > - Adding the serial key as a part of a composite index with the > token_txt to have a key-only scan. > > - Created a reverse key look-up. > > Currently, this look-up consumes 90% of the resources / clock > time of the application. Any improvements to this subsystem > will make a big impact on throughput. > > I'm very willing to trade space for speed if possible. The > environment > is: IDS 10.00.FC5, Solaris 2.10, V880 - 4 Way, 8 GB Memory - OLTP > configuration, MAX_PDQPRIORITY=50. Am I better off trying to store > the data local to the application and reference it with an internal > data > structure of some sort? > > The schema is: > > create table "appdba".token_reference > ( > token_id serial not null , > token_txt char(20) not null > ); > > > create unique index "appdba".token_reference_u01 on > "appdba".token_reference > (token_id) using btree ; -- To enforce uniqueness on the sequence > create unique index "appdba".token_reference_u02 on > "appdba".token_reference > (token_txt) using btree ; -- To enforce uniqueness on the token > text > create unique index "appdba".token_reference_u03 on > "appdba".token_reference > (token_txt,token_id) using btree ; -- To allow key only scan > alter table "appdba".token_reference add constraint primary key > (token_id) > constraint "appdba".token_reference_p01 ; > > All insight appreciated, > > --------------------------------------------------------------------------- > > Most of the tokens are numeric, but not all. A sample of the data > distribuition is below: > > Distribution for appdba.token_reference.token_txt > > Constructed on 04/15/2008 > > High Mode, 0.500000 Resolution > > > 000 DISTRIBUTION 000 > > 179: ( 50280, 50280, 9168457413 ) > 180: ( 50280, 50280, 925027502149 ) > 181: ( 50280, 50280, 925043204211 ) > 182: ( 50280, 50280, 925060608120 ) > 183: ( 50280, 50280, 925076806650 ) > 184: ( 50280, 50280, 925093505721 ) > 185: ( 50280, 50280, 937054800664 ) > 186: ( 50280, 50280, 949036208508 ) > 187: ( 50280, 50280, 949056604185 ) > 188: ( 50280, 50280, 949079006803 ) > 189: ( 50280, 50280, 951024008902 ) > 190: ( 50280, 50280, 951032002166 ) > 191: ( 50280, 50280, 951049003788 ) > 192: ( 50280, 50280, 951065902107 ) > 193: ( 50280, 50280, 951073607200 ) > 194: ( 50280, 50280, 951084504511 ) > 195: ( 50280, 50280, 9517829313 ) > 196: ( 50280, 50280, BLT7920 ) > 197: ( 50280, 50280, IA046 ) > 198: ( 50280, 50280, R11500144 ) > 199: ( 50280, 50280, R42367341 ) > 200: ( 50280, 50280, ZTL1036 ) > 201: ( 64, 64, ' ) > _______________________________________________ > Informix-list mailing list > Informix-list@iiug.org > http://www.iiug.org/mailman/listinfo/informix-list > > -- Bye now, Obnoxio "There were a myriad of problems which conspired to corrupt your reason and rob you of your common sense. Fear got the best of you, and in your panic you turned to the Labour Party. They promised you order, they promised you peace, and all they demanded in return was your silent, obedient consent."
OK, I think I've got an idea: 1. Create a function that returns the integer value of the CHAR(20) if it's an integer and returns 0 if it's not. 2. Build an index over this function. 3. Check if the value from the stream is an integer, if so use a "hinted" query that "forces" the functional index to be used, if not, "hint" the query to let it use the regular index. Just a stab in the dark. :o) the_omegamon@yahoo.com said: > Greetings All, > > I am hoping for some suggestions on the fastest way to > cross reference a set of tokens for quick look-up. The > current reference has a sample token set of ~ 10 million > unique entries that are the basis for the look-up. On a > regular schedule (multiple times daily), our application > parses an input stream, extracting tokens from that input > stream, verifying existance in the token_reference table. > If the token is not found, the token is inserted with the > next token id. In all cases, the appropriate token id is > returned and stored. I can not sort the input stream to > only do a single look-up on the distinct set of tokens > (~700K) in the input stream. > > The standard input stream decomposes into about 50 million > tokens. Each of these 50 million tokens are referenced > against the already identified 10 million tokens by a > char(20) field, token_txt. The reference to these records > are accumlated by the 4 byte serial, token_id, instead of > the char (20) token_txt for faster subsequent reference. > The table fragments are all in a single extent and statstics > have been updated. > > I have tried the following, alone and in combination with one > another, in an attempt to speed this token reference build > process: > > - Create a hash function for a direct int8/int reference value. > I have not found a hash function that is collision free where > the overhead of the hash (time and space) does not overwhelm > the original cost of the direct look-up. > > - Multiple fragmentation strategies w/PDQ. The data is poorly > distributed and does not lend itself well to be fragmented > by expression (distributions below). > > - Adding the serial key as a part of a composite index with the > token_txt to have a key-only scan. > > - Created a reverse key look-up. > > Currently, this look-up consumes 90% of the resources / clock > time of the application. Any improvements to this subsystem > will make a big impact on throughput. > > I'm very willing to trade space for speed if possible. The > environment > is: IDS 10.00.FC5, Solaris 2.10, V880 - 4 Way, 8 GB Memory - OLTP > configuration, MAX_PDQPRIORITY=50. Am I better off trying to store > the data local to the application and reference it with an internal > data > structure of some sort? > > The schema is: > > create table "appdba".token_reference > ( > token_id serial not null , > token_txt char(20) not null > ); > > > create unique index "appdba".token_reference_u01 on > "appdba".token_reference > (token_id) using btree ; -- To enforce uniqueness on the sequence > create unique index "appdba".token_reference_u02 on > "appdba".token_reference > (token_txt) using btree ; -- To enforce uniqueness on the token > text > create unique index "appdba".token_reference_u03 on > "appdba".token_reference > (token_txt,token_id) using btree ; -- To allow key only scan > alter table "appdba".token_reference add constraint primary key > (token_id) > constraint "appdba".token_reference_p01 ; > > All insight appreciated, > > --------------------------------------------------------------------------- > > Most of the tokens are numeric, but not all. A sample of the data > distribuition is below: > > Distribution for appdba.token_reference.token_txt > > Constructed on 04/15/2008 > > High Mode, 0.500000 Resolution > > > 000 DISTRIBUTION 000 > > 179: ( 50280, 50280, 9168457413 ) > 180: ( 50280, 50280, 925027502149 ) > 181: ( 50280, 50280, 925043204211 ) > 182: ( 50280, 50280, 925060608120 ) > 183: ( 50280, 50280, 925076806650 ) > 184: ( 50280, 50280, 925093505721 ) > 185: ( 50280, 50280, 937054800664 ) > 186: ( 50280, 50280, 949036208508 ) > 187: ( 50280, 50280, 949056604185 ) > 188: ( 50280, 50280, 949079006803 ) > 189: ( 50280, 50280, 951024008902 ) > 190: ( 50280, 50280, 951032002166 ) > 191: ( 50280, 50280, 951049003788 ) > 192: ( 50280, 50280, 951065902107 ) > 193: ( 50280, 50280, 951073607200 ) > 194: ( 50280, 50280, 951084504511 ) > 195: ( 50280, 50280, 9517829313 ) > 196: ( 50280, 50280, BLT7920 ) > 197: ( 50280, 50280, IA046 ) > 198: ( 50280, 50280, R11500144 ) > 199: ( 50280, 50280, R42367341 ) > 200: ( 50280, 50280, ZTL1036 ) > 201: ( 64, 64, ' ) > _______________________________________________ > Informix-list mailing list > Informix-list@iiug.org > http://www.iiug.org/mailman/listinfo/informix-list > > -- Bye now, Obnoxio "There were a myriad of problems which conspired to corrupt your reason and rob you of your common sense. Fear got the best of you, and in your panic you turned to the Labour Party. They promised you order, they promised you peace, and all they demanded in return was your silent, obedient consent."