Parallelism doesn't provide any performance gains

Question 1

A parallel index fast full scan is probably the fastest way to count the number of records of a very large table with a primary key.

There are dozens of reasons why the parallel hint did not improve performance in the original query. The most likely reason, as shown below, is that your queries are comparing a parallel full table scan with a serial index fast full scan.

Sample Schema

--Sample schema: Create table, insert 30M rows, add a primary key, gather stats.
--This takes a few minutes to setup.
create table test1(c1 number,c2 number,c3 number,c4 number,c5 number) nologging;
begin
    for i in 1 .. 300 loop
        insert /*+ append */ into test1
        select level+(i*100000),level,level,level,level
        from dual connect by level <= 100000;
        commit;
    end loop;
end;
/
alter table test1 add constraint test1_pk primary key(c1);
begin
    dbms_stats.gather_table_stats(user, 'test1');
end;
/

Explain Plans

--#1: Parallel hint - parallel full table scan.
explain plan for select /*+ parallel(test1) */ count(*) from test1;
select * from table(dbms_xplan.display);

--------------------------------------------------------------------------------------------------------
| Id  | Operation              | Name     | Rows  | Cost (%CPU)| Time     |    TQ  |IN-OUT| PQ Distrib |
--------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |          |     1 |    73  (22)| 00:00:01 |        |      |            |
|   1 |  SORT AGGREGATE        |          |     1 |            |          |        |      |            |
|   2 |   PX COORDINATOR       |          |       |            |          |        |      |            |
|   3 |    PX SEND QC (RANDOM) | :TQ10000 |     1 |            |          |  Q1,00 | P->S | QC (RAND)  |
|   4 |     SORT AGGREGATE     |          |     1 |            |          |  Q1,00 | PCWP |            |
|   5 |      PX BLOCK ITERATOR |          |    30M|    73  (22)| 00:00:01 |  Q1,00 | PCWC |            |
|   6 |       TABLE ACCESS FULL| TEST1    |    30M|    73  (22)| 00:00:01 |  Q1,00 | PCWP |            |
--------------------------------------------------------------------------------------------------------


--#2: Regular count(*) - serial index fast full scan.
explain plan for select count(*) from test1;
select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation             | Name     | Rows  | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |          |     1 |  1270  (32)| 00:00:11 |
|   1 |  SORT AGGREGATE       |          |     1 |            |          |
|   2 |   INDEX FAST FULL SCAN| TEST1_PK |    30M|  1270  (32)| 00:00:11 |
--------------------------------------------------------------------------

--#3: Parallel_index - parallel index fast full scan.
explain plan for select /*+ parallel_index(test1) */ count(*) from test1;
select * from table(dbms_xplan.display);

-----------------------------------------------------------------------------------------------------------
| Id  | Operation                 | Name     | Rows  | Cost (%CPU)| Time     |    TQ  |IN-OUT| PQ Distrib |
-----------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT          |          |     1 |  1270  (32)| 00:00:11 |        |      |            |
|   1 |  SORT AGGREGATE           |          |     1 |            |          |        |      |            |
|   2 |   PX COORDINATOR          |          |       |            |          |        |      |            |
|   3 |    PX SEND QC (RANDOM)    | :TQ10000 |     1 |            |          |  Q1,00 | P->S | QC (RAND)  |
|   4 |     SORT AGGREGATE        |          |     1 |            |          |  Q1,00 | PCWP |            |
|   5 |      PX BLOCK ITERATOR    |          |    30M|  1270  (32)| 00:00:11 |  Q1,00 | PCWC |            |
|   6 |       INDEX FAST FULL SCAN| TEST1_PK |    30M|  1270  (32)| 00:00:11 |  Q1,00 | PCWP |            |
-----------------------------------------------------------------------------------------------------------

Performance Comparison

This block of code was run several times. The first, highest, and lowest results were thrown out, and the rest averaged.

alter system flush buffer_cache;
select /*+ parallel(test1) */ count(*) from test1;
alter system flush buffer_cache;
select count(*) from test1;
alter system flush buffer_cache;
select /*+ parallel_index(test1) */ count(*) from test1;


Count(*) (serial index)             -  6.34 seconds
Parallel (parallel full table scan) -  6.20 seconds
Parallel_index (parallel index)     -  2.35 seconds

A thousand other reasons, some warnings

Maybe the queries ran the same on your system because parallelism isn't enabled, wasn't used, or wasn't useful. Check the explain plans, SQL Monitoring, or v$px_process to get an idea of how much parallelism is used. If the degree of parallelism doesn't seem right, I've put together a list of factors influencing the DOP in this answer.

Parallelism can make a huge difference with many queries, for both I/O and CPU. But 35 seconds is definitely on the small end of the scale. Parallel queries are normally used for statements that take several minutes or hours. There's going to be a large percentage of overhead with such a small query. Even if it does run faster you should consider whether it's worth running one query faster at the expense of additional resources taken away from other queries.

Question 2

It sounds like Oracle is doing a table scan to get the Count. Parallelism won't fix that, because the operation is I/O bound, not CPU bound.

You could try getting it from ALL_TABLES (which should be very fast):

SELECT NUM_ROWS FROM ALL_TABLES WHERE TABLE_NAME = 'builds';